Single-machine scheduling to minimize maximum tardiness with minimum number of tardy jobs

This paper develops a branch and bound algorithm for solving the single-machine scheduling problem with the objective of minimizing the maximum tardiness of any job, subject to the constraint that the total number of tardy jobs is minimum. The algorithm uses a new lower bounding scheme, which is based on due date realaxation. Various dominance rules are used in the algorithm to limit the size of the search tree. Results of extensive computational tests show that the proposed branch and bound algorithm is effective in solving problems with up to 1000 jobs.