Minimizing total tardiness on a single machine with sequence-dependent setup times

In this paper, we study the single machine scheduling problem with setup times for minimizing total tardiness. Such a problem is NP-hard and presents many difficulties to be solved. To reduce these difficulties, we propose a branch and bound algorithm. Our method is based on a new lower bound and is compared with Ragatz lower bound. New dominance rule and original exploration strategy are also proposed. Preliminary numerical simulations are encouraging and promising.