IDEAS home Printed from https://ideas.repec.org/a/spr/annopr/v335y2024i1d10.1007_s10479-023-05809-1.html
   My bibliography  Save this article

Chance-constrained stochastic assembly line balancing with branch, bound and remember algorithm

Author

Listed:
  • Zixiang Li

    (Wuhan University of Science and Technology
    Wuhan University of Science and Technology)

  • Celso Gustavo Stall Sikora

    (University of Hamburg)

  • Ibrahim Kucukkoc

    (Balikesir University)

Abstract

Assembly lines are widely used mass production techniques applied in various industries from electronics to automotive and aerospace. A branch, bound, and remember (BBR) algorithm is presented in this research to tackle the chance-constrained stochastic assembly line balancing problem (ALBP). In this problem variation, the processing times are stochastic, while the cycle time must be respected for a given probability. The proposed BBR method stores all the searched partial solutions in memory and utilizes the cyclic best-first search strategy to quickly achieve high-quality complete solutions. Meanwhile, this study also develops several new lower bounds and dominance rules by taking the stochastic task times into account. To evaluate the performance of the developed method, a large set of 1614 instances is generated and solved. The performance of the BBR algorithm is compared with two mixed-integer programming models and twenty re-implemented heuristics and metaheuristics, including the well-known genetic algorithm, ant colony optimization algorithm and simulated annealing algorithm. The comparative study demonstrates that the mathematical models cannot achieve high-quality solutions when solving large-size instances, for which the BBR algorithm shows clear superiority over the mathematical models. The developed BBR outperforms all the compared heuristic and metaheuristic methods and is the new state-of-the-art methodology for the stochastic ALBP.

