New lower bound for single machine total tardiness problem with sequence dependent setup

A new Lower bound is present for the NP-hard problem of scheduling N jobs on a single machine with due dates, sequence-dependent setup times, and no preemption where the objective is to minimize the total tardiness. One branch-and-bound algorithm with the new lower bound is developed to demonstrate the effectiveness of lower bound. A comparison with Ragatz’s B&B approaches indicates that the lower bound is competitive.