Research on Flexible Job-shop Scheduling Problems with Integrated Reinforcement Learning Algorithm

doi:10.3969/j.issn.1004-132X.2023.02.010

Abstract

Abstract: The flexible job-shop scheduling problems were transformed into a Markov decision process， and an algorithm D5QN integrated with 5 kinds of deep Q-network (DQN) optimizations was proposed. In the constructing of Markov process， a set of features was extracted to describe the states， and 3 sets of actions were designed by composite rules. The rewards were mapped by direct and indirect methods. The proposed algorithm was compared with the algorithms based on rules， meta-heuristic， and other reinforcement learning， which verifies the proposed algorithm may further decrease the calculating time， and have feasibility and effectiveness.

Key words: , job scheduling, intelligent dispatching, Markov decision process, reinforcement learning

摘要： 将柔性作业车间调度问题转化为马尔可夫决策过程，提出了集成5种深度Q网络（DQN）优化的算法D5QN。构建马尔可夫过程中，提取一组特征来表述状态，通过调度规则的组合设计出三组动作，通过直接和间接两种方式共同描述奖励。与基于规则、元启发式和其他强化学习算法的比较证明，所提方法可进一步缩短求解时间，并具有可行性和有效性。

关键词: 作业调度, 智能调度, 马尔可夫决策过程, 强化学习

CLC Number:

TP39

ZHANG Kai, BI Li, JIAO Xiaogang. Research on Flexible Job-shop Scheduling Problems with Integrated Reinforcement Learning Algorithm[J]. China Mechanical Engineering, 2023, 34(02): 201-207.

张凯, 毕利, 焦小刚. 集成强化学习算法的柔性作业车间调度问题研究[J]. 中国机械工程, 2023, 34(02): 201-207.

References

［1］刘晓冰，焦璇，宁涛，等. 基于双链量子遗传算法的柔性作业车间调度［J］. 计算机集成制造系统， 2015， 21（2）：495-502.
LIU Xiaobing， JIAO Xuan， NING Tao， et al. Flexible Job Shop Scheduling Based on Double-chains Quantum Genetic Algorithm［J］. Computer Integrated Manufacturing System， 2015， 21（2）：495-502.
［2］彭建刚，刘明周，张铭鑫，等. 多目标柔性作业车间调度算法研究综述［J］. 中国机械工程， 2014， 25（23）：3244-3254.
PENG Jiangang， LIU Mingzhou， ZHANG Ming-xin， et al. Review on Scheduling Algorithms for MOFJSP［J］. China Mechanical Engineering， 2014， 25（23）：3244-3254.
［3］李益兵，黄炜星，吴锐. 基于改进人工蜂群算法的多目标绿色柔性作业车间调度研究［J］. 中国机械工程， 2020， 31（11）：1344-1350.
LI Yibing， HUANG Weixing， WU Rui. Research on Multi-objective Green Flexible Job-shop Scheduling Based on Improved ABC Algorithm［J］. China Mechanical Engineering， 2020， 31（11）：1344-1350.
［4］贺长征，宋豫川，雷琦，等. 柔性作业车间多自动导引小车和机器的集成调度［J］. 中国机械工程， 2019， 30（4）：438-447.
HE Changzheng， SONG Yuchuan， LEI Qi， et al. Research Integrated Scheduling of Multiple AGVs and Machines in Flexible Job Shops［J］. China Mechanical Engineering， 2019， 30（4）：438-447.
［5］张国辉，高亮，李培根. 改进遗传算法求解柔性作业车间调度问题［J］. 机械工程学报， 2009， 45（7）：145-151.
ZHANG Guohui， GAO Liang， LI Peigen. Improved Genetic Algorithm for the Flexible Job-shop Scheduling Problem［J］. Journal of Mechanical Engineering， 2009， 45（7）：145-151.
［6］陈魁，毕利. 考虑运输时间的多目标柔性作业车间调度研究［J］. 小型微型计算机系统， 2021， 42（5）：946-952.
CHEN Kui， BI Li. Research on Multi-objective Flexible Job Shop Scheduling Considering Transport Time［J］. Microcomputer Systems， 2021， 42（5）：946-952.
［7］靳彬锋，毕利. 基于遗传算法的多目标车间调度［J］. 组合机床与自动化加工技术， 2019（4）：157-160.
JIN Binfeng， BI Li. Multi-objective Shop Scheduling Based on Genetic Algorithm［J］. Modular Machine Tool & Automatic Manufacturing Technique， 2019（4）：157-160.
［8］王霄汉，张霖，任磊，等. 基于强化学习的车间调度问题研究简述［J］. 系统仿真学报， 2021， 33（12）：2782-2719.
WANG Xiaohan， ZHANG Lin， REN Lei， et al. Brief Review on Applying Reinforcement Learning to Job Shop Scheduling Problems［J］. Journal of System Simulation， 2021， 33（12）：2782-2719.
［9］XUE T， ZENG P， YU H. A Reinforcement Learning Method for Multi-AGV Scheduling in Manufacturing［C］∥2018 IEEE International Conference on Industrial Technology（ICIT）. Lyon， 2018：1557-1561.
［10］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.
［11］LUO S. Dynamic Scheduling for Flexible Job Shop with New Job Insertions by Deep Reinforcement Learning［J］. Applied Soft Computing， 2020， 91：106208.
［12］ZHANG C， SONG W， CAO Z， et al. Learning to Dispatch for Job Shop Scheduling via Deep Reinforcement Learning［J］. Advances in Neural Information Processing Systems， 2020， 33：1621-1632.
［13］FENG Y， ZHANG L， YANG Z， et al. Flexible Job Shop Scheduling Based on Deep Reinforcement Learning［C］∥2021 5th Asian Conference on Artificial Intelligence Technology（ACAIT）. Haikou， 2021：660-666.
［14］HAN B， YANG J. A Deep Reinforcement Learning Based Solution for Flexible Job Shop Scheduling Problem［J］. Int. J. Simul. Model. ， 2021， 20（2）：375-386.

