Rebalancing of multi-manned mixed-model assembly lines with task relocation restrictions

Damla Camli; Ibrahim Kucukkoc; Zixiang Li

doi:10.65112/tcmis.10008

Authors

Damla Camli Continuous Improvement Department, Önen Food Company, Çanakkale, Turkiye https://orcid.org/0000-0002-4862-538X
Ibrahim Kucukkoc Department of Industrial Engineering, Balikesir University, Balikesir, Turkiye https://orcid.org/0000-0001-6042-6896
Zixiang Li Key Laboratory of Metallurgical Equipment and Control Technology of Ministry of Education, Wuhan University of Science and Technology, Wuhan, Hubei, China https://orcid.org/0000-0002-8570-8862

DOI:

https://doi.org/10.65112/tcmis.10008

Keywords:

Mixed-model assembly line, type-E, task relocation restrictions, rebalancing, mixed-integer programming, multi-manned workstations

Abstract

Increasing competition and customized demands have led companies to use assembly lines more flexible and efficiently. Companies need to frequently rebalance their lines to adapt changes either in the product model demand or task processing times. During which, some tasks will be required to assign a different workstation (causing a change in the task allocation) due to the nature of the rebalancing procedure. However, as the number of relocations made during rebalancing increases, the likelihood of costs and quality errors will also arise. This study aims to efficiently balance mixed-model assembly lines while restricting the number of relocations to a limited value. A mixed-integer program is proposed to maximize line efficiency (minimising both cycle time and number of workstations, called type-E) considering the number of task relocations up to a certain value. An iterative algorithm is also developed for solving large-sized problems. The model allows lower and upper bounds to be imposed on the cycle time and aims to avoid ‘substantial’ changes in task assignments during rebalancing. The multi-manned workstation case is also integrated, which gives the advantage of determining the number of operators, i.e., increasing line efficiency. Tests have shown that the heuristic algorithm achieves competitive solutions in compare with the mixed-integer programming model within short periods of time, including large-size problems.

Downloads

Download data is not yet available.

References

[1] I. Baybars, "A Survey of Exact Algorithms for the Simple Assembly Line Balancing Problem," (in English), Management Science, vol. 32, no. 8, pp. 909-932, 1986.

[2] I. Kucukkoc and D. Z. Zhang, "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, vol. 158, pp. 314-333, 2014, doi: http://dx.doi.org/10.1016/j.ijpe.2014.08.010.

[3] O. Battaïa and A. Dolgui, "A taxonomy of line balancing problems and their solution approaches," International Journal of Production Economics, vol. 142, no. 2, pp. 259-277, 2013.

[4] I. Kucukkoc and D. Z. Zhang, "Mixed-model parallel two-sided assembly line balancing problem: A flexible agent-based ant colony optimization approach," Computers & Industrial Engineering, vol. 97, pp. 58-72, 2016, doi: 10.1016/j.cie.2016.04.001.

[5] O. Yilmaz, N. Aydin, and I. Kucukkoc, "Minimization of Manufacturing Cost in Mixed-model Robotic Assembly Lines," in The Third International Conference on Applied Mathematics in Engineering (ICAMƩ’24), Ayvalik, Balikesir, Turkiye, 2024, p. 141.

[6] N. Boysen, P. Schulze, and A. Scholl, "Assembly line balancing: What happened in the last fifteen years?," European Journal of Operational Research, vol. 301, no. 3, pp. 797-814, 2022/09/16/ 2022, doi: https://doi.org/10.1016/j.ejor.2021.11.043.

[7] N. Boysen, M. Fliedner, and A. Scholl, "A classification of assembly line balancing problems," (in English), European Journal of Operational Research, vol. 183, no. 2, pp. 674-693, Dec 1 2007, doi: DOI 10.1016/j.ejor.2006.10.010.

[8] O. Battaïa and A. Dolgui, "Hybridizations in line balancing problems: A comprehensive review on new trends and formulations," International Journal of Production Economics, Article vol. 250, 2022, Art no. 108673, doi: 10.1016/j.ijpe.2022.108673.

