具有周期维护的最小化加权总完工时间的平行机调度研究
Research on Parallel Machine Scheduling Problem with Periodic Maintenance to Minimize Total Weighted Completion Times
摘要: 针对具有周期维护的最小化加权总完工时间的平行机调度问题，首先证明了该调度问题是NP-难问题，并提出最优调度方案的4条性质。然后在WSPT规则的基础上结合工件在多机环境中的分配机制(JCT、MCT、BF)提出了WSPTJCT算法、WSPTMCT算法、WSPTBF算法以及ROPT算法，其中ROPT算法为其他3个算法的最优输出。最后通过数值实验对4个算法进行性能分析，结果显示：WSPTJCT算法、WSPTBF算法以及ROPT算法的性能与最大加工时长pmax呈倒U型；工件个数n越大，WSPTJCT算法、WSPTMCT算法、WSPTBF算法以及ROPT算法的性能越好。
Abstract: 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.
文章引用：周菊. 具有周期维护的最小化加权总完工时间的平行机调度研究[J]. 运筹与模糊学, 2021, 11(3): 274-281. https://doi.org/10.12677/ORF.2021.113032

参考文献

[1] Wang, G., Sun, H. and Chu, C. (2005) Preemptive Scheduling with Availability Constraints to Minimize Total Weighted Completion Times. Annals of Operations Research, 133, 183-192. [Google Scholar] [CrossRef] 
[2] Xu, Z. and Xu, D. (2018) Single-Machine Scheduling with Workload-Dependent Tool Change Durations and Equal Processing Time Jobs to Minimize Total Completion Time. Journal of Scheduling, 21, 461-482. [Google Scholar] [CrossRef] 
[3] Kacem, I. and Chu, C. (2008) Efficient Branch-and-Bound Algorithm for Minimizing the Weighted Sum of Completion Times on a Single Machine with One Availability Constraint. International Journal of Production Economics, 112, 138-150. [Google Scholar] [CrossRef] 
[4] Huo, Y., Reznichenko, B. and Zhao, H. (2012) Minimizing Total Weighted Completion Time with Unexpected Machine Unavailability. Springer, Berlin, Heidelberg. [Google Scholar] [CrossRef] 
[5] Liu, P., Wang, C. and Lu, X. (2019) A Note on Minimizing Total Weighted Completion Time with an Unexpected Machine Unavailable Interval. Journal of Scheduling, 22, 255-262. [Google Scholar] [CrossRef] 
[6] Krim, H., Benmansour, R., Duvivier, D., et al. (2020) Heuristics for the Single Machine Weighted Sum of Completion Times Scheduling Problem with Periodic Maintenance. Computational Optimization and Applications: An International Journal, 75, 291-320. [Google Scholar] [CrossRef] 
[7] Sadfi, C., Penz, B., Rapine, C., et al. (2005) An Improved Approximation Algorithm for the Single Machine Total Completion Time Scheduling Problem with Availability Constraints. European Journal of Operational Research, 161, 3-10. [Google Scholar] [CrossRef] 
[8] Yang, S., Ma, Y., Xu, D., et al. (2011) Minimizing Total Completion Time on a Single Machine with a Flexible Maintenance Activity. Computers & Operations Research, 38, 755-770. [Google Scholar] [CrossRef] 
[9] 程贞敏, 李洪兴, 谷敏强. 最小化时间表长的平行机调度近似算法研究[J]. 北京师范大学学报(自然科学版), 2012, 48(1): 11-15.
[10] 曹雁卿. 具有周期维护的最小化工件完成时刻之和的平行机调度问题[J]. 江西科学, 2012, 30(4): 434-437.
[11] Graham, R.L., Lawler, E.L., Lenstra, J.K., et al. (1979) Optimization and Approximation in Deterministic Sequencing and Scheduling: A Survey. Annals of Discrete Mathematics, 5, 287-326. [Google Scholar] [CrossRef] 
[12] 何杰. 预防性维护下的混合型平行机调度问题研究[D]: [博士学位论文]. 长沙: 湖南大学, 2016.

为你推荐