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]	LI Yingchun, NIE Aonan, YANG Mingxuan, ZHU Dingkang, QIU Ming, YANG Gengsheng. Research on Thermal Characteristics of Auxiliary Bearing in AMBs and Friction Reduction Design [J]. China Mechanical Engineering, 2024, 35(04): 646-655.
[2]	LIANG Yongbin, FU Guang, LIN Zhigui, HE Zhicheng, ZHANG Jialuo, CHEN Tao. Design of Lane Keeping Assist Systems Based on Improved Preview Control Model [J]. China Mechanical Engineering, 2024, 35(03): 548-558.
[3]	HUANG Wei, CHI Cheng. Analysis for Aero -elastic Characteristics of Prop-Rotor in Hover with a Swept Tip [J]. China Mechanical Engineering, 2024, 35(02): 191-200.
[4]	XU Zuolin, HUANG Chuanzhen, LIU Huanlian, LIU Dun. Coating Technology and Mechanism of Modified Diamond Powder by Surface Coating of WC Powders [J]. China Mechanical Engineering, 2024, 35(02): 208-214.
[5]	YUE Jianfeng, LONG Xinyu, HUANG Yunlong, GUO Jialong, LIU Wenji. On-line Identification of Narrow Gap P-GMAW Sidewall Fusion States Based on Arc Acoustic Signals [J]. China Mechanical Engineering, 2024, 35(02): 244-250，259.
[6]	DU Xu, CHANG Zexin, ZHENG Junqiang, REN Pengfei. A Real-time Tool Path Smoothing Algorithm Considering Joint Jerk Constraints [J]. China Mechanical Engineering, 2024, 35(02): 280-286.
[7]	SUN Yuxiang, CHEN Li, LONG Bo, WANG Yanping, LIU Shihua, JIA Kun. Intelligent Layout for Pipeline Supports of Nuclear Power Plant under Complex Load [J]. China Mechanical Engineering, 2024, 35(02): 317-323，336.
[8]	LI Mozhi, ZHU Wenfeng, WANG Shunchao. Roller Pose Compensation in Automotive Body Roll-hemming Forming Process with Adhesive for Dimensional Deviation [J]. China Mechanical Engineering, 2024, 35(02): 364-370.
[9]	WANG Weijun, YANG Guilin, DU Qinghao, CHEN Qingying, . Design of 3K Planetary Gear Reducers with No Backlash [J]. China Mechanical Engineering, 2024, 35(01): 36-44,55.
[10]	GAO Jin, CUI Haibing, FAN Tao, LI Ang, DU Zunfeng. A Structural Reliability Calculation Method Based on Adaptive Kriging Ensemble Model [J]. China Mechanical Engineering, 2024, 35(01): 83-92.
[11]	SUN Haitao, ZHAN Mei, FAN Xiaoguang, GUO Jing, HAN Chao, ZHANG Jun. Research Progresses and Prospects of Compression Molding of High-performance PBX [J]. China Mechanical Engineering, 2024, 35(01): 160-180.
[12]	ZHU Fuxian, QIU Gang, ZHU Xingmin, XU Xianyi, ZHOU Jinyu. Failure Mode and Progressive Damage Analyses of Carbon-glass Hybrid Composite Single Nail and Single Shear Bolted Joints [J]. China Mechanical Engineering, 2023, 34(23): 2781-2793.
[13]	HAO Zhuangzhuang, ZHANG Qingchun, HU Yunbo, GUO Yibin, WANG Donghua, LI Wanyou. Research on Influences of Tooth Friction and Geometric Eccentricity Errors on Mesh Stiffness of Profile Shifted Spur Gear Pairs [J]. China Mechanical Engineering, 2023, 34(23): 2812-2823.
[14]	YU Shubo, LIU Zhansheng, ZHAO Chen. Dynamics Simulation Data Driven Domain Adaptive Intelligent Fault Diagnosis [J]. China Mechanical Engineering, 2023, 34(23): 2832-2841.
[15]	LIU Xiaobao, YAN Qingxiu, YI Bin, YAO Tingqiang, GU Wenjuan. Optimization of Process Parameters in Process Manufacturing Based on Ensemble Learning and Improved Particle Swarm Optimization Algorithm [J]. China Mechanical Engineering, 2023, 34(23): 2842-2853.