1
$\begingroup$

Suppose we have some trees of the following forms:

Zigzag trees

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:

Example

Then an optimal placement will be like the following:

enter image description here

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.

$\endgroup$
3
  • $\begingroup$ What are the constraints on an allowed placement? Are two nodes allowed to overlap/be on top of each other? Can trees be re-ordered into any order, or do they need to respect the original order in some way? Do you require that nodes can only be placed at integer coordinates? What do you mean by "straight"? Do you mean "vertical"? $\endgroup$
    – D.W.
    Jan 27, 2023 at 23:55
  • $\begingroup$ @D.W. The nodes are not allowed to overlap. trees must follow the order they are given. For example, in a tree with one node at bottom, then one node at top, and again one node at bottom (like /), the top node can never precede or even be at the same x position as the first bottom node. It cannot be inverted (like \/). Only integer coordinates are allowed. x coordinate must be in range [0, inf), y can only take 0 or 1. $\endgroup$ Jan 28, 2023 at 9:53
  • $\begingroup$ the first example in parentheses is /\ . I typed it like / in the previous comment by mistake. $\endgroup$ Jan 28, 2023 at 13:02

1 Answer 1

1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.