[9] Z. Li, I. Kucukkoc, and Q. Tang, "A comparative study of exact methods for the simple assembly line balancing problem," Soft Computing, vol. 24, no. 15, pp. 11459-11475, 2020/08/01 2020, doi: 10.1007/s00500-019-04609-9.

[10] N. T. Thomopoulos, "Line Balancing-Sequencing for Mixed-Model Assembly," Management Science, vol. 14, no. 2, pp. B-59-B-75, 1967, doi: 10.1287/mnsc.14.2.B59.

[11] N. T. Thomopoulos, "Mixed Model Line Balancing with Smoothed Station Assignments," Management Science, vol. 16, no. 9, pp. 593-603, 1970/05/01 1970, doi: 10.1287/mnsc.16.9.593.

[12] H. Gokcen and E. Erel, "A goal programming approach to mixed-model assembly line balancing problem," International Journal of Production Economics, vol. 48, no. 2, pp. 177-185, 1997/01/24/ 1997, doi: https://doi.org/10.1016/S0925-5273(96)00069-2.

[13] S. Emde, N. Boysen, and A. Scholl, "Balancing mixed-model assembly lines: a computational evaluation of objectives to smoothen workload," (in English), International Journal of Production Research, vol. 48, no. 11, pp. 3173-3191, 2010, doi: Doi 10.1080/00207540902810577.

[14] L. Belkharroubi and K. Yahyaoui, "A Hybrid approach for the Mixed-Model Assembly Line Balancing problem Type-II," in 2021 11th IEEE International Conference on Intelligent Data Acquisition and Advanced Computing Systems: Technology and Applications (IDAACS), 22-25 Sept. 2021 2021, vol. 1, pp. 329-332, doi: 10.1109/IDAACS53288.2021.9661039.

[15] L. Belkharroubi and K. Yahyaoui, "Solving the mixed-model assembly line balancing problem type-I using a Hybrid Reactive GRASP," Production & Manufacturing Research, vol. 10, no. 1, pp. 108-131, 2022/12/31 2022, doi: 10.1080/21693277.2022.2065380.

[16] T. Mönch, A. Huchzermeier, and P. Bebersdorf, "Variable takt times in mixed-model assembly line balancing with random customisation," International Journal of Production Research, vol. 59, no. 15, pp. 4670-4689, 2021/08/03 2021, doi: 10.1080/00207543.2020.1769874.

[17] K. Meng, Q. Tang, L. Cheng, and Z. Zhang, "Mixed-model assembly line balancing problem considering preventive maintenance scenarios: MILP model and cooperative co-evolutionary algorithm," Applied Soft Computing, vol. 127, p. 109341, 2022/09/01/ 2022, doi: https://doi.org/10.1016/j.asoc.2022.109341.

[18] Z. Zhang, M. Chica, Q. Tang, Z. Li, and L. Zhang, "A multi-objective co-evolutionary algorithm for energy and cost-oriented mixed-model assembly line balancing with multi-skilled workers," Expert Systems with Applications, vol. 236, p. 121221, 2024/02/01/ 2024, doi: https://doi.org/10.1016/j.eswa.2023.121221.

[19] A. Nourmohammadi, A. H. C. Ng, M. Fathi, J. Vollebregt, and L. Hanson, "Multi-objective optimization of mixed-model assembly lines incorporating musculoskeletal risks assessment using digital human modeling," CIRP Journal of Manufacturing Science and Technology, vol. 47, pp. 71-85, 2023/12/01/ 2023, doi: https://doi.org/10.1016/j.cirpj.2023.09.002.

[20] Y. Li, D. Liu, and I. Kucukkoc, "Mixed-model assembly line balancing problem considering learning effect and uncertain demand," Journal of Computational and Applied Mathematics, vol. 422, p. 114823, 2023/04/01/ 2023, doi: https://doi.org/10.1016/j.cam.2022.114823.

