A Survey of Exact Algorithms for the Simple Assembly Line Balancing Problem

TLDR

The simple assembly line balancing problem (SALBP) is a deterministic, exact optimization model that excludes mixed‑model, subassembly, and zoning constraints. This survey reviews the evolution of SALBP, presenting alternative 0‑1 and general integer programming formulations, related problems, and a comprehensive overview of exact solution methods and computational results. The authors limit their discussion to exact algorithms for the deterministic SALBP, omitting heuristic approaches and methods for the general or stochastic assembly line balancing problems.

Abstract

In this survey paper we discuss the development of the simple assembly line balancing problem (SALBP); modifications and generalizations over time; present alternate 0-1 programming formulations and a general integer programming formulation of the problem; discuss other well-known problems related to SALBP; describe and comment on a number of exact (i.e., optimum-seeking) methods; and present a summary of the reported computational experiences. All models discussed here are deterministic (i.e., all input parameters are assumed to be known with certainty) and all the algorithms discussed are exact. The problem is termed “simple” in the sense that no “mixed-models,” “subassembly lines,” “zoning restrictions,” etc. are considered. Due to the richness of the literature, we exclude from discussion here (a) the inexact (i.e., heuristic/approximate) algorithms for SALPB and (b) the algorithms for the general assembly line balancing problem (including the stochastic models).