Fully polynomial time approximation scheme for the total weighted tardiness minimization with a common due date

This paper deals with the total weighted tardiness minimization with a common due date on a single machine. The best previous approximation algorithm for this problem was recently presented in [H. Kellerer, V.A. Strusevich, A fully polynomial approximation scheme for the single machine weighted total tardiness problem with a common due date, Theoretical Computer Science 369 (2006) 230–238] by Kellerer and Strusevich. They proposed a fully polynomial time approximation scheme (FPTAS) of O((n6logW)/ε3)O((n6logW)/ε3) time complexity (WW is the sum of weights, nn 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/ε)O(n2/ε) time complexity. Moreover, a more effective and simpler dynamic programming algorithm is designed.