An algorithm for minimizing the range of lateness on a single machine

This paper considers the problem of minimizing the range of lateness on a single machine. All the algorithms in the literature for solving this problem are based on the branch-and-bound approach, which has an exponential time complexity. In this paper, the authors demonstrate that this problem can actually be solved in pseudo-polynomial time, and develop such an algorithm. Computational performance of this algorithm on problems with various sizes is provided.