FULLY POLYNOMIAL TIME APPROXIMATION SCHEME FOR TOTAL WEIGHTED TARDINESS MINIMIZATION UNDER A COMMON DUE DATE

摘要

This paper deals with an important scheduling problem and proposes a fully polynomial time approximation scheme for solving it. The problem -minimizing weighted total tardiness with a common due date on a single machine-was studied in [Theoretical Computer Science, 369, 230-238] by Kellerer and Strusevich. They proposed an FPTAS of O((n6 logW)/ε3) time complexity (W is the sum of weights, n is the number of jobs and ε is the error bound). For this problem we propose a new approach to obtain a more effective FPTAS of O(n2/ε) time complexity. Moreover, a more effective and simpler dynamic programming is designed.