Christian Hestermann¹,
Frank Jentz²,
Frank Puppe³,
Werner Dilger⁴

1 infor AG, 66299 Friedrichsthal (hestermann@infor.de)
² Abt. TA-SH, Hüttenwerke Krupp Mannesmann, 47259 Duisburg
³ Universität Würzburg, Am Hubland, 97074 Würzburg (puppe@informatik.uni-wuerzburg.de)
⁴ Technische Universität Chemnitz, 09107 Chemnitz (prof.dilger@informatik.tu-chemnitz.de)

8. Januar 1999

1. Ausgangslage und Gesamtziel

"Die computergestützte Produktionsplanung und ­steuerung ist eines der ältesten, aber auch anspruchsvollsten Gebiete in der betrieblichen Datenverarbeitung. Produktionsplanungs­ und ­steuerungssysteme (PPS­Systeme) gibt es seit Mitte der sechziger Jahre. Man könnte meinen, nach drei Jahrzehnten intensiver Forschung und Entwicklung müßten eigentlich alle Probleme gelöst sein. Daß dies nicht der Fall ist, zeigt das große Interesse, das der Produktionsplanung und ­steuerung gerade in der jüngsten Zeit wieder zuteil wird." ([Kurbel 1993])

"PPS [Produktionsplanung und ­steuerung] bezeichnet den Einsatz rechnerunterstützter Systeme zur organisatorischen Planung, Steuerung und Überwachung der Produktionsabläufe von der Angebotsbearbeitung bis zum Versand unter Mengen­, Termin­ und Kapazitätsaspekten. Die PPS­Hauptfunktionen sind: Produktionsprogrammplanung, Mengenplanung, Termin­ und Kapazitätsplanung, Auftragsveranlassung [und] Auftragsüberwachung." ([AWF 1985])

Dabei gehört die Produktionsplanung und ­steuerung zusammen mit Vertrieb, Entwicklung und Konstruktion, der eigentlichen Teilefertigung sowie Montage und Qualitätssicherung zu den technisch­organisatorischen Bereichen eines Unternehmens ([AWF 1985]).

[Hackstein 1989] untergliedert die in der Definition des AWF genannten PPS-Hauptfunktionen in Einzelfunktionen. Dabei lassen sich einfache aber umfangreiche Datenverwaltungsaufgaben sowie komplexere dispositive Funktionen unterscheiden. Zu den ersteren gehören z.B. die Kundenauftragsverwaltung, die Bestandsführung und Bestellschreibung, die Verfügbarkeitsprüfung sowie die im allgemeinen mit Mitteln der Betriebsdatenerfassung durchgeführte Auftragsüberwachung. Ihr Charakteristikum ist die recht gleichartige Verarbeitung großer Datenmengen nach sehr einfachen Vorschriften. Diese Datenverwaltungsaufgaben werden mittlerweile praktisch von jedem PPS­System erfüllt. So sind die grundlegenden Stammdaten zu Produkten, Aufträgen, Personal, Maschinen und Lager weitestgehend standardisiert und werden mit Hilfe von Datenbanksystemen recht zufriedenstellend verwaltet; die wesentlichen Probleme liegen hier in einer unternehmensweiten Integration der zugrundeliegenden Datenmodelle, der einheitlichen Verarbeitung sowie der Verknüpfung unterschiedlicher Systeme (z.B. CAD­PPS­Kopplung).

Anders geartet sind die komplexeren dispositiven Tätigkeiten, mit deren Hilfe die nach herkömmlichen Ansätzen getrennt behandelten Funktionen Beschaffungsrechnung, Kapazitätsbedarfsrechnung, Kapazitätsabstimmung sowie Reihenfolgeplanung erfüllt werden. Wir fassen diese bisher getrennten Bereiche unter dem Stichwort "integrierte Mengen­ und Kapazitätsdisposition" stärker zusammen, womit wir die erste der fünf Grundforderungen aus [Kernler 1993], nämlich die simultane Planung aller Elementarfaktoren, erfüllen.

Die Unterstützung der dispositiv­organisatorischen Aufgaben ist weniger weit vorangeschritten. Ihre hauptsächliche Aufgabe besteht darin, die Bedarfe an Erzeugnissen (Primärbedarfe) sowie an Teilen, Baugruppen und Werkstoffen (Sekundärbedarfe) mit den Beständen abzugleichen. Sowohl auf der Seite der Bedarfe wie auf der der Bestände kann man dabei unterscheiden in mengen­bezogene und zeit­bezogene Aspekte. Wie die bekannten mengenbezogenen Bedarfe durch vorhandene (Bestandsführung) oder zu beschaffende (Bestellschreibung und ­überwachung) Bestände gedeckt werden müssen, so müssen die zeitbezogenen Bedarfe für die direkt oder indirekt der Fertigung zugeordneten Arbeitsschritte mit den voraussichtlich zur Verfügung stehenden Kapazitäten bei Maschinen und Personal in Übereinstimmung gebracht werden.

Die dazu nötigen Planungen lassen sich im wesentlichen in drei Bereiche gliedern:

1. Die Grobplanung deckt eine weite Vorausschau von mehreren Monaten bis wenigen Jahren ab.
2. Die Mittelfristplanung ist für den Zeitraum mehrerer Tage bis weniger Monate zuständig.
3. Im Kurzfristbereich wird der Zeitraum der nächsten Schichten bis weniger Tage behandelt. Er ist sehr eng mit der Fertigungssteuerung verknüpft.

Allerdings sind die Grenzen zwischen diesen Planungsbereichen fließend.

Der Bereich der Grobplanung spielt bei den von uns bevorzugt betrachteten Auftragsfertigern keine große Rolle, da in den meisten Märkten eine zuverlässige Vorausschau auf die zukünftige Bedarfslage nur sehr schwer möglich ist. Soll sie doch durchgeführt werden, bieten sich laut [Hackstein 1989] statistische Prognose­Verfahren sowie Methoden aus dem Operations Research an. Die so ermittelten voraussichtlichen Bedarfe müssen im wesentlichen mit der zur Verfügung stehenden Kapazität abgeglichen werden.

Die Mittelfristdisposition ist eine der wichtigsten Aufgaben von PPS­Systemen. Auf ihrer Grundlage werden Entscheidungen über die aktuelle Kapazitätssituation wie anzuordnende Überstunden oder Umsetzen von Personal, aber auch über Annehmen oder Ablehnen eines potentiellen Auftrags getroffen. Meist wird mit in dreierlei Hinsicht vergröberten Daten gearbeitet:

• Es wird nicht auf der Basis einzelner Maschinen geplant, sondern es werden Maschinengruppen und ihre kumulierten Kapazitäten zugrundegelegt.
• Statt einzelner Arbeitsgänge werden Arbeitsfolgen betrachtet, z.B. werden alle Arbeitsgänge eines Auftrags aus dem Bereich Metallgrobbearbeitung zusammengefaßt.
• Und schließlich wird je Arbeitsfolge nur eine benötigte Kapazitätseinheit berücksichtigt, d.h. anstelle von Maschinen, Personal und Vorrichtungen wird nur die Maschine mit aus dem Personal abgeleiteter Kapazität betrachtet.

Ebenso wichtig für die tägliche Arbeit ist die Kurzfristplanung. Ihr Resultat ist die Festlegung einzelner Tätigkeiten für die verschiedenen in der Produktion beschäftigten Personen sowie die Sicherstellung aller weiteren benötigten Ressourcen wie Maschinen, Werkzeuge und Vorrichtungen.

Trotz der oft mangelhaften Unterstützung der dispositiven Tätigkeiten in diesen Bereichen durch herkömmliche PPS­Systeme werden sie täglich in jedem Fertigungsunternehmen mehr oder weniger gut erbracht. Vor allem im Bereich der Kurzfristplanung wird in vielen Betrieben mit wenig Unterstützung durch Planungssysteme gearbeitet. Seit Mitte der achtziger Jahre werden zwar zur Organisation der Fertigung zusätzlich zu etablierten und weiter verbesserten PPS-Systemen verstärkt rechnergestützte Planungs­ und Steuerungsinstrumente für den mittel­ und kurzfristigen Bereich eingesetzt, etwa in Form elektronischer Leitstände ([Havermann 1990], [Kurbel & Meynert 1988]). Die meisten dieser Systeme waren und sind stark an der Struktur herkömmlicher Planungsinstrumente wie Plantafeln orientiert ([Schlichte & Dicks 1990]). Sie brachten zwar einen Zuwachs an Transparenz in das Fertigungsgeschehen, doch ein großer Teil der Planung und Steuerung, z.B. das Zuordnen von Auftragspositionen zu benötigten Ressourcen und das Auflösen von Kollisionen, wurde fast immer den Benutzern überlassen. Daß das zu teilweise sehr großen Puffer­ und Liegezeiten führt, die 80 – 90 % der gesamten Durchlaufzeit betragen können, wurde schon vor Jahrzehnten nachgewiesen ([Nadzeyka & Schnabel 1975]), gilt aber in sehr vielen Fällen bis heute ([Wiendahl 1987], [Kurbel 1993]). Das liegt unter anderem daran, daß die Unterschiede zwischen Industrieunternehmen um so größer werden, je näher man sich an der Fertigungsebene befindet. Der Einsatz von Standard­Software stößt hier trotz vorgesehener Anpassbarkeit sehr schnell an Grenzen. Hier bieten sich Methoden der Künstlichen Intelligenz an, mit deren Hilfe man nicht nur auf deklarativer Ebene viele spezifische Einzelheiten der Fertigung beschreiben, sondern auch das planerische Problemlösungsverhalten der Disponenten nachbilden kann.

