A locally optimal insertion heuristic for a one-machine scheduling problem

This paper considers a one-machine scheduling problem with release dates and the minimization of the weighted number of late jobs. This problem is NP-hard. It develops a one-pass algorithm (insertion heuristic) which yields a locally optimal solution in a special left shift neighbourhood graph. Finally the paper investigates in which of the known polynomially solvable special cases the present heuristic yields an optimal solution.