A fully polynomial approximation scheme for scheduling a single machine to minimize total weighted late work

This paper studies approximation algorithms for the problem of nonpreemptively scheduling n jobs on a single machine to minimize total weighted late work, where the late work for a job is the amount of processing of this job that is performed after its due date. A family of approximation algorithms {DPÅ∈} is derived. For any ∈>0, DPÅ∈ delivers a schedule having total weighted late work which does not exceed (1+∈) times that of an optimal schedule. Since DPÅ∈ requires O(n³logn+n³/∈) time, the family {DPÅ∈} is a fully polynomial approximation scheme.