Solving multi-objective flexible job shop scheduling problems with an improved NSGA-Ⅱ based on DQN

doi:10.16731/j.cnki.1671-3133.2025.09.001

Abstract

Abstract: An improved Non-dominated Sorting Genetic Algorithm Ⅱ (NSGA-Ⅱ) based on the Deep Q-Network (DQN) is proposed to solve the Multi-Objective Flexible Job shop Scheduling Problem (MO-FJSP) with the goals of minimizing makespan and energy consumption. The Markov decision process and a reward function are defined in the DQN algorithm, considering the influence of selected machines on makespan and energy consumption both locally and globally. This approach enhances the quality of the initial population of the NSGA-Ⅱ. The elite retention strategy of the NSGA-Ⅱ is improved to ensure population diversity during execution and preserve high-quality individuals throughout the evolutionary process. The effectiveness of the DQN algorithm in generating initial solutions is validated by comparing its initial solutions with those generated by a greedy algorithm. Furthermore, the improved NSGA-Ⅱ based on the DQN algorithm is compared with other heuristic algorithms on standard and simulation cases, demonstrating its effectiveness in solving MO-FJSP.

Key words: Deep Q-Network (DQN) algorithm, multi-objective flexible job shop scheduling problem, reward function, Non-dominated Sorting Genetic Algorithm Ⅱ (NSGA-Ⅱ)

CLC Number:

TH165
TP18

ZHENG Guoliang, ZHANG Chaoyang, JI Weixi, YU Junjie. Solving multi-objective flexible job shop scheduling problems with an improved NSGA-Ⅱ based on DQN[J]. Modern Manufacturing Engineering, 2025, 540(9): 1-11.

References

[1] BRUCKER P, SCHLIE R. Job-shop scheduling with multi-purpose machines[J]. Computing, 1990, 45(4): 369-375.
[2] PEZZELLA F, MORGANTI G, CIASCHETTI G. A genetic algorithm for the Flexible Job-shop Scheduling Problem[J]. Computers & Operations Research, 2008, 35(10): 3202-3212.
[3] LIU Z, WANG J, ZHANG C, et al. A hybrid genetic-particle swarm algorithm based on multilevel neighbourhood structure for flexible job shop scheduling problem[J]. Computers & Operations Research, 2021, 135: 105431.
[4] WANG Z, HE M, WU J, et al. An improved MOEA/D for low-carbon many-objective flexible job shop scheduling problem[J]. Computers & Industrial Engineering, 2024, 188: 109926.
[5] 姜一啸, 吉卫喜, 何鑫,等基于改进非支配排序遗传算法的多目标柔性作业车间低碳调度[J]. 中国机械工程, 2022, 33(21): 2564-2577.
[6] SENG D, LI J, FANG X, et al. Low-Carbon Flexible Job-Shop Scheduling Based on Improved Nondominated Sorting Genetic Algorithm-Ⅱ[J]. International Journal of Simula-tion Modelling, 2018, 17: 712-723.
[7] MENG L, ZHANG C, ZHANG B, et al. MILP modeling and optimization of multi-objective flexible job shop scheduling problem with controllable processing times[J]. Swarm and Evolutionary Computation, 2023, 82: 101374.
[8] MNIH V, KAVUKCUOGLU K, SILVER D, et al. Human-level control through deep reinforcement learning[J]. Nature, 2015, 518(7540): 529-533.
[9] HAN B A, YANG J J. Research on Adaptive Job Shop Scheduling Problems Based on Dueling Double DQN[J]. IEEE Access, 2020, 8: 186474-186495.
[10] LEI K, GUO P, ZHAO W, et al. A multi-action deep reinforcement learning framework for flexible Job-shop scheduling problem[J]. Expert Systems with Applications, 2022, 205: 117796.
[11] CHEN R, YANG B, LI S, et al. A self-learning genetic algorithm based on reinforcement learning for flexible job-shop scheduling problem[J]. Computers & Industrial Engineering, 2020, 149: 106778.
[12] 李健, 李洹坤, 何鹏博,等.协同智能体强化学习算法的柔性作业车间调度方法研究[J]. 系统仿真学报,2024,36(11):2699-2711.
[13] 张凯, 毕利, 焦小刚. 集成强化学习算法的柔性作业车间调度问题研究[J]. 中国机械工程, 2023, 34(2): 201-207.
[14] SONG W, CHEN X, LI Q, et al. Flexible Job-Shop Scheduling via Graph Neural Network and Deep Reinforcement Learning[J]. IEEE Transactions on Industrial Informatics, 2023, 19(2): 1600-1610.
[15] LI R, GONG W, LU C. A reinforcement learning based RMOEA/D for bi-objective fuzzy flexible job shop scheduling[J]. Expert Systems with Applications, 2022, 203: 117380.
[16] BRANDIMARTE P. Routing and scheduling in a flexible job shop by tabu search[J]. Annals of Operations Research, 1993, 41(3): 157-183.
[17] 唐亮, 程峰, 吉卫喜,等. 改进ICA求解柔性作业车间插单重调度问题[J]. 计算机工程与应用, 2023, 59(21): 303-311.
[18] TIAN Y, XIANG X, ZHANG X, et al. Sampling Reference Points on the Pareto Fronts of Benchmark Multi-Objective Optimization Problems[M].[S.l.]:[s.n.], 2018.
[19] SCHOTT J R. Fault tolerant design using single and multicriteria genetic algorithm optimization[D]. Massachusetts: Massachusetts Institute of Technology,1995.
[20] ZITZLER E, THIELE L. Multiobjective evolutionary algorithms: a comparative case study and the strength Pareto approach[J]. IEEE Transactions on Evolutionary Computation, 1999, 3(4): 257-271.