Skip to main content
SpringerLink
Log in

Metaheuristic procedures for the lexicographic bottleneck assembly line balancing problem

  • General Paper
  • Published:
Journal of the Operational Research Society

Abstract

The goal of this work is to develop an improved procedure for the solution of the lexicographic bottleneck variant of the assembly line balancing problem (LB-ALBP). The objective of the LB-ALBP is to minimize the workload of the most heavily loaded workstation, followed by the workload of the second most heavily loaded workstation and so on. This problem—recently introduced to the literature (Pastor, 2011)—has practical relevance to manufacturing facilities. We design, implement and fine-tune GRASP, tabu search (TS) and scatter search (SS) heuristics for the LB-ALBP and show that our procedures are able to obtain solutions of a quality that outperforms previous approaches. We rely on both semi-greedy and memory-based designs that our experiments show to be effective. Experimental results verify the advantages of embedding such designs to improve the solution existing in the literature of this complex problem. Additionally, the extensive experimentation with 48 variants of GRASP, 12 of TS and 1 of SS establishes the benefits of adding enhanced search strategies to basic procedures.

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

Access this article

Log in via an institution

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

Instant access to the full article PDF.

Institutional subscriptions

Figure 1
Figure 2
Figure 3
Figure 4
Figure 5
Figure 6
Figure 7
Figure 8

Similar content being viewed by others

