Scheduling n jobs on one machine to minimize the maximum lateness with a minimum number of tardy jobs

This study considers the problem of scheduling n jobs, each job having an arrival time, a processing time and a due date, on a single machine with the dual objective of minimizing the maximum lateness subject to obtaining a minimum number of tardy jobs. A simple procedure is introduced to identify two critical jobs from which the maximum lateness is generated for a given sequence. The sequence of jobs between two critical jobs inclusive is called the critical path. On the basis of the critical path, Carlier's binary branching rule is adopted to minimize the maximum lateness. By fixing the position of these two critical jobs for maintaining the minimum maximum lateness, the sequence can further be reordered to reduce the number of tardy jobs. A branch and bound algorithm is presented for this purpose. The algorithm can solve problems with 50 jobs optimally within 5 seconds on a PC Pentium-100.