Das grundlegende Ziel des hier beschriebenen Projekts INKAD (= Intelligentes, kooperatives Assistenzsystem zur Dispositionsunterstützung in Produktionsplanungs- und -steuerungssystemen) ist demnach die Unterstützung der interaktiven Disposition in allen relevanten Bereichen, also vor allem im Kurz­ und Mittelfristbereich sowie bei der Grobplanung, mit wissensbasierten Methoden der Künstlichen Intelligenz. Dazu werden wesentliche Teile des Wissens, mit dem Disponenten und Fertigungsplaner die beschriebenen Aufgaben lösen, in dem intelligenten, kooperativen Assistenzsystem WIZARD (= Wissensbasierte Zuordnung in einem Assistenzsystem für die Ressourcen-Disposition) hinterlegt und dazu benutzt, die Unterstützung der Dispositionstätigkeiten zu verbessern. Dabei werden die folgenden Bereiche näher untersucht:

• Mittelfristdisposition mit simultaner Betrachtung von Mengen und Zeiten
• Kurzfristplanung unter Berücksichtigung mehrerer benötigter Ressourcen und der spezifischen Gegebenheiten vor Ort
• Formalisierung des Wissens menschlicher Disponenten und Feinplaner, sowohl über die Spezifika einzelner Fertigungen als auch über generelles Problemlöseverhalten
• beispielhafte Anbindung an ein modernes, kommerzielles PPS­System und Evaluierung in Fertigungsunternehmen

Die Wissensrepräsentation orientiert sich einerseits an den in PPS­Systemen vorhandenen Datenstrukturen für die Massendaten; andererseits werden Repräsentationsmechanismen der Künstlichen Intelligenz für das dispositive Wissen eingesetzt. Die im INKAD-Projekt eingesetzte Problemlösungsmethode "Vorschlagen-und-Vertauschen" integriert wissensbasierte Anytime-Algorithmen mit einer dezentralen, verteilten Planung mit selbständigen Agenten. Das Schwergewicht liegt dabei auf der Interaktion mit den Benutzern, die vom System intelligente Vorschläge bekommen und diese jederzeit beeinflussen können. Darüber hinaus können die Benutzer die vorhandenen Restriktionen jederzeit überarbeiten, so daß ein Planen mit laufzeit­flexibler Spezifikation möglich wird. Die Planungsverfahren werden auf verschiedenen Hierarchieebenen mit situationsabhängigen Granularitätsstufen eingesetzt und ermöglichen sowohl ein vorausschauendes als auch ein reagierendes Planen.

Aus dem Gesamtziel des Forschungsprojekts INKAD ergaben sich im einzelnen die folgenden wissenschaftlichen und technischen Arbeitsziele:

1. Bereitstellung, gegebenenfalls Anpassung vorhandener Wissensrepräsentationsformen für die Zwecke der Mittel­ und Kurzfristdisposition.
   Es ist zum einen das Wissen über die Objekte, die in der Mittel­ und Kurzfristdisposition eine Rolle spielen, zu repräsentieren, d.h. Ressourcen aller Art wie Maschinen, Material, Werkzeuge, Transporteinrichtungen und Personal, zum andern Wissen über Prozesse wie Beschaffung, Produktmodellierung, Fertigung und Qualitätskontrolle, und zum dritten Erfahrungswissen, das die Planungs­ und Dispositionsaktivitäten beeinflußt. Zur Repräsentation der ersten Art des Wissens liegen geeignet definierte Objekte nahe, für die zweite Art kommen z.B. auf die vorliegenden Zwecke angepaßte Netzpläne in Frage. Die dritte Art ist teilweise Wissen in der Form von Situations/Aktionspaaren, wobei eine Situation durch eine Reihe von Bedingungen gegeben ist, also typisches Regelwissen; teilweise ist es Wissen über Restriktionen, die eingehalten werden müssen oder sollen, wofür Constraints in Frage kommen.
2. Bereitstellung, Anpassung und Weiterentwicklung geeigneter Methoden zur Verarbeitung des Wissens.
   Es werden Objektinterpreter und Regelinterpreter mit verschiedenen Schlußmöglichkeiten benötigt. Es ist zu untersuchen, ob Simulation von Plänen ein geeignetes Hilfsmittel ist.
3. Erhebung und Formalisierung des relevanten Wissens und Aufbau von Wissensbasen.
   Das Wissen muß aus schriftlich vorliegenden Quellen (Fachliteratur, Handbücher, firmeninterne Anweisungen) und, beim Erfahrungswissen, durch Befragung der Mitarbeiter erhoben werden. In beiden Fällen hat das erhobene Wissen i.a. noch nicht die für die interne Repräsentation benötigte Form und muß deshalb formalisiert werden. Nach erfolgter Formalisierung können verschiedene Wissensbasen aufgebaut werden.
4. Anbindung an ein kommerzielles PPS­System.
   PPS­Systeme stellen Datenstrukturen und Planungsmethoden für die Mittel­ und Kurzfristdisposition bereit. Diese sind von System zu System verschieden, deshalb ist es notwendig, ein System zur intelligenten Dispositionsunterstützung so zu gestalten, daß es von konkreten PPS­Systemen unabhängig ist, eine klar definierte Schnittstelle zu diesen hat und an sie leicht angebunden werden kann. Dies soll exemplarisch durchgeführt werden.
5. Evaluierung in Fertigungsunternehmen.
   Zum Nachweis der prinzipiellen Durchführbarkeit des Ansatzes, zur Behebung von konzeptionellen Mängeln und zur Optimierung der erarbeiteten Lösung ist eine Evaluierung in der Praxis unerläßlich. Sie soll bei den jeweiligen Anwendungspartnern durchgeführt werden. Auf diese Weise sind Erfahrungen aus unterschiedlichen Einsatzbereichen zu gewinnen.

Die in der Produktionsplanung und ­steuerung herkömmlicherweise betrachteten Massendaten lassen sich, soweit sie die Disposition betreffen, im wesentlichen zwei Gruppen zuordnen: Auf der Angebotsseite stehen Bestände zur Verfügung. Darunter verstehen wir alles, was man in der Gegenwart oder der Zukunft für die Herstellung der gewünschten Erzeugnisse verwenden kann. Außerdem behandeln wir Mengen­ und Zeit­Aspekte gleichartig; die zeit­bezogenen Bestände werden herkömmlich als Kapazitäten bezeichnet.

Den Beständen stehen auf der Nachfrageseite Bedarfe gegenüber. Auch hier kann man Mengen­Bedarfe an Materialien, Teilen und Baugruppen und Zeit­Bedarfe an Maschinen, Personen usw. unterscheiden; erstere sind traditionellerweise in der Stückliste eines Produktes, letztere im zugehörigen Arbeitsplan aufgeführt (vgl. [Kurbel 1993]). In Anlehnung an [Kernler 1993] bezeichnen wir alle Objekte eines Unternehmens, zu denen man Bedarfe und Bestände verwalten kann, als Ressourcen. Außerdem fassen wir Stückliste und Arbeitsplan zu einer gemeinsamen sog. Ressourcenliste zusammen und unterstreichen damit die Notwendigkeit der "simultanen Planung aller Elementarfaktoren" ([Kernler 1993]).

Wir sehen die Ressourcenbelegungsplanung als ein kontinuierliches Zuordnungsproblem an (vgl. [Puppe 1990, Poeck 95]), bei dem beliebige Bedarfe passenden Beständen zuzuordnen sind. Im Gegensatz zu "klassischen" diskreten Zuordnungsproblemen, bei denen zwei diskrete Mengen von Angebots- und Nachfrageobjekten einander zugeordnet werden, ist bei der kontinuierlichen Zuordnung eine Objektmenge auf Intervalle (meist Zeitintervalle, dann spricht man auch von Scheduling) der anderen Objektmenge abzubilden. Im Kurzfristbereich, d.h. für einen Zeitraum weniger Schichten bis einiger Tage, kann man davon ausgehen, daß die Einkaufsteile bereits beschafft wurden oder ihre Beschaffung zumindest ausgelöst wurde. Es bleiben also zwei Arten von Zuordnungen zu tun: Materialbedarfe sind durch Bestände zu decken; dabei können z.B. unterschiedliche Reservierungen unterschieden werden, die je nach aktuellem Zustand aufrechterhalten werden müssen oder aufgehoben und neu zugeteilt werden können. Vor allem aber müssen die Bedarfe an Kapazitäten den verschiedenen Fertigungseinrichtungen zugeordnet werden. Dabei ist vor allem darauf zu achten, daß viele Operationen mehrere Ressourcen gleichzeitig benötigen; wenn nur eine fehlt, kann die gesamte Operation nicht ausgeführt werden.

Als primäre Methode kommt die in der Zuordnungs­Shell COKE realisierte Strategie "Vorschlagen­undVertauschen" zum Einsatz, die weiter unten beschrieben wird.

