erschienen in der Reihe Dissertationen zur Künstlichen Intelligenz (DISKI), Band 37, im Infix-Verlag, 1993
One of the main tasks of production planning and control is scheduling, i.e. the temporal assignment of orders to the resources needed regarding several constraints. The manufacturing of a product is done by performing a sequence of operations due to a selected routing on available machines.
A major problem when creating a schedule is the selection and usage of the appropriate scheduling algorithm to get "good" results. Important for the selection of the appropriate algorithm are the planning goals to be achieved and the events disrupting the planning environment. Most of the approaches presented so far are inflexible due to fixed algorithms with implicit goals. The planning knowledge used is not transparent, is difficult to extract and to use within other algorithms.
An approach is presented which allows the integration of different planning algorithms and the selection of the appropriate ones in given problem situations. A language for the representation of scheduling knowledge on the basis of heuristics is presented. The explicit representation of the control (meta-) knowledge used for the selection of algorithms as well as the uniform and transparent representation of different scheduling strategies are possible. The scheduling knowledge can be seperated into distinguished components and the representation is based on AND/OR trees visualizing the scheduling problem. With the combination of these components it is possible to create new scheduling algorithms easily.
The approach is implemented in Prolog giving a system which not only supports the selection of appropriate scheduling algorithms due to given goals, situations or events but also the construction and evaluation of "new" scheduling algorithms.
Die Aufgabe der Ablaufplanung als Teil der betriebswirtschaftlichen Produktionsplanung und -steuerung besteht in der zeitlichen und ressourcenbezogenen Planung einer Menge von Aufträgen zur Herstellung von Produkten. Die Herstellung eines Produkts erfolgt durch die Ausführung einer Menge von Operationen in einer vordefinierten Reihenfolge auf jeweils vorgegebenen Ressourcen, wobei zusätzliche Bedingungen berücksichtigt werden müssen.
Ein wesentliches Problem für die Erstellung "guter" Ablaufpläne stellt die Auswahl des "richtigen" Planungsverfahrens dar. Dabei spielen sowohl die durch die Planung zu erfüllenden Zielsetzungen als auch evtl. auftretende Ereignisse, die zu Störungen der Planung führen können, eine Rolle. Bestehende Verfahren sind meist auf eine spezielle Problemstellung zugeschnitten und inflexibel in dem Sinne, daß ein Planungsverfahren fest implementiert und damit eine Zielsetzung implizit definiert ist. Außerdem kann das verwendete Planungswissen nicht oder nur schwer extrahiert und für andere Verfahren nutzbar gemacht werden.
In dieser Arbeit wird ein Ansatz vorgestellt, mit dem unterschiedliche Ablaufplanungsverfahren integriert und zur Lösung einer gegebenen Problemstellung geeignete ausgewählt werden können. Dazu wird eine Sprache zur Darstellung des Ablaufplanungswissens auf Basis von Heuristiken entwickelt und verwendet. Sie erlaubt die explizite Repräsentation des für die Auswahl wichtigen Kontrollwissens, u.a. Ziele und Ereignisse, sowie die einheitliche und transparente Darstellung von Ablaufplanungsverfahren auf Basis der Problemdarstellung durch Und/Oder-Bäume. Ein Ablaufplanungsverfahren stellt die Abarbeitung eines Und/Oder-Baumes dar und kann in verschiedene Verfahrenskomponenten zerlegt werden. Durch die dynamische Kombination dieser Komponenten können auf einfache Weise "neue" Ablaufplanungsverfahren konstruiert werden.
Die Realisierung des Ansatzes in Prolog führt zu einem System, das nicht nur die Auswahl geeigneter Verfahren bei gegebenen Zielsetzungen oder Ereignissen unterstützt, sondern auch u.a. die vergleichende Betrachtung verschiedener sowie die einfache Konstruktion neuer Verfahren ermöglicht.