机器在一段时间不可用条件下的单机调度问题

机器在一段时间不可用条件下的单机调度问题

马英;杨善林;储诚斌

【期刊名称】《合肥工业大学学报（自然科学版）》 【年(卷),期】2007(030)008

【摘要】文章对机器在一段给定时间内不可用情况下部分可恢复模式的单机调度问题进行了研究,当目标函数是最小化调度长度时,首先证明了LPT规则的误差上限是α/2,并举例说明该界限是紧的;同理可证该规则对不可恢复模式调度问题的误差上限是1/2,而不是有关文献所证明的1/3,同时上例也是1/3误差上限的反例;其次提出了一个启发式算法,该算法以LPT规则得到的解作为初始解,并结合基于成对交换技术的邻域搜索对解进行改进;当目标函数是最小化加权完成时间之和时,首先证明了最优调度的一个性质,并据此提出了动态规划算法. 【总页数】5页(1010-1014)

【关键词】单机调度;部分可恢复模式;LPT规则;动态规划 【作者】马英;杨善林;储诚斌

【作者单位】合肥工业大学,管理学院,安徽,合肥,230009;合肥工业大学,管理学院,安徽,合肥,230009;合肥工业大学,管理学院,安徽,合肥,230009;特鲁瓦工业大学,工业系统优化实验室,法国,特鲁瓦,100100 【正文语种】中文

【中图分类】TP273;O221 【相关文献】

1.带不可用时间段的单机调度问题的启发式算法 [J], 杨善林; 马英; 鲁付俊 2.带不可用时间段和恶化加工时间的单机调度 [J], 马英; 左春荣; 杨善林