# Approximation in deterministic and stochastic machine scheduling

## Jäger, Sven Joachim

Classical combinatorial optimization is based on the assumption that for a given problem instance all problem data are available at the beginning (offline optimization). However, many optimization problems in practice require that some decisions be made before all information about the problem is completely known. In online optimization it is assumed that the data become known over time, whereas in stochastic optimization, unknown problem parameters are assumed to be distributed according to known probability distributions. In this thesis algorithms for scheduling problems under the three assumptions described above are developed and analyzed. In the considered problems the task is to create a schedule for the processing of a set of jobs on machines running in parallel. The jobs have different processing times and priorities. The goal is to minimize the sum of completion times of all jobs, weighted by the job priorities. In some problems there are additional requirements on feasible schedules. We restrict ourselves to algorithms that can be executed in polynomial time. Since all investigated offline optimization problems are NP-hard, under this constraint the algorithms cannot always yield an optimal schedule. Therefore, for such problems we concentrate on approximation algorithms that compute in polynomial time a schedule with a provable performance guarantee. A similar approach is adopted in the two models with uncertainty. In the developed online algorithms we bound the relative deviation of the achieved objective value from the optimum with perfect information. In stochastic scheduling we are interested in upper bounds for the ratio of the expected objective value resulting from the considered policy to the expected objective value under an optimal policy. A well-known rule for non-preemptive scheduling of jobs on identical machines in the presence of complete information is to start at any moment when a machine is free a job with maximum quotient of its priority divided by its processing time. We refine the known performance guarantee of this rule for the case that the number of machines is fixed. In addition, we transfer the rule to the stochastic scheduling problem, in which the processing times are random. This yields a policy with a performance guarantee depending on the coefficients of variation of the processing times. This performance guarantee is significantly better than the best previously known guarantee for the same policy from 1999. For instances with bounded coefficients of variation no efficiently computable policy with a better performance guarantee is known for this problem. The use of an efficiently solvable linear relaxation of the investigated problem is a common method in the design of approximation algorithms. The solution is employed for the construction of a good schedule for the initial problem. In this step randomness can be incorporated. Instead of comparing the objective value of the constructed schedule directly with that of the unknown optimal schedule, we bound the maximum possible ratio of the obtained objective value to the optimum value of the relaxation. In this dissertation this technique is applied in both an approximation algorithm for deterministic scheduling and an approximative stochastic scheduling policy. Finally, we conceive algorithms and policies for different deterministic and stochastic scheduling problems, respectively, where the jobs appear gradually and are unknown beforehand. Almost all linear relaxations cannot be solved without knowing the entire problem instance. For the preemptive relaxation employed in this thesis, however, an optimal solution can be constructed by means of a simple rule while the jobs are being processed. A further method applied is the assignment of jobs to machines using a greedy algorithm. Although the used greedy algorithms do not resort to a solution to a linear relaxation, the ratio of the objective value attained by the algorithm to the optimum objective value of such a relaxation can be bounded. To this end, a feasible dual solution is constructed, depending on the steps performed by the algorithm. A multiple of its objective value is an upper bound for the objective value of the constructed schedule. Using these techniques, we develop an online algorithm for computing preemptive schedules on unrelated machines with an improved constant performance guarantee. Furthermore, we enhance a recently published online algorithm for preemptively scheduling jobs with precedence constraints on identical machines, which additionally relies on network flow techniques. Finally, we design non-preemptive stochastic online scheduling policies for a single machine as well as for unrelated parallel machines. For these we obtain improved performance guarantees depending on two different parameters of the probability distributions.
Die klassische kombinatorische Optimierung geht von der Annahme aus, dass für eine gegebene Instanz eines Optimierungsproblems sämtliche Problemdaten von Anfang an zur Verfügung stehen (Offline-Optimierung). Viele Optimierungsprobleme in der Praxis erfordern allerdings, dass einige Entscheidungen getroffen werden, bevor alle Informationen zum Problem bekannt sind. In der Online-Optimierung wird angenommen, dass die Daten nach und nach bekannt werden, wohingegen der stochastischen Optimierung die Annahme zugrunde liegt, dass sich unbekannte Problemparameter gemäß bekannten Wahrscheinlichkeitsverteilungen verhalten. In der vorliegenden Arbeit werden Algorithmen für Probleme der Ablaufplanung (Scheduling) unter den drei oben beschriebenen Annahmen entwickelt und analysiert. Bei den betrachteten Problemen geht es darum, einen Ablaufplan für die Bearbeitung einer Menge von Aufträgen oder Prozessen (Jobs) auf parallel laufenden Maschinen zu erstellen. Dabei haben die Aufträge unterschiedliche Bearbeitungszeiten und Prioritäten. Das Ziel ist es, die Summe der mit den Prioritäten gewichteten Fertigstellungszeiten aller Aufträge zu minimieren. In einigen Problemen werden zusätzliche Anforderungen an erlaubte Ablaufpläne gestellt. Wir beschränken uns auf Algorithmen, die sich in polynomieller Zeit ausführen lassen. Da sämtliche betrachteten Offline-Optimierungsprobleme NP-schwer sind, können die Algorithmen unter dieser Einschränkung nicht immer einen optimalen Ablaufplan liefern. Deshalb konzentrieren wir uns für solche Probleme auf Approximationsalgorithmen, die in polynomieller Zeit einen Ablaufplan mit einer beweisbaren Gütegarantie berechnen. Ein ähnlicher Ansatz wird in den beiden mit Unsicherheit behafteten Modellen verfolgt. Bei den entwickelten Online-Algorithmen leiten wir obere Schranken für die relative Abweichung des erreichten Zielfunktionswerts vom Optimum bei vollständiger Information her. In der stochastischen Ablaufplanung sind wir an oberen Schranken für das Verhältnis des sich aus der betrachteten Strategie ergebenden erwarteten Zielfunktionswerts zum erwarteten Zielfunktionswert bei einer optimalen Strategie interessiert. Eine wohlbekannte Regel zur Planung nicht unterbrechbarer Aufträge auf identischen Maschinen beim Vorliegen vollständiger Information besteht darin, zu jedem Zeitpunkt, zu dem eine Maschine frei ist, einen Auftrag zu starten, bei dem der Quotient aus seiner Priorität und seiner Bearbeitungsdauer am größten ist. Wir verfeinern die bekannte Gütegarantie dieser Regel für den Fall, dass die Anzahl der Maschinen festgelegt ist. Außerdem übertragen wir sie auf das stochastische Planungsproblem, in dem die Bearbeitungszeiten zufällig sind. Dies liefert eine Strategie mit einer von den Variationskoeffizienten der Bearbeitungszeiten abhängigen Gütegarantie. Diese Gütegarantie ist deutlich besser als die zuvor bekannte Garantie für dieselbe Strategie aus dem Jahr 1999. Für Instanzen mit beschränkten Variationskoeffizienten ist für dieses Problem keine effizient berechenbare Strategie mit einer besseren Gütegarantie bekannt. Der Gebrauch einer linearen Relaxation des untersuchten Problems, welche sich effizient lösen lässt, ist eine häufige Methode im Entwurf von Approximationsalgorithmen. Die Lösung wird zur Konstruktion eines guten Ablaufplans für das Ausgangsproblem herangezogen, wobei der Zufall einfließen kann. Anstatt den Zielfunktionswert des konstruierten Ablaufplans direkt mit dem des unbekannten optimalen Ablaufplans zu vergleichen, beschränken wir das maximal mögliche Verhältnis des erhaltenen Zielfunktionswerts zum Optimalwert der Relaxation. In dieser Dissertation wird diese Technik sowohl in einem Approximationsalgorithmus für die deterministische Ablaufplanung als auch in einer approximativen stochastischen Planungsstrategie angewendet. Schließlich konzipieren wir Algorithmen und Strategien für verschiedene deterministische bzw. stochastische Ablaufplanungsprobleme, bei denen die Aufträge erst nach und nach erscheinen und vorher unbekannt sind. Fast alle linearen Relaxationen lassen sich nicht lösen, ohne die gesamte Probleminstanz zu kennen. Bei der in dieser Arbeit verwendeten präemptiven Relaxation hingegen kann eine optimale Lösung während der Bearbeitung der Aufträge anhand einer einfachen Regel konstruiert werden. Eine weitere angewendete Methode ist die Zuweisung von Aufträgen an Maschinen mittels eines Greedy-Algorithmus. Obwohl die eingesetzten Greedy-Algorithmen nicht auf eine Lösung einer linearen Relaxation zurückgreifen, lässt sich das Verhältnis des durch den Algorithmus erreichten Zielfunktionswerts zum optimalen Zielfunktionswert einer solchen Relaxation beschränken. Dazu wird eine zulässige Duallösung konstruiert, die an die vom Algorithmus durchgeführten Schritte angepasst ist. Ein Vielfaches ihres Zielfunktionswerts ist eine obere Schranke für den Zielfunktionswert des konstruierten Ablaufplans. Mithilfe dieser Techniken entwickeln wir einen Online-Algorithmus zur Berechnung präemptiver Ablaufpläne auf unabhängigen Maschinen mit einer verbesserten konstanten Gütegarantie. Ferner verbessern wir einen kürzlich veröffentlichten Online-Algorithmus zur präemptiven Ablaufplanung von Aufträgen mit Präzedenzbedingungen auf identischen Maschinen, der zusätzlich auf Netzwerkflusstechniken beruht. Für nicht unterbrechbare stochastische Aufträge entwerfen wir effizient berechenbare Online-Strategien zur Ablaufplanung auf einer Maschine sowie auf unabhängigen parallel laufenden Maschinen. Dabei erhalten wir verbesserte Gütegarantien, die von zwei verschiedenen Parametern der Wahrscheinlichkeitsverteilungen abhängen.