We are given $n$ stacks which hold "items" of different colour and a machine that can process multiple items of the same colour in one go. At each step, we can remove one item from the top of each stack and put it into our machine (so effectively the machine can process at most $n$ items in one step - for that to happen, all stacks must have items of the same colour on top). The goal is to process all items in minimal time.
Example input:
One possible solution is a greedy algorithm: at each step, just take as much items as possible and stuff them all into the machine. Unfortunately, the greedy algorithm is not optimal - it produces the following schedule for the example input:
The optimal schedule is the following:
I plan to go with some form of state space search, but maybe there is a more problem-specific and efficient approach? Links to relevant literature appreciated.