Neben den Massendaten nimmt der zweite Teil der Datenmodelle das dispositive, für die Planung notwendige Wissen der Disponenten auf. Es besteht für den Bereich der Feinplanung wiederum aus zwei Teilen: Restriktionen und Vorschläge. Mit Hilfe der Restriktionen werden die Bedingungen formuliert, die im Lauf der Planung eingehalten werden müssen (harte Restriktionen) oder sollen (weiche Restriktionen). Die harten Restriktionen beschreiben z.B. fertigungstechnische Notwendigkeiten und sollten im Verlauf der Planung nicht geändert werden. Im Unterschied dazu beschreiben die weichen Restriktionen Anforderungen, deren Erfüllung zwar erwünscht aber nicht unbedingt notwendig ist. Restriktionen können mit einem Gewicht versehen werden, das wie eine Art Strafpunkte wirkt; die Planung versucht, die Summe der Strafpunkte zu minimieren. Vorschläge dienen dazu, dem System in bestimmten Situationen Richtungen zu weisen, in denen die Lösung zu bestimmten Problemen liegen können.

Die grundsätzliche Vorgehensweise bei der Lösung von zeitkontinuierlichen Zuordnungsproblemen besteht aus 4 Schritten:

Eingabe: Angebots- und Nachfrageobjekte mit gewichteten Randbedingungen und interner Zeitschranke.

Ausgabe: Zuordnung der Nachfrageobjekte auf Zeitintervalle der Angebotsobjekte mit möglichst minimaler Verletzung der Randbedingungen.

Bis alle Nachfrageobjekte zugeordnet sind, tue Schritte 1. – 3.

1. Wähle ein Nachfrageobjekt
2. Berechne ein lokal passendes Intervall beim Angebotsobjekt
3. Überprüfe die Randbedingungen. Bei Verletzungen versuche mit Vertauschungen und alternativen Belegungen die Verletzung der Randbedinungen zu minimieren. Übernehme die relativ beste Version, die innerhalb der vorgegebenen Zeitschranke gefunden wurde.
4. Wenn zum Schluß immer noch Randbedingungen verletzt sind, versuche mit den gleichen Strategien wie in Schritt 3., allerdings mit einer höheren Zeitschranke, die Verletzungen zu minimieren.

Der Algorithmus eignet sich insbesondere auch für die interaktive Zuordnung, da jeder Zwischenschritt auf dem Bildschirm angezeigt werden kann und der Disponent jederzeit in jedem Schritt eingreifen kann. Im folgenden diskutieren wir verschiedene Strategien für die Schritte 1. – 4.

Die wichtigsten Besonderheiten des Verfahrens sind die folgenden:

1. Im ersten Schritt wird das nächste einzuplanende Nachfrage­Objekt ausgewählt. Bereits hier kann Wissen eines Disponenten einfließen, etwa indem erst Bedarfe auf Engpaßressourcen verplant werden, bevor anschließend die weniger kritischen Ressourcen zugeordnet werden. Genausogut kann auftragsbezogen vorgegangen werden: Besonders dringende Aufträge werden bevorzugt behandelt, die übrigen müssen sich in die verbleibenden Kapazitäten teilen. Das verwendete Wissen wird in sog. Vorschlagsregeln hinterlegt. Grundsätzliche Alternativen für die Vorschlagsregeln sind:

1. Zufällige Auswahl
2. Statische Vorsortierung der Vorschlagsobjekte. Beispiel: Vorsortierung entsprechend der Dringlichkeit der Aufträge oder der vorher ermittelten Knappheit der Ressourcen.
3. Statische Vorsortierung mit dynamischer Modifikation. Beispiel: Vorsortierung gemäß Dringlichkeit der Aufträge, wobei dynamisch festgestellte knappe Ressourcen die Reihenfolge der Vorschlagsobjekte jederzeit modifizieren können.
4. Dynamische Sortierung. Beispiel: Keine Vorsortierung, stattdessen wird immer das relativ beste Vorschlagsobjekt gewählt, z.B. immer die aktuell knappste Ressource.

1. Im zweiten Schritt wird zu dem ausgewählten Nachfrage­Objekt ein passendes Angebots­Objekt gesucht. In den meisten Fällen sind die benötigten Ressourcen zumindest grob in der Ressourcenliste angegeben; d.h. wenigstens die Zuordnung zu einer Maschinengruppe ist getroffen. Falls nicht, kann diese Auswahl hier vorgenommen werden; ansonsten wird z.B. eine Einzelmaschine aus der Gruppe gewählt. Ebenso werden die restlichen benötigten Ressourcen ausgewählt.
   Zugeordnet werden aber nicht nur die Ressourcen an sich, sondern es wird auf allen benötigten Ressourcen ein passendes Zeitintervall gesucht, zu dem sie gleichzeitig zur Verfügung stehen. Für beide Zuordnungen kann arbeitsplanerisches Wissen für die Feinauswahl einer passenden Ressource sowie dispositives Wissen über die Wahl eines geeigneten Zeitpunkts genutzt werden. Grundsätzliche Alternativen für die Auswahl von Partnerobjekten zu dem Objekt aus dem 1. Schritt sind:

1. Zufällige Auswahl eines Zeitintervalls eines Partnerobjektes. Beispiel: Das erste passende Partnerobjekt gemäß einer vorsortierten Reihenfolge.
2. Wähle ein Zeitintevall des Partnerobjektes mit minimaler Verletzung der Randbedingungen.
3. Wähle ein Zeitintevall des Partnerobjektes mit minimaler Verletzung der Randbedingungen und berücksichtige als sekundäres Kriterium, daß durch die Zuordnung zukünftige Zuordnungen möglichst wenig eingeschränkt werden (z.B. indem zu belegende Zeitintervalle einer Ressource so berechnet werden, daß möglichst große Blöcke von noch freien Zeitintervallen übrig bleiben).

1. Nach jedem Zuordnungsschritt können weitere Restriktionen überprüft werden. Falls hinreichend wichtige Restriktionen verletzt sind, wird mit Hilfe benutzerdefinierbarer Vertauschungsprozeduren untersucht, ob es Vertauschungen der aktuellen mit früheren Zuordnungen gibt, die die Summe der verletzten Restriktionen verringern würden. Hier läßt sich praktisch das gesamte Spektrum der Suchverfahren [Russell & Norwig 95, Teil II] einsetzen: Breitensuche, Tiefensuche, Iterative Tiefensuche, Hill-Climbing, Simulated Annealing, Beam-Search, Bestensuche, A* usw. Da vollständige Suchverfahren wegen der Größe des Suchraumes ausscheiden, muß man sich auf heuristische Suchverfahren beschränken, die zur Effizienzsteigerung durch gute Heuristiken geleitet werden müssen. Unser Basisalgorithmus ist aus Gründen der Speicherplatzeffizienz ein Beam-Search, bei dem eine begrenzte Anzahl der lokal aussichtsreichen Vertauschungsoperationen solange weiterverfolgt werden, bis die Zeitschranke abgelaufen ist. Daher kann man nicht erwarten, daß für jede verletzte Randbedingung eine optimale Korrektur gefunden werden kann. Die Effizienz dieses Verfahren hängt entscheidend von den Heuristiken ab. Deren Aufgabe ist es – grob gesagt – eine Art Frühwarnung für die Verletzung von Randbedingungen darzustellen, die bei der "naiven" Zuordnung meist erst bei der Einplanung der letzten Nachfrageobjekte sichtbar werden, wobei dann wenig Spielraum für Verbesserungen besteht. Auf konkrete Kennzahlen, die als Heuristiken brauchbar sind, gehen wir im nächsten Abschnitt ein.
2. Wenn alle Nachfrager­Objekte abgearbeitet wurden, werden in einer Nachbesserungsphase die noch immer verletzten Restriktionen erneut untersucht. Auch hier werden mögliche Vertauschungen gesucht und überprüft, ob sie zu einer Verbesserung beitragen. Die Strategie ist die gleiche wie beim Schritt 3.

Dieser letzte Schritt spielt eine wichtige Rolle bei Umplanungen. Es ist nicht sinnvoll, allzu häufig eine komplette Neuplanung vorzunehmen. Vielmehr sollte man so lange wie möglich an einem einmal erstellten Plan festhalten, um zu große Unruhe in der Fertigung zu vermeiden. Insbesondere die Positionen, die bereits für die Fertigung freigegeben und für die Arbeitspapiere erstellt und verteilt wurden, sollten nach Möglichkeit nicht mehr verändert werden. Auch im Falle lokaler Änderungen wie dem Ausfall einzelner Ressourcen muß kein Neuaufwurf der Planung erfolgen. In all diesen Fällen wird ein bestehender Plan, in dem einzelne Bedingungen verändert wurden (Maschine ausgefallen, Personal gegangen, Werkzeug gebrochen etc.), nur insoweit verändert, daß auch unter den neuen Bedingungen weiter gefertigt werden kann.

Eine wesentliche Eigenschaft des beschriebenen Verfahrens ist die Tatsache, daß an jeder Stelle und zu jedem Zeitpunkt innerhalb der Planung interaktiv eingegriffen werden kann. Die Initiative kann vom System ausgehen, etwa wenn eine Vorschlagsregel für eine bestimmte Situation vorgibt, zu einer anstehenden besonders schwierigen Entscheidung den Benutzer zu fragen; ebenso kann der Disponent jederzeit eingreifen, weitere Zuordnungen treffen, Vertauschungsmöglichkeiten mit oder ohne Überprüfung durch das System vorschlagen oder auch das Verfahren auf dem momentan erreichten Stand abbrechen.

