Journal of Shanghai Jiaotong University >
A Dual-System Reinforcement Learning Method for Flexible Job Shop Dynamic Scheduling
Received date: 2021-06-22
Online published: 2022-10-09
In the production process of aerospace structural parts, there coexist batch production tasks and research and development (R&D) tasks. Personalized small-batch R&D and production tasks lead to frequent emergency insertion orders. In order to ensure that the task is completed on schedule and to solve the flexible job shop dynamic scheduling problem, this paper takes minimization of equipment average load and total completion time as optimization goals, and proposes a dual-loop deep Q network (DL-DQN) method driven by a perception-cognition dual system. Based on the knowledge graph, the perception system realizes the representation of workshop knowledge and the generation of multi-dimensional information matrix. The cognitive system abstracts the scheduling process into two stages: resource allocation agent and process sequencing agent, corresponding to two optimization goals respectively. The workshop status matrix is designed to describe the problems and constraints. In scheduling decision, action instructions are introduced step by step. Finally, the reward function is designed to realize the evaluation of resource allocation decision and process sequence decision. Application of the proposed method in the aerospace shell processing of an aerospace institute and comparative analysis of different algorithms verify the superiority of the proposed method.
LIU Yahui, SHEN Xingwang, GU Xinghai, PENG Tao, BAO Jinsong, ZHANG Dan . A Dual-System Reinforcement Learning Method for Flexible Job Shop Dynamic Scheduling[J]. Journal of Shanghai Jiaotong University, 2022 , 56(9) : 1262 -1275 . DOI: 10.16183/j.cnki.jsjtu.2021.215
[1] | JI S X, PAN S R, CAMBRIA E, et al. A survey on knowledge graphs: Representation, acquisition, and applications[J]. IEEE Transactions on Neural Networks and Learning Systems, 2022, 33(2): 494-514. |
[2] | ISSA S, ADEKUNLE O, HAMDI F, et al. Knowledge graph completeness: A systematic literature review[J]. IEEE Access, 2021, 9: 31322-31339. |
[3] | CARVALHO A, CHOUCHENE A, LIMA T, et al. Cognitive manufacturing in industry 4.0 toward cognitive load reduction: A conceptual framework[J]. Applied System Innovation, 2020, 3(4): 55. |
[4] | LU Y Q, XU X, WANG L H. Smart manufacturing process and system automation: A critical review of the standards and envisioned scenarios[J]. Journal of Manufacturing Systems, 2020, 56: 312-325. |
[5] | ZHANG J, DING G F, ZOU Y S, et al. Review of job shop scheduling research and its new perspectives under Industry 4.0[J]. Journal of Intelligent Manufacturing, 2019, 30(4): 1809-1830. |
[6] | 巴智勇, 袁逸萍, 戴毅, 等. 考虑机器故障的作业车间调度方案鲁棒测度方法[J]. 计算机集成制造系统, 2020, 26(12): 3341-3349. |
[6] | BA Zhiyong, YUAN Yiping, DAI Yi, et al. Robustness measurement approach of job shop scheduling with machine breakdowns[J]. Computer Integrated Manufacturing Systems, 2020, 26(12): 3341-3349. |
[7] | 方佳, 陆志强. 考虑设备故障的鲁棒调度计划模板的建模优化[J]. 上海交通大学学报, 2020, 54(12): 1278-1290. |
[7] | FANG Jia, LU Zhiqiang. Modeling and optimization of robust scheduling template considering equipment failure[J]. Journal of Shanghai Jiao Tong University, 2020, 54(12): 1278-1290. |
[8] | GAO K Z, YANG F J, ZHOU M C, et al. Flexible job-shop rescheduling for new job insertion by using discrete jaya algorithm[J]. IEEE Transactions on Cybernetics, 2019, 49(5): 1944-1955. |
[9] | 王鹏飞. 群智能优化算法及在流水车间调度问题中的应用研究[D]. 长春: 吉林大学, 2019. |
[9] | WANG Pengfei. Swarm intelligence optimization algorithm and its application in flow shop scheduling problem[D]. Changchun: Jilin University, 2019. |
[10] | ZHOU B, BAO J S, LI J, et al. A novel knowledge graph-based optimization approach for resource allocation in discrete manufacturing workshops[J]. Robotics and Computer-Integrated Manufacturing, 2021, 71: 102160. |
[11] | CHAKRABORTTY R K, RAHMAN H F, RYAN M J. Efficient priority rules for project scheduling under dynamic environments: A heuristic approach[J]. Computers & Industrial Engineering, 2020, 140: 106287. |
[12] | 蒋小康, 张朋, 吕佑龙, 等. 基于混合蚁群算法的半导体生产线炉管区调度方法[J]. 上海交通大学学报, 2020, 54(8): 792-804. |
[12] | JIANG Xiaokang, ZHANG Peng, LYU Youlong, et al. Hybrid ant colony algorithm for batch scheduling in semiconductor furnace operation[J]. Journal of Shanghai Jiao Tong University, 2020, 54(8): 792-804. |
[13] | 王金凤, 陈璐, 杨雯慧. 考虑设备可用性约束的单机调度问题[J]. 上海交通大学学报, 2021, 55(1): 103-110. |
[13] | WANG Jinfeng, CHEN Lu, YANG Wenhui. A single machine scheduling problem considering machine availability constraints[J]. Journal of Shanghai Jiao Tong University, 2021, 55(1): 103-110. |
[14] | 杜轩, 潘志成. 聚类差分进化算法求解多目标工艺规划与调度集成问题[J]. 计算机集成制造系统, 2019, 25(7): 1729-1738. |
[14] | DU Xuan, PAN Zhicheng. Clustering and differential evolution algorithm for solving multi-objectives IPPS problem[J]. Computer Integrated Manufacturing Systems, 2019, 25(7): 1729-1738. |
[15] | 李聪波, 沈欢, 李玲玲, 等. 面向能耗的多工艺路线柔性作业车间分批优化调度模型[J]. 机械工程学报, 2017, 53(5): 12-23. |
[15] | LI Congbo, SHEN Huan, LI Lingling, et al. A batch splitting flexible job shop scheduling model for energy saving under alternative process plans[J]. Journal of Mechanical Engineering, 2017, 53(5): 12-23. |
[16] | PENG C, WU G L, LIAO T W, et al. Research on multi-agent genetic algorithm based on tabu search for the job shop scheduling problem[J]. PLoS One, 2019, 14(9): e0223182. |
[17] | KUNDAKCI N, KULAK O. Hybrid genetic algorithms for minimizing makespan in dynamic job shop scheduling problem[J]. Computers & Industrial Engineering, 2016, 96: 31-51. |
[18] | SHEN X N, YAO X. Mathematical modeling and multi-objective evolutionary algorithms applied to dynamic flexible job shop scheduling problems[J]. Information Sciences, 2015, 298: 198-224. |
[19] | WANG Z, ZHANG J H, YANG S X. An improved particle swarm optimization algorithm for dynamic job shop scheduling problems with random job arrivals[J]. Swarm and Evolutionary Computation, 2019, 51: 100594. |
[20] | 张洁, 张朋, 刘国宝. 基于两阶段蚁群算法的带非等效并行机的作业车间调度[J]. 机械工程学报, 2013, 49(6): 136-144. |
[20] | ZHANG Jie, ZHANG Peng, LIU Guobao. Two-stage ant colony algorithm based job shop scheduling with unrelated parallel machines[J]. Journal of Mechanical Engineering, 2013, 49(6): 136-144. |
[21] | 周亚勤, 杨长祺, 吕佑龙, 等. 双资源约束的航天结构件车间生产调度方法[J]. 机械工程学报, 2018, 54(9): 55-63. |
[21] | ZHOU Yaqin, YANG Changqi, LÜ Youlong, et al. Scheduling the production of aerospace structural parts with dual resource constraints[J]. Journal of Mechanical Engineering, 2018, 54(9): 55-63. |
[22] | 汪浩祥, 严洪森, 汪峥. 知识化制造环境中基于双层Q学习的航空发动机自适应装配调度[J]. 计算机集成制造系统, 2014, 20(12): 3000-3010. |
[22] | WANG Haoxiang, YAN Hongsen, WANG Zheng. Adaptive assembly scheduling of aero-engine based on double-layer Q-learning in knowledgeable manufacturing[J]. Computer Integrated Manufacturing Systems, 2014, 20(12): 3000-3010. |
[23] | WEI Y, PAN L, LIU S J, et al. DRL-scheduling: An intelligent QoS-aware job scheduling framework for applications in clouds[J]. IEEE Access, 2018, 6: 55112-55125. |
[24] | WANG Y D, LIU H, ZHENG W B, et al. Multi-objective workflow scheduling with deep-Q-network-based multi-agent reinforcement learning[J]. IEEE Access, 2019, 7: 39974-39982. |
[25] | LUO S. Dynamic scheduling for flexible job shop with new job insertions by deep reinforcement learning[J]. Applied Soft Computing, 2020, 91: 106208. |
[26] | HE Z L, TRAN K P, THOMASSEY S, et al. Multi-objective optimization of the textile manufacturing process using deep-Q-network based multi-agent reinforcement learning[J]. Journal of Manufacturing Systems, 2022, 62: 939-949. |
[27] | 林时敬, 徐安军, 刘成, 等. 基于深度强化学习的炼钢车间天车调度方法[J]. 中国冶金, 2021, 31(3): 37-43. |
[27] | LIN Shijing, XU Anjun, LIU Cheng, et al. Crane scheduling method in steelmaking workshop based on deep reinforcement learning[J]. China Metallurgy, 2021, 31(3): 37-43. |
[28] | BRANDIMARTE P. Routing and scheduling in a flexible job shop by tabu search[J]. Annals of Operations Research, 1993, 41(3): 157-183. |
[29] | 喻鹏, 张俊也, 李文璟, 等. 移动边缘网络中基于双深度Q学习的高能效资源分配方法[J]. 通信学报, 2020, 41(12): 148-161. |
[29] | YU Peng, ZHANG Junye, LI Wenjing, et al. Energy-efficient resource allocation method in mobile edge network based on double deep Q-learning[J]. Journal on Communications, 2020, 41(12): 148-161. |
[30] | 牟乃夏, 徐玉静, 李洁, 等. 遗传禁忌搜索算法收敛性和时间复杂度分析[J]. 河南理工大学学报(自然科学版), 2018, 37(4): 118-122. |
[30] | MOU Naixia, XU Yujing, LI Jie, et al. Analyses of convergence and time complexity of genetic tabu search algorithm[J]. Journal of Henan Polytechnic University (Natural Science), 2018, 37(4): 118-122. |
/
〈 |
|
〉 |