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) 230238] by Kellerer and Strusevich. They proposed a fully polynomial time approximation scheme (FPTAS) of O((n6logW)/?3) O ( ( n 6 log W ) / ? 3 ) time complexity (W W is the sum of weights, n 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/?) O ( n 2 / ? ) time complexity. Moreover, a more effective and simpler dynamic programming algorithm is designed.
approximation tardiness common due date fptas scheduling