[go: up one dir, main page]
Skip to main content
SpringerLink
Log in

The assembly line balancing and scheduling problem with sequence-dependent setup times: problem extension, model formulation and efficient heuristics

  • Regular Article
  • Published:
OR Spectrum Aims and scope Submit manuscript

Abstract

Assembly line balancing problems (ALBP) consist of distributing the total workload for manufacturing any unit of the products to be assembled among the work stations along a manufacturing line as used in the automotive or the electronics industries. Usually, theory assumes that, within each station, tasks can be executed in an arbitrary precedence-feasible sequence without changing station times. In practice, however, the task sequence may influence the station time considerably as sequence-dependent setups (e.g., walking distances, tool changes) have to be considered. Including this aspect leads to a joint balancing and scheduling problem, which we call SUALBSP (setup assembly line balancing and scheduling problem). In this paper, we modify the problem by modeling setups more realistically, give a new, more compact mathematical model formulation and develop effective heuristic solution procedures. Computational experiments based on existing and new data sets indicate that the new procedures outperform formerly proposed heuristics. They are able to solve problem instances of real-world size with small deviations from optimality in computation times short enough to be accepted in real-world decision support systems.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  • Allahverdi A, Ng C, Cheng T, Kovalyov M (2008) A survey of scheduling problems with setup times or costs. Eur J Oper Res 187(3): 985–1032

    Article  Google Scholar 

  • Andrés C, Miralles C, Pastor R (2008) Balancing and scheduling tasks in assembly lines with sequence-dependent setup times. Eur J Oper Res 187(3): 1212–1223

    Article  Google Scholar 

  • Arcus A (1966) A computer method of sequencing operations for assembly lines. Int J Prod Res 4: 259–277

    Article  Google Scholar 

  • Barnes R (1959) Motion and time study. Wiley, New York

    Google Scholar 

  • Bautista J, Pereira J (2002) Ant algorithms for assembly line balancing. Lecture Notes in Computer Science, vol 2463. pp 65–75

  • Baybars I (1986) A survey of exact algorithms for the simple assembly line balancing problem. Manag Sci 32: 909–932

    Article  Google Scholar 

  • Becker C, Scholl A (2006) A survey on problems and methods in generalized assembly line balancing. Eur J Oper Res 168: 694–715

    Article  Google Scholar 

  • Becker C, Scholl A (2009) Balancing assembly lines with variable parallel workplaces: problem definition and effective solution procedure. Eur J Oper Res 199: 359–374

    Article  Google Scholar 

  • Boctor F (1995) A multiple-rule heuristic for assembly line balancing. Eur J Oper Res Soc 46: 62–69

    Google Scholar 

  • Boysen N, Fliedner M (2008) A versatile algorithm for assembly line balancing. Eur J Oper Res 184: 39–55

    Article  Google Scholar 

  • Boysen N, Fliedner M, Scholl A (2007) A classification of assembly line balancing problems. Eur J Oper Res 183: 674–693

    Article  Google Scholar 

  • Boysen N, Scholl A (2009) A general solution framework for component commonality problems. BuR Business Res 2(1): 86–106

    Google Scholar 

  • Dorigo M, Blum C (2005) Ant colony optimization theory: A survey. Theoret Comput Sci 344: 243–278

    Article  Google Scholar 

  • Dorigo M, Stützle T (2003) The ant colony optimization metaheuristic: algorithms, applications, and advances, vol 57. Springer, New York, pp 250–285

  • Easton F, Faaland B, Klastorin T, Schmitt T (1989) Improved network based algorithms for the assembly line balancing problem. Int J Prod Res 27: 1901–1915

    Article  Google Scholar 

  • Erel E, Sarin S (1998) A survey of the assembly line balancing procedures. Prod Plann Control 9: 414–434

    Article  Google Scholar 

  • Helgeson W, Birnie D (1961) Assembly line balancing using the ranked positional weight technique. J Ind Eng 12(6): 394–398

    Google Scholar 

  • Jackson J (1956) A computing procedure for a line balancing problem. Manag Sci 2: 261–271

    Article  Google Scholar 

  • Kanawaty G (1992) Introduction to work study. 4th Int Labour Office, Geneva

    Google Scholar 

  • Klein M (1963) On assembly line balancing. Oper Res 11: 274–281

    Article  Google Scholar 

  • Klein R, Scholl A (1999) Computing lower bounds by destructive improvement—an application to resource-constrained project scheduling. Eur J Oper Res 112: 322–346

    Article  Google Scholar 

  • Little J, Murty K, Sweeney D, Karel C (1963) An algorithm for the traveling salesman problem. Oper Res 11: 972–989

    Article  Google Scholar 

  • Martino L, Pastor R (2010) Heuristic procedures for solving the general assembly line balancing problem with setups. Int J Prod Res 48(6): 1787–1804

    Article  Google Scholar 

  • Miller C, Tucker A, Zemlin R (1960) Integer programming formulation of the traveling salesman problem. J Assoc Comput Mach 7: 326–329

    Article  Google Scholar 

  • Nelder J, Mead R (1965) A simplex method for function minimization. Comput J 7: 308–313

    Article  Google Scholar 

  • Pastor R, Andrés C, Miralles C (2010) Corrigendum to Balancing and scheduling tasks in assembly lines with sequence-dependent setup. Eur J Oper Res 201:336–336 (European J Operational Research 187 (2008) 1212–1223)

    Google Scholar 

  • 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

    Article  Google Scholar 

  • Resende M, RibeiroC(2003) Greedy randomized adaptive search procedures. In: Glover F,Kochenberger G (eds) Handbook of Metaheuristics. Kluwer Academic Publishers, Dordrecht, pp 219–249

    Google Scholar 

  • Scholl A (1999) Balancing and sequencing of assembly lines. 2nd edn. Physica, Heidelberg

    Google Scholar 

  • 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

    Article  Google Scholar 

  • Scholl A, Boysen N, Fliedner M (2008) The sequence-dependent assembly line balancing problem. Oper Res Spectrum 30: 579–609

    Article  Google Scholar 

  • Scholl A, Fliedner M, Boysen N (2010) Absalom: Balancing assembly lines with assignment restrictions. Eur J Oper Res 200(3): 688–701

    Article  Google Scholar 

  • Scholl A, Klein R (1997) Salome: a bidirectional branch and bound procedure for assembly line balancing. INFORMS J on Comput 9: 319–334

    Article  Google Scholar 

  • Scholl A, Klein R (1999) Balancing assembly lines effectively—a computational comparison. Eur J Oper Res 114: 50–58

    Article  Google Scholar 

  • Scholl A, Voß S (1996) Simple assembly line balancing—heuristic approaches. J Heuristics 2: 217–244

    Article  Google Scholar 

  • Talbot F, Patterson J, Gehrlein W (1986) A comparative evaluation of heuristic line balancing techniques. Manag Sci 32: 430–454

    Article  Google Scholar 

  • Wilhelm W (1999) A column-generation approach for the assembly system design problem with tool changes. Int J Flexible Manuf Syst 11(2): 177–205

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Chair of Management Science, Friedrich-Schiller-University of Jena, Carl-Zeiß-Straße 3, 07743, Jena, Germany

    Armin Scholl

  2. Chair of Operations Management, Friedrich-Schiller-University of Jena, Carl-Zeiß-Straße 3, 07743, Jena, Germany

    Nils Boysen & Malte Fliedner

Authors
  1. Armin Scholl
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Nils Boysen
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Malte Fliedner
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Armin Scholl.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Scholl, A., Boysen, N. & Fliedner, M. The assembly line balancing and scheduling problem with sequence-dependent setup times: problem extension, model formulation and efficient heuristics. OR Spectrum 35, 291–320 (2013). https://doi.org/10.1007/s00291-011-0265-0

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00291-011-0265-0

Keywords

Search

Navigation