Solving stochastic multi-manned U-shaped assembly line balancing problem using differential evolution algorithm

Mohammad Zakaraia; Hegazy Zaher; Naglaa Ragaa

doi:10.4995/ijpme.2021.16084

Authors

Mohammad Zakaraia Cairo University
Hegazy Zaher Cairo University
Naglaa Ragaa Cairo University

DOI:

https://doi.org/10.4995/ijpme.2021.16084

Keywords:

Metaheurisitcs, Differential evolution algorithm, U-shaped assembly line balancing problem, Multi-manned assembly line balancing problem, Chance-constrained programming

Abstract

The U-shaped assembly lines help to have more flexibility than the straight assembly lines, where the operators can perform tasks in both sides of the line, the entrance and the exit sides. Having more than one operator in any station of the line can reduce the line length and thereby affects the number of produced products. This paper combines the U-shaped assembly line balancing problem with the multi-manned assembly line balancing problem in one problem. In addition, the processing times of the tasks are considered as stochastic, where they are represented as random variables with known means and variances. The problem is formulated as a mixed-integer linear programming and the cycle time constraints are formulated as chance-constraints. The proposed algorithm for solving the problem is a differential evolution algorithm. The parameter of the algorithm is optimized using experimental design and the computational results are done on 71 adapted problems selected from well-known benchmarks.

Downloads

Download data is not yet available.

Author Biographies

Mohammad Zakaraia, Cairo University

PhD candidate in operations research, Faculty of graduate studies for statistical research

Hegazy Zaher, Cairo University

Professor Doctor in mathematical statistics, Faculty of graduate studies for statistical research

Naglaa Ragaa, Cairo University

Associate professor in operations research, Faculty of graduate studies for statistical research

References

Abidin Çil, Zeynel, & Damla Kizilay. 2020. Constraint Programming Model for Multi-Manned Assembly Line Balancing Problem. Computers and Operations Research, 124, 105069. https://doi.org/10.1016/j.cor.2020.105069

Ajenblit, Debora A., & Roger L. Wainwright. 1998. Applying Genetic Algorithms to the U-Shaped Assembly Line Balancing Problem. Proceedings of the IEEE Conference on Evolutionary Computation, ICEC, 96-101. https://doi.org/10.1109/ICEC.1998.699329

Fathi, Masood, María Jesús Álvarez, & Victoria Rodríguez. 2016. A New Heuristic-Based Bi-Objective Simulated Annealing Method for U-Shaped Assembly Line Balancing. European Journal of Industrial Engineering, 10(2), 145-169. https://doi.org/10.1504/EJIE.2016.075849

Fattahi, Parviz, Abdolreza Roshani, & Abdolhassan Roshani. 2011a. A Mathematical Model and Ant Colony Algorithm for MultiManned Assembly Line Balancing Problem. International Journal of Advanced Manufacturing Technology, 53(1-4), 363-378. https://doi.org/10.1007/s00170-010-2832-y

Gökçen, Hadi, Kürşad Ağpak, & Recep Benzer. 2006. Balancing of Parallel Assembly Lines. International Journal of Production Economics, 103(2), 600-609. https://doi.org/10.1016/j.ijpe.2005.12.001

Hamzadayi, Alper, & Gokalp Yildiz. 2012. A Genetic Algorithm Based Approach for Simultaneously Balancing and Sequencing of Mixed-Model U-Lines with Parallel Workstations and Zoning Constraints. Computers and Industrial Engineering, 62(1), 206-215. https://doi.org/10.1016/j.cie.2011.09.008

Hamzadayi, Alper, & Gokalp Yildiz. 2013. A Simulated Annealing Algorithm Based Approach for Balancing and Sequencing of Mixed-Model U-Lines. Computers and Industrial Engineering, 66(4), 1070-1084. https://doi.org/10.1016/j.cie.2013.08.008

Jayaswal, Sachin, & Prashant Agarwal. 2014. Balancing U-Shaped Assembly Lines with Resource Dependent Task Times: A Simulated Annealing Approach. Journal of Manufacturing Systems, 33(4), 522-534. https://doi.org/10.1016/j.jmsy.2014.05.002

Kara, Yakup, Cemal Özgüven, Neşe Yalçin, & Yakup Atasagun. 2011. Balancing Straight and U-Shaped Assembly Lines with Resource Dependent Task Times. International Journal of Production Research, 49(21), 6387-6405. https://doi.org/10.1080/00207543.2010.535039

Kellegöz, Talip. 2017. Assembly Line Balancing Problems with Multi-Manned Stations: A New Mathematical Formulation and Gantt Based Heuristic Method. Annals of Operations Research, 253(1), 377-404. https://doi.org/10.1007/s10479-016-2156-x

Kellegöz, Talip, & 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, 53(3), 736-756. https://doi.org/10.1080/00207543.2014.920548

Kucukkoc, Ibrahim, & David Z. Zhang. 2015. Balancing of Parallel U-Shaped Assembly Lines. Vol. 64. Virginia Tech. https://doi.org/10.1016/j.cor.2015.05.014

Li, Ming, Qiuhua Tang, Qiaoxian Zheng, Xuhui Xia, & C. A. Floudas. 2017. Rules-Based Heuristic Approach for the U-Shaped Assembly Line Balancing Problem. Applied Mathematical Modelling, 48(2017), 423-439. https://doi.org/10.1016/j.apm.2016.12.031

