Manufacturing

Assembly line balancing

Manufacturers of vehicles, aircraft, household appliances, and consumer electronics end production the same way. They assemble the product from parts made earlier, and they do that work on an assembly line. Each item being assembled on the line is called a workpiece. Every workpiece moves through a series of stations. Each station performs its own set of tasks on that workpiece within a fixed time limit, called the cycle time. A planner assigns every task to a station. A line may build several products, follow a U-shaped layout, or put more than one worker at a station. Some lines use robots, and task times may vary. Each difference changes how the work can be split among stations, so each one defines a variant of the assembly line balancing problem.

View Markdown

The problem

The most basic variant is the simple assembly line balancing problem (SALBP), which looks for a plan that assigns every task to a station. SALBP rests on the following simplifying assumptions:

The stations form one straight line, and every workpiece passes through each station once.
Each station has one worker. All stations have the same equipment. Workers have the same skills and take the same time to perform a given task.
The line moves at a fixed pace, so every station has the same cycle time.
The line builds one product, so every workpiece needs the same tasks.
The way each task is performed is fixed in advance. The model does not choose between alternatives such as manual and automated work.
Some tasks must finish before other tasks start. Such a rule is a precedence relation. For example, the rubber seal must be fitted before the sunroof, so the sunroof cannot go to an earlier station than the rubber seal.
Every task time is fixed. It does not vary from one workpiece to the next.
A task cannot be split across stations.
Apart from the cycle time and the precedence relations, no rule limits which station a task can go to. For example, no task is tied to one particular station.

Type 1 and type 2

Type 1 (SALBP-1) minimizes the number of stations for a fixed cycle time. It is the right type when the plant knows the output the line must reach. This page covers type 1.
Type 2 (SALBP-2) minimizes the cycle time for a fixed number of stations. It is the right type when the stations already exist and the plant wants more output from them.

Why minimize the number of stations?

Fewer stations can reduce the resources the line needs, such as floor space, equipment, and staffing. They also reduce the line’s total idle time per cycle.

The cycle time is the time each station has to perform its tasks on one workpiece. It is not the time a workpiece takes to pass through the whole line. Idle time is the part of the cycle time that a station’s tasks do not fill. Across all stations, the total idle time per cycle is:

$total idle time$ $= number of stations \times cycle time$ $- \sum task times$

Here, Σ task times is the sum of all task times. The task times and the cycle time are fixed, so only the number of stations can change the total idle time.

The model boundary

The model decides only which station does each task. It takes the cycle time as given, so it does not choose the production rate. It takes the tasks and their precedence relations as given, so it does not change how the product is assembled. The order of the work inside a station, the conveyor, the supply of parts to each station, and any buffer between stations all stay outside the model.

The model does not consider how the idle time is spread across the stations. Even with the fewest possible stations, one station can sit almost empty while the others are full. A secondary objective can spread the idle time more evenly without adding a station. Adding this objective defines another variant of the problem.

In practice, the result is likely to be a starting point for the planners, not the final plan. Planners know things about the line that are hard to write as constraints, and they adjust the result by hand. Boysen, Schulze, and Scholl (2022) (opens in a new tab) reported this from their work with a large German car manufacturer.

Where the data comes from

The tasks and task times come from industrial engineers. The engineers divide the total work into tasks and estimate each task time with a predetermined motion time system, such as Methods-Time Measurement (MTM). Such a system splits a task into basic motions, such as lifting and gripping, and gives each motion a set time. The task time is the sum of these motion times. These systems are widely used in industry.
Planners collect the precedence relations from expert interviews and from computer-aided design (CAD) data.
The cycle time equals the available production time divided by the number of workpieces that the line must complete in that time.

The collected data can be as simple as one spreadsheet or CSV file, but collecting reliable data can take more work than solving the model. Boysen, Schulze, and Scholl (2022) (opens in a new tab) report this from the same project at the German car manufacturer. In that project, the precedence relations were the hardest input to collect.

A small worked example

This example was authored for this page, with seven tasks totaling 30 time units. The cycle time is 10 time units. The table below lists each task’s processing time and the tasks that must finish before it.

Tasks on the line
Task	Time	Tasks that must finish first
1	6	None
2	3	1
3	5	2
4	1	None
5	9	4
6	4	5
7	2	3, 6

Input: seven_task_line.json (opens in a new tab)

Optimal line balance

CP-SAT found the line balance below through the OpenConstraint Model Context Protocol (MCP) server. It uses three stations, the proven minimum. Like a processor pipeline, the line works on different workpieces at different stages at the same time. Each workpiece moves to the next station every cycle, with its tasks performed in precedence order. Follow the same color and letter across the diagram to track one workpiece.

Each numbered block is a task. The same color and letter identify the same workpiece.

Cycle 1Cycle 2Cycle 3Cycle 4Station 1A45B45C45D45Station 2A16B16C16Station 3A237B237