[21] Y. Delice, E. K. Aydoğan, S. Himmetoğlu, and U. Özcan, "Integrated mixed-model assembly line balancing and parts feeding with supermarkets," CIRP Journal of Manufacturing Science and Technology, vol. 41, pp. 1-18, 2023/04/01/ 2023, doi: https://doi.org/10.1016/j.cirpj.2022.12.002.

[22] M. D. Mura and G. Dini, "Improving ergonomics in mixed-model assembly lines balancing noise exposure and energy expenditure," CIRP Journal of Manufacturing Science and Technology, vol. 40, pp. 44-52, 2023/02/01/ 2023, doi: https://doi.org/10.1016/j.cirpj.2022.11.005.

[23] Z. A. Çil, Z. Li, S. Mete, and E. Özceylan, "Mathematical model and bee algorithms for mixed-model assembly line balancing problem with physical human–robot collaboration," Applied Soft Computing, vol. 93, p. 106394, 2020/08/01/ 2020, doi: https://doi.org/10.1016/j.asoc.2020.106394.

[24] H. M. Alakaş and B. Toklu, "Problem Specific Variable Selection Rules for Constraint Programming: A Type II Mixed Model Assembly Line Balancing Problem Case," Applied Artificial Intelligence, vol. 34, no. 7, pp. 564-584, 2020/06/06 2020, doi: 10.1080/08839514.2020.1731782.

[25] L. Yuwei, C. Jian'e, Z. Feng, and Z. Shijing, "A Research of Multi-Constrained Two-sided Mixed-model Assembly Line Balancing Problem Based on Genetic Algorithm," in 2020 IEEE 7th International Conference on Industrial Engineering and Applications (ICIEA), 16-21 April 2020 2020, pp. 377-381, doi: 10.1109/ICIEA49774.2020.9102104.

[26] S. Yaphiar, C. Nugraha, and A. Ma’ruf, "Mixed Model Assembly Line Balancing for Human-Robot Shared Tasks," in iMEC-APCOMS 2019, Singapore, M. N. Osman Zahid, R. Abd. Aziz, A. R. Yusoff, N. Mat Yahya, F. Abdul Aziz, and M. Yazid Abu, Eds., 2020// 2020: Springer Singapore, pp. 245-252.

[27] M. Lalaoui and A. E. Afia, "A versatile generalized simulated annealing using type-2 fuzzy controller for the mixed-model assembly line balancing problem," IFAC-PapersOnLine, vol. 52, no. 13, pp. 2804-2809, 2019/01/01/ 2019, doi: https://doi.org/10.1016/j.ifacol.2019.11.633.

[28] P. Sadeghi, R. D. Rebelo, and J. S. Ferreira, "Balancing mixed-model assembly systems in the footwear industry with a variable neighbourhood descent method," Computers & Industrial Engineering, vol. 121, pp. 161-176, 2018/07/01/ 2018, doi: https://doi.org/10.1016/j.cie.2018.05.020.

[29] B. Naderi, A. Azab, and K. Borooshan, "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, vol. 57, no. 3, pp. 643-661, 2019/02/01 2019, doi: 10.1080/00207543.2018.1476786.

[30] I. Kucukkoc, Z. Li, A. D. Karaoglan, and D. Z. Zhang, "Balancing of mixed-model two-sided assembly lines with underground workstations: A mathematical model and ant colony optimization algorithm," International Journal of Production Economics, vol. 205, pp. 228-243, 2018/11/01/ 2018, doi: https://doi.org/10.1016/j.ijpe.2018.08.009.

[31] F. Tanhaie, M. Rabbani, and N. Manavizadeh, "Simultaneous balancing and worker assignment problem for mixed-model assembly lines in a make-to-order environment considering control points and assignment restrictions," Journal of Modelling in Management, vol. 15, no. 1, pp. 1-34, 2019/09/23/ 2019, doi: https://doi.org/10.1108/JM2-04-2018-0052.

[32] T. T. M. Anh and N. Van Hop, "Matheuristics for mixed-model assembly line balancing problem with fuzzy stochastic processing time," Applied Soft Computing, vol. 160, p. 111694, 2024/07/01/ 2024, doi: https://doi.org/10.1016/j.asoc.2024.111694.

