带不可用时间段的单机调度问题的启发式算法  

A heuristic for single-machine scheduling with an availability constraint

作　　者：杨善林[1,2] 马英[1,2] 鲁付俊[1,3] 

机构地区：[1]合肥工业大学管理学院,安徽合肥230009 [2]教育部过程优化与智能决策重点实验室,安徽合肥230009 [3]奇瑞汽车股份有限公司,安徽芜湖241009

出　　处：《系统工程学报》2011年第4期500-506,共7页Journal of Systems Engineering

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

摘　　要：研究了机器带有一个不可用时间段的部分可续型单机最大完工时间调度问题,提出了一种启发式算法,证明了其相对误差界,并举例说明该界是紧的,而且据此推出了该算法对相应不可续问题的相对误差界,此界低于该问题现有算法的界.将此算法与其它算法进行了多方面的比较,包括利用随机数据进行实验以评估其相对误差,结果表明此算法是一种非常高效的启发式算法.This paper considers a semiresumable case of single machine makespan scheduling with an unavailability interval. Firstly, a heuristic is proposed, then its relative worst-case error bound is shown. Furthermore, an example is provided to show the tightness of this bound. Based on this, it is easy to deduce the error bound of this algorithm to the corresponding nonresumable case, which is lower than that of the existing algorithm for this problem. Comparisons between this heuristic and other algorithms are made from different aspects, including an experiment using random-generated data sets to evaluate its relative error. The experiment results show that this heuristic is quite effective.

关 键 词：单机调度 部分可续型 最长加工时间优先规则 

分 类 号：TP273[自动化与计算机技术—检测技术与自动化装置]