010203040

Time (units)

ABCDWorkpieces in the order they enter the line
Idle time no task fills this part of the cycle
Empty station no workpiece has reached it yet

Stations in the optimal line balance
Station	Tasks	Load
1	4, 5	10
2	1, 6	10
3	2, 3, 7	10
Total		30

A non-optimal line balance

An intuitive plan can meet every constraint but still use an unnecessary station. On a real line, that extra station can mean more equipment, more floor space, and more paid labor hours for the same output.

Each numbered block is a task. The same color and letter identify the same workpiece.

Cycle 1Cycle 2Cycle 3Cycle 4Station 1A124B124C124D124Station 2A5B5C5Station 3A36B36Station 4A7

010203040

Time (units)

ABCDWorkpieces in the order they enter the line
Idle time no task fills this part of the cycle
Empty station no workpiece has reached it yet

Stations in the rule’s line balance
Station	Tasks	Load	Idle time
1	1, 2, 4	10	0
2	5	9	1
3	3, 6	9	1
4	7	2	8
Total		30	10

The CP model

The Python excerpts below show the core of the constraint programming (CP) model. The model uses OR-Tools CP-SAT. The excerpts use the script’s default settings and leave out its code comments.

Assigning each task to a station

Each task variable in station_of has an integer domain from 1 to max_stations. When use_station_window is enabled, the model uses a precomputed earliest station for each task as its lower bound, capped at max_stations. This earliest station is calculated by dividing the total processing time of the task and all its predecessors by cycle_time, rounding up to the nearest integer, and taking at least 1.

The value of station_of[i] is the station number assigned to task i. The initial [model.new_constant(-888)] adds a dummy entry at index 0, so task IDs starting at 1 can be used directly as list indices.

num_stations is the number of stations to minimize. It also cannot exceed max_stations.

num_stations: cp_model.IntVar = model.new_int_var(1, max_stations, "m")
station_of: list[cp_model.IntVar] = [model.new_constant(-888)] + [
    model.new_int_var(
        min(precomputed.earliest_station[task], max_stations) if use_station_window else 1,
        max_stations,
        f"x_{task}",
    )
    for task in task_ids
]

model.py — solve(), lines 278–289

Keeping each station within the cycle time

Each station’s load is the total time of the tasks assigned to it. That load must not exceed the cycle time. For each station and each task, is_on is 1 exactly when the task is assigned to that station, and 0 otherwise. The weighted sum adds the times of the tasks whose is_on is 1.

for station in range(1, max_stations + 1):
    on_this_station: list[cp_model.IntVar] = []
    for task in task_ids:
        is_on: cp_model.IntVar = model.new_bool_var(f"on_{task}_{station}")
        model.add(station_of[task] == station).only_enforce_if(is_on)
        model.add(station_of[task] != station).only_enforce_if(~is_on)
        on_this_station.append(is_on)
    model.add(cp_model.LinearExpr.weighted_sum(on_this_station, times[1:]) <= cycle_time)

model.py — solve(), lines 291–300

Respecting precedence relations

A precedence relation stops a task from going to an earlier station than a task that must finish before it. gap makes this rule stricter: it is the minimum distance, in stations, from the earlier task to the later one. Tasks 1 → 2 → 3 take 14 time units in total. Dividing by the cycle time gives 14 / 10 = 1.4, so they need at least two stations. Task 3 must therefore be at least one station after task 1: gap = 1. Each neighboring pair fits on one station, so its minimum gap is 0. station_gaps calculates the minimum gap for every pair of tasks connected by precedence, including tasks with other tasks between them.

for (before, after), gap in station_gaps(instance, precomputed).items():
    model.add(station_of[before] + gap <= station_of[after])

model.py — solve(), lines 313–315

Minimizing the number of stations

The model adds station_of[task] <= num_stations only for tasks with no successors. All other tasks are already kept within this limit by the precedence constraints, so they do not need the same constraint again.

for task in task_ids:
    if not precomputed.all_successors[task]:
        model.add(station_of[task] <= num_stations)

model.py — solve(), lines 302–305

total_work_bound(instance) divides the total task time by cycle_time and rounds up; num_stations cannot be smaller than this bound. minimize asks the solver for the fewest stations.

if formulation == "full_work_bound":
    model.add(num_stations >= total_work_bound(instance))

model.minimize(num_stations)

model.py — solve(), lines 321–324

How the result is checked

An independent checker verifies the returned line balance against the input data. It checks that every task is assigned to exactly one station, each station’s load stays within the cycle time, no task is assigned to an earlier station than any of its predecessors, and the reported objective matches the station count. These checks cannot establish whether the encoded rules match the real line. The solver’s “optimal” status confirms that the line balance uses the fewest possible stations for the given model and input data. The checker does not search for a line balance with fewer stations. It also accepts the non-optimal line balance above.