Minimizing the number of tardy jobs for the single machine scheduling problem: MIP‐based lower and upper bounds

This paper considers the problem of scheduling n jobs on a single machine. A fixed processing time and an execution interval are associated with each job. Preemption is not allowed. The objective is to find a feasible job sequence that minimizes the number of tardy jobs. On the basis of an original mathematical integer programming formulation, this paper shows how good‐quality lower and upper bounds can be computed. Numerical experiments are provided for assessing the proposed approach.