Abbildung: Schematischer Ablaufplan Latex-Produktionsanlage
Der Ablauf chemischer Produktionsprozesse besteht aus einer großen Anzahl einzelner Schritte, deren Reihenfolge es zu optimieren gilt. Aufgrund der hohen Komplexität dieser Aufgaben existiert bei den praktisch eingesetzten Lösungen noch ein enormes Einsparungspotential für Verbesserungen mit Hilfe moderner Optimierungsverfahren. Einen Algorithmus für die Optimierung des Ablaufs solcher chemischer Prozesse haben wir exemplarisch an einer Produktionsanlage für Latex-Kunststoffe entwickelt und implementiert.
Gegeben ist eine Menge von Produkten, die bis zu ihrer Fertigstellung in einer Anlage eine Reihe von Bearbeitungsschritten durchlaufen. Eine solche Anlage setzt sich aus verschiedenen Teilen (Komponenten) zusammen, in denen die einzelnen Produktionsschritte ablaufen. Eine Komponente besteht aus Maschinen, die in Klassen (Maschinentypen) eingeteilt sind. In Komponenten mit mehr als einem Maschinentyp ist für jedes Produkt die Liste der Maschinen gegeben, von denen es weiterverarbeitet werden kann. Von jedem Produkt wird eine Menge hergestellt, die in einzelne Aufträge (Jobs) unterteilt ist. Für jeden Job sind die Zeiten der zugehörigen Bearbeitungsschritte (Tasks) auf den entsprechenden Komponenten und ihre Maschinenzuordnungen bekannt. Zwischen den Tasks eines Jobs sind durch den Produktionsablauf außerdem zeitliche Abhängigkeiten (Restriktionen) zu beachten. So belegt ein Umfüllvorgang zur gleichen Zeit zwei Maschinen auf unterschiedlichen Komponenten. Weitere Restriktionen können durch Vor- oder Nachbereitungsvorgänge bestimmt sein. Die Komponenten werden bei der Herstellung aller Produkte nacheinander in einer festen Reihenfolge durchlaufen. Ziel der Optimierung ist es, die Aufträge so eng aufeinanderfolgend wie möglich den Maschinen zuzuordnen, um die Summe der Leerzeiten aller Maschinen zu minimieren.
Wir haben ein Enumerationsverfahren zum Intervallscheduling entwickelt, das die beste z.Zt. bekannte Komplexität aufweist. Die äußerste Schale des Verfahrens bildet eine Listenplanung mit Prioritätsregeln. Nach der Initialisierung existiert eine Liste aller einzuplanenden Jobs (freie Jobs) sowie eine anfänglich leere Liste bereits verplanter Jobs. Freie Jobs werden sukzessive verplant, wobei zunächst nur die Anfangszeiten festgelegt werden. Bei der Festlegung eines Jobs werden für jeden noch verbleibenden freien Job die Zeiten bestimmt, zu denen die entsprechenden Tasks frühestmöglich beginnen können. Diese Zeiten werden bei der Auswahl des jeweils als nächstes zu verplanenden Jobs berücksichtigt.
Das Scheduling-Problem wird auf den verschiedenen Ebenen mit unterschiedlichen Ansätzen gelöst. Auf Komponentenebene handelt es sich um einen Enumerationsansatz, der bei Anlagen mit einem begrenzten Maschinenpark sinnvoll ist. Das Verfahren ist in diesem Punkt optimal. Ein solcher Ansatz ist auf Anlagenebene nur bei einer kleinen Anzahl von Jobs praktikabel, da man hierzu alle möglichen Anordnungen von Jobs betrachten muß. Bei Anlagen, bei denen der Großteil des Einsparungspotentials in der optimalen Belegung einzelner Komponenten liegt, die Engpässe im Produktionsprozeß darstellen, ist dies aber gar nicht vonnöten. Deshalb haben wir hier eine Greedy-Heuristik gewählt, die Ergebnisse liefert, die beweisbar relativ nah am Optimum liegen.
Das Modell wurde in einer Unix-Umgebung implementiert, die zugehörigen Programme sind in Form einer Bibliothek verfügbar.