Assembly Line Balancing
SALBP-1 — Minimise Workstations / NP-Hard
An automotive assembly line has a fixed cycle time of 40 seconds set by the production rate. 8 tasks with precedence constraints (bolt before weld, wire before cover) must be assigned to workstations so no station exceeds the cycle time. Each unnecessary workstation costs €150,000–€300,000 annually.
Where This Decision Fits
Manufacturing planning chain — the highlighted step is what this page optimizes
The Problem
Assign tasks to the minimum number of workstations respecting precedence and cycle time
Given 8 tasks with known processing times and a precedence DAG (directed acyclic graph) encoding technological ordering constraints, assign every task to exactly one workstation so that: (1) no workstation’s total task time exceeds the cycle time CT, and (2) if task i must precede task j, then i is assigned to an equal or earlier station. The objective is to minimise the number of workstations K. This is the Simple Assembly Line Balancing Problem, Type 1 (SALBP-1), proven NP-hard by Wee & Magazine (1982).
A theoretical lower bound is ⌈Σ ti / CT⌉, the total work content divided by cycle time, rounded up. Heuristic methods often achieve optimal or near-optimal solutions for practical instances.
subject to
Σk xik = 1 ∀ i // each task assigned to exactly one station
Σi ti · xik ≤ CT ∀ k // station capacity (cycle time)
Σk k · xik ≤ Σk k · xjk ∀ (i,j) ∈ E // precedence constraints
xik ∈ {0,1}, K ≥ k · xik ∀ i,k
Where xik = 1 if task i is assigned to station k, ti is the processing time of task i, CT is the cycle time, and E is the set of precedence arcs.
See Integer Programming theoryTry It Yourself
Balance an assembly line to minimise workstations
Assembly Line Balancer
8 Tasks · CT = 40s| Task | Duration (s) | Predecessors |
|---|
Ready. Click “Solve & Compare All Algorithms” to run.
| Algorithm | Stations | Efficiency % | Idle (s) |
|---|---|---|---|
| Click Solve & Compare All Algorithms | |||
The Algorithms
Three heuristic approaches to SALBP-1
Largest Candidate Rule (LCR)
O(n²) | Greedy by task timeSort all tasks in descending order of processing time. Open the first workstation. Scan the sorted list and assign the largest feasible task (one whose predecessors are all assigned and whose addition does not exceed the cycle time) to the current station. When no feasible task fits, open a new station and repeat. Simple to implement and often effective when task times are diverse.
Ranked Positional Weight (RPW)
O(n²) | Helgeson & Birnie (1961)Compute each task’s positional weight as the sum of its own processing time plus the processing times of all tasks that transitively follow it in the precedence graph. Sort tasks in descending positional weight. Assign tasks to stations in this order using the same feasibility check. RPW naturally respects precedence topology and is widely used in industry for its balance between solution quality and simplicity.
Kilbridge & Wester (Column Method)
O(n²) | Kilbridge & Wester (1961)Partition tasks into columns (levels) based on their precedence depth: column 0 contains tasks with no predecessors, column 1 contains tasks whose predecessors are all in column 0, and so on. Within each column, sort tasks by descending processing time. Assign tasks column by column to the current station as long as the cycle time allows. This method preserves the natural ordering of the DAG and tends to produce well-structured balanced solutions.
Real-World Complexity
Why practical line balancing goes beyond the basic SALBP-1 model
Beyond Simple Balancing
- Mixed-model lines — Multiple product variants on the same line require model-sequencing decisions interleaved with balancing
- Parallel stations — Bottleneck tasks exceeding cycle time can be duplicated across parallel workstations (SALBP-E / GALBP)
- Ergonomic constraints — Workers cannot perform consecutive heavy-load tasks; fatigue and posture limits must be modelled
- Zoning restrictions — Some tasks require specific equipment or must not share a station with incompatible tasks
- Stochastic task times — Real processing times vary; probabilistic or robust balancing accounts for variability
- U-shaped lines — Workers can reach both sides of a U-line, enabling cross-station task sharing
- Reconfigurable systems — Dynamic rebalancing when production mix or takt time changes seasonally
Key References
Foundational works in assembly line balancing
- (2006). “State-of-the-art exact and heuristic solution procedures for simple assembly line balancing.” European Journal of Operational Research, 168(3), 666–693.
- (1961). “Assembly line balancing using the ranked positional weight technique.” Journal of Industrial Engineering, 12(6), 394–398.
- (1961). “A heuristic method of assembly line balancing.” Journal of Industrial Engineering, 12(4), 292–298.
Need to optimize your manufacturing operations?
From assembly line balancing to production scheduling and facility layout, mathematical modeling can transform manufacturing efficiency. Let’s discuss how Operations Research can work for you.