基于增强拓扑神经进化的等效并行机动态调度  

Dynamic scheduling of identical parallel machines based on neuro evolution of augmenting topologies

作　　者：陈亚绒[1,2] 周升伟 管在林 岳磊[3] CHEN Yarong;ZHOU Shengwei;GUAN Zailin;YUE Lei(School of Mechanical and Electronic Engineering,Wenzhou University,Wenzhou 325035,Zhejiang China;School of Mechanical Science and Engineering,Huazhong University of Science and Technology,Wuhan 430074,China;School of Mechanical and Electrical Engineering,Guangzhou University,Guangzhou 510006,China)

机构地区：[1]温州大学机电工程学院,浙江温州325035 [2]华中科技大学机械科学与工程学院,湖北武汉430074 [3]广州大学机械与电气工程学院,广东广州510006

出　　处：《华中科技大学学报（自然科学版）》2022年第6期111-117,共7页Journal of Huazhong University of Science and Technology(Natural Science Edition)

基　　金：国家自然科学基金资助项目(51705370,51905196)。

摘　　要：针对工件动态到达、处理时间不确定且机器须要弹性预防维护的等效并行机调度问题,以平均流程时间最小化为目标,提出了基于强化学习的动态调度方法.将调度过程作为马尔可夫决策过程,通过定义状态空间、行为空间、奖励函数与适应度函数,提出基于增强拓扑神经进化(NEAT)算法的动态调度方法.设计三种规模问题的实例,将基于NEAT的方法与最短路径树(SPT)、先装先卸(FIFO)调度规则及基于深度Q网络(DQN)的方法进行比较,结果表明:基于NEAT的方法相比基于DQN的方法能够以更短的训练时间获得更优、更稳健的调度方案,相比SPT和FIFO调度规则能够获得更优的目标值,利用训练好的NEAT模型对随机生成的大规模问题实例的快速高质量求解结果表明,基于NEAT的调度方法具有更好的泛化性能.Aiming at the identical parallel machine scheduling problem with dynamic job’s release,uncertain processing time and machine’s flexible preventive maintenance,the dynamic scheduling method based on reinforcement learning was studied to minimize the mean flow time.Taking the scheduling process as a Markov decision process,a dynamic scheduling method based on neuro evolution of augmenting topologies(NEAT) was established by defining state space,action space,reward function and fitness function. The proposed method was compared with scheduling rules of SPT(shortest path tree),FIFO(first in first out) and deep Q network(DQN) at three scale problems experiments. The results show that the NEAT-based method can obtain a better and more robust scheduling scheme in a shorter training time than the DQN-based method, and can obtain a better target value than the scheduling rules. The fast and high-quality solution of randomly generated large-scale problem instances using the trained NEAT model shows that the NEAT-based scheduling method has good generalization performance.

关 键 词：等效并行机调度 预防维护 强化学习 增强拓扑神经进化 深度Q网络 

分 类 号：TH166[机械工程—机械制造及自动化]