A branch-and-bound algorithm to minimize total tardiness with different release dates

This article deals with the scheduling problem for minimizing total tardiness with unequal release dates. A set of jobs have to be scheduled on a machine able to perform only one job at a time. No preemptive job is allowed. This problem has been proved to be NP-hard. The paper proves some dominance properties, and provides a lower bound polynomially computed for this problem. On the basis of the previous results, a branch-and-bound algorithm is proposed, to solve the problem. This algorithm was tested on hard problems involving 30 jobs and also on relatively easy problems with up to 230 jobs. Detailed computational results are given.