Bicriteria Scheduling on Parallel Processors
Final Report Abstract
Ablaufplanungsprobleme treten in allen Wissensgebieten und in allen Lebensbereichen auf. Sie bestehen im Allgemeinen darin, eine Menge von Aufträgen einer Menge von Prozessoren so zuzuordnen, dass bestimmte Optimierungsziele möglichst gut erreicht werden. In dem Projekt verwenden wir das Modell paralleler, identisch qualifizierter Prozessoren. Das eine Optimierungsziel besteht darin, die Planlänge, d.h. den Fertigstellungszeitpunkt des Auftrags, dessen Bearbeitung als letztes beendet wird, zu minimieren. Als zweites Optimierungsziel soll die Anzahl der Auftragsunterbrechungen minimiert werden. Weniger Auftragsunterbrechungen bedeuten weniger Kosten (z.B. Qualitätskosten, Transportkosten, Lagerkosten, Kosten für zusätzliche Produktionsfaktoren, die benötigt werden, um einen Prozessor nach einem Auftragswechsel umzurüsten, usw.). Hierbei ist es so, dass ein Tradeoff zwischen den Zielen möglichst geringe Planlänge und möglichst wenige Auftragsunterbrechungen besteht: im Allgemeinen gilt, dass eine geringere Planlänge durch mehr Auftragsunterbrechungen erzielt werden kann, bzw. dass weniger Auftragsunterbrechungen eine größere Planlänge zur Folge haben. Zur Lösung solcher bikriterieller Probleme gibt es zwei Möglichkeiten: Die erste Möglichkeit besteht darin, eine Konvexkombination der beiden Kriterien zur Lösung des Problems zu verwenden. Hierbei besteht die Hauptaufgabe darin, die korrekten Parameter für das zur Lösung zu verwendende mathematische Programm so zu bestimmen, dass die Präferenzen des Entscheidungsträgers möglichst gut berücksichtigt werden. In unserem Projekt haben wir hierfür den Analytic Hierarchy Process (AHP) verwendet. Eine zweite Möglichkeit besteht darin, eines der beiden Optimierungsziele zu fixieren und das andere zu optimieren. Konkret wird im ersten Fall die Anzahl der maximal zulässigen Auftragsunterbrechungen auf eine Zahl i fixiert, und das Problem besteht nun darin, einen Ablaufplan mit minimaler Planlänge zu finden, der nicht mehr als i Auftragsunterbrechungen beinhaltet. Im zweiten allowed Fall wird die maximal zulässige Planlänge auf einen Wert Cmax fixiert, und das Problem besteht nun darin, einen Ablaufplan mit möglichst wenigen Auftragsunterbrechungen zu finden, der nicht länger allowed ist als Cmax . Zur Lösung dieser kombinatorischen Optimierungsprobleme müssen eine Reihe klassischer Probleme gelöst werden, zum Beispiel das Problem P | | Cmax , in dem keine Auftragsunterbrechungen erlaubt sind, oder das Problem Subset Sum, bei dem es darum geht, eine Teilmenge der Aufträge zu bestimmen, deren Summe der Auftragslängen einen bestimmten Wert ergibt. Da es sich bei diesen Problemen um NP-vollständige Probleme handelt, sind auch die in dem Projekt behandelten Probleme NP-vollständig. Zur Lösung wurden exakte Algorithmen und Heuristiken entwickelt. Ziel weiterer Arbeiten ist, die exakten Algorithmen dahingehend zu verbessern, dass auch größere Probleme mit mehr Aufträgen gelöst werden können.
