Color Sequencing - Programmers Heaven

Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

Categories

Welcome to the new platform of Programmer's Heaven! We apologize for the inconvenience caused, if you visited us from a broken link of the previous version. The main reason to move to a new platform is to provide more effective and collaborative experience to you all. Please feel free to experience the new platform and use its exciting features. Contact us for any issue that you need to get clarified. We are more than happy to help you.

Color Sequencing

Posts: 1Member
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:

[code] (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.[/code]

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, , 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?