Tardiness minimization on parallel machines

We consider the NP-hard problem of scheduling jobs on identical parallel machines to minimize total tardiness. We present properties that characterize the structure of an optimal schedule. We propose a branch and bound algorithm that incorporates the properties along with an efficient lower bounding scheme. We find that optimal solutions can be obtained in reasonable times for problem with up to 15 jobs. In the last part of the study we extend the results to uniform parallel machines.