A Multi Objective Parallel Machine Scheduling Model for Bicycle Painting Problem
DOI:
https://doi.org/10.9744/jti.28.1.%25pKeywords:
Scheduling, parallel machine, multiobjective, painting, metaheuristicsAbstract
This paper addresses the complex multiobjective parallel machine scheduling problem within a bicycle painting department. The painting process is characterized by sequence-dependent setup times driven by frequent color changes and the critical need to align painting output with assembly shop requirements to prevent stock accumulation. The research develops a mathematical model with two primary objectives: minimizing the sequence mismatch between painting and assembly and minimizing total setup time. Unlike prior research, this study simultaneously addresses sequence-dependent setups caused by color changes, the management of multiple parallel paint lines within daily capacity limits, and the critical requirement that painting output matches the input sequence needed for assembly. Given the NP-hard nature of the problem, a Genetic Algorithm (GA) method is proposed to solve the problem. Other methods such as Ant Colony Optimization (ACO), Particle Swarm Optimization (PSO), and Variable Neighborhood Search (VNS), are used to compare with the GA. The methods are evaluated using real-world data from a bicycle company. Results indicate that VNS outperforms GA for the objective value. The objective value score of VNS is 91.23% compared to the Genetic Algorithm 86.72%. However, the GA runtimes are significantly faster, five times better than the VNS.
Downloads
References
[1] A Agárdi, and K. Nehéz, “Parallel machine scheduling with Monte Carlo tree search,” Acta Polytechnica, vol. 61, no. 2, pp. 307 – 312, April 2021, doi: https://doi.org/10.14311/ap.2021.61.0307
[2] M. Gallo, G. Mazzuto, F Ciarapica, and M. Bevilacqua, “Artificial intelligence to solve production scheduling problems in real industrial settings: Systematic literature review,” Electronics, vol. 12, no. 23, pp. 4732 – 4732, 2023, doi: https://doi.org/10.3390/electronics12234732
[3] M. Moser, N. Musilu, A. Schaerf and F Winter, “Exact and metaheuristic approaches for unrelated parallel machine scheduling,” Journal of Scheduling, vol. 25, no 5, pp. 507 – 534, 2021. doi: https://doi.org/10.1007/s10951-021-00714-6.
[4] F. F. Boctor, D. Zaatour, and J. Renaud, “Scheduling parallel extrusion lines,” Journal of Project Management, vol. 9, no. 1, pp. 1 – 16, 2023, doi: https://doi.org/10.5267/j.jpm.2023.11.002
[5] F. Winter, and N. Musliu, “Constraint-based scheduling for paint shops in the automotive supply industry,” ACM Transactions on Intelligent Systems and Technology, vol. 12 no. 5, Article 58, 2021 https://doi.org/10.1145/3430710
[6] R Zhang, “Environment-aware production scheduling for paint shops in automobile manufacturing: a multi-objective optimization approach,”. International Journal of Environmental Research and Public Health. Vol. 15, no. 1, p. 32, 2018 https://doi.org/10.3390/ijerph15010032
[7] Y. Zhang, Y. Shi, and J. Xu, “Research on PBS buffer scheduling strategy problems based on genetic algorithms,” 2025 International Conference on Education, Management and Information Technology (EMIT 2025), July 2025, doi: https://doi.org/10.1051/itmconf/20257701022/pdf.
[8] S. Vasilis, N. Nikos, A. Kosmas, and M. Dimitris, “A toolbox of agents for scheduling the paint shop in bicycle industry,” Procedia CIRP, Jan. 2022, doi: https://doi.org/10.1016/j.procir.2022.05.124.D.
[9] H. Zhang, and W Ding “A decomposition algorithm for dynamic car sequencing problems with buffers,” Applied Sciences. vol 13, no. 12, p. 7336, 2023 https://doi.org/10.3390/app13127336.
[10] V. Siatras, E. Bakopoulos, P. Mavrothalassitis, N. Nikolakis, and K. Alexopoulos, “Production scheduling based on a multi-agent system and digital twin: A bicycle industry case,” Information, June 2024, doi: https://doi.org/10.3390/info15060337.
[11] I. K. Singgih, O. Yu, B. Kim, J. Koo, and S. Lee, “Production scheduling problem in a factory of automobile component primer painting”. J. Intell. Manuf, vol. 31, pp. 1483 – 1496, 2020, doi: https://doi.org/10.1007/
s10845-019-01524-6
[12]. F. Winter, N. Musliu, E. Demirović, and C. Mrkvicka, “Solution approaches for an automotive paint shop scheduling problem” Proceedings of the International Conference on Automated Planning and Scheduling, vol. 29, pp. 573–581, 2019, doi: https://doi.org/10.1609/icaps.v29i1.3524
[13] S. Bysko, J. Krystek and S. Bysko, “Two approaches to car sequencing in the paint shop” J. Phys.: Conf. Ser. 1780 012028, 2021, doi: https://doi.org/10.1088/1742-6596/1780/1/012028
[14] F. Yu, Y. Peng, J. Li, G Zhou, L. Chen “An analysis of optimization for car pbs scheduling based on greedy strategy state transition algorithm”, Applied Sciences, vol 13. no. 10, p. 6194, 2023, https://doi.org/
10.3390/app13106194
[15] J. Yang, T. Sun, X. Huang, K. Peng, Z. Chen, G. Qian, Z. Qian “Optimizing painting sequence scheduling based on adaptive partheno-genetic algorithm” Processes. vol. 9, no. 10, p. 1714, 2021, https://doi.org/
10.3390/pr9101714
[16] J. Adan, “A hybrid genetic algorithm for parallel machine scheduling with setup times: A comparative study of metaheuristics on large problem instances,” Journal of Intelligent Manufacturing, no. 33, pp. 2059–2073, 2022, doi: https://doi.org/10.1007/s10845-022-01959-4 Springer.
[17] X. Wang, and Y. Zhu, “Hybrid genetic algorithm for flexible job shop scheduling with sequence-dependent setup times and job lag times,” IEEE Access, pp. 99:1-1, 2021, doi: https://doi.org/10.1109/ACCESS.
2021.3096007
[18] A. Berthier, A. Yalaoui, H. Chehade, F. Yalaoui, L. Amodeo and C Bouillot, “Unrelated parallel machines scheduling with dependent setup times, machine eligibility, and resource constraints”, Computers & Industrial Engineering, 170, 108736, 2022, https://doi.org/10.1016/j.cie.2022.108736
[19] M. Kurdi, “Modifying the ant colony algorithm for the open shop scheduling problem with the objective of minimizing makespan” Knowledge-Based Systems, 242, 108323. 2022, doi: https://doi.org/10.1016/
j.knosys.2022.108323.
[20] F. Pulansari and T. D. Retno “The unrelated parallel machine scheduling with a dependent time setup using ant colony optimization algorithm”, Jurnal Teknik Industri: Jurnal Keilmuan dan Aplikasi Teknik Industri, vol. 23, no 1, pp. 65-74, 2021, doi: https://doi.org/10.9744/jti.23.1.65-74
[21] S. Yan, G. Zhang, J Sun, and W Zhang, W., “An improved ant colony optimization for solving the flexible job shop scheduling problem with multiple time constraints,” Mathematical Biosciences and Engineering, vol. 20, no. 4, pp.7519–7547, 2023. doi: https://doi.org/10.3934/mbe.2023325.
[22] R. Wu, Z. Tian, X. Li, C. Wu, H. Tang, and Y. Li, “Improved discrete particle swarm optimization algorithm for solving fuzzy flexible job shop machines and automated guided vehicles fusion scheduling problem.” Engineering Applications of Artificial Intelligence, 160 (Part B), 111951, 2025, https://doi.org/
10.1016/j.engappai.2025.111951.
[23] K. Sun, D. Zheng, H. Song, Z. Cheng, X. Lang, W. Yuan, J. Wang, “Hybrid genetic algorithm with variable neighborhood search for flexible job shop scheduling problem in a machining system.” Expert Systems with Applications, vol 215, 119359, 2023, doi: https://doi.org/10.1016/j.eswa.2022.119359
[24] X. Wan, and T Jiang, “A dominance relations-based variable neighborhood search for assembly job shop scheduling with parallel machines,” Processes, 13 (5), 1578, 2025, doi: https://doi.org/10.3390/pr13051578
[25] A. Sahoo, R. K. Dalei, S. K. Rath, U. K. Sahu, and K. Tiwary. “Parameter optimisation of genetic algorithm utilising Taguchi design for gliding trajectory optimisation of missile”, Defense Science Journal, vol. 74, no. 1, January 2024, pp. 127-142, 2024, doi: https://doi.org/10.14429/dsj.74.18496
Downloads
Published
Issue
Section
License
Copyright (c) 2026 Dave Charlton Limantara, I Gede Agus Widyadana
This work is licensed under a Creative Commons Attribution 4.0 International License.
Articles published in the Jurnal Teknik Industri: Jurnal Keilmuan dan Aplikasi Teknik Industri will be Open-Access articles distributed under the terms and conditions of the Creative Commons Attribution License (CC BY).
This work is licensed under a Creative Commons Attribution License (CC BY).
