zbMATH — the first resource for mathematics

A survey of exact algorithms for the simple assembly line balancing problem. (English) Zbl 0601.90081
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).

90B35 Deterministic scheduling theory in operations research
90B30 Production models
90C10 Integer programming
90-02 Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming
90C09 Boolean programming
Full Text: DOI