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 and Bound (BandB) 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 BandB algorithm solves relatively large instances in just a few seconds, on a personal computer.