A Branch and Bound Method to Minimize the Number of Late Jobs on a Single Machine

The 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, 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. Numerical experiments are presented. 1 Introduction This study concerns the general one-machine scheduling problem denoted by 1jr j j P U j in the standard classification. A set J of n jobs has to be scheduled on a single machine, no 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 must be completed before its due date d j . The start time of job J j is denoted by t j (t j r ..