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 nonpree mptively scheduling n jobs on a single machine to minimize total weigh ted late work, where the late work for a job is the amount of processi ng of this job that is performed after its due date. A family of appro ximation algorithms {DP(epsilon)} is derived. For any epsilon > 0, DP( epsilon) delivers a schedule having total weighted late work which doe s not exceed (1 + epsilon) times that of an optimal schedule. Since DP (epsilon) requires O(n3 log n + n3/epsilon) time, the family {DP(epsil on)} is a fully polynomial approximation scheme.