[33] D. Schibelbain, T. C. Lopes, and L. Magatão, "A method to balancing robotic mixed-model assembly lines: Practical constraints, computational challenges, and performance estimation," Computers & Industrial Engineering, vol. 197, p. 110595, 2024/11/01/ 2024, doi: https://doi.org/10.1016/j.cie.2024.110595.

[34] C. G. S. Sikora, "Balancing mixed-model assembly lines for random sequences," European Journal of Operational Research, vol. 314, no. 2, pp. 597-611, 2024/04/16/ 2024, doi: https://doi.org/10.1016/j.ejor.2023.10.008.

[35] X. Zhang et al., "Human-Robot Collaboration in Mixed-Flow Assembly Line Balancing under Uncertainty: An Efficient Discrete Bees Algorithm," Journal of Industrial Information Integration, vol. 41, p. 100676, 2024/09/01/ 2024, doi: https://doi.org/10.1016/j.jii.2024.100676.

[36] S. El Machouti, M. Hlyal, A. Babay, and J. E. Alami, "Optimisation of Simple Assembly Line Balancing Problem Type E: A Systematic Literature Review," Management Systems in Production Engineering, vol. 32, no. 2, pp. 162-173, 2024, doi: 10.2478/mspe-2024-0016.

[37] J. Plans and A. Corominas, "Modelling and solving the SALB-E problem," in Proceedings of the 1999 IEEE International Symposium on Assembly and Task Planning (ISATP'99) (Cat. No.99TH8470), 24-24 July 1999 1999, pp. 356-360, doi: 10.1109/ISATP.1999.782984.

[38] N.-C. Wei and I. M. Chao, "A solution procedure for type E simple assembly line balancing problem," Computers & Industrial Engineering, vol. 61, no. 3, pp. 824-830, 2011/10/01/ 2011, doi: https://doi.org/10.1016/j.cie.2011.05.015.

[39] P. T. Zacharia and A. C. Nearchou, "A meta-heuristic algorithm for the fuzzy assembly line balancing type-E problem," Computers & Operations Research, vol. 40, no. 12, pp. 3033-3044, 2013/12/01/ 2013, doi: https://doi.org/10.1016/j.cor.2013.07.012.

[40] R. Esmaeilbeigi, B. Naderi, and P. Charkhgard, "The type E simple assembly line balancing problem: A mixed integer linear programming formulation," Computers & Operations Research, vol. 64, pp. 168-177, 2015/12/01/ 2015, doi: https://doi.org/10.1016/j.cor.2015.05.017.

[41] M. Jusop and M. F. F. Ab Rashid, "Optimisation of Assembly Line Balancing Type-E with Resource Constraints Using NSGA-II," Key Engineering Materials, vol. 701, pp. 195-199, 2016, doi: 10.4028/www.scientific.net/KEM.701.195.

[42] M. N. A. Khalid, U. K. Yusof, and H. Iida, "An Artificial Immune System Approach for Solving Type-E Assembly Line Balancing Problem with Problem-Specific Information," in 2020 IEEE 16th International Conference on Control & Automation (ICCA), 9-11 Oct. 2020 2020, pp. 1590-1595, doi: 10.1109/ICCA51439.2020.9264382.

[43] N. Manavizadeh, M. Rabbani, D. Moshtaghi, and F. Jolai, "Mixed-model assembly line balancing in the make-to-order and stochastic environment using multi-objective evolutionary algorithms," (in English), Expert Systems with Applications, vol. 39, no. 15, pp. 12026-12031, Nov 1 2012, doi: DOI 10.1016/j.eswa.2012.03.044.

[44] P. Su, N. Wu, and Z. Yu, "A Petri net-based heuristic for mixed-model assembly line balancing problem of Type-E," International Journal of Production Research, vol. 52, no. 5, pp. 1542-1556, 2014/03/04 2014, doi: 10.1080/00207543.2013.849010.

[45] A. Legesse, E. Tesfaye, and E. Berhan, "Multi-objective optimization of mixed model assembly line balancing in an assemble-to-order industry with stochastic environment," International Journal of Engineering, Science and Technology, vol. 12, no. 3, pp. 90-107, 2020.

[46] G. Fan, H. Zheng, Z. Jiang, J. Liu, and S. Lou, "Multi-objective assembly line rebalancing problem based on complexity measurement in green manufacturing," Engineering Applications of Artificial Intelligence, vol. 132, p. 107884, 2024/06/01/ 2024, doi: https://doi.org/10.1016/j.engappai.2024.107884.

[47] T. Çimen, A. Baykasoğlu, and S. Demirkol Akyol, "A detailed review and analysis of assembly line rebalancing problems," Assembly Automation, vol. 42, no. 6, pp. 742-760, 2022.

[48] K. Ağpak, "An approach to find task sequence for re‐balancing of assembly lines," Assembly Automation, vol. 30, no. 4, pp. 378-387, 2010, doi: 10.1108/01445151011075834.

[49] C. Yang, J. Gao, and L. Sun, "A multi-objective genetic algorithm for mixed-model assembly line rebalancing," Computers & Industrial Engineering, vol. 65, no. 1, pp. 109-116, 2013/05/01/ 2013, doi: https://doi.org/10.1016/j.cie.2011.11.033.

[50] F. Serin, S. Mete, and E. Çelik, "An efficient algorithm for U-type assembly line re-balancing problem with stochastic task times," Assembly Automation, vol. 39, no. 4, pp. 581-595, 2019, doi: 10.1108/AA-07-2018-106.

[51] F. S. Oliveira, K. Vittori, R. M. O. Russel, and X. L. Travassos, "Mixed assembly line rebalancing: A binary integer approach applied to real world problems in the automotive industry," International Journal of Automotive Technology, vol. 13, no. 6, pp. 933-940, 2012/10/01 2012, doi: 10.1007/s12239-012-0094-4.

[52] F. Makssoud, D. Y. C. D. Maurizio Faccio, O. Battaïa, A. Dolgui, K. Mpofu, and O. Olabanji, "Re-balancing problem for assembly lines: new mathematical model and exact solution method," (in english), Emerald, 2015 2015.

[53] I. Kucukkoc and D. Z. Zhang, "Type-E Parallel Two-Sided Assembly Line Balancing Problem: Mathematical Model and Ant Colony Optimisation based Approach with Optimised Parameters," Computers & Industrial Engineering, vol. DOI: 10.1016/j.cie.2014.12.037, 2015, doi: 10.1016/j.cie.2014.12.037.

[54] D. Camli and I. Kucukkoc, "Rebalancing of multi-manned assembly lines with model variability," in The Third International Conference on Applied Mathematics in Engineering (ICAMƩ’24), Ayvalik, Balikesir, Turkiye, 2024, p. 125.

[55] Y. Haimes, "On a bicriterion formulation of the problems of integrated system identification and system optimization," IEEE transactions on systems, man, and cybernetics, no. 3, pp. 296-297, 1971.

[56] I. Kucukkoc, S. Finco, M. Peron, and G. Aydin Keskin, "Including mechanical requirements in a bi-objective nesting and scheduling model for additive manufacturing," European Journal of Operational Research, vol. 325, no. 3, pp. 416-432, 2025/09/16/ 2025, doi: https://doi.org/10.1016/j.ejor.2025.03.022.

[57] O. Yilmaz, N. Aydin, and I. Kucukkoc, "Bi-objective optimization of human-robot collaborative mixed-model multiple assembly lines considering model assignment and energy consumption," Journal of Computational and Applied Mathematics, vol. 473, p. 116876, 2026/02/01/ 2026, doi: https://doi.org/10.1016/j.cam.2025.116876.

[58] D. Çamlı, "Karışık modelli montaj hatlarında hat etkinliğinin maksimizasyonu ve bir uygulama," MSc Thesis, Balikesir University (Turkey), 2024.

[59] N. Boysen, M. Fliedner, R. Klein, and A. Scholl. "Assembly Line Balancing Problem Benchmark Data Sets." http://assembly-line-balancing.de/ (accessed 16 Dec 2023).