Abstract：To enhance the processing efficiency of vacuum heat treatment workshop with the goal of minimizing makespan, this paper constructs a mathematical model for mixed-batch scheduling that considers incompatible families of jobs. An improved memetic algorithm is proposed for dynamic scheduling of equipment. Typical local search strategies for batch scheduling are analyzed. The heuristic algorithms and memetic algorithms based on greedy and hill-climbing strategies are used as benchmark algorithms. The scheduling results of various algorithms are compared with the lower bound of the problem, and large-scale simulations show that the newly designed improved memetic algorithm outperforms other algorithms in a multi-job family environment, thus effectively improving scheduling performance.
黄锦钿. 基于改进文化基因算法的设备混合批动态调度[J]. 复杂系统与复杂性科学, 2025, 22(4): 71-77.
HUANG Jindian. Dynamic Scheduling for Mixed-batch Equipment Based on an Improved Memetic Algorithm[J]. Complex Systems and Complexity Science, 2025, 22(4): 71-77.
[1] FAN G Q, WANG J Q, LIU Z X. Two-agent scheduling on mixed batch machines to minimise the total weighted makespan[J]. International Journal of Production Research, 2023, 61(1):238257. [2] TAN M, YANG H L, SU Y X. Genetic algorithms with greedy strategy for green batch scheduling on non-identical parallel machines[J]. Memetic Computing, 2019, 11(4):439452. [3] SU B T, XIE N M, YANG Y J. Hybrid genetic algorithm based on bin packing strategy for the unrelated parallel workgroup scheduling problem[J]. Journal of Intelligent Manufacturing, 2021, 32: 957969. [4] 杨栋.差异工件并行批调度问题中遗传算法研究[J].计算机系统应用,2019,28(10):196200. YANG D. Research on Genetic algorithm for scheduling of parallel batch processing machines with non-identical job size[J]. Computer Systems & Applications,2019,28(10): 196200. [5] KUSUMA P D. Multi-objective batch scheduling in collaborative multi-product flow shop system by using non-dominated sorting genetic algorithm[J]. International Journal of Advanced Computer Science and Applications (IJACSA),2021,12(9):349357. [6] ARROYO J E C, LEUNG J Y T. Scheduling unrelated parallel batch processing machines with non-identical job sizes and unequal ready times[J]. Computers & Operations Research, 2017(78): 117128. [7] ZHOU H, PANG J, CHEN P K, et al. A modified particle swarm optimization algorithm for a batch-processing machine scheduling problem with arbitrary release times and non-identical job sizes[J]. Computers & Industrial Engineering, 2018, 123(SEP):6781. [8] SHAO W S, SHAO Z S, PI D H. A multi-neighborhood-based multi-objective memetic algorithm for the energy-efficient distributed flexible flow shop scheduling problem[J]. Neural Computing and Applications,2022,34(24): 2230322330. [9] GENG K F, YE C M. A memetic algorithm for energy-efficient distributed re-entrant hybrid flow shop scheduling problem[J]. Journal of Intelligent & Fuzzy Systems,2021,41(2): 39513971. [10] LIU Q H, LI X Y, GAO L,et al. A multiobjective memetic algorithm for integrated process planning and scheduling problem in distributed heterogeneous manufacturing systems[J]. Memetic Computing,2022,14(2): 193209. [11] 王海霞, 张兵, 芮延年, 等.基于改进文化基因算法的轧制规程优化[J].南京理工大学学报,2021,45(6):700707. WANG H X, ZHANG B,RUI Y N,et al. Rolling schedule optimization based on improved memetic algorithm[J]. Journal of Nanjing University of Science and Technology, 2021,45(6):700707. [12] SONG H B, YANG Y H, LIN J,et al. An effective hyper heuristic-based memetic algorithm for the distributed assembly permutation flow-shop scheduling problem[J]. Applied Soft Computing Journal,2023,135:110022. [13] QIU F, GENG N,WANG H G. An improved memetic algorithm for integrated production scheduling and vehicle routing decisions[J]. Computers and Operations Research,2023,152:106127. [14] LOU H Y, WANG X P, DONG Z M,et al. Memetic algorithm based on learning and decomposition for multiobjective flexible job shop scheduling considering human factors[J]. Swarm and Evolutionary Computation,2022,75:101204. [15] 袁帅鹏,李铁克,王柏琳.带运输时间混合流水车间成组调度的协同进化文化基因算法[J].控制理论与应用,2023,40(3):430440. YU S P, LI T K, WANG B L, Co-evolutionary memetic algorithm for the hybridflow shop group scheduling with transportation times[J]. Control Theory & Applications, 2023,40(3):430440.
