IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v200y2010i3p688-701.html
   My bibliography  Save this article

Absalom: Balancing assembly lines with assignment restrictions

Author

Listed:
  • Scholl, Armin
  • Fliedner, Malte
  • Boysen, Nils

Abstract

Assembly line balancing problems (ALBPs) arise whenever an assembly line is configured, redesigned or adjusted. An ALBP consists of distributing the total workload for manufacturing products among the work stations along the line. On the one hand, research has focussed on developing effective and fast solution methods for exactly solving the simple assembly line balancing problem (SALBP). On the other hand, a number of real-world extensions of SALBP have been introduced but solved with straight-forward and simple heuristics in many cases. Therefore, there is a lack of procedures for exactly solving such generalized ALBP. In this paper, we show how to extend the well-known solution procedure Salome [Scholl, A., Klein, R., 1997. Salome: A bidirectional branch-and-bound procedure for assembly line balancing. Informs J. Comput. 9 319-334], which is able to solve even large SALBP instances in a very effective manner, to a problem extension with different types of assignment restrictions (called ARALBP). The extended procedure, referred to as Absalom, employs a favorable branching scheme, an arsenal of bounding rules and a variety of logical tests using ideas from constraint programming. Computational experiments show that Absalom is a very promising exact solution approach although the additional assignment restrictions complicate the problem considerably and necessitate a relaxation of some components of Salome.

