Is this a known combinatorial optimization/scheduling problem? 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.
Your problem is equivalent to Shortest Common Supersequence (SCS) and was considered in $[1]$ by the name Scheduling on batch machines with precedence constraints as chains and compatibilities. If items in the problem are of the same color then such problem is in P and can be solved in $O(n^2)$  $[2]$.

What concerns approximability a good source is A compendium of NP optimization problems.

The lastest results on SCS can be found in $[3,4]$.

For practical algorithms see $[5]$ whose author states that "Hybrid MA-BS is a current state-of-the-art technique for the SCSP $[6]$ ".


Brauner N., Naves G. Scheduling chains of operations on a batching machine with disjoint sets of operation compatibility.
Brucker P. Scheduling algorithms (Chapter 8. Batching Problems).
Timkovsky V. G. Some Approximations for Shortest Common Nonsubsequences and Supersequences.
Gotthilf Z. and Lewenstein M. Improved Approximation Results on the Shortest Common Supersequence Problem.
Kubalik J. Efficient stochastic local search algorithm for solving the shortest common supersequence problem.
Blum, C., Cotta, C., Fernandez, A. J., Gallardo, J. E. A Probabilistic Beam Search Approach to the Shortest Common Supersequence Problem.