Approximation schemes for scheduling jobs with common due date on parallel machines to minimize total tardiness

The problem of scheduling n nonpreemptive jobs having a common due date d on m, m greater than or equal to 2, parallel identical machines to minimize total tardiness is studied. Approximability issues are discussed and two families of algorithms {A(epsilon)} and {B-epsilon} are presented such that (T-0 - T*)/(T* + d) less than or equal to epsilon holds for any problem instance and any given epsilon > 0, where T* is the optimal solution value and T-0 is the value of the solution delivered by A(epsilon) or B-epsilon. Algorithms A(epsilon) and B-epsilon run in O(n(2)m/epsilon(m-1)) and O(n(m+1)/epsilon(m)) time, respectively, if m is a constant. For m = 2, algorithm A(epsilon) can be improved to run in O(n(3)/epsilon) time.