Dominance rules for single machine schedule with sequence dependent setup and due date

Some dominance rules are proposed for the problems of scheduling N jobs on a single machine with due dates, sequence dependent setup times and no preemption. Two algorithms based on Ragatz's branch and bound scheme are developed including the dominance rules where the objective is to minimize the maximum tardiness or the total tardiness. Computational experiments demonstrate the effectiveness of the dominance rules.