带不可用时间段和恶化加工时间的单机调度  

Single machine scheduling with an availability constraint and deteriorating jobs

作　　者：马英[1] 左春荣[1,2] 杨善林[1,2] 

机构地区：[1]合肥工业大学管理学院,安徽合肥230009 [2]教育部过程优化与智能决策重点实验室,安徽合肥230009

出　　处：《系统工程学报》2010年第3期371-378,共8页Journal of Systems Engineering

基　　金：国家高技术研究发展计划(863)重点资助项目(2008AA042901);国家自然科学基金重大研究计划资助项目(90718037);国家自然科学基金重点资助项目(70631003);国家自然科学基金资助项目(70871032);教育部博士点基金资助项目(200803590007)

摘　　要：对机器带有一个不可用时间段并且加工时间恶化的不可续型单机最大完工时间调度问题进行了研究,简单说明了此问题的NP-困难性,提出了一种动态规划算法以得到最优解,并给出了最短正常加工时间优先规则的最坏情况误差界限,最后提出了一种启发式算法来寻求近似解.实验结果表明该启发式算法无论从时间上还是解的质量上都是非常优异的,与动态规划给出的最优解相比,其平均相对误差仅为0.082%,最大误差也仅为3.448%,并且将近有一半的算例能得到最优解.This paper studies the single machine scheduling with an availability constraint and deteriorating jobs.The objective is to minimize makespan for nonresumable case.The NP-hardness of this problem is shown.A dynamic programming algorithm is proposed to obtain the optimal solution.Then an exact worst-case error bound of the shortest normal processing time first rule is given.At last,a heuristic algorithm is provided for searching the near-optimal solution.Experiment results show that this heuristic algorithm ...

关 键 词：单机调度 不可用时间段 恶化加工时间 动态规划 启发式算法 

分 类 号：O221[理学—运筹学与控制论]