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

Multi-manned assembly line balancing problem with dependent task times: a heuristic based on solving a partition problem with constraints

Author

Listed:
  • Andreu-Casas, Enric
  • García-Villoria, Alberto
  • Pastor, Rafael

Abstract

This paper aims to study a variant of the multi-manned assembly line balancing problem (MALBP), which considers the possibility of multiple workers simultaneously performing different tasks at the same workstation. In most cases it is assumed that task times are deterministic. This paper takes into account possible interferences between workers and deals with the MALBP with task times depending on the number of workers at the station. Different procedures are developed: resolutions on the basis of a mathematical model, two Relax-and-Fix procedures, a heuristic based on solving a partition problem with constraints (named “HEUR_PART”) and a set of other variants of the HEUR_PART procedure. The computational experiments indicate that HEUR_PART and the HEUR_PART_SGL variant are the proposals that perform best. Additionally, we show that they obtain better results than the ones published in the literature.

Suggested Citation

  • Andreu-Casas, Enric & García-Villoria, Alberto & Pastor, Rafael, 2022. "Multi-manned assembly line balancing problem with dependent task times: a heuristic based on solving a partition problem with constraints," European Journal of Operational Research, Elsevier, vol. 302(1), pages 96-116.
    • Handle: RePEc:eee:ejores:v:302:y:2022:i:1:p:96-116
    DOI: 10.1016/j.ejor.2021.12.002
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221721010080
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2021.12.002?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. Michels, Adalberto Sato & Lopes, Thiago Cantos & Sikora, Celso Gustavo Stall & Magatão, Leandro, 2019. "A Benders’ decomposition algorithm with combinatorial cuts for the multi-manned assembly line balancing problem," European Journal of Operational Research, Elsevier, vol. 278(3), pages 796-808.
    2. 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).
    3. Talip Kellegöz & Bilal Toklu, 2015. "A priority rule-based constructive heuristic and an improvement method for balancing assembly lines with parallel multi-manned workstations," International Journal of Production Research, Taylor & Francis Journals, vol. 53(3), pages 736-756, February.
    4. Thomas R. Hoffmann, 1963. "Assembly Line Balancing with a Precedence Matrix," Management Science, INFORMS, vol. 9(4), pages 551-562, July.
    5. 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.
    6. Murat Şahin & Talip Kellegöz, 2019. "Balancing Multi-Manned Assembly Lines With Walking Workers: Problem Definition, Mathematical Formulation, and an Electromagnetic Field Optimisation Algorithm," International Journal of Production Research, Taylor & Francis Journals, vol. 57(20), pages 6487-6505, October.
    7. Abdolreza Roshani & Davide Giglio, 2017. "Simulated annealing algorithms for the multi-manned assembly line balancing problem: minimising cycle time," International Journal of Production Research, Taylor & Francis Journals, vol. 55(10), pages 2731-2751, May.
    8. Ding, Fong-Yuen & Zhu, Jin & Sun, Hui, 2006. "Comparing two weighted approaches for sequencing mixed-model assembly lines with multiple objectives," International Journal of Production Economics, Elsevier, vol. 102(1), pages 108-131, July.
    9. 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.
    10. 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.
    11. Abolfazl Kazemi & Abdolhossein Sedighi, 2013. "A cost-oriented model for balancing mixed-model assembly lines with multi-manned workstations," International Journal of Services and Operations Management, Inderscience Enterprises Ltd, vol. 16(3), pages 289-309.
    12. 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.
    13. Wucheng Yang & Wenming Cheng, 2020. "A Mathematical Model and a Simulated Annealing Algorithm for Balancing Multi-manned Assembly Line Problem with Sequence-Dependent Setup Time," Mathematical Problems in Engineering, Hindawi, vol. 2020, pages 1-16, May.
    14. 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.
    15. Dillenberger, Christof & Escudero, Laureano F. & Wollensak, Artur & Zhang, Wu, 1994. "On practical resource allocation for production planning and scheduling with period overlapping setups," European Journal of Operational Research, Elsevier, vol. 75(2), pages 275-286, June.
    16. García-Villoria, Alberto & Corominas, Albert & Nadal, Adrià & Pastor, Rafael, 2018. "Solving the accessibility windows assembly line problem level 1 and variant 1 (AWALBP-L1-1) with precedence constraints," European Journal of Operational Research, Elsevier, vol. 271(3), pages 882-895.
    17. Rafael Pastor & Alberto García-Villoria & Manuel Laguna & Rafael Martí, 2015. "Metaheuristic procedures for the lexicographic bottleneck assembly line balancing problem," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 66(11), pages 1815-1825, November.
    18. 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.
    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. Murat Şahin & Talip Kellegöz, 2023. "Benders’ decomposition based exact solution method for multi-manned assembly line balancing problem with walking workers," Annals of Operations Research, Springer, vol. 321(1), pages 507-540, February.
    2. Mao, Zhaofang & Sun, Yiting & Fang, Kan & Huang, Dian & Zhang, Jiaxin, 2024. "Balancing and scheduling of assembly line with multi-type collaborative robots," International Journal of Production Economics, Elsevier, vol. 271(C).

    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 & 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.
    2. Battaïa, Olga & Dolgui, Alexandre, 2022. "Hybridizations in line balancing problems: A comprehensive review on new trends and formulations," International Journal of Production Economics, Elsevier, vol. 250(C).
    3. Michels, Adalberto Sato & Lopes, Thiago Cantos & Magatão, Leandro, 2020. "An exact method with decomposition techniques and combinatorial Benders’ cuts for the type-2 multi-manned assembly line balancing problem," Operations Research Perspectives, Elsevier, vol. 7(C).
    4. Murat Şahin & Talip Kellegöz, 2023. "Benders’ decomposition based exact solution method for multi-manned assembly line balancing problem with walking workers," Annals of Operations Research, Springer, vol. 321(1), pages 507-540, February.
    5. 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).
    6. Michels, Adalberto Sato & Lopes, Thiago Cantos & Sikora, Celso Gustavo Stall & Magatão, Leandro, 2019. "A Benders’ decomposition algorithm with combinatorial cuts for the multi-manned assembly line balancing problem," European Journal of Operational Research, Elsevier, vol. 278(3), pages 796-808.
    7. Hashemi-Petroodi, S. Ehsan & Thevenin, Simon & Kovalev, Sergey & Dolgui, Alexandre, 2022. "Model-dependent task assignment in multi-manned mixed-model assembly lines with walking workers," Omega, Elsevier, vol. 113(C).
    8. Hashemi-Petroodi, S. Ehsan & Thevenin, Simon & Kovalev, Sergey & Dolgui, Alexandre, 2023. "Markov decision process for multi-manned mixed-model assembly lines with walking workers," International Journal of Production Economics, Elsevier, vol. 255(C).
    9. Sternatz, Johannes, 2015. "The joint line balancing and material supply problem," International Journal of Production Economics, Elsevier, vol. 159(C), pages 304-318.
    10. 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.
    11. Talip Kellegöz, 2017. "Assembly line balancing problems with multi-manned stations: a new mathematical formulation and Gantt based heuristic method," Annals of Operations Research, Springer, vol. 253(1), pages 377-404, June.
    12. Ömer Faruk Yılmaz & Büşra Yazıcı, 2022. "Tactical level strategies for multi-objective disassembly line balancing problem with multi-manned stations: an optimization model and solution approaches," Annals of Operations Research, Springer, vol. 319(2), pages 1793-1843, December.
    13. 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.
    14. 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.
    15. Christian Weckenborg & Karsten Kieckhäfer & Christoph Müller & Martin Grunewald & Thomas S. Spengler, 2020. "Balancing of assembly lines with collaborative robots," Business Research, Springer;German Academic Association for Business Research, vol. 13(1), pages 93-132, April.
    16. Thiago Cantos Lopes & Celso Gustavo Stall Sikora & Adalberto Sato Michels & Leandro Magatão, 2020. "Mixed-model assembly lines balancing with given buffers and product sequence: model, formulation comparisons, and case study," Annals of Operations Research, Springer, vol. 286(1), pages 475-500, March.
    17. 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.
    18. 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.
    19. 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.
    20. 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.

    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:302:y:2022:i:1:p:96-116. 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.