Fast approximation algorithm for job sequencing with deadlines

The problem under consideration is to schedule jobs on a machine in order to minimize the sum of the penalties of delayed jobs. A “range-and-bound” method is proposed for finding a tight bound P? such that P?≤P1≤2P?, P1 being the minimal sum desired. The considered scheduling problem, for n jobs and accuracy ε > 0, is solved by a fully polynomial ε-approximation algorithm in $\text{O(n}{}^2\text{log n +}\text{n}{}^2\text{ε}\text{)}$ time and $\text{O(}\text{n}{}^2\text{ε}\text{)}$ space.