Wir beschäftigen uns mit einem Teilproblem des Produktionsprozesses, das in der Lackierstraße (dem paint shop) auftritt, in der täglich eine Sequenz von verschiedenen Karosserietypen in den nachgefragten Farben lackiert wird. Bei jedem Farbwechsel müssen die Farbdüsen der Sprühpistolen gereinigt werden. Dies erhöht einerseits die Produktionskosten, andererseits belasten die überschüssigen Farbreste das Abwasser. Eine Minimierung der Farbwechsel ist also wünschenswert.
Bislang werden dazu heuristische Verfahren eingesetzt. Dabei werden zumeist Farbsortierspeicher benutzt, mit denen die vorgegebene Sequenz von Karosserietypen kurzzeitig abgeändert und anschließend wieder hergestellt werden kann.
Wir konnten durch eine geeignete Abstraktion neue theoretische Aussagen über die einfachste Form des Problems gewinnen, bei der die Reihenfolge der Karosserietypen unverändert gelassen wird und nur durch die Änderung der Farbreihenfolge die Anzahl der Farbwechsel minimiert werden soll. Es zeigte sich, dass bereits dieses Problem sowohl für nur zwei verschiedene Karosserietypen und eine beliebige Anzahl von Farben als auch für nur zwei Farben und eine beliebige Anzahl von Karosserietypen -vollständig ist. Für den Fall, dass sowohl die Anzahl der verschiedenen Karosserietypen als auch die Anzahl der Farben beschränkt ist, konnten wir ein dynamisches Programm angeben, das das Problem in polynomieller Zeit löst.
Kontakt: combopt@zpr.uni-koeln.de