IDEAS home Printed from https://ideas.repec.org/a/eee/jomega/v78y2018icp85-98.html
   My bibliography  Save this article

An exact approach for the robust assembly line balancing problem

Author

Listed:
  • Pereira, Jordi
  • Álvarez-Miranda, Eduardo

Abstract

This work studies an assembly line balancing problem with uncertainty on the task times. In order to deal with the uncertainty, a robust formulation to handle changes in the operation times is put forward. In order to solve the problem, several lower bounds, dominance rules and an enumeration procedure are proposed. These methods are tested in a computational experiment using different instances derived from the literature and then compared to similar previous approaches. The results of the experiment show that the method is able to solve larger instances in shorter running times. Furthermore, the cost of protecting a solution against uncertainty is also investigated. The results highlight that protecting an assembly line against moderate levels of uncertainty can be achieved at the expense of small quantities of additional resources (stations).

Suggested Citation

  • Pereira, Jordi & Álvarez-Miranda, Eduardo, 2018. "An exact approach for the robust assembly line balancing problem," Omega, Elsevier, vol. 78(C), pages 85-98.
    • Handle: RePEc:eee:jomega:v:78:y:2018:i:c:p:85-98
    DOI: 10.1016/j.omega.2017.08.020
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0305048316310325
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.omega.2017.08.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. 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.
    2. Jordi Pereira, 2015. "Empirical evaluation of lower bounding methods for the simple assembly line balancing problem," International Journal of Production Research, Taylor & Francis Journals, vol. 53(11), pages 3327-3340, June.
    3. 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.
    4. 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.
    5. 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.
    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. Gabrel, Virginie & Murat, Cécile & Thiele, Aurélie, 2014. "Recent advances in robust optimization: An overview," European Journal of Operational Research, Elsevier, vol. 235(3), pages 471-483.
    8. 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.
    9. Pereira, Jordi, 2016. "Procedures for the bin packing problem with precedence constraints," European Journal of Operational Research, Elsevier, vol. 250(3), pages 794-806.
    10. 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.
    11. 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.
    12. Dimitris Bertsimas & Melvyn Sim, 2004. "The Price of Robustness," Operations Research, INFORMS, vol. 52(1), pages 35-53, February.
    13. 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.
    14. 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.
    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. 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.
    17. 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.
    18. 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.
    19. 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.
    20. 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.
    21. 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.
    22. 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.
    23. 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.
    24. E Gurevsky & Ö Hazır & O Battaïa & A Dolgui, 2013. "Robust balancing of straight assembly lines with interval task times☆," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 64(11), pages 1607-1613, November.
    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. 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).
    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. 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.
    4. 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).
    5. 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).
    6. 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.

    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. Pereira, Jordi, 2016. "Procedures for the bin packing problem with precedence constraints," European Journal of Operational Research, Elsevier, vol. 250(3), pages 794-806.
    4. 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.
    5. 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.
    6. Jordi Pereira & Mariona Vilà, 2016. "A new model for supply chain network design with integrated assembly line balancing decisions," International Journal of Production Research, Taylor & Francis Journals, vol. 54(9), pages 2653-2669, May.
    7. 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.
    8. 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.
    9. 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).
    10. 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.
    11. Sternatz, Johannes, 2015. "The joint line balancing and material supply problem," International Journal of Production Economics, Elsevier, vol. 159(C), pages 304-318.
    12. Orlando Rivera Letelier & François Clautiaux & Ruslan Sadykov, 2022. "Bin Packing Problem with Time Lags," INFORMS Journal on Computing, INFORMS, vol. 34(4), pages 2249-2270, July.
    13. Raphael Kramer & Mauro Dell’Amico & Manuel Iori, 2017. "A batching-move iterated local search algorithm for the bin packing problem with generalized precedence constraints," International Journal of Production Research, Taylor & Francis Journals, vol. 55(21), pages 6288-6304, November.
    14. Calleja, Gema & Corominas, Albert & García-Villoria, Alberto & Pastor, Rafael, 2016. "Hybrid metaheuristics for the Accessibility Windows Assembly Line Balancing Problem Level 2 (AWALBP-L2)," European Journal of Operational Research, Elsevier, vol. 250(3), pages 760-772.
    15. 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.
    16. 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.
    17. 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.
    18. 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.
    19. 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.
    20. Minghai Yuan & Hongyan Yu & Jinting Huang & Aimin Ji, 2019. "Reconfigurable assembly line balancing for cloud manufacturing," Journal of Intelligent Manufacturing, Springer, vol. 30(6), pages 2391-2405, 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:eee:jomega:v:78:y:2018:i:c:p:85-98. 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/wps/find/journaldescription.cws_home/375/description#description .

    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.