Suggested Citation

  • 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.
    • Handle: RePEc:eee:ejores:v:200:y:2010:i:3:p:688-701
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377-2217(09)00057-5
    Download Restriction: Full text for ScienceDirect subscribers only
    ---><---

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

    Other versions of this item:

    References listed on IDEAS

    as
    1. Klein, Robert, 1999. "Computing lower bounds by destructive improvement - an application to resource-constrained project scheduling," Publications of Darmstadt Technical University, Institute for Business Studies (BWL) 10913, Darmstadt Technical University, Department of Business Administration, Economics and Law, Institute for Business Studies (BWL).
    2. 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.
    3. Armin Scholl & Robert Klein, 1997. "SALOME: A Bidirectional Branch-and-Bound Procedure for Assembly Line Balancing," INFORMS Journal on Computing, INFORMS, vol. 9(4), pages 319-334, November.
    4. Carlier, Jacques, 1982. "The one-machine sequencing problem," European Journal of Operational Research, Elsevier, vol. 11(1), pages 42-47, September.
    5. 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.
    6. Berger, Ilana & Bourjolly, Jean-Marie & Laporte, Gilbert, 1992. "Branch-and-bound algorithms for the multi-product assembly line balancing problem," European Journal of Operational Research, Elsevier, vol. 58(2), pages 215-222, April.
    7. 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.
    8. 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.
    9. 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.
    10. 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.
    11. 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).
    12. E. H. Bowman, 1960. "Assembly-Line Balancing by Linear Programming," Operations Research, INFORMS, vol. 8(3), pages 385-389, June.
    13. 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).
    14. Gokcen, Hadi & Erel, Erdal, 1997. "A goal programming approach to mixed-model assembly line balancing problem," International Journal of Production Economics, Elsevier, vol. 48(2), pages 177-185, January.
    15. Wilbert E. Wilhelm & Radu Gadidov, 2004. "A Branch-and-Cut Approach for a Generic Multiple-Product, Assembly-System Design Problem," INFORMS Journal on Computing, INFORMS, vol. 16(1), pages 39-55, February.
    16. G. M. Buxey, 1974. "Assembly Line Balancing with Multiple Stations," Management Science, INFORMS, vol. 20(6), pages 1010-1021, February.
    17. R Pastor & C Andrés & A Duran & M Pérez, 2002. "Tabu search algorithms for an industrial multi-product and multi-objective assembly line balancing problem, with reduction of the task dispersion," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 53(12), pages 1317-1323, December.
    18. 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.
    19. Scholl, Armin & Klein, Robert, 1999. "Balancing assembly lines effectively - A computational comparison," European Journal of Operational Research, Elsevier, vol. 114(1), pages 50-58, April.
    20. E. M. Dar-El & Y. Rubinovitch, 1979. "Must--A Multiple Solutions Technique for Balancing Single Model Assembly Lines," Management Science, INFORMS, vol. 25(11), pages 1105-1114, November.
    21. Roger V. Johnson, 1988. "Optimally Balancing Large Assembly Lines with "Fable"," Management Science, INFORMS, vol. 34(2), pages 240-253, February.
    22. Miltenburg, John, 1998. "Balancing U-lines in a multiple U-line facility," European Journal of Operational Research, Elsevier, vol. 109(1), pages 1-23, August.
    23. 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.
    24. Saltzman, Matthew J. & Baybars, Ilker, 1987. "A two-process implicit enumeration algorithm for the simple assembly line balancing problem," European Journal of Operational Research, Elsevier, vol. 32(1), pages 118-129, October.
    25. Klein, Robert & Scholl, Armin, 1999. "Computing lower bounds by destructive improvement: An application to resource-constrained project scheduling," European Journal of Operational Research, Elsevier, vol. 112(2), pages 322-346, January.
    26. S D Lapierre & A B Ruiz, 2004. "Balancing assembly lines: an industrial case study," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 55(6), pages 589-597, June.
    27. 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.
    28. 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.
    29. .Ilker Baybars, 1986. "A Survey of Exact Algorithms for the Simple Assembly Line Balancing Problem," Management Science, INFORMS, vol. 32(8), pages 909-932, August.
    30. 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)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Bautista, Joaquín & Batalla-García, Cristina & Alfaro-Pozo, Rocío, 2016. "Models for assembly line balancing by temporal, spatial and ergonomic risk attributes," European Journal of Operational Research, Elsevier, vol. 251(3), pages 814-829.
    2. Roland Braune, 2022. "Packing-based branch-and-bound for discrete malleable task scheduling," Journal of Scheduling, Springer, vol. 25(6), pages 675-704, December.
    3. Klindworth, Hanne & Otto, Christian & Scholl, Armin, 2012. "On a learning precedence graph concept for the automotive industry," European Journal of Operational Research, Elsevier, vol. 217(2), pages 259-269.
    4. Lopes, Thiago Cantos & Sikora, C.G.S. & Molina, Rafael Gobbi & Schibelbain, Daniel & Rodrigues, L.C.A. & Magatão, Leandro, 2017. "Balancing a robotic spot welding manufacturing line: An industrial case study," European Journal of Operational Research, Elsevier, vol. 263(3), pages 1033-1048.
    5. 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.
    6. Atiya Al-Zuheri & Lee Luong & Ke Xing, 2016. "Developing a multi-objective genetic optimisation approach for an operational design of a manual mixed-model assembly line with walking workers," Journal of Intelligent Manufacturing, Springer, vol. 27(5), pages 1049-1065, October.
    7. Sternatz, Johannes, 2015. "The joint line balancing and material supply problem," International Journal of Production Economics, Elsevier, vol. 159(C), pages 304-318.
    8. 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.
    9. Boysen, Nils & Schulze, Philipp & Scholl, Armin, 2022. "Assembly line balancing: What happened in the last fifteen years?," European Journal of Operational Research, Elsevier, vol. 301(3), pages 797-814.
    10. Pereira, Jordi & Álvarez-Miranda, Eduardo, 2018. "An exact approach for the robust assembly line balancing problem," Omega, Elsevier, vol. 78(C), pages 85-98.
    11. Rasul Esmaeilbeigi & Bahman Naderi & Parisa Charkhgard, 2016. "New formulations for the setup assembly line balancing and scheduling problem," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 38(2), pages 493-518, March.
    12. Koltai, Tamás & Dimény, Imre & Gallina, Viola & Gaal, Alexander & Sepe, Chiara, 2021. "An analysis of task assignment and cycle times when robots are added to human-operated assembly lines, using mathematical programming models," International Journal of Production Economics, Elsevier, vol. 242(C).
    13. Sikora, Celso Gustavo Stall & Lopes, Thiago Cantos & Magatão, Leandro, 2017. "Traveling worker assembly line (re)balancing problem: Model, reduction techniques, and real case studies," European Journal of Operational Research, Elsevier, vol. 259(3), pages 949-971.
    14. 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.
    15. 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.
    16. Eduardo Álvarez-Miranda & Jordi Pereira & Harold Torrez-Meruvia & Mariona Vilà, 2021. "A Hybrid Genetic Algorithm for the Simple Assembly Line Balancing Problem with a Fixed Number of Workstations," Mathematics, MDPI, vol. 9(17), pages 1-19, September.
    17. 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.
    18. Jietao Dong & Linxuan Zhang & Tianyuan Xiao, 2018. "A hybrid PSO/SA algorithm for bi-criteria stochastic line balancing with flexible task times and zoning constraints," Journal of Intelligent Manufacturing, Springer, vol. 29(4), pages 737-751, April.

    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. 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.
    2. 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.
    3. 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.
    4. 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.
    5. 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.
    6. Boysen, Nils & Schulze, Philipp & Scholl, Armin, 2022. "Assembly line balancing: What happened in the last fifteen years?," European Journal of Operational Research, Elsevier, vol. 301(3), pages 797-814.
    7. 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.
    8. 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.
    9. 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.
    10. 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.
    11. 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.
    12. Walter, Rico & Schulze, Philipp & Scholl, Armin, 2021. "SALSA: Combining branch-and-bound with dynamic programming to smoothen workloads in simple assembly line balancing," European Journal of Operational Research, Elsevier, vol. 295(3), pages 857-873.
    13. Sternatz, Johannes, 2015. "The joint line balancing and material supply problem," International Journal of Production Economics, Elsevier, vol. 159(C), pages 304-318.
    14. 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.
    15. 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.
    16. 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.
    17. Lopes, Thiago Cantos & Pastre, Giuliano Vidal & Michels, Adalberto Sato & Magatão, Leandro, 2020. "Flexible multi-manned assembly line balancing problem: Model, heuristic procedure, and lower bounds for line length minimization," Omega, Elsevier, vol. 95(C).
    18. Lopes, Thiago Cantos & Sikora, C.G.S. & Molina, Rafael Gobbi & Schibelbain, Daniel & Rodrigues, L.C.A. & Magatão, Leandro, 2017. "Balancing a robotic spot welding manufacturing line: An industrial case study," European Journal of Operational Research, Elsevier, vol. 263(3), pages 1033-1048.
    19. 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.
    20. Peeters, Marc & Degraeve, Zeger, 2006. "An linear programming based lower bound for the simple assembly line balancing problem," European Journal of Operational Research, Elsevier, vol. 168(3), pages 716-731, February.

    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:ejores:v:200:y:2010:i:3:p:688-701. See general information about how to correct material in RePEc.

    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/eor .

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

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.