为了提高真空热处理车间的加工效率,以最小化完工时间为目标,构建考虑不相容工件族的混合批调度数学模型,设计用于设备动态调度的改进文化基因算法。分析批调度典型局部搜索策略,并将基于贪婪策略和爬山策略的启发式算法和文化基因算法作为基准对比算法。各种算法的调度结果与问题最优解下界比较,通过大规模算例仿真验证发现:新设计的改进文化基因算法在多工件族环境下运算结果明显优于其他算法,能有效提升调度性能。
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.
[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.
