An Exact Method to Minimize the Number of Tardy Jobs in Single Machine Scheduling

This paper considers the problem of scheduling n jobs on a single machine to minimize the number of tardy jobs (or late jobs). Each job has a release date, a processing time and a due date. The general case with non-equal release dates and different due dates is considered. Using new and efficient lower bounds and several dominance rules, a branch and bound scheme is proposed based on the definition of a master sequence, i.e., a sequence containing at least an optimal sequence. With this procedure, 95% of 140-job instances are optimally solved in a maximum of one-hour CPU time. 1 Introduction This study concerns the general one-machine scheduling problem denoted by 1jr j j P U j in the standard classification [5]. A set J of n jobs has to be scheduled on a single machine, preemption is not allowed, no precedence relation among jobs is assumed, and only one job can be processed at a time. Each job J j has a release date r j , needs p j time units to be processed on the machine, and m..