Optimum placement of zigzag trees in order to minimize the makespan

Question

Suppose we have some trees of the following forms:

We want to place these trees in a linear fashion in a way such that the last node has the minimum distance to the first node. For instance, if we have the following trees:

Then an optimal placement will be like the following:

The minimum distance between the first node and the last node (which could be called "the makespan") is 5.

Note that we can stretch an edge, but we can't make an oblique edge straight or change its direction. The nodes have to be placed in a maximum of two rows (Like the trees themselves).

What would be the optimal placement strategy? We have all the trees upfront (this is an offline problem).

Motivation: I was trying to find an optimal schedule for a jobshop problem with two machines in presence of some form of recirculation. My modeling led to this problem.

Answer 1

The given trees are, in fact, paths. They can be encoded/given as a multiset of pairs $(\ell, \text{direction})$ where $\ell$ is the length of the path and $\text{direction}$ is either $\text{top}$ or $\text{bottom}$ that indicates whether the path should start at the top row or at the bottom row. For instance, the trees in the question are given by $(2,\textrm{top})$, $(2,\text{top})$, $(4,\text{bottom})$, $(3,\text{bottom})$.

Here is a simple greedy algorithm. The idea is to arrange to the top row earlier for the remaining part of a path scheduled for the top row if it has the most nodes not arranged yet. Ditto for the bottom row.

1. $column \leftarrow 0$

2. Initialize two empty priority queues, $top\_queue$ and $bottom\_queue$. A bigger number in the queue has higher priority.
   Insert $\ell$ into $top\_queue$ for all $(\ell, \text{ top})$.
   Insert $\ell$ into $bottom\_queue$ for all $(\ell, \text{ bottom})$.

3. While either $top\_queue$ or $bottom\_queue$ is not empty:

   1. Add $column$ by $1$.
   2. If $top\_queue$ is not empty, pop an element. Let it be $t$.
   3. If $bottom\_queue$ is not empty, pop an element. Let it be $b$.
   4. If $t>1$, insert $t-1$ to $bottom\_queue$.
   5. If $b>1$, insert $b-1$ to $top\_queue$.

   When an element is popped from a queue, imagine the current node of the corresponding path is put onto column $column$. The remaining part of the path, which is $1$ shorter, is then inserted to the other queue.

4. Return $column$, which is the minimum makespan possible.

If we add steps that track the identities of the numbers and the elements popped in order, the algorithm can return the optimum placement as well.