Zwei weitere besondere Eigenschaften des verwendeten Algorithmus seien hier erwähnt: Erstens wird für jeden einzelnen Vertauschungsschritt eine bestimmte, evtl. dynamisch vom Gewicht der verletzten Restriktionen abhängige Maximalzeit vorgegeben. Wird innerhalb dieser Zeit keine günstigere Vertauschung gefunden, wird der Algorithmus trotzdem bei Schritt 1. mit dem nächsten Nachfrage-Objekt fortgesetzt. Dadurch stellt man sicher, daß der Algorithmus auch unter ungünstigen Bedingungen terminiert (Any­Time­Eigenschaft). Man trägt damit dem Umstand Rechnung, daß es bestimmte Restriktionen gibt, für die in sinnvoller Zeit keine gute Auflösung gefunden werden kann, was in der betrieblichen Praxis ein bekanntes Phänomen ist, wo nicht ein irgendwie "optimaler" Plan gesucht wird, sondern im Normalfall auch ein weniger guter Plan ausreicht. Je nach zur Verfügung stehender Zeit kann man die Zeitschranken mehr oder weniger großzügig gestalten und damit die Qualität des Planes beeinflussen, der um so besser wird, je mehr Suchzeit zugelassen wird.

Zweitens wird keine einmal gemachte Zuordnung einfach zurückgezogen, wie das bei herkömmlichen Backtracking­Algorithmen der Fall ist. Stattdessen wächst die Anzahl der getroffenen Zuordnungen stets monoton; ein einmal erreichter Stand wird in jedem Fall beibehalten oder verbessert. Damit wird verhindert, daß sich das Verfahren bei schwierigen Problemen "totläuft".

Eine Evaluation der angegeben Alternativen für die Vorschlagen-und-Vertauschen-Strategie findet sich in [Poeck&Puppe 92]. Dabei stellte sich heraus, daß je schwieriger die zu lösenden Zuordnungsaufgaben sind, desto mehr lohnt sich eine aufwendigere Berechnungsstrategie in den frühen Phasen des Zuordnungsalgorithmus (also die ziemlich aufwendige Berechnung der Alternativen 1.4 und 2.3).

Zunächst muß man sich über das Hauptoptimierungskriterium für die Disposition klar werden. Dabei gibt es mehrere Kandidaten wie Termintreue, kurze Durchlaufzeiten, geringe Liegezeiten, maximale Kapazitätsauslastung oder hohe Robustheit gegenüber unvorgesehenen Änderungen und deren vielfältige Kombinationen. Diese Kriterien werden in der Bewertung durch Gewichtung der entsprechenden Constraints ausgedrückt, wobei z.B. bei allgemeiner Bevorzugung von hoher Termintreue zusätzlich unterschiedliche Aufträge eine unterschiedliche Gewichtung z.B. je nach Höhe der Konventionalstrafen bei Terminüberschreitung bekommen können. Für die Zuordnung ist es sehr wichtig, daß für alle relevanten Kriterien eine Art "Frühindikator" berechnet werden kann, der auch schon bei partiellen Plänen eine Abschätzung widerspiegelt, wie gut sie die Randbedingungen einhalten werden. Im folgenden geben wir eine Übersicht über entsprechende Kennzahlen:

• Termintreue von Aufträgen, wenn noch nicht alle Operationen eingeplant sind: Eine einfache Abschätzung ist, ob die Zeit nach der zuletzt eingeplanten Operation noch für die übrigen Operationen ausreichen kann, um den versprochenen Endtermin zu halten. Dabei können auch Schätzwerte für Puffer- oder Rüstzeiten mitberücksichtigt werden. Eine aufwendigere Abschätzung ist eine Vorberechnung eines frühesten und spätesten Termin für jede Operation und eine Überprüfung, ob alle derzeit eingeplanten Operationen innerhalb ihres erlaubten Intervalles liegen.
• Kapazitätsauslastung einer Ressource für größere Zeitintervalle, z.T. Tage, Wochen oder Monate. Ressourcen mit hoher Auslastung stellen für die entsprechenden Zeitintervalle Engpaßressourcen dar.
• Kostenstruktur von Ressourcen: Manche Ressourcen sind im Betrieb immer verfügbar und deren Nutzung verursacht keine Zusatzkosten, während andere Ressourcen Kosten direkt oder nur indirekt proportional zu ihrer Nutzung verursachen. Zu letzteren können z.B. Ressourcen gehören, die eine Normalauslastung haben, die mit entsprechenden Zusatzkosten aber auch überschritten werden kann.
• Dichte eines Auftrages: Abschätzung, wie eng die Operationen eines Auftrages aufeinander folgen. Eine hohe Dichte bedeutet oft eine geringe Robustheit bei Störungen. Zur effektiven Abschätzung der Dichte benötigt man eine Vorgabe in Form von erwünschten Pufferzeiten zwischen je zwei Operationen eines Auftrages. Aus der Dichte aller Aufträge kann auch die Robustheit des Gesamtplanes gegenüber externen Störungen geschätzt werden.
• Flexibilität einer Operation: Sie berechnet sich aus der ressourcen- und der auftragsbedingten Flexibilität einer Operation:
• Ressourcenbedingte Flexibilität einer Operation bzw. eines Auftrages: Diese ergibt sich aus der Kapazitätsauslastung der für die Operation(en) benötigten Ressourcen, wobei auch eventuelle Alternativressourcen berücksichtigt werden. Sie sinkt entsprechend, wenn mehrere Ressourcen für die Durchführung der Operation erforderlich sind.
• Auftragsbedingte Flexibilität einer Operation: Diese ergibt sich aus der Anzahl und der Flexibilität der Vorgänger bzw. Nachfolger-Operationen im Auftrag. Eine Operation mit vielen, dicht aufeinanderfolgenden bereits eingeplanten Vorgänger-Operationen kann nur schwer nach hinten verschoben werden und eine Operation mit vielen noch einzuplanenden Nachfolge-Operationen kann bei einer Verschiebung nach vorne den Spielraum der Nachfolge-Operationen erheblich einengen.

Natürlich können die Kennzahlen nicht die grundlegenden Konflikte in den allgemeinen Planungszielen ausgleichen, weswegen zusätzliches Wissen erforderlich ist, wie die Kennzahlen zueinander in Beziehung gesetzt werden (z.B. Priorität auf Termintreue, Auslastung, Dichte oder Robustheit).

Obwohl die Kennzahlen teilweise auf der Basis partieller Pläne abgeschätzt werden können, bleibt das Problem bestehen, daß man sie einigermaßen zuverlässig erst mit fertigen Plänen berechnen kann. Um diesen scheinbaren Widerspruch aufzuheben, wollen wir eine iterative Zuordnung vornehmen, wobei in der ersten Phase nur eine grobe Planung mit wenigen und abgeschwächten Restriktionen erfolgt, die in jeder Phase verfeinert werden, und die letzte Phase das Endergebnis liefert. Dabei dienen die berechneten Kennzahlen einer abgeschlossenen Phase als Heuristiken für die nächste, die dann entsprechend der teilgeplanten Operationen ständig verfeinert werden. Randbedingungen, die bei einer vergröberten Planung abgeschwächt werden können, sind:

• Vergröberung der Zeitstruktur: Statt termingenau zu planen, kann man auch größere Zeiteinheiten (z.B. Tage, Wochen, Monate) als undifferenzierten Block betrachten, wobei dann andere Berechnungsverfahren für Termine notwendig werden.
• Vergröberung der Ressourcen zu Ressourcengruppen, die sich zumindest partiell wechselseitig ersetzen können, einschließlich Abstraktion von Rüstzeiten.
• Vergröberung der Operationen zu weniger differenzierten Operationen, die auf ähnlichen Ressourcen arbeiten (z.B. Metallverarbeitung, Oberflächenbearbeitung, Montage usw.). Sie benötigen dann als Ressourcen nur die oben erwähnten Ressourcengruppen. Falls es relativ unkritische Ressourcen gibt, kann man diese bei der Vergröberung auch weglassen.
• Zusammenfassen von Operationen zu Makrooperationen. Während die Vergröberung nur die Anzahl der Operations- und Ressourcentypen reduziert, aber die Anzahl der Operationen nicht beeinflußt, kann man durch Zusammenfassung von Operationen zu Makrooperationen auch die Anzahl reduzieren. Die Makrooperationen müssen allerdings zu den Ressourcengruppen passen, d.h. es müssen darauf alle Einzeloperationen gefertigt werden können, und sie benötigen auf der Ressourcengruppe entsprechend mehr Zeit.

Die Phasenplanung mit zunächst vergröberten Randbedingungen hilft nicht nur bei der Berechnung der Kennzahlen für die detailliertern Planungsläufe, sondern auch bei einer Frühererkennung von unter den vorgebenen Randbedingungen wahrscheinlich unlösbaren Konflikten, zu deren Lösung der Disponent die Randbedingungen verändern muß (z.B. Überstunden anordnen, Aufträge ablehnen oder eine Fremdvergabe aushandeln). Die Phasenplanung kann man auch als eine Verfeinerung der traditionellen Zweiteilung in Mittelfrist- und Kurzfristdisposition betrachten.

