ISBN 9783843948142

978-3-8439-4814-2, Reihe Mathematik

Huy Minh Lê
Robust Single Machine Scheduling-Location Problems

168 Seiten, Dissertation Technische Universität Kaiserslautern (2021), Softcover, A5

Zusammenfassung / Abstract

Diese Arbeit widmet sich der Integration zweier Probleme: Scheduling- und Standortprobleme unter Berücksichtigung von Unsicherheit. Beide Problemklassen sind klassische Probleme der kombinatorischen Optimierung und des Operations Research mit zahlreichen Anwendungen z.B. in der Logistik oder der Produktionsplanung. Scheduling- und Standort-Probleme wurden getrennt intensiv untersucht, allerdings gibt es kaum Arbeiten zur Verbindung der beiden Problemklassen. Insbesondere die Integration von Unsicherheit eröffnet hier neue Sichtweisen und Herausforederungen. Die Aufgabe bei den kombinierten Scheduling-Standort-Problemen besteht darin, eine Maschine in einem Netzwerk zu platzieren und dort dann die Jobs, die sich in den Netzwerkknoten befinden, sequentiell zu bearbeiten. Das Ziel ist es, den Zielfunktionswert im schlimmsten Szenario (absolute Robustheit) bzw. die Differenz zur besten Lösung im schlimmsten Szenario (Regret Robustheit) zu minimieren. Die Unsicherheit besteht im Kontext dieser Arbeit den Kantenlängen im Netzwerk. Wir verwenden das Konzept der Gamma-Robustheit, um die Unsicherheit zu modellieren: Die Gesamtabweichung der unsicheren Parameter von ihren Nominalwerten darf einen Schwellenwert nicht überschreiten. Die Hauptergebnisse sind die ersten Algorithmen mit polynomieller Laufzeit zur exakten Lösung der robusten Probleme. Wir zeigen, dass das robuste absolute Einzelmaschinen-Makespan-Scheduling-Problem mit der Unsicherheit des Freigabezeiten durch einen Sortieralgorithmus gelöst werden kann. Für das Regret Kriterium geben wir einen O(n logn) Algorithmus an; dieser hat die gleiche Laufzeit wie das beste bekannte Verfahren im nicht-robusten Fall. Für die kombinierten Probleme betrachten wir den Fall, dass das Netzwerk ein Baum ist. Wir entwickeln für die Makespan-Optimierung zwei Polynomialzeit-Algorithmen, von denen einer eine Laufzeit in O(n^4 logn) hat und der andere in O(n^7) läuft.