This might interest some of you. I have this table of 44 colors of a product. While the base product materials are the same, the dyes have different chemical compositions -- and some can be run right after the other in a mixer, some can't. The table looks something like this:

                (Next Batch)
(In Mixer)  White   Blue   Green   Orange   Black
White         X       X      X        X       X
Blue                  X                       X
Green                 X      X        X
Orange                                X       X
Black                                         X
...etc.

Where there's an 'X', the mixer can go from the color in the mixture to the next batch. Where there's a blank, the mixer has to be completely cleaned out (the process of about an hour).

So I'm writing an application that takes a subset of these colors (whatever the customers have ordered and needs to be made that day) and tries to find the run with the fewest cleanouts possible.

What I've come up with so far (and works for small numbers of colors) is a brute-force algorithm that tries every product in every order and returns the shortest list. E.g. For White, Blue, and Green, the program returns "White, Blue, <Cleanout>, Green". The only problem with this is that the algorithm is N!. The execution time for 8 colors is less than a second. 9 colors takes about 6 seconds. 10 takes almost a full minute (10! = 3,628,800 combinations to check). 11 colors is almost 12 minutes....you can see where this is going.

There's gotta be a mathematical model for this somewhere and a better algorithm, but I'm not sure what it's called. Has anybody seen a problem like this before?