Eine kritische Größe bei der Planung ist der Umgang mit unvorhergesehenen Ereignissen wie dem Ausfall von Maschinen oder Personal, der Annahme zusätzlicher (Notfall)Aufträge oder das verspätete Eintreffen von Zulieferteilen. Die bloße Fähigkeit zur reaktiven Planung, die im Vorschlagen- und-Vertauschen-Algorithmus im vierten Schritt mitabgedeckt wird, reicht nicht aus, wenn z.B. der Plan so dicht war, daß eine gute Umplanung schlicht unmöglich ist. Stattdessen sollte von vornherein soviel Pufferzeit in den Originalplan eingebaut werden, daß unvorhergesehene Ereignisse im üblichen Rahmen durch Ausnutzung der Pufferzeiten kompensiert werden können. Die kritische Frage ist hier, wie groß die Pufferzeiten angesetzt werden sollten. Dazu gibt es verschiedene Verfahren: Abschätzung durch erfahrene Disponenten, systematische Auswertung der Betriebsdaten über Störungen und die Einhaltung der Planzeiten in der Vergangenheit oder auch eine Simulation von Plänen mit entsprechend vorgegebener Wahrscheinlichkeitsverteilungen zufällig generierten Störereignissen. Bei letzterer ist wichtig, daß die Simulation auch die Fähigkeit zur Umplanung besitzt, ähnlich wie dies in der Realität auch erfolgen würde. Dies kann man durch Kopplung eines Simulationssystems mit einem reaktiven Planer erreichen (s. [Beck 1998]).

Die nachfolgenden Abschnitte zeigen die Umsetzung der beschriebenen Konzepte in dem System WIZARD.

Die Massendaten sind mit Hilfe einer Klassenhierarchie repräsentiert, wie sie in Abb. 1 zu sehen ist. Ein Auftrag beschreibt eine Folge von Operationen, von denen jede aus beliebig vielen Arbeitsplatz-, Personal-, Material- und Werkzeug-Positionen bestehen. Jede Position besitzt mindestens eine Dauer bzw. Menge sowie einen Verweis auf die von ihr benötigte Ressource. Die Ressourcen ihrerseits sind dargestellt durch Instanzen der Klassen Arbeitsplatz, Personal, Material oder Werkzeug.

Abbildung 2 zeigt beispielhaft Daten, wie sie aus einem PPS-System an WIZARD übergeben wurden. Die drei Operationen bestehen jeweils aus einer Arbeitsplatz-Position (gekennzeichnet durch "AG"); die zeitlich vorletzte Operation Demo11_2 benötigt zusätzlich das Material "Lack weiß". Pro Operation wurde ein frühester und ein spätester Termin übernommen. Innerhalb dieses vorberechneten Terminrahmens sollte jede Operation begonnen werden. Mit Hilfe des Zustands werden geplante, begonnene, beendete etc. Arbeitsschritte unterschieden.

Die Restriktionen, die als Teil des dispositiven Wissens beschreiben, welche Anforderungen ein guter Plan erfüllen muß, können — wie das gesamte restliche Wissen (Vorschläge, Korrkturfunktionen usw.) — graphisch editiert werden. Abbildung 3 zeigt als Beispiel einen Dialog, in dem einzelne vordefinierte Restriktionen aktiviert oder deaktiviert werden können. Außerdem kann man jeder Restriktion ein Gewicht zuweisen; in der Abbildung wird definiert, daß es als "sehr schwere Verletzung" gilt, wenn ein Auftrag nicht pünktlich fertiggestellt wird. Diese eher intuitiven Angaben werden intern in Strafpunkte umgesetzt. Bei der aktuellen Bewertung einer Restriktionsverletzung wird außerdem ihr Schweregrad berechnet, denn es macht z.B. bei der Überlappung zweier Operationen einen erheblichen Unterschied, ob sie sich nur für kurze Zeit oder etwa ihre gesamte Durchführungszeit überschneiden.

Im Rahmen einer Diplomarbeit ([Beck 1998]) wurde als Erweiterung zu WIZARD das Simulationssystem DyBBS realisiert. Es erlaubt die graphische Modellierung einer Fertigung in Form von Ereignisgraphen. Jedes Ereignis tritt mit einer bestimmten terminabhängigen Wahrscheinlichkeit ein, setzt i.a. den Zustand einer Komponente um und kann beliebige weitere Auswirkungen haben. Eine spezielle Auswirkung ist das Anstoßen einer Umplanung durch WIZARD, sobald Plan und simulierte Wirklichkeit sich zu weit voneinander entfernt haben. Damit ist es möglich, die dynamische Qualität der von WIZARD errechneten Ablaufpläne, also ihre Robustheit gegen unvorhergesehene Ereignisse, zu überprüfen und sinnvolle oder gar notwendige Puffer besser abzuschätzen.

Abbildung 4 zeigt ein Beispiel für die graphische Benutzeroberfläche von WIZARD. In der Mitte zeigt das Zeitlineal den aktuellen Tag, den dargestellten Zeitraum (hier 4 Wochen ab dem 27.12.98) sowie (als hellgraue Balken) die Wochenenden. In der unteren linken Anzeige werden zusätzliche Meldungen wie verletzte Restriktionen usw. ausgegeben.

Über dem Zeitlineal sind exemplarisch drei Ansichten derselben Ressource dargestellt. Die erste ist ein Balkendiagramm; es entspricht bekannten Gantt-Diagrammen. Jede Operation wird durch einen Balken repräsentiert; dessen Position relativ zum Zeitlineal zeigt ihren Starttermin, seine Länge entspricht der Bearbeitungszeit. Die zweite Darstellung ist ein sog. Kapazitätsgebirge. Sie zeigt vor allem bei Maschinengruppen sehr übersichtlich an, wo Unter- und Überdeckungen existieren. Die dritte Darstellung, die sog. Saldierungsgraphik, zeigt dagegen summarisch den Auslastungsgrad der Ressource in der gewählten Auflösung (hier wochenweise).

Interaktion ist durch drag-and-drop möglich; so kann einer Operation ein neuer Starttermin oder eine andere (z.B. Ausweich-) Ressource zugewiesen werden. Bei jeder Interaktion werden im Hintergrund alle aktiven Restriktionen geprüft; das Resultat wird sofort unten rechts angezeigt. Dadurch wird der Planer auch auf Probleme hingewiesen, die nicht direkt sichtbar sind, etwa weil die entsprechende Darstellung aktuell nicht geladen ist.

Dieses Kapitel gibt einen Überblick zu dem an der Professur Künstliche Intelligenz der TU Chemnitz entwickelten Multiagentensystem MAPS (Multi­Agenten-Planungs­System). Es werden die Hauptmerkmale von MAPS kurz erläutert, die Anbindung zu WIZARD beschrieben und es werden bisherige Ergebnisse vorgestellt.

Die wichtigste Motivation für die Erstellung von MAPS ist, ein flexibles Werkzeug für die Ressourcenbelegungsplanung basierend auf Techniken und Methoden der verteilten Künstlichen Intelligenz (VKI) für den praktischen Einsatz zu erstellen und zu evaluieren. Dafür wurden unter anderem Ideen von Mitarbeitern der Professur aufgegriffen und erweitert [Dilger and Kassel, 1993, Dilger et al., 1995].

Ziel des Sytems ist es, sinnvolle und robuste Belegungspläne zu berechnen, die praktischen Kriterien und Gesichtspunkten, z. B. Berücksichtigung von Schichtplänen, Multiressourcen oder früheste und späteste Termine für die einzelnen Arbeitsgänge, genügen. Dabei ist es — im Unterschied zu typischen Aufgabenstellungen im Operations Research — ein untergeordnetes Ziel, den Arbeitsplan mit der kleinsten Summe aller Durchlaufzeiten zu finden, als viel mehr überhaupt einen Arbeitsplan, der so wenige Restriktionen wie möglich verletzt. Ein weiteres Ziel für MAPS ist es, einen bestehenden Arbeitsplan neuen Anforderungen (die entstehen können, wenn z. B. eine Maschine ausfällt oder ein unvorhergesehener dringender Auftrag zu bearbeiten ist) so anzupassen, daß notwendige Änderungen minimal bleiben und der Plan sich nur lokal verändert.

In MAPS sind zwei verschiedene Planungsstrategien für Multiagenten realisiert, eine eng gekoppelte und eine lose gekoppelte. Die eng gekoppelte Strategie basiert auf der Idee, daß die beteiligten Agenten (siehe nächstes Teilkapitel) an einem Arbeitsgang alle in einer neuen Startzeit für diesen übereinstimmen müssen (detailliert beschrieben in [Wellner and Dilger, 1998]). Wenn ein Agent seinen lokalen Arbeitsplan ändern möchte, muß er die Änderung mit den entsprechenden anderen Agenten aushandeln. Als Ergebnis einer solchen Verhandlungsrunde ergibt sich eine Startzeit, die alle Agenten akzeptieren.

Bei der lose gekoppelten Methode wird der Selbstorganisationsaspekt des Agentensystems in den Vordergrund gestellt (siehe [Wellner and Dilger, 1999]). Jeder Agent versendet als Nachricht eine für sich selber akzeptable Startzeit eines Arbeitsganges an alle beteiligten Agenten, die dies auch erst einmal akzeptieren müssen. Sie können aber im nachhinein eine neue Nachricht mit einer neuen Startzeit versenden. Entscheidend dabei ist, daß sie bei der Festlegung einer neuen Startzeit auf die Wünsche und Intentionen der anderen Agenten mit eingehen, die sie im Verlauf der Verhandlungen aus dem Verhalten dieser zu erlernen versuchen. Gewisse Synchronisationsnachrichten sind nach bestimmten Zeiteinheiten notwendig, um einen kohärenten Plan zu gewährleisten.

