Tardiness minimization on parallel machines

Azizoğlu, Meral
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.

Citation Formats
M. Azizoğlu and Ö. KIRCA, “Tardiness minimization on parallel machines,” International Journal of Production Economics, vol. 55, no. 2, pp. 163–168, 1998, Accessed: 00, 2020. [Online]. Available: https://hdl.handle.net/11511/34448.