Single-objective flexible job-shop scheduling problem based on improved dung beetle optimization

Shuangji Yao; Yunfei Guo; Botao Yang; You Lv; Marco Ceccarelli; Xiaoshuang Dai; Giuseppe Carbone; Shuangji Yao; Yunfei Guo; Botao Yang; You Lv; Marco Ceccarelli; Xiaoshuang Dai; Giuseppe Carbone

doi:10.3934/steme.2024018

STEM Education

2024, Volume 4, Issue 3: 299-327. doi: 10.3934/steme.2024018

Previous Article Next Article

Research article

Single-objective flexible job-shop scheduling problem based on improved dung beetle optimization

1.
Department School of Vehicle and Energy, Yanshan University, Qinhuangdao 066004, China
2.
Hebei Key Laboratory of specialized Transportation Equipment, Qinhuangdao 066004, China
3.
Shenyang Xinbaolu Aviation Technology Co., Ltd, Shenyang, 110000 China
4.
Department of Industrial Engineering, University of Rome Tor Vergata, Rome 0018511, Italy
5.
Department of Mechanical, Energy and Management Engineering, University of Calabria, Rende, Italy

Academic Editor: Mingfeng Wang

Received: 03 April 2024 Revised: 20 June 2024 Accepted: 22 July 2024 Published: 31 July 2024

Given the characteristics of the flexible job-shop scheduling problem and the practical production of a given enterprise, a flexible job-shop scheduling model was proposed to minimize the maximum completion time. A novel algorithm was proposed to solve the model by integrating the dung beetle optimization algorithm and the simulated annealing algorithm. Algorithmic improvements include the design of a single-layer process encoding scheme with machine selection during decoding to ensure a higher level of the initial population. During population update, the dung beetle optimization algorithm was applied for optimization, followed by simulated annealing operations to enhance the convergence speed and solution quality of the algorithm. Through simulation experiments and comparisons with other algorithms, the effectiveness and superiority of the proposed algorithm were validated. In addition, the feasibility of the algorithm was tested through a real-world factory production case. In conclusion, the improvements made in this paper to the algorithms and scheduling models offer valuable insights into the educational aspects of job-shop scheduling. For instance, the single-layer encoding proposed herein simplifies the coding process, making it more accessible for beginners. Additionally, the accompanying decoding strategy yields relatively higher-quality initial solutions, facilitating subsequent optimization processes by accelerating convergence without compromising solution quality. Students were able to gain a better understanding of real workshop conditions through this project, going beyond the sole goal of minimizing completion time. They began to consider more complex situations in the machining process, such as machine breakdowns, changes in machining schedules, and the load on bottleneck machines and total machine load. This allowed students to have a holistic view of a complex production workshop. In terms of education, the project improved students' ability to consider practical aspects when solving problems and provided them with a way to solve problems.
- flexible job-shop scheduling problems,
- maximum completion time,
- dung beetle optimizer,
- simulated annealing,
- single layer encoding
Citation: Shuangji Yao, Yunfei Guo, Botao Yang, You Lv, Marco Ceccarelli, Xiaoshuang Dai, Giuseppe Carbone. Single-objective flexible job-shop scheduling problem based on improved dung beetle optimization[J]. STEM Education, 2024, 4(3): 299-327. doi: 10.3934/steme.2024018

Related Papers:

Abstract

Given the characteristics of the flexible job-shop scheduling problem and the practical production of a given enterprise, a flexible job-shop scheduling model was proposed to minimize the maximum completion time. A novel algorithm was proposed to solve the model by integrating the dung beetle optimization algorithm and the simulated annealing algorithm. Algorithmic improvements include the design of a single-layer process encoding scheme with machine selection during decoding to ensure a higher level of the initial population. During population update, the dung beetle optimization algorithm was applied for optimization, followed by simulated annealing operations to enhance the convergence speed and solution quality of the algorithm. Through simulation experiments and comparisons with other algorithms, the effectiveness and superiority of the proposed algorithm were validated. In addition, the feasibility of the algorithm was tested through a real-world factory production case. In conclusion, the improvements made in this paper to the algorithms and scheduling models offer valuable insights into the educational aspects of job-shop scheduling. For instance, the single-layer encoding proposed herein simplifies the coding process, making it more accessible for beginners. Additionally, the accompanying decoding strategy yields relatively higher-quality initial solutions, facilitating subsequent optimization processes by accelerating convergence without compromising solution quality. Students were able to gain a better understanding of real workshop conditions through this project, going beyond the sole goal of minimizing completion time. They began to consider more complex situations in the machining process, such as machine breakdowns, changes in machining schedules, and the load on bottleneck machines and total machine load. This allowed students to have a holistic view of a complex production workshop. In terms of education, the project improved students' ability to consider practical aspects when solving problems and provided them with a way to solve problems.

