Single machine scheduling to minimize the number of early and tardy jobs

The authors study single machine scheduling problems with the objective of minimizing the number of early and tardy jobs. Several cost structures are considered: job-independent, job-dependent and symmetric, and job-dependent and asymmetric. The first two problem-classes are shown to be polynomially solvable, whereas the latter is shown to be NP-hard, and heuristic solution methods are introduced. An extensive numerical study tests the performance of the proposed algorithms. Finally, separate treatment is given to the pre-emptive versions of the above models.