Reinforcement learning NSGA-II for multi-objective flexible job shop scheduling
CSTR:
Author:
Clc Number:

TH11

  • Article
  • | |
  • Metrics
  • |
  • Reference [23]
  • |
  • Related [20]
  • | | |
  • Comments
    Abstract:

    Non-dominated sorting genetic algorithm II (NSGA-II) has the shortcomings of insufficient diversity, prematurity and local convergence in solving the multi-objective optimal scheduling problem in flexible job shop. In this study, an improved NSGA-II algorithm based on reinforcement learning (RLNSGA-II) is proposed. To avoid NSGA-II to fall into the problem of local convergence, a two-population evolution strategy is introduced. The sex determination method is used to split the population into two populations, and different cross mut-ation operators are used in the evolution process to increase the local and global search capabilities of the algorithm. In order to solve the problem of insufficient diversity caused by the NSGA-II elite strategy, multiple diversity metrics are integrated, and reinforcement learning is used to dynamically optimize the split ratio parameters in the population iteration process to maintain diversity and improve algorithm convergence performance. Finally, simulation experiments and performance analysis are carried out through Kacem standard calculation examples, verifying the effectiveness and superiority of RLNSGA-II.

    Reference
    [1] Kacem I, Hammadi S, Borne P. Approach by localization and multiobjective evolutionary optimization for flexible job-shop scheduling problems[J]. IEEE Transactions on Systems, Man, and Cybernetics, Part C (Applications and Reviews), 2002, 32(1):1-13.
    [2] Moslehi G, Mahnam M. A Paretoapproach to multi-objective flexible job-shop scheduling problem using particle swarm optimization and local search[J]. International Journal of Production Economics, 2011, 129(1):14-22.
    [3] 王思涵,黎阳,李新宇.基于鲸鱼群算法的柔性作业车间调度方法[J].重庆大学学报, 2020, 43(1):1-11.Wang S H, Li Y, Li X Y. An improved whale swarm algorithm for flexible job-shop scheduling problem[J]. Journal of Chongqing University, 2020, 43(1):1-11.(in Chinese)
    [4] Gong G L, Deng Q W, Gong X R, et al. A new double flexible job-shop scheduling problem integrating processing time, green production, and human factor indicators[J]. Journal of Cleaner Production, 2018, 174:560-576.
    [5] 曾强,常梦辉,王孟华,等.混合工作日历下柔性作业车间多目标调度优化方法[J].重庆大学学报, 2019, 42(7):10-26.Zeng Q, Chang M H, Wang M H, et al. Multi-objective optimization method for FJSP under mixed work calendars[J]. Journal of Chongqing University, 2019, 42(7):10-26.(in Chinese)
    [6] Deb K, Pratap A, Agarwal S, et al. A fast and elitist multiobjective genetic algorithm:NSGA-II[J]. IEEE Transactions on Evolutionary Computation, 2002, 6(2):182-197.
    [7] Seng D W, Li J W, Fang X J, et al. Low-carbon flexible job-shop scheduling based on improved nondominated sorting genetic algorithm-II[J]. International Journal of Simulation Modelling, 2018, 17(4):712-723.
    [8] 缪嘉成,李朝阳,陈兵奎.结合Kriging与改进NSGA-Ⅱ的RV减速器优化[J].重庆大学学报, 2021, 44(2):65-78.Miao J C, Li C Y, Chen B K. Optimization of an RV reducer by integrating Kriging with improved NSGA-Ⅱ[J]. Journal of Chongqing University, 2021, 44(2):65-78.(in Chinese)
    [9] 陈辅斌,李忠学,杨喜娟.基于改进NSGA2算法的多目标柔性作业车间调度[J].工业工程, 2018, 21(2):55-61.Chen F B, Li Z X, Yang X J. Multi-objective flexible job shop scheduling based on improved NSGA2 algorithm[J]. Industrial Engineering Journal, 2018, 21(2):55-61.(in Chinese)
    [10] 胡成玉,余果,颜雪松,等.基于改进多目标优化算法的分布式数据中心负载调度[J].控制与决策, 2021, 36(1):159-165.Hu C Y, Yu G, Yan X S, et al. Multi-objective optimization of energy and performance management in distributed data centers[J]. Control and Decision, 2021, 36(1):159-165.(in Chinese)
    [11] 程子安,童鹰,申丽娟,等.双种群混合遗传算法求解柔性作业车间调度问题[J].计算机工程与设计, 2016, 37(6):1636-1642.Cheng Z A, Tong Y, Shen L J, et al. Double population hybrid genetic algorithm for solving flexible job shop scheduling problem[J]. Computer Engineering and Design, 2016, 37(6):1636-1642.(in Chinese)
    [12] Chen Y, Hu J L, Hirasawa K, et al. Optimizing reserve size in genetic algorithms with reserve selection using reinforcement learning[C]//SICE Annual Conference 2007, September 17-20, 2007, Takamatsu. IEEE, 2007:1341-1347.
    [13] 王晓燕,刘全,傅启明,等.基于强化学习的多策略选择遗传算法[J].计算机工程, 2011, 37(8):149-152.Wang X Y, Liu Q, Fu Q M, et al. Multiple policy selection genetic algorithm based on reinforcement learning[J]. Computer Engineering, 2011, 37(8):149-152.(in Chinese)
    [14] 封硕,郑宝娟,陈文兴,等.支持强化学习RNSGA-Ⅱ算法在航迹规划中应用[J].计算机工程与应用, 2020, 56(3):246-251.Feng S, Zheng B J, Chen W X, et al. RNSGA-Ⅱ algorithm supporting reinforcement learning and its application in UAV path planning[J]. Computer Engineering and Applications, 2020, 56(3):246-251.(in Chinese)
    [15] Raghuwanshi M M, Kakde O G. Genetic algorithm with species and sexual selection[C]//2006 IEEE Conference on Cybernetics and Intelligent Systems. June 7-9, 2006, Bangkok, Thailand. IEEE, 2006:1-8.
    [16] 张超勇,饶运清,刘向军,等.基于POX交叉的遗传算法求解Job-Shop调度问题[J].中国机械工程, 2004, 15(23):2149-2153.Zhang C Y, Rao Y Q, Liu X J, et al. An improved genetic algorithm for the job shop scheduling problem[J]. China Mechanical Engineering, 2004, 15(23):2149-2153.(in Chinese)
    [17] 李密青,郑金华,肖桂霞,等.一种多目标进化算法的分布度评价方法[J].模式识别与人工智能, 2008,21(5):695-703.Li M Q, Zheng J H, Xiao G X, et al. A diversity metric for multi-objective evolutionary algorithm[J]. Pattern Recognition and Artificial Intelligence, 2008, 21(5):695-703.(in Chinese)
    [18] Kacem I, Hammadi S, Borne P. Pareto-optimality approach for flexible job-shop scheduling problems:hybridization of evolutionary algorithms and fuzzy logic[J]. Mathematics and Computers in Simulation, 2002, 60(3/4/5):245-276.
    [19] 赵博选,高建民,付颖斌,等.求解柔性作业车间调度问题的多策略融合Pareto人工蜂群算法[J].系统工程理论与实践, 2019, 39(5):1225-1235.Zhao B X, Gao J M, Fu Y B, et al. A multi-strategy integration Pareto artificial bee colony algorithm for flexible job shop scheduling problems[J]. Systems Engineering-Theory&Practice, 2019, 39(5):1225-1235.(in Chinese)
    [20] Huang X B, Guan Z L, Yang L X. An effective hybrid algorithm for multi-objective flexible job-shop scheduling problem[J]. Advances in Mechanical Engineering, 2018, 10(9):168781401880144.
    [21] 孟冠军,杨大春,陶细佩.基于混合人工蜂群算法的多目标柔性作业车间调度问题研究[J].计算机应用研究, 2019, 36(4):972-974,979.Meng G J, Yang D C, Tao X P. Study on multi-objective flexible Job-Shop scheduling problem based on hybrid artificial bee colony algorithm[J]. Application Research of Computers, 2019, 36(4):972-974,979.(in Chinese)
    [22] 王建华,潘宇杰,孙瑞.自适应Jaya算法求解多目标柔性车间绿色调度问题[J].控制与决策, 2021, 36(7):1714-1722.Wang J H, Pan Y J, Sun R. Multi-objective flexible job shop green scheduling problem with self-adaptiveJaya algorithm[J]. Control and Decision, 2021, 36(7):1714-1722.(in Chinese)
    [23] 吴贝贝,张宏立,王聪,等.基于正态云模型的状态转移算法求解多目标柔性作业车间调度问题[J].控制与决策, 2021, 36(5):1181-1190.Wu B B, Zhang H L, Wang C, et al. State transition algorithm based on normal cloud model for solving multiobjective flexible job shop scheduling problem[J]. Control and Decision, 2021, 36(5):1181-1190.(in Chinese)
    Cited by
    Comments
    Comments
    分享到微博
    Submit
Get Citation

尹爱军,闫文涛,张厚望.面向多目标柔性作业车间调度的强化学习NSGA-II算法[J].重庆大学学报,2022,45(10):113~123

Copy
Share
Article Metrics
  • Abstract:671
  • PDF: 1471
  • HTML: 1037
  • Cited by: 0
History
  • Received:November 26,2020
  • Revised:May 12,2021
  • Online: November 01,2022
Article QR Code