Ablaufplanung (Scheduling)

Jürgen Sauer

Universität Oldenburg
Fachbereich Informatik
Escherweg 2, 26121 Oldenburg
0441-9722-220
e-mail: sauer@informatik.uni-oldenburg.de

erschienen in: KI 2/97, Das aktuelle Schlagwort, Scientec, 1997

In der Ablaufplanung werden Probleme der zeitlichen Zuordnung von Aktivitäten zu limitierten Ressourcen betrachtet, wobei unterschiedliche Nebenbedingungen (Hard/ Soft Constraints) zu berücksichtigen sind und bestimmte Ziele erreicht bzw. optimiert werden sollen. Ablaufplanung unterscheidet sich vor allem durch den konkreten Zeitbezug vom anderen wichtigen Planungsbereich, der Aktionsplanung (planning), siehe KI-Lexikon 1/90.

Ablaufplanungsprobleme treten in unterschiedlichen Anwendungsgebieten auf, so z.B. in der betrieblichen Produktion, bei Software-Projekten, der Bettenbelegung eines Krankenhauses oder bei Betriebsmitteln in Rechnersystemen. Die Produktionsablaufplanung ist ein wichtiges und intensiv untersuchtes Anwendungsgebiet. Man hat hier:

Aufträge zur Herstellung von Produkten. Für Produkte kann es verschiedene Herstellungsvarianten mit unterschiedlichen Herstellungsschrittengeben.
Maschinen, Rohstoffe und Personal als Ressourcen, die i.allg. für mehrere Produkte zur Verfügung stehen.
Nebenbedingungen vor allem technischer Art wie Herstellvorschriften oder das Verbot der Doppelbelegung von Ressourcen.
Betriebswirtschaftliche Zielsetzungen wie strikte Termineinhaltung oder Kostenoptimierung.

Gesucht wird ein Ablaufplan (eine terminliche Zuordnung der einzelnen Aktionen zu Ressourcen), der die gegebenen Nebenbedingungen und Zielsetzungen erfüllt.

Charakteristisch für die Ablaufplanung sind ein dynamischer Problembereich, ein kombinatorisch großer Suchraum und unsicheres Wissen. Die Komplexität ergibt sich aus der Fülle möglicher Alternativen für Ablaufpläne und der Synchronisation einer Vielzahl von Aktivitäten, Bedingungen und Zielvorgaben. Unsicheres Wissen ergibt sich u.a. aus geschätzten Werten für Ausführungszeiten und ungenauen Vorgaben aus übergeordneten Planungssystemen. Die Dynamik des Problembereichs resultiert aus Ereignissen und Störungen, die ständig neue Planungssituationen schaffen.

Zur Lösung von Ablaufplanungsproblemen werden zwei Aufgabenkomplexe unterschieden. Bei der prädiktiven Ablaufplanung wird der Plan vorausschauend für einen bestimmten Zeitabschnitt unter Annahme einer statischen Planungsumgebung erstellt. In der reaktiven Ablaufplanung steht die Anpassung des Plans an neue Situationen im Mittelpunkt, wobei möglichst viel vom bestehenden Plan erhalten bleiben soll.

Im Bereich des Operations Research werden bereits seit Anfang der 50er Jahre Ablaufplanungsprobleme untersucht, wobei der Schwerpunkt auf die Optimierung einzelner Zielfunktionen gelegt wird. Da bereits einfache Problemstellungen NP-hart sind, werden hier i.allg. idealisierte Probleme (z.B. Flow-Shop- oder Job-Shop-Scheduling) betrachtet, die Komplexitätsbetrachtungen erlauben und der Suche nach geeigneten Heuristiken dienen. In realen Produktionsumgebungen sind die Ergebnisse nur schwer oder nur für spezielle Anwendungsgebiete nutzbar, hier dominieren noch einfache Verfahren wie Netzplantechnik oder Prioritätsregeln.

