In vielen Fällen ist die Auftragsreihenfolge ein wesentlicher Faktor, um die Kapazitäten der Anlagen auszuschöpfen und die Lieferzeitpunkte einzuhalten, Allerdings sind die Kombinationsmöglichkeiten zur Reihenfolgenbildung oft so hoch, dass selbst schnelle Computer die optimale Reihenfolge nicht in sinnvoller Zeit berechnen können.

Hier setzen wir das heuristische Verfahren ACO (Ant Colony Optimization) ein, das bei der Reihenfolgenbildung schneller als andere Verfahren (z.B. genetische Algorithmen) ist.

Was ist ACO?

ACO ist ein Beispiel für Schwarmintelligenz.  Die Ameisen finden schnell einen kurzen Weg zwischen Futterquelle und Nest, indem sie Pheromon (Duftstoffe) abgeben und der stärksten Spur folgen. Sie machen das natürlich nicht bewusst, ihre Schwarmintelligenz hat sich evolutionär entwickelt. 

Dieses effiziente Verhalten natürlicher Ameisen wird auf auf einen Algorithmus übertragen. Mit dem Verfahren kann z.B. das Routingproblem "Travelling salesman problem TSP" ("finde die kürzeste Route durch n Städte") bearbeitet werden, das auf konventionellem Weg nicht in sinnvoller Zeit berechnet werden kann. Solche Probleme heißen NP-hart.

Eine ausführliche Präsentation finden Sie im Video
"Auftragssteuerung durch den Ameisenalgorithmus".

Routenplanung:

Falls Sie Routen- und Transportaufgaben mit mehr als zehn Anlaufpunkten haben - wir entwickeln ein Optimierungsprogramm, welches nicht nur die Strecke, sondern auch andere Parameter wie Wert der Lieferung, Lieferzeitpunkt usw. berücksichtigt.

Durch diese Ermittlung wird auch die Beladungsreihenfolge von LKW oder Waggon festgelegt und optimiert.

ACO in der Fertigungssteuerung:

Das Problem der Einsteuerung ist wie das TSP eine Reihenfolgeoptimierung, wobei die zu minimierenden Parameter Verspätung und Rüstzeit (und andere gewünschte Prioritäten) sind.

Reihenfolgeoptimierung:

Mit ACO können außerdem beliebige Reihenfolgeprobleme behandelt werden, sei es in der Personalplanung (möglichst effektiver Einsatz der Mitarbeiter unter Berücksichtigung von Qualifikation, Schichtmodellen, Pausenzeiten etc.) oder bei der Beladungsreihenfolge von Transportmitteln (unter Berücksichtigung von Wert, Volumen und Entladereihenfolge) u.s.w.

Realisierung:

Bisher gelöst und realisiert ist das "Single machine total tardiness problem" (SMTTP). Es beinhaltet die Minimierung der Verspätungen vor einer Einzelmaschine unter gleichzeitiger Minimierung der Rüstzeit. Dieses lässt sich auch in Kostenstellen einsetzen, in welchen die Aufträge nacheinander mehrere Maschinengruppen durchlaufen und die Durchläufe nicht notwendig gleich sind. Realisiert und installiert wurde dieses Programmpaket bisher bei der Firma ebm-papst in St. Georgen. Mehr dazu finden Sie unter "Projekte.Fertigungssteuerung".

Ausblick:

Derzeit wird bei uns am "Parallel machines total tardiness problem mit ACO" (PMTTP) geforscht und die Entwicklung ist bereits weit fortgeschritten. Mit .PMTTP ist die Aufgabe beschrieben, wie man einen Pool von Aufträgen in parallel angeordnete, nicht notwendig gleiche Maschinen einsteuert , um ebenfalls den Servicegrad zu verbessern und die Maschinen besser auszulasten.