Optimal sequential operation interleaving

Question

0.00/5 (No votes)

See more:

Hi all,

This isn't homework, just an illustrative example of the sort of problem I'm trying to solve:

Suppose I had a number of pots that I wanted to paint different multi-coloured designs on, and each design involves different colours that have to be painted on in the right sequence. Some designs involve the same colour twice but because of the way the colours overlap, you can't do them both at the same time, you have to maintain the order the colours are painted on.

I am looking for an algorithm to interleave the painting operations for a number of pots so that I have to wash the brush out the least number of times, i.e. so that there are the least number of colour changes from first operation to last.

Is there a standard way to do this? I've got an aging home-grown implementation that I'm updating and I'm sure it's been done before, and better!

Posted 23-Apr-12 6:14am

hairy_hats

Add a Solution

1 solution

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

CPallini · Answer 1 · 2012-04-23T07:07:00

Solution 1

You may try the Simulated Annealing[^] algorithm, it is relatively simple to implement.

Posted 23-Apr-12 7:07am

CPallini

Comments

hairy_hats 23-Apr-12 13:57pm

I used SA during my PhD - I was hoping for something more deterministic.

CPallini 23-Apr-12 14:02pm

There's nothing more deterministic then randomness :-D.
Well, you probably know more than me about optimization algorithms, so I'm useless.
:-)

hairy_hats 23-Apr-12 14:19pm

You're definitely not that! Thanks anyway. :)

CPallini 26-Apr-12 9:48am

Did you already see this?
http://en.wikipedia.org/wiki/Register_allocation