Li, Zixiang, Mukund Nilakantan Janardhanan, & Humyun Fuad Rahman. 2021. Enhanced Beam Search Heuristic for U-Shaped Assembly Line Balancing Problems. Engineering Optimization, 53(4), 594-608. https://doi.org/10.1080/0305215X.2020.1741569

Michels, Adalberto Sato, Tiago Cantos Lopes, Celso Gustavo Stall Sikora, & Leandro Magatão. 2018. With Practical Extensions The Robotic Assembly Line Design ( RALD ) Problem: Model and Case Studies with Practical Extensions. Computers & Industrial Engineering, 120, 320-333. https://doi.org/10.1016/j.cie.2018.04.010

Michels, Adalberto Sato, Thiago Cantos Lopes, Celso Gustavo Stall Sikora, & Leandro Magatão. 2019. A Benders' Decomposition Algorithm with Combinatorial Cuts for the Multi-Manned Assembly Line Balancing Problem. European Journal of Operational Research, 278(3), 796-808. https://doi.org/10.1016/j.ejor.2019.05.001

Miltenburg, G.J., & J. Wijngaard. 1994. U-Line Line Balancing Problem. Management Science, 40(10), 1378-1388. https://doi.org/10.1287/mnsc.40.10.1378

Nourmohammadi, Amir, Masood Fathi, Mostafa Zandieh, & Morteza Ghobakhloo. 2019. A Water-Flow like Algorithm for Solving U-Shaped Assembly Line Balancing Problems. IEEE Access, 7, 129824-129833. https://doi.org/10.1109/ACCESS.2019.2939724

Oksuz, Mehmet Kursat, Kadir Buyukozkan, & Sule Itir Satoglu. 2017. U-Shaped Assembly Line Worker Assignment and Balancing Problem: A Mathematical Model and Two Meta-Heuristics. Computers and Industrial Engineering, 112, 246-263. https://doi.org/10.1016/j.cie.2017.08.030

Rabbani, Masoud, Seyed Mahmood Kazemi, & Neda Manavizadeh. 2012. Mixed Model U-Line Balancing Type-1 Problem: A New Approach. Journal of Manufacturing Systems, 31(2), 131-138. https://doi.org/10.1016/j.jmsy.2012.02.002

Sabuncuoglu, Ihsan, Erdal Erel, & Arda Alp. 2009. Ant Colony Optimization for the Single Model U-Type Assembly Line Balancing Problem. International Journal of Production Economics, 120(2), 287-300. https://doi.org/10.1016/j.ijpe.2008.11.017

Scholl, A., & R. Klein. 1999. ULINO: Optimally Balancing U-Shaped JIT Assembly Lines. International Journal of Production Research, 37(4), 721-736. https://doi.org/10.1080/002075499191481

Sresracoo, Poontana, Nuchsara Kriengkorakot, Preecha Kriengkorakot, & Krit Chantarasamai. 2018. U-Shaped Assembly Line Balancing by Using Differential Evolution Algorithm. Mathematical and Computational Applications, 23(4), 79. https://doi.org/10.3390/mca23040079

Taha, Hamdy. 2017. Operations Research an Introduction. 10th ed. edited by R. Horton, Marcia; Partridge, Julian; Stark, Holly; Brands, Amanda; Agarwal, Aditee; Raheja. Harlow: Pearson Education Limited.

Yilmaz, Ö.F., Ö.F. Demirel, S. Zaim, & S. Sevim. 2020. Assembly Line Balancing by Using Axiomatic Design Principles: An Application from Cooler Manufacturing Industry. International Journal of Production Management and Engineering, 8(1), 31-43. https://doi.org/10.4995/ijpme.2020.11953

Yılmaz, Faruk. 2020a. Robust Optimization for U-Shaped Assembly Line Worker Assignment and Balancing Problem with Uncertain Task Times¨Omer Times¨ Times¨Omer. CRORR, 11(2), 229-239. https://doi.org/10.17535/crorr.2020.0018

Yılmaz, Ömer Faruk. 2020b. An Integrated Bi-Objective U-Shaped Assembly Line Balancing and Parts Feeding Problem: Optimization Model and Exact Solution Method. Annals of Mathematics and Artificial Intelligence, 1-18. https://doi.org/10.1007/s10472-020-09718-y

Zakaraia, Mohammad, Hegazy Zaher, & Naglaa Ragaa. 2021. Stochastic Local Search for Solving Chance-Constrained MultiManned U-Shaped Assembly Line Balancing Problem with Time and Space Constraints. Journal of University of Shanghai for Science and Technology, 23(04), 278-295. https://doi.org/10.51201/JUSST/21/04242

Zhang, Beikun, & Liyun Xu. 2020. An Improved Flower Pollination Algorithm for Solving a Type-II U-Shaped Assembly Line Balancing Problem with Energy Consideration. Assembly Automation, 40(6), 847-856. https://doi.org/10.1108/AA-07-2019-0144

Zhang, Zikai, Qiuhua Tang, & Manuel Chica. 2020. Multi-Manned Assembly Line Balancing with Time and Space Constraints: A MILP Model and Memetic Ant Colony System. Computers and Industrial Engineering, 150, 106862. https://doi.org/10.1016/j.cie.2020.106862