Skip to main content
Erschienen in: Soft Computing 15/2020

12.12.2019 | Methodologies and Application

A comparative study of exact methods for the simple assembly line balancing problem

verfasst von: Zixiang Li, Ibrahim Kucukkoc, Qiuhua Tang

Erschienen in: Soft Computing | Ausgabe 15/2020

Einloggen

Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

Exact methods have shown advanced and promising performance in solving the simple assembly line balancing problem, known as NP-hard. This research investigates the impact of various structural parameters on the performance of exact methods, including branching methods, search direction, method to achieve upper bounds, utilized lower bounds, utilized dominance rules and search strategy. In accordance with the structural parameter evaluation, utilized dominance rules and search strategy have shown the most important effect on the exact methods’ performance. This research also improves and re-implements three well-known exact methods [i.e., SALOME, bounded dynamic programming (BDP) heuristic and branch, bound and remember (BBR) algorithm] using effective parameters. Computational study demonstrates that the utilization of high-performance structural parameters enhances the performance of exact methods by a significant margin. The re-implemented BBR method with proper parameters shows clear superiority over all the published exact methods and might be regarded as the state-of-the-art exact methodology.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Anhänge
Nur mit Berechtigung zugänglich
Literatur
Zurück zum Zitat Battaïa O, Dolgui A (2013) A taxonomy of line balancing problems and their solution approaches. Int J Prod Econ 142(2):259–277 Battaïa O, Dolgui A (2013) A taxonomy of line balancing problems and their solution approaches. Int J Prod Econ 142(2):259–277
Zurück zum Zitat Bautista J, Pereira J (2007) Ant algorithms for a time and space constrained assembly line balancing problem. Eur J Oper Res 177(3):2016–2032MATH Bautista J, Pereira J (2007) Ant algorithms for a time and space constrained assembly line balancing problem. Eur J Oper Res 177(3):2016–2032MATH
Zurück zum Zitat Bautista J, Pereira J (2009) A dynamic programming based heuristic for the assembly line balancing problem. Eur J Oper Res 194(3):787–794MATH Bautista J, Pereira J (2009) A dynamic programming based heuristic for the assembly line balancing problem. Eur J Oper Res 194(3):787–794MATH
Zurück zum Zitat Blum C (2008) Beam-ACO for simple assembly line balancing. INFORMS J Comput 20(4):618–627MATH Blum C (2008) Beam-ACO for simple assembly line balancing. INFORMS J Comput 20(4):618–627MATH
Zurück zum Zitat Blum C (2010) Iterative beam search for simple assembly line balancing with a fixed number of work stations. arXiv preprint arXiv:1012.3273 Blum C (2010) Iterative beam search for simple assembly line balancing with a fixed number of work stations. arXiv preprint arXiv:​1012.​3273
Zurück zum Zitat Blum C, Miralles C (2011) On solving the assembly line worker assignment and balancing problem via beam search. Comput Oper Res 38(1):328–339MathSciNetMATH Blum C, Miralles C (2011) On solving the assembly line worker assignment and balancing problem via beam search. Comput Oper Res 38(1):328–339MathSciNetMATH
Zurück zum Zitat Borba L, Ritt M (2014) A heuristic and a branch-and-bound algorithm for the assembly line worker assignment and balancing problem. Comput Oper Res 45:87–96MathSciNetMATH Borba L, Ritt M (2014) A heuristic and a branch-and-bound algorithm for the assembly line worker assignment and balancing problem. Comput Oper Res 45:87–96MathSciNetMATH
Zurück zum Zitat Borba L, Ritt M, Miralles C (2018) Exact and heuristic methods for solving the robotic assembly line balancing problem. Eur J Oper Res 270(1):146–156MathSciNetMATH Borba L, Ritt M, Miralles C (2018) Exact and heuristic methods for solving the robotic assembly line balancing problem. Eur J Oper Res 270(1):146–156MathSciNetMATH
Zurück zum Zitat Boysen N, Fliedner M, Scholl A (2007) A classification of assembly line balancing problems. Eur J Oper Res 183(2):674–693MATH Boysen N, Fliedner M, Scholl A (2007) A classification of assembly line balancing problems. Eur J Oper Res 183(2):674–693MATH
Zurück zum Zitat Çil ZA, Mete S, Özceylan E, Ağpak K (2017) A beam search approach for solving type II robotic parallel assembly line balancing problem. Appl Soft Comput 61:129–138 Çil ZA, Mete S, Özceylan E, Ağpak K (2017) A beam search approach for solving type II robotic parallel assembly line balancing problem. Appl Soft Comput 61:129–138
Zurück zum Zitat Ege Y, Azizoglu M, Ozdemirel NE (2009) Assembly line balancing with station paralleling. Comput Ind Eng 57(4):1218–1225 Ege Y, Azizoglu M, Ozdemirel NE (2009) Assembly line balancing with station paralleling. Comput Ind Eng 57(4):1218–1225
Zurück zum Zitat Esmaeilbeigi R, Naderi B, Charkhgard P (2015) The type E simple assembly line balancing problem: a mixed integer linear programming formulation. Comput Oper Res 64:168–177MathSciNetMATH Esmaeilbeigi R, Naderi B, Charkhgard P (2015) The type E simple assembly line balancing problem: a mixed integer linear programming formulation. Comput Oper Res 64:168–177MathSciNetMATH
Zurück zum Zitat Fleszar K, Hindi KS (2003) An enumerative heuristic and reduction methods for the assembly line balancing problem. Eur J Oper Res 145(3):606–620MathSciNetMATH Fleszar K, Hindi KS (2003) An enumerative heuristic and reduction methods for the assembly line balancing problem. Eur J Oper Res 145(3):606–620MathSciNetMATH
Zurück zum Zitat Hoffmann TR (1963) Assembly line balancing with a precedence matrix. Manag Sci 9(4):551–562 Hoffmann TR (1963) Assembly line balancing with a precedence matrix. Manag Sci 9(4):551–562
Zurück zum Zitat Hoffmann TR (1992) Eureka: a hybrid system for assembly line balancing. Manag Sci 38(1):39–47MATH Hoffmann TR (1992) Eureka: a hybrid system for assembly line balancing. Manag Sci 38(1):39–47MATH
Zurück zum Zitat Johnson RV (1988) Optimally balancing large assembly lines with “Fable”. Manag Sci 34(2):240–253 Johnson RV (1988) Optimally balancing large assembly lines with “Fable”. Manag Sci 34(2):240–253
Zurück zum Zitat Kellegöz T, Toklu B (2012) An efficient branch and bound algorithm for assembly line balancing problems with parallel multi-manned workstations. Comput Oper Res 39(12):3344–3360MATH Kellegöz T, Toklu B (2012) An efficient branch and bound algorithm for assembly line balancing problems with parallel multi-manned workstations. Comput Oper Res 39(12):3344–3360MATH
Zurück zum Zitat Klein R, Scholl A (1996) Maximizing the production rate in simple assembly line balancing—a branch and bound procedure. Eur J Oper Res 91(2):367–385MATH Klein R, Scholl A (1996) Maximizing the production rate in simple assembly line balancing—a branch and bound procedure. Eur J Oper Res 91(2):367–385MATH
Zurück zum Zitat Lapierre SD, Ruiz A, Soriano P (2006) Balancing assembly lines with tabu search. Eur J Oper Res 168(3):826–837MathSciNetMATH Lapierre SD, Ruiz A, Soriano P (2006) Balancing assembly lines with tabu search. Eur J Oper Res 168(3):826–837MathSciNetMATH
Zurück zum Zitat Li Z, Kucukkoc I, Nilakantan JM (2017) Comprehensive review and evaluation of heuristics and meta-heuristics for two-sided assembly line balancing problem. Comput Oper Res 84:146–161MathSciNetMATH Li Z, Kucukkoc I, Nilakantan JM (2017) Comprehensive review and evaluation of heuristics and meta-heuristics for two-sided assembly line balancing problem. Comput Oper Res 84:146–161MathSciNetMATH
Zurück zum Zitat Li Z, Kucukkoc I, Zhang Z (2018) Branch, bound and remember algorithm for U-shaped assembly line balancing problem. Comput Ind Eng 124:24–35 Li Z, Kucukkoc I, Zhang Z (2018) Branch, bound and remember algorithm for U-shaped assembly line balancing problem. Comput Ind Eng 124:24–35
Zurück zum Zitat Liu SB, Ng KM, Ong HL (2008) Branch-and-bound algorithms for simple assembly line balancing problem. Int J Adv Manuf Technol 36(1):169–177 Liu SB, Ng KM, Ong HL (2008) Branch-and-bound algorithms for simple assembly line balancing problem. Int J Adv Manuf Technol 36(1):169–177
Zurück zum Zitat Miralles C, García-Sabater JP, Andrés C, Cardós M (2008) Branch and bound procedures for solving the assembly line worker assignment and balancing problem: application to sheltered work centres for disabled. Discrete Appl Math 156(3):352–367MathSciNetMATH Miralles C, García-Sabater JP, Andrés C, Cardós M (2008) Branch and bound procedures for solving the assembly line worker assignment and balancing problem: application to sheltered work centres for disabled. Discrete Appl Math 156(3):352–367MathSciNetMATH
Zurück zum Zitat Morrison DR, Sewell EC, Jacobson SH (2014) An application of the branch, bound, and remember algorithm to a new simple assembly line balancing dataset. Eur J Oper Res 236(2):403–409MATH Morrison DR, Sewell EC, Jacobson SH (2014) An application of the branch, bound, and remember algorithm to a new simple assembly line balancing dataset. Eur J Oper Res 236(2):403–409MATH
Zurück zum Zitat Nourie FJ, Venta ER (1991) Finding optimal line balances with OptPack. Oper Res Lett 10(3):165–171MATH Nourie FJ, Venta ER (1991) Finding optimal line balances with OptPack. Oper Res Lett 10(3):165–171MATH
Zurück zum Zitat Ogan D, Azizoglu M (2015) A branch and bound method for the line balancing problem in U-shaped assembly lines with equipment requirements. J Manuf Syst 36:46–54 Ogan D, Azizoglu M (2015) A branch and bound method for the line balancing problem in U-shaped assembly lines with equipment requirements. J Manuf Syst 36:46–54
Zurück zum Zitat Otto A, Otto C, Scholl A (2013) Systematic data generation and test design for solution algorithms on the example of SALBPGen for assembly line balancing. Eur J Oper Res 228(1):33–45MathSciNetMATH Otto A, Otto C, Scholl A (2013) Systematic data generation and test design for solution algorithms on the example of SALBPGen for assembly line balancing. Eur J Oper Res 228(1):33–45MathSciNetMATH
Zurück zum Zitat Pape T (2015) Heuristics and lower bounds for the simple assembly line balancing problem type 1: overview, computational tests and improvements. Eur J Oper Res 240(1):32–42MathSciNetMATH Pape T (2015) Heuristics and lower bounds for the simple assembly line balancing problem type 1: overview, computational tests and improvements. Eur J Oper Res 240(1):32–42MathSciNetMATH
Zurück zum Zitat Pereira J (2015) Empirical evaluation of lower bounding methods for the simple assembly line balancing problem. Int J Prod Res 53(11):3327–3340 Pereira J (2015) Empirical evaluation of lower bounding methods for the simple assembly line balancing problem. Int J Prod Res 53(11):3327–3340
Zurück zum Zitat Pereira J (2018) The robust (minmax regret) assembly line worker assignment and balancing problem. Comput Oper Res 93:27–40MathSciNetMATH Pereira J (2018) The robust (minmax regret) assembly line worker assignment and balancing problem. Comput Oper Res 93:27–40MathSciNetMATH
Zurück zum Zitat Pereira J, Álvarez-Miranda E (2018) An exact approach for the robust assembly line balancing problem. Omega 78:85–98 Pereira J, Álvarez-Miranda E (2018) An exact approach for the robust assembly line balancing problem. Omega 78:85–98
Zurück zum Zitat Sabuncuoglu I, Erel E, Tanyer M (2000) Assembly line balancing using genetic algorithms. J Intell Manuf 11(3):295–310 Sabuncuoglu I, Erel E, Tanyer M (2000) Assembly line balancing using genetic algorithms. J Intell Manuf 11(3):295–310
Zurück zum Zitat Scholl A, Becker C (2006) State-of-the-art exact and heuristic solution procedures for simple assembly line balancing. Eur J Oper Res 168(3):666–693MathSciNetMATH Scholl A, Becker C (2006) State-of-the-art exact and heuristic solution procedures for simple assembly line balancing. Eur J Oper Res 168(3):666–693MathSciNetMATH
Zurück zum Zitat Scholl A, Klein R (1997) SALOME: a bidirectional branch-and-bound procedure for assembly line balancing. INFORMS J Comput 9(4):319–334MATH Scholl A, Klein R (1997) SALOME: a bidirectional branch-and-bound procedure for assembly line balancing. INFORMS J Comput 9(4):319–334MATH
Zurück zum Zitat Scholl A, Klein R (1999) Balancing assembly lines effectively—a computational comparison. Eur J Oper Res 114(1):50–58MATH Scholl A, Klein R (1999) Balancing assembly lines effectively—a computational comparison. Eur J Oper Res 114(1):50–58MATH
Zurück zum Zitat Scholl A, Voß S (1997) Simple assembly line balancing—heuristic approaches. J Heuristics 2(3):217–244 Scholl A, Voß S (1997) Simple assembly line balancing—heuristic approaches. J Heuristics 2(3):217–244
Zurück zum Zitat Sewell EC, Jacobson SH (2012) A branch, bound, and remember algorithm for the simple assembly line balancing problem. INFORMS J Comput 24(3):433–442MathSciNetMATH Sewell EC, Jacobson SH (2012) A branch, bound, and remember algorithm for the simple assembly line balancing problem. INFORMS J Comput 24(3):433–442MathSciNetMATH
Zurück zum Zitat Sternatz J (2014) Enhanced multi-Hoffmann heuristic for efficiently solving real-world assembly line balancing problems in automotive industry. Eur J Oper Res 235(3):740–754MathSciNetMATH Sternatz J (2014) Enhanced multi-Hoffmann heuristic for efficiently solving real-world assembly line balancing problems in automotive industry. Eur J Oper Res 235(3):740–754MathSciNetMATH
Zurück zum Zitat Vilà M, Pereira J (2013) An enumeration procedure for the assembly line balancing problem based on branching by non-decreasing idle time. Eur J Oper Res 229(1):106–113MathSciNetMATH Vilà M, Pereira J (2013) An enumeration procedure for the assembly line balancing problem based on branching by non-decreasing idle time. Eur J Oper Res 229(1):106–113MathSciNetMATH
Zurück zum Zitat Vilà M, Pereira J (2014) A branch-and-bound algorithm for assembly line worker assignment and balancing problems. Comput Oper Res 44:105–114MathSciNetMATH Vilà M, Pereira J (2014) A branch-and-bound algorithm for assembly line worker assignment and balancing problems. Comput Oper Res 44:105–114MathSciNetMATH
Zurück zum Zitat Wei N-C, Chao IM (2011) A solution procedure for type E simple assembly line balancing problem. Comput Ind Eng 61(3):824–830 Wei N-C, Chao IM (2011) A solution procedure for type E simple assembly line balancing problem. Comput Ind Eng 61(3):824–830
Zurück zum Zitat Wu E-F, Jin Y, Bao J-S, Hu X-F (2008) A branch-and-bound algorithm for two-sided assembly line balancing. Int J Adv Manuf Technol 39(9):1009–1015 Wu E-F, Jin Y, Bao J-S, Hu X-F (2008) A branch-and-bound algorithm for two-sided assembly line balancing. Int J Adv Manuf Technol 39(9):1009–1015
Zurück zum Zitat Xiaofeng H, Erfei W, Jinsong B, Ye J (2010) A branch-and-bound algorithm to minimize the line length of a two-sided assembly line. Eur J Oper Res 206(3):703–707MATH Xiaofeng H, Erfei W, Jinsong B, Ye J (2010) A branch-and-bound algorithm to minimize the line length of a two-sided assembly line. Eur J Oper Res 206(3):703–707MATH
Zurück zum Zitat Yolmeh A, Salehi N (2017) A branch, price and remember algorithm for the U shaped assembly line balancing problem. arXiv preprint arXiv:1708.04127 Yolmeh A, Salehi N (2017) A branch, price and remember algorithm for the U shaped assembly line balancing problem. arXiv preprint arXiv:​1708.​04127
Metadaten
Titel
A comparative study of exact methods for the simple assembly line balancing problem
verfasst von
Zixiang Li
Ibrahim Kucukkoc
Qiuhua Tang
Publikationsdatum
12.12.2019
Verlag
Springer Berlin Heidelberg
Erschienen in
Soft Computing / Ausgabe 15/2020
Print ISSN: 1432-7643
Elektronische ISSN: 1433-7479
DOI
https://doi.org/10.1007/s00500-019-04609-9

Weitere Artikel der Ausgabe 15/2020

Soft Computing 15/2020 Zur Ausgabe