References

[1]	Liu, X.X., Liu, C.B. and Tao, Z., Study on Scheduling Optimization for Flexible Job Shop. Applied Mechanics and Materials, 2010, 26: 821‒825. https://doi.org/10.4028/www.scientific.net/AMM.26-28.821 doi: 10.4028/www.scientific.net/AMM.26-28.821
[2]	Józefowska, J. and Zimniak, A., Optimization tool for short-term production planning and scheduling. International Journal of Production Economics, 2008,112(1): 109‒120. https://doi.org/10.1016/j.ijpe.2006.08.026 doi: 10.1016/j.ijpe.2006.08.026
[3]	Qu, M., Zuo, Y., Xiang, F. and Tao, F., An improved electromagnetism-like mechanism algorithm for energy-aware many-objective flexible job shop scheduling. The International Journal of Advanced Manufacturing Technology, 2022,119(7-8): 4265‒4275. https://doi.org/10.1007/s00170-022-08665-8 doi: 10.1007/s00170-022-08665-8
[4]	Park, M.J. and Ham, A., Energy-aware flexible job shop scheduling under time-of-use pricing. International Journal of Production Economics, 2022,248: 108507. https://doi.org/10.1016/j.ijpe.2022.108507 doi: 10.1016/j.ijpe.2022.108507
[5]	Liu, L., Jiang, T., Zhu, H. and Shang, C., A New Interior Search Algorithm for Energy-Saving Flexible Job Shop Scheduling with Overlapping Operations and Transportation Times. Axioms, 2022, 11(7): 306. https://doi.org/10.3390/axioms11070306 doi: 10.3390/axioms11070306
[6]	Eberhart, R. and Kennedy, J., A new optimizer using particle swarm theory. in MHS'95. Proceedings of the Sixth International Symposium on Micro Machine and Human Science, 1995, 39‒43. IEEE. https://doi.org/10.1109/MHS.1995.494215
[7]	Mirjalili, S., Mirjalili, S.M. and Lewis, A., Grey Wolf Optimizer. Advances in Engineering Software, 2014, 69: 46‒61. https://doi.org/10.1016/j.advengsoft.2013.12.007 doi: 10.1016/j.advengsoft.2013.12.007
[8]	Mirjalili, S. and Lewis, A., The Whale Optimization Algorithm. Advances in Engineering Software, 2016, 95: 51‒67. https://doi.org/10.1016/j.advengsoft.2016.01.008 doi: 10.1016/j.advengsoft.2016.01.008
[9]	Chen, F., Li, X. and Yang, X., Multi-objective Flexible Job Shop Scheduling based on Improved NSGA2 Algorithm. Industrial Engineering Journal, 2018, 21(2): 55‒61.
[10]	Rajalakshmi, S. and Kanmani, S., A comprehensive review on recent intelligent metaheuristic algorithms. International Journal of Swarm Intelligence, 2022, 7(2): 182. https://doi.org/10.1504/IJSI.2022.123076 doi: 10.1504/IJSI.2022.123076
[11]	Aghaee, Z., Ghasemi, M.M., Beni, H.A., Bouyer, A. and Fatemi, A., A survey on meta-heuristic algorithms for the influence maximization problem in the social networks. Computing, 2021,103(11): 2437‒2477. https://doi.org/10.1007/s00607-021-00945-7 doi: 10.1007/s00607-021-00945-7
[12]	Shen, L., Zhen, G. and Zhu, H., Improved Migratory Bird Migration Algorithm for Flexible Job Shop Scheduling. Journal of Physics: Conference Series, 2022, 2219(1): 012036. https://doi.org/10.1088/1742-6596/2219/1/012036 doi: 10.1088/1742-6596/2219/1/012036
[13]	Chen, R., Yang, B., Li, S. and Wang, S., A self-learning genetic algorithm based on reinforcement learning for flexible job-shop scheduling problem. Computers & Industrial Engineering, 2020,149: 106778. https://doi.org/10.1016/j.cie.2020.106778 doi: 10.1016/j.cie.2020.106778
[14]	Wang, S.X., Zhang, C.Y. and Jin, L.L., A Hybrid Genetic Algorithm for Flexible Job-Shop Scheduling Problem. Advanced Materials Research, 2014,889-890: 1179‒1184. https://doi.org/10.4028/www.scientific.net/AMR.889-890.1179 doi: 10.4028/www.scientific.net/AMR.889-890.1179
[15]	Gu, X.L., Huang, M. and Liang, X., A Discrete Particle Swarm Optimization Algorithm With Adaptive Inertia Weight for Solving Multiobjective Flexible Job-shop Scheduling Problem. IEEE Access, 2020, 8: 33125‒33136. https://doi.org/10.1109/ACCESS.2020.2974014 doi: 10.1109/ACCESS.2020.2974014
[16]	Anuar, N.I., Fauadi, M.M., Saptari, A. and Hao, X., Improved Multi-Objective Particle Swarm Optimization For Job-Shop Scheduling Problems. Journal of Advanced Manufacturing Technology (JAMT), 2020, 14(3): 33‒49.
[17]	Zhao, X.H., Wei, Y.F., Wang, K.F. and Ni, Y.Q., Research on Flexible Job Shop Scheduling Problem Based on Improved Ant Colony Algorithm. Modular Machine Tool & Automatic Manufacturing Technique, 2022, 2: 165‒168. https://doi.org/10.13462/j.cnki.mmtamt.2022.02.038 doi: 10.13462/j.cnki.mmtamt.2022.02.038
[18]	Luan, F., Wu, S.Q., Li, F.K., Jia, J.Y. and Cai, Z.Y., A Whale Swarm Optimization Algorithm for Solving Flexible Job Shop Scheduling Problem. Mechanical Science and Technology for Aerospace Engineering, 2020, 39(2): 241‒246. https://doi.org/10.13433/j.cnki.1003-8728.20190114 doi: 10.13433/j.cnki.1003-8728.20190114
[19]	Yuan, Y., Xu, H. and Yang, J.D., A hybrid harmony search algorithm for the flexible job shop scheduling problem. Applied Soft Computing, 2013, 13(7): 3259‒3272. https://doi.org/10.1016/j.asoc.2013.02.013. doi: 10.1016/j.asoc.2013.02.013
[20]	Li, X., Peng, Z., Du, B., Guo, J., Xu, W. and Zhuang, K., Hybrid artificial bee colony algorithm with a rescheduling strategy for solving flexible job shop scheduling problems. Computers & Industrial Engineering, 2017,113: 10‒26. https://doi.org/10.1016/j.cie.2017.09.005 doi: 10.1016/j.cie.2017.09.005
[21]	Tian, Y., Tian, Y.N. and Liu, X., Review on Algorithms for Flexible Job Shop Scheduling Problem. Journal of Yan'an University(Natural Science Edition), 2021, 40(3): 64‒70. https://doi.org/10.13876/J.cnki.ydnse.2021.03.064 doi: 10.13876/J.cnki.ydnse.2021.03.064
[22]	Lv, S.Y. and Yu, P., A Review of Green Flexible Job-shop Scheduling Problem. Logistics Engineering and Management, 2022, 44(5): 107‒111.
[23]	Luo, X., Qian, Q. and Fu, Y., Review of Application of Genetic Algorithms for Solving Flexible Job Shop Scheduling Problems. Computer Engineering and Applications, 2019, 55(23): 15‒21.
[24]	Xue, J. and Shen, B., Dung beetle optimizer: a new meta-heuristic algorithm for global optimization. The Journal of Supercomputing, 2023, 79(7): 7305‒7336. https://doi.org/10.1007/s11227-022-04959-6 doi: 10.1007/s11227-022-04959-6
[25]	Xue, J. and Shen, B., A novel swarm intelligence optimization approach: sparrow search algorithm. Systems Science & Control Engineering, 2020, 8(1): 22‒34. https://doi.org/10.1080/21642583.2019.1708830 doi: 10.1080/21642583.2019.1708830
[26]	Xia, W. and Wu, Z., An effective hybrid optimization approach for multi-objective flexible job-shop scheduling problems. Computers & Industrial Engineering, 2005, 48(2): 409‒425. https://doi.org/10.1016/j.cie.2005.01.018 doi: 10.1016/j.cie.2005.01.018
[27]	Sun, J. and Xu, L., Disruption management for solving FJSP with improved genetic algorithm. Journal of Physics: Conference Series, 2020, 1656(1): 012013. https://doi.org/10.1088/1742-6596/1656/1/012013 doi: 10.1088/1742-6596/1656/1/012013
[28]	Sule, B. and Lawal, I., An Improve Object-oriented Approach for Multi-objective Flexible Job-shop Scheduling Problem (FJSP). International Journal of Computer Science and Information Technology, 2019, 11(5): 91‒108. https://doi.org/10.5121/ijcsit.2019.11508 doi: 10.5121/ijcsit.2019.11508
[29]	Xu, W., Liang, J., Gao, Z., Yu, F. and Sheng, S., Improved Harmony Search Algorithm for Solving FJSP. Computer Applications and Software, 2022. 39(6): 273‒279,335. (Chinese)
[30]	Tian, M., Zhang, G. and Liu, R., Solve FJSP Considering Transport Time via Particle Swarm Genetic Hybrid Algorithm. Operations Research and Management Science, 2019, 28(4): 78‒88.
[31]	Shi, X., Li, Y., Deng, D. and Long, W., Self-adaptive Multistage GA-IWO for Solving Flexible Job Shop Scheduling Problem. Journal of Mechanical Engineering, 2019, 55(6): 223‒232.
[32]	Jiang, T., Mk Series Calculation Example of Flexible Job-shop Scheduling Problem, CSDN.
[33]	Yan, X., Ye, C.M. and Yao, Y.Y., Solving Job-Shop scheduling problem by quantum whale optimization algorithm. Application Research of Computers, 2019, 36(4): 975‒979. https://doi.org/10.19734/j.issn.1001-3695.2017.10.0985 doi: 10.19734/j.issn.1001-3695.2017.10.0985
[34]	Tian, Y.N., Tian, Y., Liu, X. and Zhao, Y.L., An Improved Grey Wolf Algorithm for Flexible Job Shop Scheduling Problem. Computer and Modernization, 2022, 8: 78‒85.
[35]	Jia, P. and Wu, T., A Hybrid Genetic Algorithm for Flexible Job-shop Scheduling Problem. Journal of Xi'an Polytechnic University, 2020, 34(5): 80‒86. https://doi.org/10.13338/j.issn.1674-649x.2020.05.013 doi: 10.13338/j.issn.1674-649x.2020.05.013
[36]	Guo, Y., 222. Baidu Netdisk 2023 05/2023.

