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

摘要：

研究了机器带有一个不可用时间段的部分可续型单机最大完工时间调度问题,提出了一种启发式算法,证明了其相对误差界,并举例说明该界是紧的,而且据此推出了该算法对相应不可续问题的相对误差界,此界低于该问题现有算法的界.将此算法与其它算法进行了多方面的比较,包括利用随机数据进行实验以评估其相对误差,结果表明此算法是一种非常高效的启发式算法.

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

所属期刊栏目：26

分类号：TP273(自动化技术及设备)

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

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

页数：共7页

页码：500-506