Single machine scheduling to minimize total weighted tardiness

The problem of minimizing the total weighted tardiness in single machine scheduling is a well-known strongly NP-hard problem. In this paper, we present an O(n2) time approximation algorithm for the problem, where n is the number of jobs. We further investigate different sub-models of the problem and obtain interesting properties and results. We begin with the model where the job due dates are affine-linear functions of their processing times and the job tardiness weights are proportional to their processing times. For this model, we classify the NP-hardness of the problem with respect to different affine-linear functions, and provide an O(nlogn) algorithm for each of the polynomially solvable problems. The second model we investigate is one where all job due dates have equal slacks, namely the SLK due-date model. Results for this model include: the problem is NP-hard in the ordinary sense; a pseudo-polynomial algorithm with time complexity O(n2P) is derived, where P is the sum of all of the processing times; and a fully polynomial-time approximation scheme is constructed.