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

作者：杨善林; 马英; 鲁付俊

来源：系统工程学报, 2011, (04): 500-506.

• 单机调度
• 部分可续型
• 最长加工时间优先规则 single-machine scheduling
• semiresumable case
• longest processing time first rule

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

• 单位
  奇瑞汽车股份有限公司; 合肥工业大学