Comparative Analysis of Exact, Heuristic and Metaheuristic Algorithms for Flexible Assembly Scheduling

• Autorzy: Maghiar Octavian , Selea Teodora , Copie Adrian , Micota Flavia , Marin Mircea

Identyfikatory

DOI

10.15439/2023F2715

• Języki publikacji: EN

Abstrakty

EN

Real-world manufacturing scenarios usually lead to difficult assembly scheduling problems. Besides strict precedence constraints between jobs or operations, such problems incorporate constraints related to maintenance activities on working stations (machines) and specific setup times when different operations are executed on the same machine. This paper analyzes the performance of several approaches, based on mathematical programming and on (meta)heuristics, to solve flexible assembly scheduling problems characterized by an arbitrary tree-like structure of the operation network. In this context, a specific encoding of candidate solutions and some specific perturbation operators are proposed. The encoding and the operators allows the distribution of sub(batches) of operations on several machines which leads, for some assembly scheduling problems, to a significant decrease of the makespan.

Słowa kluczowe

EN

computer science; job shop scheduling; processor; perturbation methods; metaheuristics; maintenance engineering; encoding

PL

informatyka; harmonogram pracy; procesor; metoda perturbacji; metaheurystyka; inżynieria utrzymania ruchu; kodowanie

• Wydawca: Polskie Towarzystwo Informatyczne
• Czasopismo: Annals of Computer Science and Information Systems
• Rocznik: 2023
• Tom: Vol. 35
• Strony: 615--625
• Opis fizyczny: Bibliogr. 14 poz., tab., wykr., rys.

Twórcy

autor

Maghiar Octavian

• West University of Timișoara, Department of Computer Science, blvd. Vasile Pârvan, 4, 300223, Timișoara, Romania

autor

Selea Teodora

• West University of Timișoara, Department of Computer Science, blvd. Vasile Pârvan, 4, 300223, Timișoara, Romania

autor

Copie Adrian

• West University of Timișoara, Department of Computer Science, blvd. Vasile Pârvan, 4, 300223, Timișoara, Romania

autor

Micota Flavia

• West University of Timișoara, Department of Computer Science, blvd. Vasile Pârvan, 4, 300223, Timișoara, Romania

autor

Marin Mircea

• West University of Timișoara, Department of Computer Science, blvd. Vasile Pârvan, 4, 300223, Timișoara, Romania

Bibliografia

• 1. H. Xiong, S. Shi, D. Ren, and J. Hu, “A survey of job shop scheduling problem: The types and models,” Computers Operations Research, vol. 142, 2022. http://dx.doi.org/https://doi.org/10.1016/j.cor.2022.105731
• 2. T. Morton and D. W. Pentico, Heuristic scheduling systems: with applications to production systems and project management. John Wiley & Sons, 1993, vol. 3.
• 3. W. Lin, Q. Deng, W. Han, G. Gong, and K. Li, “An effective algorithm for flexible assembly job-shop scheduling with tight job constraints,” Int. Trans. Oper. Res., vol. 29, no. 1, pp. 496–525, 2022. http://dx.doi.org/10.1111/itor.12767. [Online]. Available: https://doi.org/10.1111/itor.12767
• 4. Q. Liu, X. Li, H. Liu, and Z. Guo, “Multi-objective metaheuristics for discrete optimization problems: A review of the state-of-the-art,” Applied Soft Computing, vol. 93, p. 106382, 2020.
• 5. A. Agrawal, G. Harhalakis, I. Minis, and R. Nagi, “‘just-in-time’production of large assemblies,” IIE transactions, vol. 28, no. 8, pp. 653–667, 1996.
• 6. S.-G. Dastidar and R. Nagi, “Batch splitting in an assembly scheduling environment,” International Journal of Production Economics, vol. 105, no. 2, pp. 372–384, 2007.
• 7. H.-y. Wang, Y.-w. Zhao, X.-l. Xu, and W.-L. Wang, “A batch splitting job shop scheduling problem with bounded batch sizes under multiple-resource constraints using genetic algorithm,” in 2008 IEEE Conference on Cybernetics and Intelligent Systems. IEEE, 2008, pp. 220–225.
• 8. X. Li, J. Lu, C. Yang, and J. Wang, “Research of flexible assembly job-shop batch–scheduling problem based on improved artificial bee colony,” Frontiers in Bioengineering and Biotechnology, vol. 10, p. 909548, 2022.
• 9. F. Chan, T. Wong, and L. Chan, “Lot streaming for product assembly in job shop environment,” Robotics and Computer-Integrated Manufacturing, vol. 24, no. 3, pp. 321–331, 2008. http://dx.doi.org/https://doi.org/10.1016/j.rcim.2007.01.001. [Online]. Available: https://www.sciencedirect.com/science/article/pii/S0736584507000063
• 10. F. Chan, T. Wong, and L. Chan, “The application of lot streaming to assembly job shop under resource constraints,” IFAC Proceedings Volumes, vol. 41, no. 2, pp. 14 852–14 857, 2008. http://dx.doi.org/https://doi.org/10.3182/20080706-5-KR-1001.02514 17th IFAC World Congress. [Online]. Available: https://www.sciencedirect.com/science/article/pii/S1474667016413790
• 11. A. Maoudj, B. Bouzouia, A. Hentout, A. Kouider, and R. Toumi, “Distributed multi-agent scheduling and control system for robotic flexible assembly cells,” J. Intell. Manuf., vol. 30, no. 4, pp. 1629–1644, 2019. http://dx.doi.org/10.1007/s10845-017-1345-z. [Online]. Available: https://doi.org/10.1007/s10845-017-1345-z
• 12. I. Kacem, S. Hammadi, and P. Borne, “Approach by localization and multiobjective evolutionary optimization for flexible job-shop scheduling problems,” IEEE Transactions on Systems, Man, and Cybernetics, Part C (Applications and Reviews), vol. 32, no. 1, pp. 1–13, 2002. http://dx.doi.org/10.1109/TSMCC.2002.1009117
• 13. P. Fattahi, M. S. Mehrabad, and F. Jolai, “Mathematical modeling and heuristic approaches to flexible job shop scheduling problems,” J Intell Manuf, vol. 18, p. 331–342, 2007. http://dx.doi.org/https://doi.org/10.1007/s10845-007-0026-8
• 14. C. Talens, P. Perez-Gonzalez, V. Fernandez-Viagas, and J. M. Framiñan, “New hard benchmark for the 2-stage multi-machine assembly scheduling problem: Design and computational evaluation,” Comput. Ind. Eng., vol. 158, p. 107364, 2021. http://dx.doi.org/10.1016/j.cie.2021.107364. [Online]. Available: https://doi.org/10.1016/j.cie.2021.107364

Uwagi

1. Thematic Tracks Regular Papers

2. Opracowanie rekordu ze środków MEiN, umowa nr SONP/SP/546092/2022 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2024).