References

  • Adenso-Díaz B and Laguna M (2006). Fine-tuning of algorithms using fractional experimental designs and local search. Operations Research 54 (1): 99–114.

    Article  Google Scholar 

  • Battaïa O and Dolgui A (2013). A taxonomy of line balancing problems and their solution approaches. International Journal of Production Economics 142 (2): 259–277.

    Article  Google Scholar 

  • Baybars I (1986). A survey of exact algorithms for the simple assembly line balancing problem. Management Science 32 (8): 900–932.

    Article  Google Scholar 

  • Becker C and Scholl A (2006). A survey on problems and methods in generalized assembly line balancing. European Journal of Operational Research 168 (3): 694–715.

    Article  Google Scholar 

  • Boysen N, Fliedner M and Scholl A (2006). A classification of assembly line balancing problems. Working paper 12/2006, Friedrich-Schiller-Universität Jena: Thuringia, Germany.

  • Boysen N, Fliedner M and Scholl A (2007). A classification of assembly line balancing problems. European Journal of Operational Research 183 (2): 674–693.

    Article  Google Scholar 

  • Boysen N, Fliedner M and Scholl A (2008). Assembly line balancing: Which model to use when? International Journal of Production Economics 111 (2): 509–528.

    Article  Google Scholar 

  • Capacho L, Pastor R, Dolgui A and Gunshinskaya O (2009). An evaluation of constructive heuristic methods for solving the alternative subgraphs assembly line balancing problem. Journal of Heuristics 15 (2): 109–132.

    Article  Google Scholar 

  • Cheshmehgaz HR, Haron H, Kazemipour F and Desa MI (2012). Accumulated risk of body postures in assembly line balancing problem and modelling through a multi-criteria fuzzy-genetic algorithm. Computers & Industrial Engineering 63 (2): 503–512.

    Article  Google Scholar 

  • Corominas A and Pastor R (2009). A note on ‘a comparative evaluation of assembly line balancing heuristics’. International Journal of Advanced Manufacturing Technology 44 (7–8): 817.

    Article  Google Scholar 

  • Corominas A, Ferrer L and Pastor R (2011). Assembly line balancing: General resource-constrained case. International Journal of Production Research 49 (12): 3527–3542.

    Article  Google Scholar 

  • Cortés P, Muñuzuri J, Onieva L, Larrañeta J, Vozmediano JM and Alarcón JC (2006). Andalucía assesses the investment needed to deploy a fiber-optic network. Interfaces 36 (2): 105–117.

    Article  Google Scholar 

  • Ding F-Y, Zhu J and Sun H (2006). Comparing two weighted approaches for sequencing mixed-model assembly lines with multiple objectives. International Journal of Production Economics 102 (1): 108–131.

    Article  Google Scholar 

  • Duarte A and Martí R (2007). Tabu search and GRASP for the maximum diversity problem. European Journal of Operational Research 178 (1): 71–84.

    Article  Google Scholar 

  • Feo TA and Resende MGC (1989). A probabilistic heuristic for a computationally difficult set covering problem. Operations Research Letters 8 (2): 67–81.

    Article  Google Scholar 

  • Gamberini R, Grassi A and Rimini B (2006). A new multi-objective heuristic algorithm for solving the stochastic assembly line re-balancing problem. International Journal of Production Economics 102 (2): 226–243.

    Article  Google Scholar 

  • Glover F (1977). Heuristics for integer programming using surrogate constraints. Decision Sciences 8 (1): 156–166.

    Article  Google Scholar 

  • Glover F (1986). Future paths for integer programming and links to artificial intelligence. Computers and Operations Research 5 (5): 533–549.

    Article  Google Scholar 

  • Glover F (1998). A template for scatter search and path relinking. In: Hao J-K, Lutton E, Ronald E, Schoenauer M and Snyers D (eds). Artificial Evolution. Lecture Notes in Computer Science, Vol. 1363, Springer: London, UK, pp 13–54.

  • Glover F and Laguna M (1997). Tabu Search. Kluwer Academic Publisher: Norwell, MA.

    Book  Google Scholar 

  • Hoffman TR (1992). EUREKA: A hybrid system for assembly line balancing. Management Science 38 (1): 39–47.

    Article  Google Scholar 

  • Inman RR and Leon M (1994). Scheduling duplicate serial stations in transfer lines. International Journal of Production Research 32 (11): 2631–2644.

    Article  Google Scholar 

  • Johnson RV (1988). Optimally balancing large assembly lines with fable. Management Science 34 (2): 240–253.

    Article  Google Scholar 

  • Kao EPC and Queyranne M (1982). On dynamic programming methods for assembly line balancing. Operations Research 30 (2): 375–390.

    Article  Google Scholar 

  • Laguna M and Martí R (2003). Scatter Search. Kluwer Academic Publisher: Cambridge, UK.

    Book  Google Scholar 

  • Lusa A (2008). A survey of the literature on the multiple or parallel assembly line balancing problem. European Journal of Industrial Engineering 2 (1): 50–72.

    Article  Google Scholar 

  • Martino L and Pastor R (2010). Heuristic procedures for solving the general assembly line balancing problem with setups. International Journal of Production Research 48 (6): 1787–1804.

    Article  Google Scholar 

  • Merengo C, Nava F and Pozzetti A (1999). Balancing and sequencing manual mixed-model assembly lines. International Journal of Production Research 37 (12): 2835–2860.

    Article  Google Scholar 

  • Miltenburg J (2002). Balancing and scheduling mixed-model U-shaped production lines. International Journal of Flexible Manufacturing Systems 14 (2): 119–151.

    Article  Google Scholar 

  • Moodie CL and Young HH (1965). A heuristic method of assembly line balancing for assumptions of constant or variable work element times. Journal of Industrial Engineering 16 (1): 23–29.

    Google Scholar 

  • Park K, Park S and Kim W (1997). A heuristic for an assembly line balancing problem with incompatibility, range, and partial precedence constraints. Computers & Industrial Engineering 32 (2): 321–332.

    Article  Google Scholar 

  • Pastor R (2011). LB-ALBP: The lexicographic bottleneck assembly line balancing problem. International Journal of Production Research 49 (8): 2425–2442.

    Article  Google Scholar 

  • Pastor R, Chueca I and García-Villoria A (2012). A heuristic procedure for solving the lexicographic bottleneck assembly line balancing problem (LB-ALBP). International Journal of Production Research 50 (7): 1862–1876.

    Article  Google Scholar 

  • Pastor R and Ferrer L (2009). An improved mathematical program to solve the simple assembly line balancing problem. International Journal of Production Research 47 (11): 2943–2959.

    Article  Google Scholar 

  • Ponnambalam SG, Aravindan P and Mogileeswar G (1999). A comparative evaluation of assembly line balancing heuristics. International Journal of Advanced Manufacturing Technology 15 (8): 577–586.

    Article  Google Scholar 

  • Rachamadugu R and Talbot B (1991). Improving the equality of workload assignments in assembly lines. International Journal of Production Research 29 (3): 619–633.

    Article  Google Scholar 

  • Rekiek B, Lit P and Delchambre A (2002). Hybrid assembly line design and user’s preferences. International Journal of Production Research 40 (5): 1095–1111.

    Article  Google Scholar 

  • Rubinovitz J and Levitin G (1995). Genetic algorithm for assembly line balancing. International Journal of Production Economics 41 (1–3): 343–354.

    Article  Google Scholar 

  • Scholl A and Becker C (2006). State-of-the-art exact and heuristic solution procedures for simple assembly line balancing. European Journal of Operational Research 168 (3): 666–693.

    Article  Google Scholar 

  • Scholl A and Klein R (1997). SALOME: A bidirectional branch and bound procedure for assembly line balancing. Informs Journal on Computing 9 (4): 319–334.

    Article  Google Scholar 

  • Scholl A and Voß S (1996). Simple assembly line balancing-heuristic approaches. Journal of Heuristics 2 (3): 217–244.

    Article  Google Scholar 

  • Talbot FB and Patterson JH (1984). An integer programming algorithm with network cuts for solving the assembly line balancing problem. Management Science 30 (1): 85–99.

    Article  Google Scholar 

  • Talbot F, Patterson JH and Gehrlein WV (1986). A comparative evaluation of heuristic line balancing techniques. Management Science 32 (4): 430–454.

    Article  Google Scholar 

  • Wee TS and Magazine MJ (1982). Assembly line balancing as generalized bin packing. Operations Research Letters 1 (2): 56–58.

    Article  Google Scholar 

  • White WW (1961). Comments on a paper by Bowman. Operations Research 9 (2): 274–276.

    Article  Google Scholar 

Download references

Acknowledgements

This research has been partially supported by the Ministerio de Educación Cultura y Deporte of Spain (Grant Ref. PRX12/00016) and by the Ministerio de Economía y Competitividad of Spain (Grant Ref. TIN2012-35632). We would like to thank the reviewers for their valuable comments and suggestions that improved the quality of the paper.

Author information

Authors and Affiliations

  1. Universitat Politècnica de Catalunya, Barcelona, Spain

    Rafael Pastor & Alberto García-Villoria

  2. University of Colorado at Boulder, Boulder, CO, USA

    Manuel Laguna

  3. Universitat de València, València, Spain

    Rafael Martí

Authors
  1. Rafael Pastor
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Alberto García-Villoria
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Manuel Laguna
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Rafael Martí
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Alberto García-Villoria.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Pastor, R., García-Villoria, A., Laguna, M. et al. Metaheuristic procedures for the lexicographic bottleneck assembly line balancing problem. J Oper Res Soc 66, 1815–1825 (2015). https://doi.org/10.1057/jors.2014.138

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1057/jors.2014.138

Keywords

Search

Navigation