Approximation algorithms for minimizing the total weighted tardiness on a single machine

摘要

Given a single machine and a set of jobs with due dates, the classical NP-hard problem of scheduling to minimize total tardiness is a well-understood one. Lawler gave a fully polynomial-time approximation scheme (FPTAS) for it some 20 years ago. If the jobs have positive weights the problem of minimizing total weighted tardiness seems to be considerably more intricate, it. In this paper, we give some of the first approximation algorithms for it. We examine first the weighted problem with a fixed number of due dates and we design a pseudopolynomial algorithm for it. We show how to transform the pseudopolynomial algorithm to an FPTAS for the case where the weights are polynomially bounded. For the case with an arbitrary number of due dates and polynomially bounded processing times, we provide a quasipolynomial algorithm which produces a schedule whose value has an additive error proportional to the weighted sum of the due dates. We also investigate the performance of algorithms for minimizing the related total weighted late work objective.