Suggested Citation

  • Zixiang Li & Celso Gustavo Stall Sikora & Ibrahim Kucukkoc, 2024. "Chance-constrained stochastic assembly line balancing with branch, bound and remember algorithm," Annals of Operations Research, Springer, vol. 335(1), pages 491-516, April.
  • Handle: RePEc:spr:annopr:v:335:y:2024:i:1:d:10.1007_s10479-023-05809-1
    DOI: 10.1007/s10479-023-05809-1
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10479-023-05809-1
    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-023-05809-1?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. Zixiang Li & Zeynel Abidin Çil & Süleyman Mete & Ibrahim Kucukkoc, 2020. "A fast branch, bound and remember algorithm for disassembly line balancing problem," International Journal of Production Research, Taylor & Francis Journals, vol. 58(11), pages 3220-3234, June.
    2. 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.
    3. Yuchen Li & Ibrahim Kucukkoc & Xiaowen Tang, 2021. "Two-sided assembly line balancing that considers uncertain task time attributes and incompatible task sets," International Journal of Production Research, Taylor & Francis Journals, vol. 59(6), pages 1736-1756, March.
    4. Borba, Leonardo & Ritt, Marcus & Miralles, Cristóbal, 2018. "Exact and heuristic methods for solving the Robotic Assembly Line Balancing Problem," European Journal of Operational Research, Elsevier, vol. 270(1), pages 146-156.
    5. 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.
    6. 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.
    7. 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.
    8. Runyu Li & Gang Liu, 2017. "An uncertain goal programming model for machine scheduling problem," Journal of Intelligent Manufacturing, Springer, vol. 28(3), pages 689-694, March.
    9. Kucukkoc, Ibrahim & Li, Zixiang & Karaoglan, Aslan D. & Zhang, David Z., 2018. "Balancing of mixed-model two-sided assembly lines with underground workstations: A mathematical model and ant colony optimization algorithm," International Journal of Production Economics, Elsevier, vol. 205(C), pages 228-243.
    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. 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.
    12. Lai, Tsung-Chyan & Sotskov, Yuri N. & Dolgui, Alexandre, 2019. "The stability radius of an optimal line balance with maximum efficiency for a simple assembly line," European Journal of Operational Research, Elsevier, vol. 274(2), pages 466-481.
    13. 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).
    14. Robert L. Carraway, 1989. "A Dynamic Programming Approach to Stochastic Assembly Line Balancing," Management Science, INFORMS, vol. 35(4), pages 459-471, April.
    15. 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.
    16. Xiaobo Zhao & Jianyong Liu & Katsuhisa Ohno & Shigenori Kotani, 2007. "Modeling and analysis of a mixed‐model assembly line with stochastic operation times," Naval Research Logistics (NRL), John Wiley & Sons, vol. 54(6), pages 681-691, September.
    17. Morrison, David R. & Sewell, Edward C. & Jacobson, Sheldon H., 2014. "An application of the branch, bound, and remember algorithm to a new simple assembly line balancing dataset," European Journal of Operational Research, Elsevier, vol. 236(2), pages 403-409.
    18. Wenqiang Zhang & Weitao Xu & Gang Liu & Mitsuo Gen, 2017. "An effective hybrid evolutionary algorithm for stochastic multiobjective assembly line balancing problem," Journal of Intelligent Manufacturing, Springer, vol. 28(3), pages 783-790, March.
    19. Yufu Ning & Taoyong Su, 2017. "A multilevel approach for modelling vehicle routing problem with uncertain travelling time," Journal of Intelligent Manufacturing, Springer, vol. 28(3), pages 683-688, March.
    20. 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.
    21. Diefenbach, Johannes & Stolletz, Raik, 2022. "Stochastic assembly line balancing: General bounds and reliability-based branch-and-bound algorithm," European Journal of Operational Research, Elsevier, vol. 302(2), pages 589-605.
    22. Emel Kızılkaya Aydoğan & Yılmaz Delice & Uğur Özcan & Cevriye Gencer & Özkan Bali, 2019. "Balancing stochastic U-lines using particle swarm optimization," Journal of Intelligent Manufacturing, Springer, vol. 30(1), pages 97-111, January.
    23. Ö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.
    24. Chiang, Wen-Chyuan & Urban, Timothy L., 2006. "The stochastic U-line balancing problem: A heuristic procedure," European Journal of Operational Research, Elsevier, vol. 175(3), pages 1767-1781, December.
    25. Yılmaz Delice & Emel Kızılkaya Aydoğan & Uğur Özcan, 2016. "Stochastic two-sided U-type assembly line balancing: a genetic algorithm approach," International Journal of Production Research, Taylor & Francis Journals, vol. 54(11), pages 3429-3451, June.
    26. 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.
    27. Li, Zixiang & Kucukkoc, Ibrahim & Zhang, Zikai, 2020. "Branch, bound and remember algorithm for two-sided assembly line balancing problem," European Journal of Operational Research, Elsevier, vol. 284(3), pages 896-905.
    28. 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.
    29. Evgeny Gurevsky & Olga Battaïa & Alexandre Dolgui, 2012. "Balancing of simple assembly lines under variations of task processing times," Annals of Operations Research, Springer, vol. 201(1), pages 265-286, December.
    30. 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.
    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. 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).
    2. 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.
    3. Diefenbach, Johannes & Stolletz, Raik, 2022. "Stochastic assembly line balancing: General bounds and reliability-based branch-and-bound algorithm," European Journal of Operational Research, Elsevier, vol. 302(2), pages 589-605.
    4. Pereira, Jordi & Álvarez-Miranda, Eduardo, 2018. "An exact approach for the robust assembly line balancing problem," Omega, Elsevier, vol. 78(C), pages 85-98.
    5. Li, Zixiang & Kucukkoc, Ibrahim & Zhang, Zikai, 2020. "Branch, bound and remember algorithm for two-sided assembly line balancing problem," European Journal of Operational Research, Elsevier, vol. 284(3), pages 896-905.
    6. Sikora, Celso Gustavo Stall, 2024. "Balancing mixed-model assembly lines for random sequences," European Journal of Operational Research, Elsevier, vol. 314(2), pages 597-611.
    7. Shibasaki, Rui S. & Rossi, André & Gurevsky, Evgeny, 2024. "A new upper bound based on Dantzig-Wolfe decomposition to maximize the stability radius of a simple assembly line under uncertainty," European Journal of Operational Research, Elsevier, vol. 313(3), pages 1015-1030.
    8. Urban, Timothy L. & Chiang, Wen-Chyuan, 2016. "Designing energy-efficient serial production lines: The unpaced synchronous line-balancing problem," European Journal of Operational Research, Elsevier, vol. 248(3), pages 789-801.
    9. Schmid, Nico André & Montreuil, Benoit & Limère, Veronique, 2024. "Modeling and solving integrated assembly line balancing, assembly line feeding, and facility sizing problems," International Journal of Production Economics, Elsevier, vol. 277(C).
    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. Marcel Albus & Timothée Hornek & Werner Kraus & Marco F. Huber, 2025. "Towards scalability for resource reconfiguration in robotic assembly line balancing problems using a modified genetic algorithm," Journal of Intelligent Manufacturing, Springer, vol. 36(2), pages 1175-1199, February.
    12. Marcus Ritt & Alysson M. Costa & Cristóbal Miralles, 2016. "The assembly line worker assignment and balancing problem with stochastic worker availability," International Journal of Production Research, Taylor & Francis Journals, vol. 54(3), pages 907-922, February.
    13. Lai, Tsung-Chyan & Sotskov, Yuri N. & Dolgui, Alexandre & Zatsiupa, Aksana, 2016. "Stability radii of optimal assembly line balances with a fixed workstation set," International Journal of Production Economics, Elsevier, vol. 182(C), pages 356-371.
    14. Bentaha, Mohand Lounes & Battaïa, Olga & Dolgui, Alexandre & Hu, S. Jack, 2015. "Second order conic approximation for disassembly line design with joint probabilistic constraints," European Journal of Operational Research, Elsevier, vol. 247(3), pages 957-967.
    15. 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.
    16. Wen-Chyuan Chiang & Timothy L. Urban & Chunyong Luo, 2016. "Balancing stochastic two-sided assembly lines," International Journal of Production Research, Taylor & Francis Journals, vol. 54(20), pages 6232-6250, October.
    17. 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).
    18. 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).
    19. Li, Mingxing & Huang, George Q., 2021. "Production-intralogistics synchronization of industry 4.0 flexible assembly lines under graduation intelligent manufacturing system," International Journal of Production Economics, Elsevier, vol. 241(C).
    20. Kucukkoc, Ibrahim & Zhang, David Z., 2014. "Mathematical model and agent based solution approach for the simultaneous balancing and sequencing of mixed-model parallel two-sided assembly lines," International Journal of Production Economics, Elsevier, vol. 158(C), pages 314-333.

    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:335:y:2024:i:1:d:10.1007_s10479-023-05809-1. 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.