序列相关Setup单机调度的最小化最大拖期分枝定界算法

Branch-and-Bound Algorithm for Scheduling on Single Processor with Sequence-Dependent Setup Times to Minimize Maximum Tardiness

研究了具有序列相关Setup带交货期的单机调度NP问题,优化目标是最小化最大拖期.通过松弛子路径连通约束,提出了基于AP算法的下界方法.在算法下界的基础上,基于下界解建立了以改进Karp-Steel补偿启发式方法构成的上界构造方法.发现了反映问题特性的两条优势规则.最后依托Ragatz提出的分枝定界算法框架,引入上界和下界方法,以及两条优势规则,形成了求解该问题的分枝定界枚举算法.通过计算实验证明了算法的有效性.

The NP-hard problem of scheduling N jobs on a single processor with due dates and sequence-dependent setup times is studied, where the objective is to minimize the maximum tardiness. By relaxing the connectivity constraints to eliminate subtours the lower bound methods are proposed. Then, the upper bound methods are constructed by the modified Karp-Steel patching heuristic method based on the solution of lower bound problem. Two dominance rules are proved according to the natural features of the problem. An algorithm based on Ragatz＇s branch-and-bound permutation schemes is thus developed including the implementation of lower and upper bounding procedures and dominance roles. Computational experiments demonstrate the effectiveness of the algorithm.