Assembly line balancing: What does machine precedence mean?

Question

I am looking at the looking at the following classical integer programming model for assembly line balancing:

R.R.Vemuganti's "Applications of Set Covering, Set Packing and Set Partitioning Models: A Survey", in Handbook of Combinatorial Optimization (Vol.1) pp. 573-746.

"Assembly Line Balancing" is section 7.1. There are $n$ tasks to be done on upto $n$ machines (as few as possible) within a time duration $c$.

• The task processing times are $\{t_i | i=1,2,\cdots,n\}$

• The precedence relationships consist of a set of node pairs $P=\{(i,j)\implies \text{ task } i \text{ precedes task } j \}$

• $c$ is the time by which all tasks must be done

Question: What does the following mean? If $(i,j)\in P$ and tasks $i$ and $j$ are assigned to machines $s(i)$ and $s(j)$, respectively, then $s(i)\le s(j)$.

As far as I can see, machine numbers are categorical data whose magnitudes have no meaning.

It looks as if the intent is to have lower numbered machines do tasks that have higher precedence. Wouldn't this rule out sections of the solution space that could contain better solutions? I don't see anything that forces task $i$ to finish before task $j$ just because it is assigned to a lower number machine.

In case it provides missing context, here is the integer program:

• Binary indicator/decision variable $x_{ik}=1$ if task $i$ is assigned to machine $k$, $x_{ik}=0$ otherwise

• Binary indicator/decision variable $y_k=1$ if machine $k$ is used and can therefore have tasks assigned to it, $y_k=0$ otherwise (the objective function minimizes the number of machines used)

• $i=1,2,\cdots,n \quad \text{and} \quad k=1,2,\cdots,n$

Objective function:

\begin{equation} \min \sum_{k=1}^n y_k \end{equation}

such that

\begin{eqnarray} \sum_{k=1}^n x_{ik}=1 & \quad & i=1,2,\cdots,n \\ \sum_{i=1}^n t_i x_{ik} \le c y_k & \quad & k=1,2,\cdots,n \\ \sum_{k=1}^h x_{ik}\ge x_{jh} & \quad & (i,j)\in P \quad \text{and} \quad h=1,2,\cdots,n \end{eqnarray}

The first constraint assigns each task to one machine.

The second constraint assgns tasks only to machines that are being used, and ensures that the total work time on that machine doesn't exceed the limit $c$.

The third constraint enforces precedences between tasks. I can see how it forces the machine number for task $j$ to be no smaller than the machine number for task $i$, but I don't see how this forces task $i$ to finish before task $j$ starts.

---

Elaboration on my points of confusion

The scheduling that I've passingly looked at in decades past consisted of assigning operations to CPUs and deploying assets to different missions. There are precedence relationships, but they depend on the availability of CPUs or assets, not the identity label of each CPU/asset. Since Vemuganti's basic ALB imposes constraints based on station identity, it seems to me (maybe naively) that this unnecessarily constrains the solution space, possibly excluding better solutions than otherwise.

I tried to understand the features of the operational problem that necessitate these constraints. The only one I've seen is fontanf's answer about the serial arrangement of stations. I responded with a comment showing that even if they are arranged serially by station number, the flow of stuff don't necessarily follow that sequence. Instead, the outputs of one station can be sent to the input of any station. This is a lot more like the scheduling I saw in the past, wherein precedences and station numbers are completely unrelated.

That is why I think that I'm missing an assumption. For example is there an unspoken rule that stuff can flow only forward in the sequence of stations, even if they skip stations? Is this due to common real-world limitations in assembly line environments? It seems like a problem feature that is critical to the mathematical modelling. If it is true, then I wonder why it isn't explicit.

Answer 1

The machines are in sequence, not in parallel.

Consider a same product which requires a number of tasks to be built. Some of these tasks have precedence constraints. If there are $m$ stations (machines), then $m$ units of this product are built in parallel, one on each station. On each station, the unit built on this station is at a different level of completion. At the end of the cycle time, each station gives its unit to the next station; the first station starts a new one and the last station finishes one. Thus, the cycle time must be at least the time that requires the station with the longest assigned tasks.

Once two tasks have been assigned to a station, they can be performed in any order on this station, including one that satisfies the precedence constraints.

Note that this is one way to set up an assembly line, and others are possible. Another classical one is the U-line where a unit comes back towards the first station after reaching the last station. This reduces the impact of the precedence constraints. Here is an illustration from this article:

Answer 2

Besides the useful answer of @fontanf, let's say:

If you wanted to try solving the line balancing problem for the first time, I strongly recommended you read some basic concepts and fundamentals of this field which could be easily found by googling. For example, this one.

After that, each assembly line problem might be interpreted as a directed graph in which every node in this graph represents a task and each arc represents the relation between this task with others. This relation is so-called as a precedence constraint. Please, see the following picture:

As you can see there are $57$ tasks that should be processed on the pre-defined resources. As a good example for the multi-tasks precedence relationship, as long as tasks #$22,23,24,...$ will not be processed, task #$8$ is not being processed too.

Now, back to your question: If $(i,j)\in P$ and tasks $i$ and $j$ are assigned to machines $s(i)$ and $s(j)$, respectively, then $s(i) \leq s(j)$, I think $s$ referred as start time of each job on machine $s$ and it obviously clear that by definition of the precedence set, $s(i) \leq s(j)$.

Also, if you are willing to use Mixed-integer linear programming to formulate and solve your problem, as it is a varients of the Resource-Constrained Project Scheduling, this and this links would be very useful.