Author's biography Dr. Shuangji Yao is currently an associate professor at Yanshan University, China. His research interests cover aspects of Technology and theory of special carrying equipment and Special robot technology. He is a member of IEEE; Yunfei Guo graduated in Yanshan University(China), He has a master degree of Mechanical Engineering in Vehicle Engineering from Yanshan University. He is specialized in flexible job-shop scheduling problem and dung beetle optimizer; Botao Yang is a graduate student currently pursuing a master degree of mechanical engineering in vehicle engineering at Yanshan University(China), He is extremely passionate about control algorithm and the data science domain; You Lv is a Senior Engineer. He is mainly committed to the research of processing and manufacturing technology of complex parts, and is currently the CTO of Shenyang Xinbaolu Aviation Technology Co., Ltd. in China Dr; Dr. Marco Ceccarelli is currently a professor at University of Rome Tor Vergata, Italy. He was the Chair of the IFToMM (International Federation for the Promotion of Mechanism and Machine Science) and Editor in Chief of journal Robotics; Xiaoshuang Dai is an Engineer. She is mainly committed to the processing and manufacturing process design and production planning of complex parts, and is now working in the technical department of Shenyang Xinbaolu Aviation Technology Co., Ltd. in China. Dr; Dr. Giuseppe Carbone is currently a professor at University of Calabria, Italy. He is Chair of the IFToMM TC on Robotics and Mechatronics and Editor in Chief of ROBOTICA Journal (Cambridge University Press)

Reader Comments

Your name:*

Email:*
© 2024 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)