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 and are presented. Contained in the first family is a -approximation algorithm , for any positive integer , which uses truncated enumeration; requires time and space. The two other families and are fully polynomial approximation schemes which are based on the rounding of state variables in dynamic programming formulations. In the superior scheme, for is a -approximation algorithm which has a time requirement of and a space requirement of .