An efficient formulation for minimizing the number of late jobs in single-machine scheduling

A new mixed-integer linear programming formulation for the minimization of the number of late jobs on a single machine is presented. The general problem is considered, i.e., when release dates and due dates can be different. This formulation is compared to one that was investigated in a previous work, and is shown to be much more interesting. The new modeling, not only allows the same lower bound to be determined faster, but can readily be extended to the weighted case. Some powerful cuts are also proposed, that were not valid in the previous formulation, which improve the quality of the bound. Some computational experiments are presented.