新工件到达干扰下单机最大延迟时间重调度

摘要

在一批新工件突然到达的干扰条件下,研究了总序位干扰量受上限的单机最大延迟时间重调度问题.在建立起若干结构化占优性质和针对部分排序的两种下界计算式的基础上,开发了含两阶段的启发式算法以及精确求解问题的分支定界算法.通过数值实验对比考察了分支定界算法在较小规模算例上的计算效率,并分析了两阶段启发式算法在较大规模算例(总工件数n不小于100)上的解质量与适用条件.实验结果表明,所提分支定界算法在n不超过16算例上的计算耗时显著优于CPLEX优化软件;对于干扰容许率不小于0.6,或者新工件比例不小于0.95而干扰容许率在0.1以内的较大规模算例,宣采用所提出的两阶段启发式算法进行求解.