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

摘要：

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

关键词：时间窗维护、学习效应、虚拟维护、LPT-SPT、P-VNS

所属期刊栏目：16

分类号：F224(经济计算、经济数学方法)

资助基金：国家高技术研究发展计划863项目2008AA042104;国家自然科学基金资助项目70871077

在线出版日期：2011-12-14（万方平台首次上网日期，不代表论文的发表时间）

页数：共7页

页码：68-74