Hide/Show Apps

Tardiness minimization on parallel machines

1998-07-01
Azizoğlu, Meral
KIRCA, ÖMER
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 problems with up to 15 jobs. In the last part of the study we extend the results to uniform parallel machines.