Is this a known combinatorial optimization/scheduling problem?

Question

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.

Answer 1

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]$ ".

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

Answer 2

The optimization problems seems to be equivalent to shortest common supersequence as well. The two results I found related to approximating this problem (it is NP-hard in general) are this and this. There are some inapproximability results and much weaker approximation results it seems. The first paper shows $\Omega(\log^\delta n)$ hardness of approximation and a polynomial factor approximation.

Here is a simple fact (I will use your terminology instead of the shortest common supersequence terminology): if there are $k$ colors, then the greedy algorithm (take the items from the color class that has the most available balls) is a $k$ approximation. Say at some step of the optimal we take a set $X$ of $|X| = x$ items, and consider the time step in the algorithm when we first took items from $X$. At that time step in the algorithm there were at least $x$ nonempty stacks (since not all $x$ items from $X$ are taken yet) and by averaging the algorithm took at least $x/k$ items. So the problem has a polytime dynamic programming solution when there are constantly many stacks, and a constant greedy approximation when there are constantly many color classes.