APPROXIMATION ALGORITHMS FOR SCHEDULING A SINGLE-MACHINE TO MINIMIZE TOTAL LATE WORK

In the problem of scheduling a single machine to minimize total late work, there are n jobs to be processed, each of which has an integer processing time and an integer due date. The objective is to find a sequence of jobs which minimizes the total late work, where the late work for a job is the amount of processing of this job that is performed after its due date. Three families of approximation algorithms {E(k)}, {A(epsilon)} and (B(epsilon)} are presented. Contained in the first family is a (1 + 1/k)-approximation algorithm E(k), for any positive integer k less-than-or-equal-to n, which uses truncated enumeration; E(k) requires O(n(k+1)) time and O(n) space. The two other families {A(epsilon)} and B(epsilon)} are fully polynomial approximation schemes which are based on the rounding of state variables in dynamic programming formulations. In the superior scheme, for O < epsilon < 1, B(epsilon is a (1 + epsilon)-approximation algorithm which has a time requirement of O(n2/epsilon) and a space requirement of O(n/epsilon).