具有周期维护的最小化加权总完工时间的平行机调度研究  

Research on Parallel Machine Scheduling Problem with Periodic Maintenance to Minimize Total Weighted Completion Times

作　　者：周菊 

机构地区：[1]贵州大学数学与统计学院,贵州 贵阳

出　　处：《运筹与模糊学》2021年第3期274-281,共8页Operations Research and Fuzziology

摘　　要：针对具有周期维护的最小化加权总完工时间的平行机调度问题,首先证明了该调度问题是NP-难问题,并提出最优调度方案的4条性质。然后在WSPT规则的基础上结合工件在多机环境中的分配机制(JCT、MCT、BF)提出了WSPTJCT算法、WSPTMCT算法、WSPTBF算法以及ROPT算法,其中ROPT算法为其他3个算法的最优输出。最后通过数值实验对4个算法进行性能分析,结果显示:WSPTJCT算法、WSPTBF算法以及ROPT算法的性能与最大加工时长pmax呈倒U型;工件个数n越大,WSPTJCT算法、WSPTMCT算法、WSPTBF算法以及ROPT算法的性能越好。This paper tackles the parallel machine scheduling problem with periodic maintenance to minimize the weighted sum of completion times. This problem is proved to be NP-hard and four properties are proposed. Then, WSPTJCT algorithm, WSPTMCT algorithm and WSPTBF algorithm are proposed with three assignment mechanisms (JCT, MCT, BF) and WSPT rules. ROPT algorithm is the best one of the outputs of the three algorithms. Finally, the performance of the four algorithms is analyzed by numerical experiments. The results show that the performance of WSPTJCT algorithm, WSPTMCT algorithm, WSPTBF algorithm and ROPT algorithm is inverted U-shaped with the maximum processing time pmax and increases with the number of jobs n.

关 键 词：周期维护 平行机调度 WSPT规则 加权总完工时间 

分 类 号：TP3[自动化与计算机技术—计算机科学与技术]