Assembly Line Balancing

Assembly Line Balancing Problem (ALBP) is the operations-research problem of assigning N indivisible elementary tasks to the stations of a serial assembly line so that the workload of each station does not exceed the cycle time (takt) and the precedence relations between tasks (i must precede j) are respected. Its simple form, the Simple Assembly Line Balancing Problem (SALBP), comes in two main variants: SALBP-1 (takt given, minimise station count) and SALBP-2 (station count given, minimise takt). The canonical MIP formulation is by Salveson (1955); the comprehensive survey is Scholl and Becker (2006). The generalised form GALBP covers parallel workers, U-shaped lines, mixed-model production, equipment selection, ergonomic load and zoning — taxonomy in Boysen, Fliedner and Scholl (2007) and Battaia and Dolgui (2013). A common bonus objective is workload smoothness (minimise inter-station workload variance); additional constraint families are same-station obligations, forbidden-pair prohibitions and zoning (tasks confined to a stretch of the line). Solution methods: branch-and-bound (SALOME), full MIP, column generation, priority-rule heuristics (Helgeson-Birnie 1961 ranked positional weight, COMSOAL — Arcus 1966), tabu search and genetic algorithms.