考虑维护且加工时间可变的单机调度问题研究

Study on Single-machine Problem with Maintenance and Variable Processing Time

解决了考虑多阶段时间窗(Time-window)[u,v]周期性维护的情况下,因工件加工存在学习效应,加工时间可变时目标函数为最小makespan的单机调度问题。证明了维护次数θ的上界θUB,首次提出虚拟维护的概念,在此基础上给出了两阶段模型来描述该问题。然后,本文给出了多项式时间复杂度的启发式算法,LPT-SPT算法;以及将初始解群和接受概率等概念引入变领域搜索算法(Variable Neighborhood Search,VNS),提出了改进的VNS算法,基于群的变领域搜索(Populated Variable Neighborhood Search,P-VNS)。最后,大量的实例验证了LPT-SPT算法和P-VNS有着较高的时间效率和很好的解精度。

This paper studies a single-machine scheduling problem with multi-phase maintenance and variable processing time to minimize the makespan.The upper bound θUB of the number of maintenance is proved.This problem is modeled by a two-phase BIP model based on the concept of virtual maintenance,which is first provided.Then,LPT-SPT algorithm with polynomial time complexity is given.And we also proposed the improved variable neighborhood search（VNS）,populated variable neighborhood search（P-VNS）,which is formulated by adding the solution population and accept probability to the basic VSN.Finally,computational results show that LPT-SPT and P-VNS perform well in the time efficiency and accuracy.