The single-machine scheduling problem to minimize total tardiness subject to minimum number of tardy jobs

We consider the scheduling problem to minimize the total tardiness of a job set keeping the number of tardy jobs to its minimum value. A simple algorithm is presented to obtain an optimal sequence when the set of tardy jobs is specified. A set of properties is presented that explores the structure induced by the minimum number of tardy jobs requirement. The general problem is solved optimally by employing an efficient Branch & Bound (B&B) search that takes advantage of the theory developed. We identify special cases where the Moore-Hodgson algorithm can be applied to find the optimal tardy job set. Computational experiments show that the B&B algorithm solves relatively large instances in just a few seconds, on a personal computer.