Minimizing late jobs in the general one machine scheduling problem

In this paper, the problem of minimizing the number of late jobs on one machine is investigated. The general problem is considered, i.e. with release dates and different due dates. A lower bound is first proposed, based on the relaxation of a Mixed-Integer Linear Programming formulation of the problem. A heuristic is then presented. Its effectiveness is computationally studied by comparison with the lower bound.