[1]	ZHANG Yinan, DING Jianwan. Friction Model of Robot Joints Considering Influences of Temperature [J]. China Mechanical Engineering, 2023, 34(02): 127-134.
[2]	WANG Haiyan, ZHOU Zhitong, WU YeFU Qilin. Modeling of Cutting Force in Helical Milling of Titanium Alloys Based on Oblique Cutting Theory [J]. China Mechanical Engineering, 2023, 34(02): 142-147.
[3]	WANG Ziguang, LIU Jinxin, YIN Jian, ZHOU Ping, SHA Zhihua, KANG Renke. Surface Quality of Ultra-precision Grinding of Silicon with Fine Diamond Grinding Wheels [J]. China Mechanical Engineering, 2023, 34(02): 245-251.
[4]	HANG Yang, YAN Kanghao, HUANG Dan. Analyses of Friction and Sealing Characteristics of Piston/Bushing Interfaces Considering Elastic Deformations#br# [J]. China Mechanical Engineering, 2023, 34(01): 17-26.
[5]	YIN Haibin, TAO Jian, LI Qian, ZHOU Jia, . Analysis on Grasping Ability for a Soft Robotic Hand with Structural Decoupling of Actuator and Variable Stiffness Mechanisms [J]. China Mechanical Engineering, 2023, 34(01): 27-35.
[6]	HE Yufan, SUN Jianghong, GAO Feng, LI Naizheng, HE Xueping, WANG Junjian. Design,Analysis and Optimization of a Cone External Surface Mounting Manipulator [J]. China Mechanical Engineering, 2023, 34(01): 55-64.
[7]	XU Zhedong, HOU Gongyu, YANG Li, HUANG Xiaojun. Selection of Shield Construction Parameters in Specific Sections Based on e-SVR and Improved Particle Swarm Optimization Algorithm [J]. China Mechanical Engineering, 2022, 33(24): 3007-3014.
[8]	HE HonglinZ, HAO Weipeng, YU Zhihao, LONG Yufan, YAN Yinqi, LI Ji. Topological Dynamics Optimization of Constrained Damping Plates Based on Bilinear Material Interpolation Model [J]. China Mechanical Engineering, 2022, 33(23): 2783-2789，2878.
[9]	JIANG Chuangyu, ZHANG Baoqiang, CHEN Yun, WANG Cunfu, LUO Huageng, HU Jiexiang, CAO Longchao. Study on Mechanics Properties and Numerical Convergence of Gyroid Cellular Structures [J]. China Mechanical Engineering, 2022, 33(23): 2790-28000.
[10]	DING Yandong, LUO Nianmeng, YANG Aodi, WANG Shuting, ZHU Haoran, XIE Xianda. Efficient Multigrid Isogeometric Topology Optimization under Bézier Element Stiffness Mapping [J]. China Mechanical Engineering, 2022, 33(23): 2801-2810.
[11]	YANG Yuhao, ZHENG Wei, WANG Yingjun, . An Efficient Isogeometric Topology Optimization Method Using DOF Reduction and Convergence Acceleration [J]. China Mechanical Engineering, 2022, 33(23): 2811-2821.
[12]	MENG Liang, ZHONG Mingzhe, LI Wenbiao, XIA Liang, GAO Tong, ZHU Jihong, ZHANG Weihong, . Topology Optimization Design of Aero-engine External System Brackets for Additive Manufacturing [J]. China Mechanical Engineering, 2022, 33(23): 2822-2832.
[13]	ZOU Wuyou, DU Chun, AI Jianping, SHAN Bin. Optimization Design of TiO2 Porous Ceramic Structures for Catalyst Carrier Applications [J]. China Mechanical Engineering, 2022, 33(23): 2833-2843.
[14]	JIAO Chen, CHAO Long, ZHU Lei, SHEN Lida, LIANG Huixin, DAI Ning, WANG Changjiang, SUN Jun. Design and Manufacture Method of Bionic Porous Structures for Orthopedic Implants [J]. China Mechanical Engineering, 2022, 33(23): 2844-2850.
[15]	TANG Yongfeng, LU Ping, LIU Bin, JIANG Kaiyong, YAN Binggong, LIU Jiawei, HAN Wei, . Design and Mechanics Property Analysis for Different Graded Irregular Porous Structures [J]. China Mechanical Engineering, 2022, 33(23): 2859-2866.