IDEAS home Printed from https://ideas.repec.org/a/eee/proeco/v142y2013i2p259-277.html
   My bibliography  Save this article

A taxonomy of line balancing problems and their solutionapproaches

Author

Listed:
  • Battaïa, Olga
  • Dolgui, Alexandre

Abstract

Line balancing belongs to a class of intensively studied combinatorial optimization problems known to be NP-hard in general. For several decades, the core problem originally introduced for manual assembly has been extended to suit robotic, machining and disassembly contexts. However, despite various industrial environments and line configurations, often quite similar or even identical mathematical models have been developed. The objective of this survey is to analyze recent research on balancing flow lines within many different industrial contexts in order to classify and compare the means for input data modelling, constraints and objective functions used. This survey covers about 300 studies on line balancing problems. Particular attention is paid to recent publications that have appeared in 2007–2012 to focus on new advances in the state-of-the-art.

Suggested Citation

  • Battaïa, Olga & Dolgui, Alexandre, 2013. "A taxonomy of line balancing problems and their solutionapproaches," International Journal of Production Economics, Elsevier, vol. 142(2), pages 259-277.
  • Handle: RePEc:eee:proeco:v:142:y:2013:i:2:p:259-277
    DOI: 10.1016/j.ijpe.2012.10.020
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0925527312004616
    Download Restriction: Full text for ScienceDirect subscribers only

    File URL: https://libkey.io/10.1016/j.ijpe.2012.10.020?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Allan L. Gutjahr & George L. Nemhauser, 1964. "An Algorithm for the Line Balancing Problem," Management Science, INFORMS, vol. 11(2), pages 308-315, November.
    2. Thomas R. Hoffmann, 1963. "Assembly Line Balancing with a Precedence Matrix," Management Science, INFORMS, vol. 9(4), pages 551-562, July.
    3. Erel, Erdal & Gokcen, Hadi, 1999. "Shortest-route formulation of mixed-model assembly line balancing problem," European Journal of Operational Research, Elsevier, vol. 116(1), pages 194-204, July.
    4. Digiesi, Salvatore & Kock, Ad A.A. & Mummolo, Giovanni & Rooda, Jacobus E., 2009. "The effect of dynamic worker behavior on flow line performance," International Journal of Production Economics, Elsevier, vol. 120(2), pages 368-377, August.
    5. Andres, Carlos & Miralles, Cristobal & Pastor, Rafael, 2008. "Balancing and scheduling tasks in assembly lines with sequence-dependent setup times," European Journal of Operational Research, Elsevier, vol. 187(3), pages 1212-1223, June.
    6. Amaia Lusa, 2008. "A survey of the literature on the multiple or parallel assembly line balancing problem," European Journal of Industrial Engineering, Inderscience Enterprises Ltd, vol. 2(1), pages 50-72.
    7. Amen, Matthias, 2000. "An exact method for cost-oriented assembly line balancing," International Journal of Production Economics, Elsevier, vol. 64(1-3), pages 187-195, March.
    8. Delorme, Xavier & Dolgui, Alexandre & Kovalyov, Mikhail Y., 2012. "Combinatorial design of a minimum cost transfer line," Omega, Elsevier, vol. 40(1), pages 31-41, January.
    9. Gagnon, R. J. & Ghosh, S., 1991. "Assembly line research: Historical roots, research life cycles and future directions," Omega, Elsevier, vol. 19(5), pages 381-399.
    10. Gamberini, Rita & Grassi, Andrea & Rimini, Bianca, 2006. "A new multi-objective heuristic algorithm for solving the stochastic assembly line re-balancing problem," International Journal of Production Economics, Elsevier, vol. 102(2), pages 226-243, August.
    11. Boysen, Nils & Fliedner, Malte & Scholl, Armin, 2007. "A classification of assembly line balancing problems," European Journal of Operational Research, Elsevier, vol. 183(2), pages 674-693, December.
    12. Biskup, Dirk, 1999. "Single-machine scheduling with learning considerations," European Journal of Operational Research, Elsevier, vol. 115(1), pages 173-178, May.
    13. Hu, Xiaofeng & Wu, Erfei & Jin, Ye, 2008. "A station-oriented enumerative algorithm for two-sided assembly line balancing," European Journal of Operational Research, Elsevier, vol. 186(1), pages 435-440, April.
    14. Roger V. Johnson, 1983. "A Branch and Bound Algorithm for Assembly Line Balancing Problems with Formulation Irregularities," Management Science, INFORMS, vol. 29(11), pages 1309-1324, November.
    15. Bautista, Joaquin & Pereira, Jordi, 2007. "Ant algorithms for a time and space constrained assembly line balancing problem," European Journal of Operational Research, Elsevier, vol. 177(3), pages 2016-2032, March.
    16. Urban, Timothy L. & Chiang, Wen-Chyuan, 2006. "An optimal piecewise-linear program for the U-line balancing problem with stochastic task times," European Journal of Operational Research, Elsevier, vol. 168(3), pages 771-782, February.
    17. Scholl, Armin & Becker, Christian, 2006. "State-of-the-art exact and heuristic solution procedures for simple assembly line balancing," European Journal of Operational Research, Elsevier, vol. 168(3), pages 666-693, February.
    18. Dolgui, A. & Ihnatsenka, I., 2009. "Branch and bound algorithm for a transfer line design problem: Stations with sequentially activated multi-spindle heads," European Journal of Operational Research, Elsevier, vol. 197(3), pages 1119-1132, September.
    19. Boysen, Nils & Fliedner, Malte & Scholl, Armin, 2008. "Assembly line balancing: Which model to use when," International Journal of Production Economics, Elsevier, vol. 111(2), pages 509-528, February.
    20. Bautista, Joaquín & Pereira, Jordi, 2009. "A dynamic programming based heuristic for the assembly line balancing problem," European Journal of Operational Research, Elsevier, vol. 194(3), pages 787-794, May.
    21. Scholl, Armin, 1995. "Balancing and sequencing of assembly lines," Publications of Darmstadt Technical University, Institute for Business Studies (BWL) 9690, Darmstadt Technical University, Department of Business Administration, Economics and Law, Institute for Business Studies (BWL).
    22. Corominas, Albert & Pastor, Rafael & Plans, Joan, 2008. "Balancing assembly line with skilled and unskilled workers," Omega, Elsevier, vol. 36(6), pages 1126-1132, December.
    23. Becker, Christian & Scholl, Armin, 2009. "Balancing assembly lines with variable parallel workplaces: Problem definition and effective solution procedure," European Journal of Operational Research, Elsevier, vol. 199(2), pages 359-374, December.
    24. Scholl, Armin & Klein, Robert, 1997. "SALOME. a bidirectional branch and bound procedure for assembly line balancing," Publications of Darmstadt Technical University, Institute for Business Studies (BWL) 7890, Darmstadt Technical University, Department of Business Administration, Economics and Law, Institute for Business Studies (BWL).
    25. Costa, Alysson M. & Miralles, Cristóbal, 2009. "Job rotation in assembly lines employing disabled workers," International Journal of Production Economics, Elsevier, vol. 120(2), pages 625-632, August.
    26. Otto, Alena & Scholl, Armin, 2011. "Incorporating ergonomic risks into assembly line balancing," European Journal of Operational Research, Elsevier, vol. 212(2), pages 277-286, July.
    27. Miralles, Cristobal & Garcia-Sabater, Jose Pedro & Andres, Carlos & Cardos, Manuel, 2007. "Advantages of assembly lines in Sheltered Work Centres for Disabled. A case study," International Journal of Production Economics, Elsevier, vol. 110(1-2), pages 187-197, October.
    28. G. M. Buxey, 1974. "Assembly Line Balancing with Multiple Stations," Management Science, INFORMS, vol. 20(6), pages 1010-1021, February.
    29. Nearchou, Andreas C., 2011. "Maximizing production rate and workload smoothing in assembly lines using particle swarm optimization," International Journal of Production Economics, Elsevier, vol. 129(2), pages 242-250, February.
    30. Dolgui, Alexandre & Guschinsky, Nikolai & Levin, Genrikh, 2006. "A special case of transfer lines balancing by graph approach," European Journal of Operational Research, Elsevier, vol. 168(3), pages 732-746, February.
    31. J. L. C. Macaskill, 1972. "Production-Line Balances for Mixed-Model Lines," Management Science, INFORMS, vol. 19(4-Part-1), pages 423-434, December.
    32. Dolgui, A. & Guschinsky, N. & Levin, G. & Proth, J.-M., 2008. "Optimisation of multi-position machines and transfer lines," European Journal of Operational Research, Elsevier, vol. 185(3), pages 1375-1389, March.
    33. Sawik, Tadeusz, 2002. "Monolithic vs. hierarchical balancing and scheduling of a flexible assembly line," European Journal of Operational Research, Elsevier, vol. 143(1), pages 115-124, November.
    34. Kara, Yakup & Paksoy, Turan & Chang, Ching-Ter, 2009. "Binary fuzzy goal programming approach to single model straight and U-shaped assembly line balancing," European Journal of Operational Research, Elsevier, vol. 195(2), pages 335-347, June.
    35. Bhattacharjee, T. K. & Sahu, S., 1990. "Complexity of single model assembly line balancing problems," Engineering Costs and Production Economics, Elsevier, vol. 18(3), pages 203-214, January.
    36. Roger V. Johnson, 1988. "Optimally Balancing Large Assembly Lines with "Fable"," Management Science, INFORMS, vol. 34(2), pages 240-253, February.
    37. Lapierre, Sophie D. & Ruiz, Angel & Soriano, Patrick, 2006. "Balancing assembly lines with tabu search," European Journal of Operational Research, Elsevier, vol. 168(3), pages 826-837, February.
    38. Amen, Matthias, 2006. "Cost-oriented assembly line balancing: Model formulations, solution difficulty, upper and lower bounds," European Journal of Operational Research, Elsevier, vol. 168(3), pages 747-770, February.
    39. Sarin, Subhash C. & Erel, Erdal & Dar-El, Ezey M., 1999. "A methodology for solving single-model, stochastic assembly line balancing problem," Omega, Elsevier, vol. 27(5), pages 525-535, October.
    40. F. Brian Talbot & James H. Patterson & William V. Gehrlein, 1986. "A Comparative Evaluation of Heuristic Line Balancing Techniques," Management Science, INFORMS, vol. 32(4), pages 430-454, April.
    41. McGovern, Seamus M. & Gupta, Surendra M., 2007. "A balancing method and genetic algorithm for disassembly line balancing," European Journal of Operational Research, Elsevier, vol. 179(3), pages 692-708, June.
    42. Emde, Simon & Boysen, Nils & Scholl, Armin, 2010. "Balancing mixed-model assembly lines: a computational evaluation of objectives to smoothen workload," Publications of Darmstadt Technical University, Institute for Business Studies (BWL) 79442, Darmstadt Technical University, Department of Business Administration, Economics and Law, Institute for Business Studies (BWL).
    43. Bautista, Joaquín & Pereira, Jordi, 2011. "Procedures for the Time and Space constrained Assembly Line Balancing Problem," European Journal of Operational Research, Elsevier, vol. 212(3), pages 473-481, August.
    44. Norman Keith Womer, 1979. "Learning Curves, Production Rate, and Program Costs," Management Science, INFORMS, vol. 25(4), pages 312-319, April.
    45. Kahan, Tomer & Bukchin, Yossi & Menassa, Roland & Ben-Gal, Irad, 2009. "Backup strategy for robots' failures in an automotive assembly system," International Journal of Production Economics, Elsevier, vol. 120(2), pages 315-326, August.
    46. van Zante-de Fokkert, Jannet I. & de Kok, Ton G., 1997. "The mixed and multi model line balancing problem: a comparison," European Journal of Operational Research, Elsevier, vol. 100(3), pages 399-412, August.
    47. Özcan, Ugur, 2010. "Balancing stochastic two-sided assembly lines: A chance-constrained, piecewise-linear, mixed integer program and a simulated annealing algorithm," European Journal of Operational Research, Elsevier, vol. 205(1), pages 81-97, August.
    48. Xiaofeng, Hu & Erfei, Wu & Jinsong, Bao & Ye, Jin, 2010. "A branch-and-bound algorithm to minimize the line length of a two-sided assembly line," European Journal of Operational Research, Elsevier, vol. 206(3), pages 703-707, November.
    49. Thomas R. Hoffmann, 1992. "Eureka: A Hybrid System for Assembly Line Balancing," Management Science, INFORMS, vol. 38(1), pages 39-47, January.
    50. Sotskov, Yuri N. & Dolgui, Alexandre & Portmann, Marie-Claude, 2006. "Stability analysis of an optimal balance for an assembly line with fixed cycle time," European Journal of Operational Research, Elsevier, vol. 168(3), pages 783-797, February.
    51. Sabuncuoglu, Ihsan & Erel, Erdal & Alp, Arda, 2009. "Ant colony optimization for the single model U-type assembly line balancing problem," International Journal of Production Economics, Elsevier, vol. 120(2), pages 287-300, August.
    52. Fleszar, Krzysztof & Hindi, Khalil S., 2003. "An enumerative heuristic and reduction methods for the assembly line balancing problem," European Journal of Operational Research, Elsevier, vol. 145(3), pages 606-620, March.
    53. Scholl, Armin & Boysen, Nils, 2009. "Designing parallel assembly lines with split workplaces: Model and optimization procedure," International Journal of Production Economics, Elsevier, vol. 119(1), pages 90-100, May.
    54. Guschinskaya, Olga & Dolgui, Alexandre, 2009. "Comparison of exact and heuristic methods for a transfer line balancing problem," International Journal of Production Economics, Elsevier, vol. 120(2), pages 276-286, August.
    55. McMullen, Patrick R. & Frazier, Gregory V., 1997. "A heuristic for solving mixed-model line balancing problems with stochastic task durations and parallel stations," International Journal of Production Economics, Elsevier, vol. 51(3), pages 177-190, September.
    56. Bukchin, Yossi & Rabinowitch, Ithai, 2006. "A branch-and-bound based solution approach for the mixed-model assembly line-balancing problem for minimizing stations and task duplication costs," European Journal of Operational Research, Elsevier, vol. 174(1), pages 492-508, October.
    57. James R. Jackson, 1956. "A Computing Procedure for a Line Balancing Problem," Management Science, INFORMS, vol. 2(3), pages 261-271, April.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Boysen, Nils & Fliedner, Malte & Scholl, Armin, 2008. "Assembly line balancing: Which model to use when," International Journal of Production Economics, Elsevier, vol. 111(2), pages 509-528, February.
    2. Sternatz, Johannes, 2014. "Enhanced multi-Hoffmann heuristic for efficiently solving real-world assembly line balancing problems in automotive industry," European Journal of Operational Research, Elsevier, vol. 235(3), pages 740-754.
    3. Hamta, Nima & Fatemi Ghomi, S.M.T. & Jolai, F. & Akbarpour Shirazi, M., 2013. "A hybrid PSO algorithm for a multi-objective assembly line balancing problem with flexible operation times, sequence-dependent setup times and learning effect," International Journal of Production Economics, Elsevier, vol. 141(1), pages 99-111.
    4. Boysen, Nils & Fliedner, Malte & Scholl, Armin, 2007. "A classification of assembly line balancing problems," European Journal of Operational Research, Elsevier, vol. 183(2), pages 674-693, December.
    5. Bautista, Joaquín & Pereira, Jordi, 2011. "Procedures for the Time and Space constrained Assembly Line Balancing Problem," European Journal of Operational Research, Elsevier, vol. 212(3), pages 473-481, August.
    6. Scholl, Armin & Fliedner, Malte & Boysen, Nils, 2010. "Absalom: Balancing assembly lines with assignment restrictions," European Journal of Operational Research, Elsevier, vol. 200(3), pages 688-701, February.
    7. Otto, Alena & Otto, Christian & Scholl, Armin, 2013. "Systematic data generation and test design for solution algorithms on the example of SALBPGen for assembly line balancing," European Journal of Operational Research, Elsevier, vol. 228(1), pages 33-45.
    8. Boysen, Nils & Fliedner, Malte, 2008. "A versatile algorithm for assembly line balancing," European Journal of Operational Research, Elsevier, vol. 184(1), pages 39-56, January.
    9. E. C. Sewell & S. H. Jacobson, 2012. "A Branch, Bound, and Remember Algorithm for the Simple Assembly Line Balancing Problem," INFORMS Journal on Computing, INFORMS, vol. 24(3), pages 433-442, August.
    10. Bautista, Joaquín & Pereira, Jordi, 2009. "A dynamic programming based heuristic for the assembly line balancing problem," European Journal of Operational Research, Elsevier, vol. 194(3), pages 787-794, May.
    11. Becker, Christian & Scholl, Armin, 2006. "A survey on problems and methods in generalized assembly line balancing," European Journal of Operational Research, Elsevier, vol. 168(3), pages 694-715, February.
    12. Pape, Tom, 2015. "Heuristics and lower bounds for the simple assembly line balancing problem type 1: Overview, computational tests and improvements," European Journal of Operational Research, Elsevier, vol. 240(1), pages 32-42.
    13. Vilà, Mariona & Pereira, Jordi, 2013. "An enumeration procedure for the assembly line balancing problem based on branching by non-decreasing idle time," European Journal of Operational Research, Elsevier, vol. 229(1), pages 106-113.
    14. Becker, Christian & Scholl, Armin, 2009. "Balancing assembly lines with variable parallel workplaces: Problem definition and effective solution procedure," European Journal of Operational Research, Elsevier, vol. 199(2), pages 359-374, December.
    15. Scholl, Armin & Becker, Christian, 2006. "State-of-the-art exact and heuristic solution procedures for simple assembly line balancing," European Journal of Operational Research, Elsevier, vol. 168(3), pages 666-693, February.
    16. Delorme, Xavier & Dolgui, Alexandre & Kovalyov, Mikhail Y., 2012. "Combinatorial design of a minimum cost transfer line," Omega, Elsevier, vol. 40(1), pages 31-41, January.
    17. Pereira, Jordi & Álvarez-Miranda, Eduardo, 2018. "An exact approach for the robust assembly line balancing problem," Omega, Elsevier, vol. 78(C), pages 85-98.
    18. Sternatz, Johannes, 2015. "The joint line balancing and material supply problem," International Journal of Production Economics, Elsevier, vol. 159(C), pages 304-318.
    19. Christian Becker & Armin Scholl, 2008. "Balancing assembly lines with variable parallel workplaces: Problem definition, model and exact solution procedure," Jena Research Papers in Business and Economics - Working and Discussion Papers (Expired!) 06/2008, Friedrich-Schiller-University Jena, School of Economics and Business Administration.
    20. Araújo, Felipe F.B. & Costa, Alysson M. & Miralles, Cristóbal, 2012. "Two extensions for the ALWABP: Parallel stations and collaborative approach," International Journal of Production Economics, Elsevier, vol. 140(1), pages 483-495.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:proeco:v:142:y:2013:i:2:p:259-277. See general information about how to correct material in RePEc.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: . General contact details of provider: http://www.elsevier.com/locate/ijpe .

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/ijpe .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service hosted by the Research Division of the Federal Reserve Bank of St. Louis . RePEc uses bibliographic data supplied by the respective publishers.