单机序列相关Setup最小化最大拖期算法

Algorithm for single machne schedule with sequence dependent setup to minimize maximum tardiness

研究了一个具有序列相关Setup带交货期的单机调度NP问题,优化目标是最小化最大拖期。提出了一个求解该问题的分枝定界枚举算法,其中包括确定问题上界和下界的方法,以及两条优势规则。计算实验证明了本文提出算法的有效性。

The NP-hard problem of scheduling N jobs on a single machine with due dates, sequence-dependent setup was addressed, where the objective was to minimize the maximum tardiness. An algorithm based on branchand-bound permutation schemes was developed including the implementation of lower and upper bounding procedures, and two dominance rules. Computational experiments demonstrate the effectiveness of the algorithm.