> ') ;?> ') ;?> '); ?>

Ein Färbungsproblem aus der Automobilproduktion

Bei der Bestellung eines neuen Automobils haben Kunden die Wahl zwischen einer Vielzahl von Ausstattungsmerkmalen (Sonnendach, 3 oder 5 Türen, etc.) und Farben. Die europäische Automobilindustrie trägt dem Rechnung, indem verschiedene Modelle nicht - wie z. B. in den Vereinigten Staaten üblich - auf Vorrat, sondern der Nachfrage entsprechend produziert werden. Dies erfordert eine sorgfältige Planung der Produktion; insbesondere hat die Reihenfolge, in der eingehende Bestellungen bearbeitet werden, erheblichen Einfluss auf Qualität und Kosten.

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 $\mathcal{NP}$-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

') ;?> ') ;?> '); ?>