Proceedings of the 18th Conference on Computer Science and Intelligence Systems

DOI: http://dx.doi.org/10.15439/2023F2715

Citation: Proceedings of the 18th Conference on Computer Science and Intelligence Systems, M. Ganzha, L. Maciaszek, M. Paprzycki, D. Ślęzak (eds). ACSIS, Vol. 35, pages 615–625 (2023)

Full text

Abstract. 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.

References

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. ——, “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