Ablaufplanung ist ein Optimierungsproblem

Die Planung von Aufgaben auf einem System mit begrenzten Ressourcen, wie z. B. die Planung astronomischer Beobachtungen auf einer begrenzten Anzahl von Instrumenten/Teleskopen/Zeiten, erinnert an einige bekannte NP-schwere Probleme. Im Kern handelt es sich bei der Zeitplanung um ein Optimierungsproblem mit diskreten Variablen. Ausgehend von einem Pool möglicher Beobachtungen besteht die Aufgabe darin, diejenige Beobachtungssequenz auszuwählen, die den Wert einer gegebenen Zielfunktion maximiert/minimiert, die so einfach sein kann wie die Maximierung der Öffnungszeit oder die Minimierung der Zielluftmassen, aber in der Regel wird eine viel komplexere Zielfunktion verwendet.

Zu jedem Zeitpunkt t wird ein Beobachtungsblock entweder ausgeführt oder nicht (eine Beobachtung kann nicht teilweise geplant werden), daher unterscheidet sich die Zeitplanung von Standard-Optimierungsproblemen mit kontinuierlichen Variablen in der Hinsicht, dass die Eingangsvariablen (geplante oder nicht geplante Aufgabe) nur zwei Werte haben, was sie zu einer Unterklasse der so genannten ganzzahligen Programmierung macht, die zumindest NP-komplett ist.

Betrachtet man die klassischen 21 NP-kompletten Probleme von Karp, so ähnelt die Terminplanung dem Knapsack-Problem (wie fülle ich einen Knapsack optimal): Der Knapsack ist die in Frage kommende Zeitspanne (z.B. eine Nacht) und die in den Knapsack zu packenden Gegenstände sind die Beobachtungen mit individuellen Beobachtungszeiten und individuellen wissenschaftlichen Rückgaben. Klassische Knapsack-Probleme haben Gegenstände mit konstanten Gewichten und Werten, was bei der Planung von Beobachtungen nicht immer strikt eingehalten wird: Die Zeit, die für eine Beobachtung benötigt wird (d. h. das Gewicht des Gegenstands), kann von seiner Position am Himmel abhängen, während der Wert (d. h. der wissenschaftliche Ertrag) von der genauen Beobachtungszeit abhängen kann, aber im Allgemeinen ist die Verwandtschaft des Planungsproblems mit dem Knapsack-Problem ziemlich offensichtlich.

Ein weiteres Karp-Problem ist das Job-Shop-Problem, bei dem es darum geht, eine Reihe von Aufträgen mit unterschiedlichen Bearbeitungszeiten so auf eine Reihe von Maschinen zu verteilen, dass die Zeitspanne, d. h. die Gesamtzeit bis zur Fertigstellung, minimiert wird. Das berühmte Problem des Handlungsreisenden kann als ein JSP mit einer einzigen Maschine (dem Handlungsreisenden) verstanden werden, dessen Aufträge die verschiedenen zu besuchenden Städte sind. In ähnlicher Weise kann die Planung von Beobachtungen an einem einzelnen Teleskop als ein Job-Shop-Problem betrachtet werden, mit dem Ziel, die insgesamt verstrichene Beobachtungszeit zu minimieren. Eine Variante des Job-Shop-Problems, das flexible Job-Shop-Problem, lockert die Anforderung, dass Vorgänge, die klassischerweise nacheinander auf einer einzigen Maschine ausgeführt werden müssen, nun nacheinander auf einer (Teil-)Menge identischer Maschinen geplant werden können. Dies stellt die Terminplanung in einem Netzwerk von Roboterteleskopen dar.

Übersetzt mit www.DeepL.com/Translator (kostenlose Version)

Ein grundlegendes Konzept der Standardoptimierung ist die Notwendigkeit, die Zielfunktion a priori zu definieren. Für viele Anwendungen ist dies unkritisch, aber für die wissenschaftsbezogene Optimierung, die unter dem unspezifischen Begriff "wissenschaftlicher Ertrag" zusammengefasst wird, kann es von Vorteil sein, wenn die konkrete Auswahl in einer späteren Entscheidungsphase getroffen werden kann.

Eine Pareto-optimale Lösung ist jede machbare Lösung eines Mehrzieloptimierungsproblems, die alle Nebenbedingungen des Problems erfüllt und gleichzeitig nicht weiter verbessert werden kann, ohne mindestens eine andere Zielfunktion zu verschlechtern. Alle diese möglichen Lösungen erstrecken sich über die Pareto-Grenze; sobald diese definiert ist, können verschiedene Normen, die a posteriori auf die Lösungsvektoren angewendet werden, einen einzigen Zeitplan ergeben.

Reine Constraint-Satisfaction-Probleme sind Probleme mit einer konstanten Zielfunktion, aber mit einer Reihe von Nebenbedingungen, die erfüllt werden müssen, um eine gültige Lösung zu erhalten. Ein berühmtes Beispiel ist das Acht-Damen-Rätsel, bei dem acht Damen so auf einem Schachbrett platziert werden müssen, dass sich keine Damen gegenseitig bedrohen. Ein astronomischer Zeitplan kann auch bestimmte Nebenbedingungen erfüllen, wie z. B. die Sichtbarkeit des Ziels (einschließlich der Monddistanz), die Kalibrierungsanforderungen und die erforderliche Instrumentenausstattung, so dass eine langfristige Planung zufriedenstellend gelöst werden kann, wenn alle Bedingungen berücksichtigt werden. Kurzfristige Planungen mit nicht konstanten Zielfunktionen können dann an kleineren, z. B. nicht verletzenden Proben durchgeführt werden. Dieser Ansatz wurde erfolgreich bei der Planung des Hubble-Weltraumteleskops demonstriert, wo die langfristige Planung ("Zyklen") als einfaches CSP mit einem Programm namens SPIKE betrachtet wurde. Die kurzfristige Planung auf Wochenbasis wurde dann mit einem Greedy-Schema namens SPSS (Science Planning and Scheduling System) weiter optimiert.

Wie Scheduling gelöst werden kann

Das Beispiel mit den acht Königinnen soll veranschaulichen, wie schnell NP-komplette Probleme rechenintensiv werden können. Die Platzierung von 8 Königinnen auf 64 Feldern ergibt 64 uber 8 oder 4.426.165.368 mögliche Kombinationen. Beruecksichtigt man, dass immer nur eine einzelne Königin in einer Zeile/Spalte stehen kann, bleiben immer noch 8⁸ =16.777.216 mögliche Kombinationen übrig. Wenn man die Symmetrien des Problems nutzt, reduziert man weiter auf 8!=40320 Möglichkeiten. Dies ist mit Brute-Force-Techniken leicht zu bewältigen, aber schon bei einem 20x20-Brett muss man 20!~2,433 × 10¹⁸ Möglichkeiten berücksichtigen. Ähnliche Argumente gelten für die Beobachtung der Zeitplanung, so dass Brute-Force-Angriffe als gescheitert gelten. Aber es gibt eine Rettung: Wenn man nicht nur an der einzigen, besten Lösung interessiert ist, sondern auch beweisen will, dass es keine bessere Lösung gibt, kommen Heuristiken ins Spiel. Auf der folgenden Seite werden einige heuristische Verfahren, die für die Planung von Terminen nützlich sind, sowie einige Anwendungsfälle aufgeführt.

• Greedy Algorithmus
• Simulated Annealing
• Simplex Verfahren der linearen Optimierung
• Evolutionäre Algorithmen/Genetische Algorithmen
• Ameisenalgorithmus/Partikelschwarmoptimierung
• Neurale Netzwerke