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

Single-machine rescheduling of minimizing the maximum lateness with the disruptive arrival of new jobs

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

Under an unexpected arrival of new jobs, this paper considers the single-machine maximum late- ness rescheduling problem subject to an upper limit on the total sequence disruption. Several problem-specific structural properties and two lower bounds related to partial sequences are first established. Subsequently, a two-stage heuristic algorithm and an exact branch-and-bound algorithm are developed to solve of this problem. In our numerical experiments, the efficiency of the branch-and-bound algorithm was comparatively examined for small-sized instances, and solution quality and applicability of the two-stage heuristic algorithm were ana- lyzed for instances with not less than 100 jobs. Experimental results reveal that the branch-and-bound algorithm significantly outperforms the CPLEX optimizer in execution time for instances with up to 16 jobs, and in case of tolerance rates not less than 0.6, or ratios of new jobs not less than 0.95 corresponding to tolerance rates less than 0.1, the two-stage heuristic algorithm is recommended for relatively large-sized instances.