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

作者：蒋志高,董明

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

发文机构：上海交通大学工业工程与物流管理系

关键词：时间窗维护学习效应虚拟维护LPT-SPTP-VNStime-window maintenancelearning effectvirtual maintenanceVNSP-VNS

分类号： F224[经济管理—国民经济]