Beide Strategien unterscheiden sich bezüglich der Art und Weise, wie sie den Suchraum möglicher Belegungpläne bewältigen oder wie mit Constraints umgegangen wird. Aus Sicht der VKI kann man feststellen, daß die eng gekoppelte Strategie auf deliberativen und die lose gekoppelte Strategie auf reaktiven und adaptiven Agenten basiert.

2.5.2 Kurzbeschreibung der Kopplung MAPS-Wizard

Es gibt zwei Arten von Agenten in MAPS: Auftragsagenten und Ressourcenagenten. Ein allgemeines Schema eines MAPS­Agenten zeigt Abbildung 5. Zur Initialisierung des Agentensystems wird für jeden bestehenden Auftrag in Wizard ein Auftragsagent und für jede Ressource (u. a. Maschinen, Personal oder Spezialwerkzeuge) ein Ressourcenagent angelegt und mit den notwendigen Informationen ausgestattet. Somit bekommt jeder Agent einen Überblick über "seine" Arbeitsgänge, deren Reihefolge, einzuhaltende Zeitspannen und mehr. Ziel eines jeden Agenten ist es, eine interne Bewertungsfunktion (siehe [Wellner and Dilger, 1998]) zu maximieren, die den momentanen Erfolg der korrekten Einplanung all seiner Arbeitsgänge widerspiegelt.

Durch die enge Ankopplung von MAPS an Wizard können in MAPS viele, bereits in Wizard implementierte Funktionen problemlos übernommen werden. Dazu gehören z.B. Funktionen für den korrekten Umgang mit Schichtplänen oder Funktionen und Datenstrukturen für eine flexible Handhabung von Ressourcenbelegungen.

Mittels einfacher Menüaufrufe kann MAPS aus Wizard heraus initialisiert und gestartet werden. Verschiedene Standardplanungsroutinen (bedingt durch eine Sequenzialisierung der Multiagentenplanung) sind voreingestellt und können vom Nutzer je nach Bedarf aufgerufen werden. Zur Kopplung MAPS­ Wizard gehört weiterhin eine Transferfunktion für die Plandaten von MAPS nach Wizard und umgekehrt.

Beide Planungsstrategien wurden sowohl an Standarddaten aus dem Operations Research als auch an Praxisdaten getestet (in [Wellner and Dilger, 1999] näher beschrieben). Da MAPS keine besondere Anpassung für OR­Daten erfahren hat (kürzester Plan vs. robuster Plan), sind die Ergebnisse nicht im optimalen Bereich ([Blazewicz, 1993]) für OR­Daten. Die Fähigkeiten von MAPS kommen erst bei Tests mit Daten aus der betrieblichen Praxis, etwa des Kooperationspartners Hüttenwerke Krupp Mannesmann zur Geltung. MAPS versucht, je nach Strategie entweder so viele als mögliche Arbeitsgänge ohne Verletzung einer Restriktion und die restlichen mit geringst möglichem Verletzungsgrad einzuplanen (eng gekoppelte Strategie), oder, ausgehend von einer eher willkürlichen Startbelegung, die Anzahl der Restriktionsverletzungen schrittweise zu minimieren (lose gekoppelte Strategie).

Für das letzte Teilstück des Projekts verbleibt eine noch bessere Anpassung von MAPS an Praxisanforderungen (insbesondere eine Optimierung der benötigten Planzeit) und eine Erweiterung der Agentenfähigkeiten für eine Alternativressourcenplanung.

Außer den beschriebenen Präsentationen und Machbarkeitsanalysen wurden auch vergleichbare Systeme untersucht. Als Beispiel sei das System FEKOR der Firma FLS in Aachen genannt. Es stammt aus der Kunststoffindustrie und wird seit Mitte der siebziger Jahre entwickelt. Das zentrale Planungsverfahren stammt aus dem Operations Research; genaueres hierzu war nicht zu erfahren. Ähnlich wie WIZARD plant FEKOR simultan alle von einer Operation benötigten Ressourcen; besonderer Wert wird dabei auf die in der Kunststoffindustrie sehr wichtige Werkzeugverwaltung sowie auf die Rüstoptimierung gelegt. Dazu sind alle Aktivitäten mit Kosten belegt; die Gesamtsumme der Kosten ist zu minimieren. Wie bei WIZARD werden alle zur Planung benötigten Daten im Hauptspeicher gehalten; dazu sind nach Herstellerangaben mindestens 128 MB Hauptspeicher notwendig; das bewegt sich in derselben Größenordnung wie bei WIZARD. Die komplette Optimierung von ca. 1000–1500 Operationen dauert ca. 10–30 Minuten. Das System ist in C programmiert; die graphische Oberfläche, die ein paar interessante Eigenschaften aufweist (dynamische Anzeige von Vorgänger- und Nachfolger-Relation, automatische Verplanung aller Nachfolger nach Verschieben einer Operation) wurde mit C++ realisiert, während die Datenverwaltung und einfache Dialoge mit Microsoft Access gemacht wurde.

Obwohl das System seit mehr als 20 Jahre auf dem Markt ist, wurde es in dieser Zeit nur ca. 30 mal installiert. Nach Herstellerangaben liegt das vor allem an zwei Faktoren: Erstens ist es sehr schwierig, den für die Planung zuständigen Disponenten das Vertrauen zu geben, daß das System alle zu beachtenden Randbedingungen tatsächlich einhält. Solange das nicht wirklich "geglaubt" wird, planen viele Unternehmen lieber "von Hand". Zweitens wurde das System unabhängig von einem Standard-PPS-System entwickelt und muß daher als Stand-alone-Lösung ohne Integration angesehen werden. Der Hersteller selbst ist sehr entwicklungslastig; ein hinreichend großer Vertrieb konnte bisher nicht aufgebaut werden.

Der Nachweis der ausreichenden Beachtung aller relevanten Restriktionen, die in WIZARD noch dazu graphisch editiert werden können, wird bei INKAD im angebrochenen dritten Jahr der praktischen Evaluationen erbracht werden. Der zweiten Nachteil der mangelnden Integration, der auch für Produkte wie den jetzt von der Firma Polydata vertriebenen AHP-Leitstand gilt, wurde bei INKAD durch die von Anfang an konsequente Anbindung an das Standardsystem infor:NT vermieden.

Die 1990 gegründeten Hüttenwerke Krupp Mannesmann (kurz HKM) stellen für die Mutterfirmen, die Krupp­Stahl AG und die Mannesmann­Röhrenwerke­AG, ca. 4 Millionen Tonnen Rohstahl in unterschiedlichsten Sorten her. Von insgesamt 3500 Mitarbeitern wird ein Umsatz von jährlich ca. 1,7 Milliarden DM erwirtschaftet. Die von uns untersuchte, zum Unternehmensbereich Anlagenwirtschaft gehörende Zentralwerkstatt der HKM ist für die Instandhaltung der produktionstechnischen Anlagen zuständig. Mit ca. 200 Mitarbeitern in der Werkstatt selbst und ca. 100 weiteren im Außendienst entspricht die Werkstatt einem durchschnittlichen mittelständischen Unternehmen.

Die Dispositionsart in der Zentralwerkstatt ist überwiegend kundenauftragsorientiert, d.h. einzelne Reparatur­Aufträge werden gezielt auf Kundenanforderung erledigt. Bei dieser Art von Aufträgen müssen die jeweiligen Auftragstermine unbedingt eingehalten werden; sie machen etwa 60% des Auftragsvolumens aus und erhalten eine der externen Prioritäten 1 bis 3. Daneben gibt es eine Anzahl sogenannter Füllaufträge (externe Priorität größer als 3), die zwar ebenfalls einen gewünschten Fertigstellungstermin besitzen, der aber abhängig von der Auslastung verschoben werden darf.

Zur Zeit werden — mit Hilfe des Produktionsplanungs- und -steuerungssystems VPPS von infor — von zwei bis drei Termindisponenten ca. 60 Arbeitsplätze zentral geplant, auf denen pro Schicht 80 Mitarbeiter, angeleitet von ca. 3 Schicht­Meistern, eingesetzt sind. Um auch in Notfallsituationen durchgängig erreichbar zu sein, werden die Mitarbeiter nach einem relativ komplizierten Schicht­Schema eingesetzt. Im Durchschnitt werden ca. 1.500 Aufträge mit einer ungefähren Durchlaufzeit zwischen 2 und 14 Wochen bearbeitet. Täglich werden nach Arbeitsplätzen sortierte Listen gedruckt und verteilt. Die Aufträge mit Verzug werden bevorzugt bearbeitet, wobei man mit verschiedenen Maßnahmen versucht, sie zu beschleunigen. Die größte Bedeutung hat das kurzfristige Anordnen von Überstunden und Mehrarbeit; daneben wird Personal umgesetzt bzw. Arbeit auf Ausweicharbeitsplätze verlagert.

Im Verlauf des Jahres 1999 wird die Organisation der Werkstatt schrittweise auf Gruppentechnologie umgestellt werden, d.h. es werden mehrere Fertigungs­Inseln eingerichtet, die die wesentlichen Arbeitsbereiche Zerspanen, Schweißen und Montage selbständig ausführen können.

In Vorbereitung auf den Echt-Einsatz des Systems WIZARD wurden die folgenden Arbeiten durchgeführt:

