Problem statement: The simple assembly line balancing problem (SALBP) is the basic optimization problem in assembly line balancing research. Given is a set of tasks each of which has a deterministic task time. The tasks are partially ordered by precedence relations defining a precedence graph as depicted below.
The paced assembly line consists of a sequence of (work) stations. In each (work-) station a subset of the tasks is performed by a single operator. The resulting station time (sum of the respective task times) must not exceed the cycle time. Concerning the precedence relations, no task is allowed to be executed in an earlier station than any of its predecessors.
Problem versions: The main problem parameters are the cycle time c and the number of stations m. Depending on what is given and what is to be optimized, different versions of SALBP are defined:
- SALBP-F: Given m and c, a precedence- and cycle time-feasible assignment of the tasks to the m stations is requested.
- SALBP-1: Given the cycle time c, the number of stations is minimized. In the picture above, the optimal solution for the SALBP-1 instance with c=66 is given by defining the loads S1 to S5 of m=5 stations.
- SALBP-2: Given the number of stations m, the cycle time is minimized, or equivalently, the production rate is maxmized.
- SALBP-E: Given feasible ranges for m and c, the line effiency is maximized, or equivalenty, the line capacity m*c is minimized.
Data sets and codes: In the subpages, data sets and codes of solution procedures for the different versions of SALBP are provided for download:
- Benchmark Data Sets by Scholl (1993)
- Benchmark Data Sets by Otto et al. (2013)
- SALOME – Branch & Bound for SALBP
- BBR- Branch & Bound & Remember for SALBP-1
Baybars, I. (1986): A survey of exact algorithms for the simple assembly line balancing problem. Management Science 32, 909-932.
Scholl, A. (1999): Balancing and sequencing of assembly lines. 2nd ed., Physica, Heidelberg.