Abstract
Assembly line balancing problems (ALBP) arise whenever an assembly line is configured, redesigned or adjusted. An ALBP consists of distributing the total workload for manufacturing any unit of the products to be assembled among the work stations along the line. The sequence-dependent assembly line balancing problem (SDALBP) is an extension of the standard simple assembly line balancing problem (SALBP) which has significant relevance in real-world assembly line settings. SDALBP extends the basic problem by considering sequence-dependent task times. In this paper, we define this new problem, formulate several versions of a mixed-integer program, adapt solution approaches for SALBP to SDALBP, generate test data and perform some preliminary computational experiments. As a main result, we find that applying SALBP-based search procedures is very effective, whereas modelling and solving the problem with MIP standard software is not recommendable.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Baybars I (1986) A survey of exact algorithms for the simple assembly line balancing problem. Manage Sci 32:909–932
Becker C, Scholl A (2006) A survey on problems and methods in generalized assembly line balancing. Eur J Oper Res 168:694–715
Bockmayr A, Pisaruk N (2001) Solving assembly line balancing problems by combining IP and CP. In: Proceedings of the 6th Annual Workshop of the ERCIM Working Group on Constraints, Prague, Czech Republic
Bowman EH (1960) Assembly-line balancing by linear programming. Oper Res 8:385–389
Boysen N, Fliedner M, Scholl A (2006) A classification of assembly line balancing problems. Eur J Oper Res (in press)
Erel E, Sarin SC (1998) A survey of the assembly line balancing procedures. Prod Plan Control 9:414–434
Ghosh S, Gagnon RJ (1989) A comprehensive literature review and analysis of the design, balancing and scheduling of assembly systems. Int J Prod Res 27:637–670
Hackman ST, Magazine MJ, Wee TS (1989) Fast, effective algorithms for simple assembly line balancing problems. Oper Res 37:916–924
Hoffmann TR (1992) EUREKA: a hybrid system for assembly line balancing. Manage Sci 38:39–47
Johnson RV (1988) Optimally balancing large assembly lines with “FABLE”. Manage Sci 34:240–253
Lübke M (2006) Methoden der Präferenzmessung: Formale Analyse, Vergleich und Weiterentwicklung. Diploma Thesis, University of Jena
Patterson JH, Albracht JJ (1975) Assembly-line balancing: Zero-one programming with Fibonacci search. Oper Res 23:166–172
Peeters M, Degraeve Z (2006) An linear programming based lower bound for the simple assembly line balancing problem. Eur J Oper Res 168:716–731
Pinnoi A, Wilhelm WE (1997) A family of hierarchical models for assembly system design. Int J Prod Res 35:253–280
Rekiek B, Dolgui A, Delchambre A, Bratcu A (2002) State of art of optimization methods for assembly line design. Annu Rev Control 26:163–174
de Reyck B, Herroelen W (1997) Assembly line balancing by resource-constrained project scheduling—A critical appraisal. Found Comput Control Eng 22:143–167
Saltzman MJ, Baybars I (1987) A two-process implicit enumeration algorithm for the simple assembly line balancing problem. Eur J Oper Res 32:118–129
Scholl A (1993) Data of assembly line balancing problems. Schriften zur Quantitativen Betriebswirtschaftslehre 16/93, TU Darmstadt
Scholl A (1999) Balancing and sequencing assembly lines, 2nd edn. Physica, Heidelberg
Scholl A, Becker C (2006) State-of-the-art exact and heuristic solution procedures for simple assembly line balancing. Eur J Oper Res 168:666–693
Scholl A, Klein R (1997) SALOME: A bidirectional branch and bound procedure for assembly line balancing. Inf J Comput 9:319–334
Scholl A, Klein R (1999) Balancing assembly lines effectively—a computational comparison. Eur J Oper Res 114:50–58
Scholl A, Voß S (1996) Simple assembly line balancing—Heuristic approaches. J Heuristics 2:217–244
Sprecher A (1999) A competitive branch-and-bound algorithm for the simple assembly line balancing problem. Int J Prod Res 37:1787–1816
Talbot FB, Patterson JH, Gehrlein WV (1986) A comparative evaluation of heuristic line balancing techniques. Manage Sci 32:430–454
Thangavelu SR, Shetty CM (1971) Assembly line balancing by zero-one integer programming. AIIE Trans 3:61–68
Ugurdag HF, Rachamadugu R, Papachristou CA (1997) Designing paced assembly lines with fixed number of stations. Eur J Oper Res 102:488–501
Wee TS, Magazine MJ (1982) Assembly line balancing as generalized bin packing. Oper Res Lett 1:56–58
White WW (1961) Comments on a paper by Bowman. Oper Res 9:274–276
Williams HP (1999) Model building in mathematical programming, 4th edn. Wiley, New York
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Scholl, A., Boysen, N. & Fliedner, M. The sequence-dependent assembly line balancing problem. OR Spectrum 30, 579–609 (2008). https://doi.org/10.1007/s00291-006-0070-3
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00291-006-0070-3