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³ log n + n³/ε) time, the family {DP_ε} is a fully polynomial approximation scheme.