IDEAS home Printed from https://ideas.repec.org/a/spr/annopr/v321y2023i1d10.1007_s10479-022-05118-z.html
   My bibliography  Save this article

Benders’ decomposition based exact solution method for multi-manned assembly line balancing problem with walking workers

Author

Listed:
  • Murat Şahin

    (Celal Bayar University
    Gazi University)

  • Talip Kellegöz

    (Gazi University)

Abstract

This article considers multi-manned assembly line balancing problems with walking workers. The objective of the problem is the minimization of number of workers and workstations simultaneously. Several exact-solution algorithms based on Benders’ decomposition are proposed to solve the problem optimally. In one of the algorithms a constructive heuristic that generates effective task-worker assignments and some problem-specific symmetry breaking constraints are used. Moreover, the solutions obtained by meta-heuristic in the literature are used as starting points to increase the performance of proposed decomposition methods. A benchmark set of 99 instances are used to analyze the performance of the proposed exact methods, contribution of the developed heuristic and the ability of Benders’ decomposition on improving the starting solutions. Our results indicate a significiant improvement in the optimal solvability of the problem for larger-sized instances. Suggested methods also improve the results of the meta-heuristic method for significant number of instances. Consequntly, proposed methods solved most of instances optimally and they are able to find the optimal solutions of 17 instances that cannot be solved optimally with previous methods.

Suggested Citation

  • 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.
    • Handle: RePEc:spr:annopr:v:321:y:2023:i:1:d:10.1007_s10479-022-05118-z
    DOI: 10.1007/s10479-022-05118-z
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10479-022-05118-z
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10479-022-05118-z?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. Emre Cevikcan & Dicle Aslan & Fatma Betul Yeni, 2020. "Disassembly line design with multi-manned workstations: a novel heuristic optimisation approach," International Journal of Production Research, Taylor & Francis Journals, vol. 58(3), pages 649-670, February.
    5. 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.
    6. 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.
    7. Bahman Naderi & Ahmed Azab & Katayoun Borooshan, 2019. "A realistic multi-manned five-sided mixed-model assembly line balancing and scheduling problem with moving workers and limited workspace," International Journal of Production Research, Taylor & Francis Journals, vol. 57(3), pages 643-661, February.
    8. John J. Bartholdi & Donald D. Eisenstein, 1996. "A Production Line that Balances Itself," Operations Research, INFORMS, vol. 44(1), pages 21-34, February.
    9. Akpinar, Sener & Elmi, Atabak & Bektaş, Tolga, 2017. "Combinatorial Benders cuts for assembly line balancing problems with setups," European Journal of Operational Research, Elsevier, vol. 259(2), pages 527-537.
    10. 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.
    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. 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.
    13. 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.
    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. 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).
    16. Rahmaniani, Ragheb & Crainic, Teodor Gabriel & Gendreau, Michel & Rei, Walter, 2017. "The Benders decomposition algorithm: A literature review," European Journal of Operational Research, Elsevier, vol. 259(3), pages 801-817.
    17. Gianni Codato & Matteo Fischetti, 2006. "Combinatorial Benders' Cuts for Mixed-Integer Linear Programming," Operations Research, INFORMS, vol. 54(4), pages 756-766, August.
    18. Dian Huang & Zhaofang Mao & Kan Fang & Biao Yuan, 2022. "Combinatorial Benders decomposition for mixed-model two-sided assembly line balancing problem," International Journal of Production Research, Taylor & Francis Journals, vol. 60(8), pages 2598-2624, 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. 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).
    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 & 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.
    4. 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.
    5. 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.
    6. 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).
    7. 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).
    8. 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).
    9. Ö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.
    10. Hassan Zohali & Bahman Naderi & Vahid Roshanaei, 2022. "Solving the Type-2 Assembly Line Balancing with Setups Using Logic-Based Benders Decomposition," INFORMS Journal on Computing, INFORMS, vol. 34(1), pages 315-332, January.
    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. Han, Jialin & Zhang, Jiaxiang & Zeng, Bing & Mao, Mingsong, 2021. "Optimizing dynamic facility location-allocation for agricultural machinery maintenance using Benders decomposition," Omega, Elsevier, vol. 105(C).
    13. 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.
    14. Fang, Kan & Wang, Shijin & Pinedo, Michael L. & Chen, Lin & Chu, Feng, 2021. "A combinatorial Benders decomposition algorithm for parallel machine scheduling with working-time restrictions," European Journal of Operational Research, Elsevier, vol. 291(1), pages 128-146.
    15. 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.
    16. Maher, Stephen J., 2021. "Implementing the branch-and-cut approach for a general purpose Benders’ decomposition framework," European Journal of Operational Research, Elsevier, vol. 290(2), pages 479-498.
    17. William B. Haskell & Wenjie Huang & Huifu Xu, 2018. "Preference Elicitation and Robust Optimization with Multi-Attribute Quasi-Concave Choice Functions," Papers 1805.06632, arXiv.org.
    18. Clavijo López, Christian & Crama, Yves & Pironet, Thierry & Semet, Frédéric, 2024. "Multi-period distribution networks with purchase commitment contracts," European Journal of Operational Research, Elsevier, vol. 312(2), pages 556-572.
    19. Belieres, Simon & Hewitt, Mike & Jozefowiez, Nicolas & Semet, Frédéric & Van Woensel, Tom, 2020. "A Benders decomposition-based approach for logistics service network design," European Journal of Operational Research, Elsevier, vol. 286(2), pages 523-537.
    20. Ö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.

    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:spr:annopr:v:321:y:2023:i:1:d:10.1007_s10479-022-05118-z. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    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.