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.

  • $\begingroup$ Are you aware that in manufacturing, a part often needs to visit machines in a particular sequence? For example, in a car factory, you must first put the wheels on a car (at the wheel installation station) and then check the wheel alignment (at the alignment machine). If a car doesn’t have wheels yet, then it’s not possible to check the wheel alignment. It’s not possible to put wheels on at the alignment machine, either; the wheel installation station is the only station which can do that. $\endgroup$ Commented Feb 19, 2022 at 22:52
  • $\begingroup$ As far as I know, that is taken care of by the precedence relationships. I recently updated my question with an "Elaboration on my points of confusion". Many problems of scheduling operations onto limited resources contain precedence relationships. This is my first problem where the precedence relationships depend on the identity label (station/machine number) of the resource. This dependency is what I'm confused about. Regarding the point that only certain stations can install wheels, Vemuganti does not model task-specific capabilities that are nonuniformly available across all stations. $\endgroup$ Commented Feb 20, 2022 at 0:08
  • $\begingroup$ Actually, I have seen in the past where subsets of the resources have the capabilities for subsets of the tasks, but these were explicit in the problem description. It fundamentally changes the mathematical modelling. It is not part of Vemuganti's description, and not part of his integer programming solution. $\endgroup$ Commented Feb 20, 2022 at 0:10

2 Answers 2


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:

enter image description here

enter image description here

  • $\begingroup$ I'm trying to build up a picture from your description. I went right back to E.H.Bowman's 1960 paper. He has a precedence graph, but the constraints look very different. He doesn't show a layout of the machines, but I was thinking of them as random access; you can take semi-finished product from any machine to any other machine for further work. A sequential layout of machines doesn't seem to make sense because any machine has the functionality to do any task. In your layout, with $m$ machines operating in parallel, why does one machine have to hand off to the next? $\endgroup$ Commented Feb 19, 2022 at 8:43
  • 1
    $\begingroup$ Because it is more efficient to do the a few tasks a lot of times rather than a lot of tasks a few times. And some tasks might require some learning/training, and it wouldn't possible to train everyone for all tasks $\endgroup$
    – fontanf
    Commented Feb 19, 2022 at 10:30
  • $\begingroup$ Interesting. The cost of changing tasks on a machine is not reflected in the objective function. In Vemuganti's next subsection 7.2 (Discrete Lot Sizing and Scheduling), he explicitly states the overhead of changing functions (or at least, changing products) and that such cost is incorporated into the cost and the scheduling of a product onto a machine. $\endgroup$ Commented Feb 19, 2022 at 14:55
  • $\begingroup$ For the assembly line balancing problem here, if the problem admits solutions with few machines and many tasks, there are going to be many tasks per machine anyway, and the overhead will not be reflected in the model. There seem to be many assumptions about the problem that is not reflected in the textual description. $\endgroup$ Commented Feb 19, 2022 at 14:55
  • 1
    $\begingroup$ Yes, it's a fundamental version of the problem. That's how research works in OR: start with the fundamental version of the problem and then add complexity. If you search in the literature, you'll find many variants considering additional aspects of the problem. Real world lot sizing and scheduling problems are also much more complex than the ones presented in the books $\endgroup$
    – fontanf
    Commented Feb 19, 2022 at 15:55

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:

enter image description here

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.

  • $\begingroup$ Thanks, A.Omidi. The idea of precedence is quite familiar to me. I googed assembly-line-balancing before posting. I didn't come across indications of the serial layout of the machines, so fontanf's description of this helps, though in my mind, I'm still trying to square this off with the problem description. The start time of task $i$ must precede task $j$, but that is not the same as the stated constraint that machine $s(i)$ has a lower number than machine $s(j)$ (which is the constraint in the integer program). $\endgroup$ Commented Feb 19, 2022 at 15:54
  • $\begingroup$ A 2nd reason why I thought that $s(\cdot)$ doesn't refer to start time is that we need a tighter constraint: The end time of $i$ must precede the start time of $j$. This automatically happens if machine $s(i)$'s output feeds $s(j)$'s input, i.e., $s(i)+1=s(j)$. But this is not what is stated, nor is it modelled in the integer program. $\endgroup$ Commented Feb 19, 2022 at 15:54
  • 1
    $\begingroup$ @user2153235, about your first comment, the main goal of the line balancing problem is to assign the tasks to the predefined resources (e.g. machines, humans, etc.) in which all of the resources almost have the same cycle time. These models referred to SALBP's models. AFAIK, it is a bit different from how the tasks might be performed on the machines that usually referred to the detailed scheduling problem. In your case, I think what you mentioned in the last sentence goes to a variant of the parallel machine scheduling problem rather than line balancing. Do you try that? $\endgroup$
    – A.Omidi
    Commented Feb 20, 2022 at 5:22
  • 1
    $\begingroup$ @user2153235, for the second and third comments I really do not understand what you are trying to do. I am afraid. Would you say please, what do you mean by $s(0)$ and what is $s(i/j) + 1or2$ meaning? I think you refer to the detailed scheduling problem? Am I right? $\endgroup$
    – A.Omidi
    Commented Feb 20, 2022 at 5:25
  • 1
    $\begingroup$ I also poorly define $c$ as the time by which all tasks must be done. Yes, it is, but not for the same instance of the assembly line's output product. Each station is working on different instance of the same product. With this understanding, it's probably unnecessary to clarify what I mean by $s(i)$, but for completeness, I meant exactly what I describe Vemuganti as saying. It is the number of the machine which is assigned the task $i$. So there is no $s(0)$ or $s(i/j)$. Thank you for pointing me to the terminology which got me the right information. $\endgroup$ Commented Feb 20, 2022 at 7:35

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.