Memetic Algorithm for Dynamic Joint Flexible Job Shop Scheduling with Machines and Transportation Robots
Yingmei He*, Bin Xin*,, Sai Lu*, Qing Wang*, and Yulong Ding**
*School of Automation, Beijing Institute of Technology
No.5 Zhongguancun South Street, Haidian District, Beijing 10081, China
**Peng Cheng Laboratory
Shenzhen 518055, China
In this study, the dynamic joint scheduling problem for processing machines and transportation robots in a flexible job shop is investigated. The study aims to minimize the order completion time (makespan) of a job shop manufacturing system. Considering breakdowns, order insertion and battery charging maintenance of robots, an event-driven global rescheduling strategy is adopted. A novel memetic algorithm combining genetic algorithm and variable neighborhood search is designed to handle dynamic events and obtain a new scheduling plan. Finally, numerical experiments are conducted to test the effect of the improved operators. For successive multiple rescheduling, the effectiveness of the proposed algorithm is verified by comparing it with three other algorithms under dynamic events, and through statistical analysis, the results verify the effectiveness of the proposed algorithm.
-  F. Zhao, X. He, and L. Wang, “A two-stage cooperative evolutionary algorithm with problem-specific knowledge for energy-efficient scheduling of no-wait flow-shop problem,” IEEE Trans. Cybern., Vol.51, No.11, pp. 5291-5303, 2020.
-  F. Zhao, R. Ma, and L. Wang, “A self-learning discrete jaya algorithm for multiobjective energy-efficient distributed no-idle flow-shop scheduling problem in heterogeneous factory system,” IEEE Trans. Cybern., doi: 10.1109/TCYB.2021.3086181, 2021.
-  S. Zhou, L. Xing, X. Zheng et al., “A self-adaptive differential evolution algorithm for scheduling a single batch-processing machine with arbitrary job sizes and release times,” IEEE Trans. Cybern., Vol.51, No.3, pp. 1430-1442, 2019.
-  A. Ham, “Transfer-robot task scheduling in job shop,” Int. J. Prod. Res., Vol.59, No.3, pp. 813-823, 2021.
-  A. Ham, “Transfer-robot task scheduling in flexible job shop,” J. Intell. Manuf., Vol.31, pp. 1783-1793, 2020.
-  S. M. Homayouni and D. B. M. M. Fontes, “Production and transport scheduling in flexible job shop manufacturing systems,” J. Glob. Optim., Vol.79, pp. 463-502, 2021.
-  Y. Xu, M. Sahnoun, F. B. Abdelaziz, and D. Baudry, “A simulated multi-objective model for flexible job shop transportation scheduling,” Ann. Oper. Res., Vol.311, pp. 899-920, 2022.
-  J. Yan, Z. Liu, C. Zhang et al., “Research on flexible job shop scheduling under finite transportation conditions for digital twin workshop,” Robot. Comput. Integr. Manuf., Vol.72, Article No.102198, 2021.
-  M. Li and D. Lei, “An imperialist competitive algorithm with feedback for energy-efficient flexible job shop scheduling with transportation and sequence-dependent setup times,” Eng. App. Artif. Intell., Vol.103, Article No.104307, 2021.
-  W. Ren, Y. Yan, Y. Hu, and Y. Guan, “Joint optimisation for dynamic flexible job-shop scheduling problem with transportation time and resource constraints,” Int. J. Prod. Res., Vol.60, No.18, pp. 5675-5696, 2022.
-  Y. Fang, C. Peng, P. Lou et al., “Digital-Twin-Based Job Shop Scheduling Toward Smart Manufacturing,” IEEE Trans Industr. Inform., Vol.15, No.12, pp. 6425-6435, 2019.
-  A. Baykasoğlu, F. S. Madenoğlu, and A. Hamzadayi, “Greedy randomized adaptive search for dynamic flexible job-shop scheduling,” J. Manuf. Systm., Vol.56, pp. 425-451, 2020.
-  Z. Cao, L. Zhou, B. Hu, and C. Lin, “An Adaptive Scheduling Algorithm for Dynamic Jobs for Dealing with the Flexible Job Shop Scheduling Problem,” Bus. Inf. Syst. Eng., Vol.61, pp. 299-309, 2019.
-  F. Zhang, Y. Mei, S. Nguyen, and M. Zhang, “Evolving Scheduling Heuristics via Genetic Programming with Feature Selection in Dynamic Flexible Job-Shop Scheduling,” IEEE Trans. Cybern., Vol.51, No.4, pp. 1797-1811, 2021.
-  R. Yonemoto and H. Suwa, “Reactive Scheduling Based on Adaptive Manipulator Operations in a Job Shop Configuration with Two Machines,” Int. J. Automation Technol., Vol.15, No.5, pp. 661-668, 2021.
-  W. Tian and H. Zhang, “A dynamic job-shop scheduling model based on deep learning,” Adv. Prod. Eng. Manag., Vol.16, No.1, pp. 23-36, 2021.
-  W. Chen, H. Yang, and Y. Hao, “Scheduling of Dynamic Multi-Objective Flexible Enterprise Job-Shop Problem Based on Hybrid QPSO,” IEEE Access, Vol.7, pp. 127090-127097, 2019.
-  F. Zhang, Y. Mei, S. Nguyen, and M. Zhang, “Collaborative Multifidelity-Based Surrogate Models for Genetic Programming in Dynamic Flexible Job Shop Scheduling,” IEEE Trans. Cybern., Vol.52, No.8, pp. 8142-8156, 2021.
-  Y. He, B. Xin, S. Lu, and Y. Ding, “Dynamic Integrated Flexible Job Shop Scheduling with Transportation Robot,” The 7th Int. Workshop on Advanced Computational Intelligence and Intelligent Informatics Conf. (IWACIII2021), Article No.M2-4-6, 2021.
-  W.-L. Liu, Y.-J. Gong, W.-N. Chen et al., “Coordinated charging scheduling of electric vehicles: A mixed-variable differential evolution approach,” IEEE Trans. Intell. Transp. Syst., Vol.21, No.12, pp. 5094-5109, 2019.
-  M. R. Garey, D. S. Johnson, and R. Sethi, “The complexity of flowshop and jobshop scheduling,” Math. Oper. Res., Vol.1, No.2, pp. 117-129, 1976.
-  K.-M. Lee, T. Yamakawa, and K.-M. Lee, “A genetic algorithm for general machine scheduling problems,” 1998 2nd Int. Conf. Knowledge-Based Intelligent Electronic Systems Proc. KES’98, Vol.2, pp. 60-66, 1998.
-  G. Syswerda, “Uniform crossover in genetic algorithms,” Proc. 3rd Int. Conf. on Genetic Algorithms (ICGA), pp. 2-9, 1989.
-  N. Mladenović and P. Hansen, “Variable neighborhood search,” Comput. Oper. Res., Vol.24, No.11, pp. 1097-1100, 1997.
-  P. Brandimarte, “Routing and scheduling in a flexible job shop by tabu search,” Ann. Oper. Res., Vol.41, pp. 157-183, 1993.
-  S. M. Homayouni, D. B. M. M. Fontes, and J. F. Goncalves, “A multistart biased random key genetic algorithm for the flexible job shop scheduling problem with transportation,” Int. Trans. Oper. Res., Vol.30, No.2, pp. 688-716, 2020.
This article is published under a Creative Commons Attribution-NoDerivatives 4.0 Internationa License.