• Untersuchung der Arbeitsweise der Disponenten:
  Im Rahmen vieler Besprechungen sowie einer an der Universität Würzburg durchgeführten Diplomarbeit ([Busch 1997]) wurde untersucht, wie die Disponenten in der Termin- und Auftragssteuerung (TAS) arbeiten. Die Arbeit ist im wesentlichen zweigeteilt. Eine Person kümmert sich um die aktuelle Woche, d.h. sie plant bei ungeplanten Ereignissen um, druckt und verteilt neue Fertigungs-Unterlagen, spricht Personalumsetzungen und Sonderschichten ab, klärt die Ursache und mögliche Behebungen von Problemen und so weiter. Diese Arbeit besteht im wesentlichen aus der Kommunikation mit allen am Fertigungsprozeß Beteiligten und ist nicht Inhalt des Forschungsprojekts.
  Die andere Person ist für die eigentliche Planung zuständig. Sie erhält im wöchentlichen Rhythmus die Personalplanung der Fertigungsmeister; je Maschinengruppe wird festgelegt, wieviel Kapazität in den kommenden 2 – 4 Wochen zur Verfügung stehen wird. Bisher wird diese Kapazität um einen Planungsfaktor vermindert, der um so größer ist, je weiter in die Zukunft geblickt wird. Zum Beispiel wird die Plankapazität der nächsten Woche zu 80% verplant, wogegen die der übernächsten Woche nur mehr zu 60% belegt wird. Der Grund für diese willkürliche Kapazitätsverminderung besteht darin, daß VPPS kein Verfahren bietet, die in einem bestimmten Zeitraum verplante, aber nicht erledigte Arbeit automatisch unter Beachtung der Randbedingungen in die Zukunft zu verlagern. Die Kapazitätsreduktion sorgt daher für Puffer, der das manuelle Verschieben erleichtert. Gleiches gilt für Aufträge, die in der Zwischenzeit neu anfallen. Da WIZARD unter anderem diese automatische Verschiebung bietet, kann in Zukunft die gesamte Kapazität auch verplant werden.
  Darüber hinaus unterstützt WIZARD eine weitere Besonderheit der Planung bei HKM: Zwischen zwei Arbeitsgängen muß in der Regel ein Arbeitstag liegen, d.h. der Nachfolger darf wegen aufwendiger Revisionstätigkeiten frühestens am folgenden Arbeitstag begonnen werden. Außerdem werden die Kapazitäten nur wochenweise kontrolliert, d.h. Arbeitsgänge werden lediglich tagesgenau eingeplant.
• TAS-Erweiterung:
  Bis Anfang 1998 wurde ein großer Teil der Aufträge unabhängig von der TAS durchgeführt. Es handelte sich dabei vor allem um die Aufträge der sog. Rolleninsel, die fast im Routinegeschäft die Förderrollen der Stahlgußanlage instandsetzen bzw. erneuern. Das dazu im Hause HKM selbst entwickelte System "Fertigungsplaner" wurde abgelöst; auch diese Aufträge werden nun über VPPS verwaltet. Dazu wurde die TAS um eine weitere Person verstärkt.
• Erweiterung von WIZARD:
  Nachdem die bisherige Zusammenarbeit mit der Universität Würzburg zur Zufriedenheit verlief, wurde ein zusätzlicher Entwicklungsauftrag für ein Betriebsinformationssystem BIS vergeben. Das System ist voll in WIZARD integriert und ermöglicht es, Auswertungen (fast) beliebiger Kennzahlen über beliebige Datenmengen zu spezifizieren, auszuführen und die Ergebnisse nach Microsoft Excel zu exportieren. Das System wird zusammen mit WIZARD Anfang 1999 in Betrieb genommen.
• System-Aufrüstung:
  Um eine einheitliche Betriebssystembasis zu schaffen, wurde das System VPPS auf das Release 4.5 unter Windows NT 4.0 angehoben. Dazu war ein erheblicher Ausbau der Hardware notwendig. Gleichzeitig erlaubt dieses Vorgehen die Erstellung beliebiger Auswertung über die Standard-Datenbank-Schnittstelle ODBC (Open Database Connectivity).

Da die Echteinführung bei HKM zum Zeitpunkt des Erscheinens dieses Berichts noch nicht abgeschlossen ist, kann trotz bisher ermutigender Teilergebnisse über weitergehende konkrete Erfahrungen noch nicht berichtet werden.

Das Produktionsplanungs­ und ­steuerungssystem infor:NT (bisher: VPPS, "PPS im Verbund") wird seit 1985 von der infor AG, Friedrichsthal, entwickelt. Die zuerst realisierte Komponente, der infor­CIM­Leitstand zur Fertigungsplanung und ­steuerung, wurde erstmals im November 1986 vorgestellt. Er besteht aus der Auftragsverwaltung, Funktionen zur Saldierung von Ressourcen sowie zur Terminrechnung für Aufträge und Maschinen. Zur graphischen Visualisierung bietet er eine elektronische Plantafel mit zwei Darstellungsmöglichkeiten, dem Balken-Diagramm und einer Saldierungsgraphik. Darüber hinaus enthält er eine integrierte Betriebs­, Maschinen­ und Personaldatenerfassung, die später um Ankopplungen zu entsprechenden Fremdsystemen erweitert wurde.

Seit ca. 1989 wurde der Leitstand sukzessive zu einem kompletten PPS­System für kleine und mittelständische Fertigungsunternehmen erweitert. Es ist hochgradig modular aufgebaut und umfaßt alle wesentlichen Module zu den wichtigsten Organisationseinheiten wie Einkauf, Vertrieb, Lagerwirtschaft, Finanzwesen und Kostenrechnung und weitere.

infor AG ist mit über 1.200 Installationen von infor:NT (Stand: Ende 1998) Marktführer auf ihrem Gebiet der anspruchsvollen Produktionsplanungs­ und ­steuerungssysteme auf leistungsfähigen Arbeitsplatzrechnern. Unter den Anwendern des Produktes befinden sich neben vielen mittelständischen Unternehmen so bekannte Unternehmen wie Mercedes­Benz, Siemens und DASA. infor besitzt Erfahrungen aus einer großen Zahl erfolgreicher Installationen, die fast in jedem Fall mit umfangreichen Einführungs­ und Projektführungsarbeiten verbunden sind.

Das im INKAD-Projekt entwickelte System WIZARD wurde erstmalig im Februar 1998 dem Führungskreis von infor vorgestellt. Aufgrund des sehr positiven Echos wurde beschlossen, das System im weiteren Verlauf des Projekts möglichst eng an infor:NT anzubinden und die Arbeiten nach Abschluß des Projekts so zu intensivieren, daß es noch im Lauf des Jahres 2000 als Standardmodul angeboten und eingesetzt werden kann. Für das Jahr 1999 werden zu diesem Zweck erhebliche zusätzliche Entwicklungskapazitäten zur Verfügung gestellt.

Die Anbindung an das Vorgängersystem VPPS, vor allem in der bei HKM eingesetzten Version 4.5, wurde über eine sog. ODBC-Schnittstelle realisiert. Damit ist der direkte Zugriff auf die Datenbank-Relationen von VPPS möglich, d.h. alle relevanten Daten werden online aus der Datenbank gelesen, womit eine große Aktualität der Daten sichergestellt ist.

Die Integration in das aktuelle System infor:NT erfolgt entweder über einen dem Microsoft-COM-Standard entsprechenden Zugriff auf den sog. Tabellenserver von infor:NT oder direkt über eine Einbindung als ActiveX-Komponente. Damit ist WIZARD eine der ersten externen Komponenten, die im Rahmen des Forschungsprojekts KoSPuD zusammen mit dem Partner Fhg-IAO in Stuttgart an infor:NT angebunden werden.

Parallel zu den beschriebenen Entwicklungsarbeiten wurde das System WIZARD öffentlich vorgestellt.
Die erste Präsentation fand im März 1998 auf der Cebit statt. Sowohl infor-Kundenberater, die in ihrem Tagesgeschäft bei Fertigungsunternehmen mit den Problemen konfrontiert sind, die WIZARD zu lösen verspricht, als auch Vertreter interessierter Firmen selbst bestätigten den guten Eindruck. Insgesamt konnte das System ca. 20 Anwendern in einer längeren Vorführung gezeigt werden.

Im Herbst 1998 wurde WIZARD dann auf den sog. infor-Anwendertreffen vorgestellt, und zwar in Sulzbach bei Stuttgart, Berlin, Basel und Köln. Bei jedem Treffen wurde es in einem Vortrag von eineinhalb Stunden Länge einem Kreis von je 30–50 Zuhörern vorgestellt. Die Zuhörer kamen aus verschiedenen Firmen mit sehr unterschiedlichen Anforderungen. Durch die anpassbare Grundstruktur des Systems konnten für viele der in der Praxis auftretenden Probleme Lösungen aufgezeigt werden, die die Firmenvertreter zufriedenstellten.

Ähnlich positiv verliefen weitere Präsentationen im Dezember 1998, sowohl vor ca. 40 infor-Vertriebsmitarbeitern als auch vor ca. 60 infor-Kundenberatern, deren Aufgabe darin besteht, bei Einführungs- oder Umstellungsprojekten mit den Kunden zusammen Lösungen zu erarbeiten und diese in den Unternehmen einzuführen.

Aufgrund der beschriebenen Präsentationen haben sich zahlreiche weitere Firmen gemeldet, die an einer Evaluation von WIZARD interessiert sind. Bei mehreren Terminen mit diesen Firmen wurde geklärt, inwieweit WIZARD für die Probleme der jeweiligen Fertigungen geeignet ist. Ein Auszug der Gespräche wird hier wiedergegeben. Die beschriebenen potentiellen Anwender sind anonymisiert.

