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 = 2, parallel identical machines to minimize total tardiness is studied. Approximability issues are discussed and two families of algorithms {Ae} and {Be} are presented such that (T⁰ − T^*)/(T^* + d) = e holds for any problem instance and any given e > 0, where T^* is the optimal solution value and T⁰ is the value of the solution delivered by Ae or Be. Algorithms Ae and Be run in O(n^2m/e^m-1) and O(n^m+1/e^m) time, respectively, if m is a constant. For m = 2, algorithm Ae can be improved to run in O(n³/e) time.