Seit Anfang der 80er Jahre werden Methoden der KI eingesetzt, um die Lösung praktischer Ablaufplanungsprobleme vor allem durch neue Modellierungs- und Problemlösungstechniken zu unterstützen. In der Modellierung werden Frame-basierte, regelbasierte und vor allem Constraint-basierte Ansätze eingesetzt. Sie erlauben u.a. die explizite Darstellung und Verarbeitung von anwendungsspezifischem Problemlösungswissen. Zur Generierung oder Anpassung von Ablaufplänen werden verwendet:

Heuristische Verfahren:

Sie umfassen allgemeine heuristische Prinzipien wie Problemzerlegung und heuristische Suchverfahren wie Beam-Suche, Suche mit Prioritätsregeln, Constraint-basierte oder opportunistische Suche. Heuristiken werden sowohl im OR als auch in der KI untersucht.
Constraint-basierte Verfahren:

Im Mittelpunkt stehen hier die zu berücksichtigenden Constraints. Ablaufplanung wird als Constraint Satisfaction Problem betrachtet und mit entsprechenden Methoden, insbesondere Sprachen der Constraint-Logik-Programmierung, verarbeitet.
Verfahren des Soft Computing und zur iterativen Verbesserung:

Sie werden in den letzten Jahren verstärkt untersucht, so z.B. Fuzzy-Logik zur Verarbeitung des in der Ablaufplanung vorhandenen unsicheren Wissens oder Neuronale Netze zur Auswahl einzuplanender Aktivitäten oder der Bewertung von Situationen. Genetische Algorithmen und iterative Verbesserungstechniken wie Threshold Exception, Simulated Annealing oder Sintflutalgorithmen werden zur Verbesserung von Plänen und als Näherungsverfahren für Optimierungsprobleme eingesetzt.
Verteilte Künstliche Intelligenz:

Um die häufig organisatorisch verteilte Lösung von Ablaufplanungsproblemen in den Anwendungsgebieten nachzubilden, werden vor allem Multi-Agenten-Systeme betrachtet, in denen die kooperierenden Agenten entweder gemeinsam eine Lösung zu optimieren versuchen oder jeweils eine eigene Lösung ermitteln, die Teil der Gesamtlösung ist.
Meta-Ablaufplanung:

Hier soll durch Integration von Wissen über Ablaufplanung die Planung selbst oder die Auswahl geeigneter Verfahren zur Lösung der Probleme unterstützt werden.

Aus dem Bereich der KI stammende Ansätze für Ablaufplanungssysteme wurden bisher meist als wissensbasierte Systeme präsentiert. Erste Ansätze haben große Beachtung gefunden, sind aber nicht aus dem Stadium von Prototypen herausgekommen. Ein Kritikpunkt ist die häufig fehlende Möglichkeit der interaktiven Steuerung des Planungsprozesses durch manuelle Vorgaben oder Änderungen des Benutzers, was für die Aktzeptanz und Anwendbarkeit besonders wichtig erscheint.

Literatur

Blazewicz, J., Ecker, K.H., Schmidt, G., Weglarz, J.: "Scheduling in Computer and Manufacturing Systems", Springer, 1994.

Dorn, J., Froeschl, K.A.: "Scheduling of Production Processes", Ellis Horwood, 1993.

Hertzberg, J.: "Planen", KI-Lexikon, KI 1/90, 1990.

Schultz, J., Weigelt, M., Mertens, P.: "Verfahren für die rechnergestützte Produktions feinplanung - ein Überblick", in: Wirtschaftsinformatik, 37. Jahrgang, Heft Nr. 6, 1995.

Smith, S.F.: "Knowledge-based production management: approaches, results and prospects", in: Production Planning & Control, Vol. 3, No. 4, 1992.

Kerr, R.M., Szelke, E.: "Artificial Intelligence in Reactive Scheduling", Chapman & Hall, 1995.

Sauer, J.: "Wissensbasiertes Lösen von Ablaufplanungsproblemen durch explizite Heuristiken", DISKI Band 37, infix-Verlag, 1993.

Zweben, M., Fox, M.S.: "Intelligent Scheduling", Morgan Kaufmann Publishers, 1994.