Fa. G stellt Formen her, mit deren Hilfe z.B. Armaturenbretter mit lederähnlicher Oberflächenstruktur gefertigt werden. Die Fertigung besteht im wesentlichen aus 8 Arbeitsfolgen; diese entsprechen grob den Kapazitäts-Gruppen. Die Arbeitsfolgen lassen sich in Modellbau, Modellvorbereitung, Galvanik sowie Endmontage und Versand gliedern.
Die meiste Arbeit ist manueller Natur. Da dazwischen sehr viel technologisch bedingte Liegezeit anfällt, gibt es einen klaren Unterschied zwischen Durchlaufzeit und Bearbeitungszeit (= Arbeitsinhalt). Damit liegen in einer Bearbeitungsstation viele parallele Arbeiten gleichzeitig.
Die ca. 90 Personen in der Fertigung werden von 3 Disponenten geplant. Es wird i.a. wochenweise geplant, d.h. Donnerstag mittag ist der Plan für die kommende Woche fertig. Die Werker arbeiten nach einem festen Schichtmodell, aus dem sich auch die Überstunden ergeben.

Im laufenden Betrieb werden ca. 350 – 400 Aufträge bearbeitet; ein Auftrag läuft zwischen 20 und 40 Wochen. Auf Basis von Microsoft Excel wurde eine graphische Plantafel mit hohem Detaillierungsgrad und einigen Besonderheiten realisiert. Darin wird i.w. in der Auftragssicht gearbeitet. Die Farbe der Balken in der Auftragssicht entspricht nicht dem Bearbeitungszustand, sondern der Kapazitätsgruppe. Je Auftrag gibt es drei "Planungslinien": Eine ursprüngliche Planungslinie (= Kundenwunschtermin), das aktuelle Soll (= feingeplant) und das aktuelle Ist.

Es gibt zwei Arten spezieller Restriktionen:

1. Die Komplexität von Tätigkeiten: kleine, mittlere und große Bauteile können normal, schwierig oder extrem sein. An einem Tag soll ein Werker nicht nur extreme oder große Teile bearbeiten, da das physisch zu anstrengend wäre.
2. Bestimmte Tätigkeiten können in einer Gruppe nur von einem Teil des Personals ausgeführt werden. Gleichzeitig sollen nicht die einzelnen Personen geplant werden, sondern nur summarisch die Gruppen.

Im Januar 1999 wird in einem ersten Prototyp bei Fa. G präsentiert werden, wie sich die dortigen Anforderungen mit WIZARD realisieren lassen.

Fa. P1 besteht aus einer zentralen Dispositionsabteilung in Frankfurt am Main sowie mehr als zehn dezentralen Fertigungsstätten in ganz Deutschland, die kundenbezogene Drucksachen herstellen, verpacken und versenden. "Dem Kunden wird eine neue Form der Einlieferung und Bearbeitung seiner Post angeboten, die elektronische Einlieferung und die Übernahme des Druckens und Kuvertierens. Die Sendungen werden durch Fa. P1 nach den Vorgaben des Kunden produziert und so empfängernah wie möglich gedruckt, kuvertiert und dem Briefdienst zur Zustellung übergeben." [Pflicht 1998]

Bei P1 existieren also zwei Zuordnungsprobleme:

1. Es muß entschieden werden, welcher der dezentralen Fertigungsstandorte einen Auftrag durchführen kann. Dabei sind die wichtigsten Restriktionen die geographische Nähe zum Kunden, festgestellt anhand der Postleitzahl, die freien Kapazitäten an den Standorten und die jeweils von einem Auftrag benötigte bzw. an einem Standort vorhandene Technologie (Farb-Druck, mehrseitiger Druck, Beilagen, Papierformate etc.).
   Für dieses Zuordnungsproblem eignen sich die Daten- und Wissensstrukturen von WIZARD nur eingeschränkt. Mit der zugrundeliegenden Zuordnungsshell COKE, auf der WIZARD basiert, wäre eine Realisierung allerdings ohne allzu großen Aufwand möglich.
2. Die einzelnen Produktionsstandorte sind als herkömmliche streng kundenauftragsorientierte Fertigungen zu modellieren, ähnlich wie HKM. Der wichtigste Unterschied besteht in einem speziellen Typ von Aufträgen, den sog. Grundlastaufträgen: "Unter einem Grundlastauftrag ist ein Auftrag zu verstehen, der einen Produktionszeitraum größer als einen Tag hat (in der Regel [...] 1–4 Wochen). Die Gesamtmenge des Auftrags soll dann gleichmäßig auf alle Produktionstage verteilt werden." In der Literatur wird eine solche Planung als "preemptive scheduling" bezeichnet, d.h. ein langer Arbeitsschritt (hier z.B. Drucken einer sehr großen Anzahl) kann durch einen kürzeren unterbrochen werden. Nach Abschluß des kürzeren wird der lange einfach fortgesetzt.
   Dieses Planungsproblem paßt mit einer Erweiterung sehr gut zu WIZARD: Zu jeder Operation ist nicht nur ein Starttermin zu vergeben, sondern mehrere. So kann eine ununterbrochene Ausführung mit einem Starttermin belegt werden; die Fortsetzung nach Unterbrechung bekommt dann den nächsten Starttermin und so weiter. Dadurch wird das Aufsplitten einer Operation in mehrere vermieden werden, die das Umplanen (neuerliches Aufteilen eines mehrtägigen Blocks oder Zusammenfassen einer Folge kurzer Blöcke) erheblich schwieriger machen würde.

Fa. P1 wird sich im Rahmen einer erweiterten Ausschreibung im Laufe des Jahres 1999 entscheiden, ob ein Einsatz von WIZARD erwünscht ist.

Fa. P2 in Süddeutschland stellt große, kundenspezifische Fertigungsanlagen her. Eine komplette Neufertigung dauert über ein Jahr; daneben werden große, bis zu 100 Operationen umfassende Aufträge zur Überholung und Modernisierung bestehender Anlagen sowie kürzere Reparatur-Aufträge ausgeführt.

Zwei Besonderheiten machen diesen Anwender interessant:

1. Nur 30–40% der Aufträge haben eine explizite Stückliste; die restlichen werden nach Muster quasi "on the fly" gefertigt. Da beide Auftragstypen gemeinsam bearbeitet werden, ist die Zusammenfassung und Vergröberung von Kapazitätsbedarfen notwendig, damit auch die Aufträge ohne detaillierte Auftragsstrukturen korrekt eingeplant werden können. Hier können die in WIZARD vorbereiteten Aggregierungs- und Detaillierungsfunktionen eingesetzt werden.
2. Die zur Verfügung stehende Arbeitszeit (herkömmlich und in WIZARD als Schichtplan hinterlegt) soll nicht nur ressourcen-, sondern operationsweise festgelegt werden. Damit können spezielle Reparaturaufträge z.B. auch am Wochenende ausgeführt werden, wogegen Routineaufträge, die dieselbe Ressource benötigen, nur in der Routinearbeitszeit eingeplant werden. In WIZARD ist das durch die objektorientierte Struktur ohne weiteres machbar: Eine Operation kann einen eigenen Schichtplan bekommen; ansonsten wird sie nach dem Schichtplan der benötigten Ressourcen eingeplant.

Bei Fa. P2 kommt es vor allem darauf an, ein Planungstool zu haben, das in die restliche Software-Struktur im Hause möglichst gut eingebunden ist. Hier erweist sich also die enge Integration von WIZARD in infor:NT als Vorteil.

Insgesamt kann festgestellt werden, daß WIZARD für eine Vielzahl der in der Praxis auftretenden Probleme mit machbarem Zusatzaufwand Lösungen bieten kann.

Im ausstehenden dritten Jahr des Verbundprojekts INKAD stehen drei Aufgaben im Vordergrund:

1. Erweiterung:
   Die in Kap. 2.2 eingeführten Wissensarten werden implementiert und mit unterschiedlichen Datenbeständen und Einsatzszenarien untersucht. Daraus ergeben sich sowohl allgemeine Erkenntnisse über vorhandenes und notwendiges Wissen als auch quasi vorgefertigte Schablonen für Restriktionen und Vorschläge, die den Anpassungsaufwand bei Einführung bei einem neuen Anwender erheblich verringern werden.
2. Evaluation:
   Das entwickelte System WIZARD wird zuerst beim Projektpartner Hüttenwerke Krupp Mannesmann in Einsatz gehen. Die dort gemachten Erfahrungen werden direkt in die Weiterentwicklung einfließen. Darüber hinaus wird das System bei weiteren Firmen evaluiert werden, die zum Teil anders gelagerte Probleme haben. Da bereits im Vorfeld während der Entwicklung viele derartige Anforderungen erhoben und beachtet wurden, sind die Aussichten für einen erfolgreichen Einsatz sehr groß.
3. Integration:
   Die bereits begonnene Anbindung an das kommerziell sehr erfolgreiche PPS-System infor:NT wird vorangetrieben. Ziel ist es, die bisherigen, aber veralteten Planungswerkzeuge in infor:NT zu ersetzen. Um dem Benutzer die Arbeit mit dem System so weit zu vereinfachen, wird darauf zu achten sein, die Integration möglichst nahtlos zu gestalten.

Das längerfristige Ziel des Kooperationspartners infor AG ist die Einführung und Vermarktung von WIZARD als Standardmodul von infor:NT.