Ein einfaches Beispiel für komplexe Optimierung

Als nicht aus der Praxis gegriffenes, dafür aber hoffentlich instruktives Szenarium betrachten wir die Fertigung von übergroßen Schachfiguren aus massiven Holzrohlingen. An diesem Beispiel sollen die Begriffe Station, Auftrag, Rüstoperation, Rüstzeit und Rüstkosten illustriert werden. Die Rohlinge durchlaufen verschiedene Stationen (Drechselbank, Fräse, Lackierkabine ) mit mehr oder weniger restriktiv vorgegebener Reihenfolge.

Allen Figuren gemeinsam sind die folgenden Fertigungssschritte:

Fertigungsschritt Bearbeitungsstation Dauer
ABD: Abdrehen des Rotationsymmetrischen Anteils und Kürzen des Rohlings Drechselbank 30 min
FB: Fräsen einer Ausspahrung und Einsetzen eines Bodengewichtes zur Verbesserung der Standsicherheit Fräse 40 min
LS oder LW : Lackieren in den Farben schwarz oder Weiss Lackierkabine 15 min

Bei nicht rotationsymmetrischen Figuren (z.B dem Springer) sind noch zusätzliche Fräsarbeiten erforderlich. Bei einem Springer umfaßt das einen zusätzlichen Schritt:

Fertigungsschritt Bearbeitungsstation Dauer
KF: Fräsen des Figurenkopfes Fräse 60 min

Beim Bauern ist die Reihenfolge der drei Fertigungsschritte fest vorgegeben, nämlich ABD,FB,FS beim schwarzen, bzw ABD,FB,LW beim weissen Bauern.

Beim Springer ist dagegen nicht zwingend vorgegeben ob zuerst der Figurenkopf oder zuerst die Bodenplatte gefräst werden soll. Zulässige Abfolgen wären hier: ABD,FB,KF,FS und ABD,KF,FB, beim schwarzen, bzw ABD,KF,FB,LW beim weissen Springer.

Trägt man die direkten Vorgänger->Nachfolger Beziehungen in ein Netzdiagramm ein so erhält man für einen wessen Bauern und einen schwarzen Springer folgende Netzwerke:

TaskPrototype weisser Bauer
weisser Bauer
TaskPrototype schwarzer Springer
schwarzer Springer

Ein weiterer, für die Ablaufplanung relevanter Punkt sind Rüstoperationen, das sind Arbeiten, die an den Stationen erledigt werden müssen, bevor ein bestimmter Auftragstyp bearbeitet werden kann. Mit dem Themenkomplex Rüstoperationen verbunden sind die Begriffe Rüstzeiten und Rüstkosten. Rüstzeiten sind die Zeiten während derer eine Station umgerüstet wird, und in denen daher keine Aufträge bearbeit werden können, Rüstkosten sind die Kosten die durch Rüstoperationen entstehen.

In unserem Beispiel muß die Lackierkabine und das Spritzwerkzeug gereinigt und getrocknet werden wenn die Farbe gewechselt wird, was jedesmal 60 min daurt und 60 Euro kostet. Auch an der Fräse fallen solche Arbeiten an, wenn vom Fräsen für Boden--Aussparungen auf das Fräsen eines Springeropfes umgestellt wird. Diese Operation fällt mit 30 Minuten Dauer und 150 Euro Kosten ins Gewicht. ( Bei der Umstellung Figurenkopf fräsen -> Boden--Ausparung sollen derartige Operationen nicht nötig werden).

Wenden wir uns nun einem konkreten Fertigungsproblem zu: Ein schwarzer Bauer (SB), ein weisser Bauer (SW), ein schwarzer Springer (SS) und ein weisser Springer (SW) sollen produziert werden.

Wie kann die Produktion dieser 4 Produkte so organisiert werden dass :

Der folgende Arbeitsplan realisiert wurde mit der eingebauten "Evolution" Optimierung erzeugt. Er realisiert die optimale Lösung für die Zielsetzung minimaler Rüstkosten (50 euro). Dies wird jedoch mit dem Preis einer nicht optimalen Gesamtdurchlaufzeit (698 min) bezahlt.

Will man statt der Reduktion der Rüstkosten die Reduktion der Durchlaufzeiten in den Vordergrund stellen, so stellt man einfach die Gewichtung der Rüstkosten in der Zielfunktion des Evolution Algoritmus anders ein. Gewichtet man die Rüstkosten mit dem Gewicht "0" und die Durchlaufzeit mit dem Gewicht 1 dann erzeugt "Evolution" einen völlig anderen Arbeitsplan:

Dieser Arbeitsplan realisiert eine bessere Gesammtdurchlaufzeit der vier Aufträge (530 min), dies jedoch um den Preis von 6 x höheren Gesamtrüstkosten (300 Euro).

Die obigen Beispiele illustrieren die simple Tatsache, daß eine simultane Optimierung von Durchlaufzeiten und Rüstkosten im Algemeinen nicht möglich ist, und das eine vernünftige Gewichtung dieser Kenngrößen gefunden werden muß. Der Evolution Algoritmus erlaubt es jede Gewichtung der Kenngrößen Gesamtdurchlauftzeit, Gesamtrüstzeit und Gesamtrüstkosten einzustellen und zu optimieren.