A coloring problem fromthe automobile industry")?> When ordering a new automobile, the customer has the choice between a large variety of features (e.g. sun roof, 3 or 5 doors, etc.) and colors. In contrast to the US automobile industry, European car manufacturers produce cars according to the actual demand. This generates the need for a thoroughly planned production; especially the sequence, in which the orders are treated, has a high impact on quality and cost.
We focus on a subproblem of the production process which occurs in the paint shop, where everyday a sequence of various car bodies has to be painted in the demanded colors. Whenever a color change occurs, the jets of the spray robots have to be cleaned. That gives rise not only to production cost, but also generates water pollution. Consecutively, a minimization of color changes is desirable. Until now, the problem is mainly solved by heuristically methods which use storages for changing and restoring a sequence of car bodies quickly.
Using suitable abstraction, we obtained new theoretical results on the most simplified problem formulation, in which the sequence of car bodies remains unchanged, and the minimization of color changes is achieved by exclusively changing their color sequence. Even this problem is NP-complete both in the case of only two car body types and an arbitrary number of colors and in the case of an arbitrary number of car bodies and only two colors. For the case in which both the number of car bodies and the number of colors are bounded, we developed a dynamic program which solves the problem in polynomial time.
(Literature on this subject.)