A fully polynomial approximation scheme for the single machine weighted total tardiness problem with a common due date

详细信息	查看全文 | 推荐本文 |

• 作者：Hans Kellerer ; Vitaly A. Strusevich
• 关键词：Single machine scheduling ; Weighted total tardiness ; Dynamic programming ; FPTAS
• 刊名：Theoretical Computer Science
• 出版年：2006
• 期刊代码：114_03043975
• 类别：cp
• 出版时间：15 December 2006
• 卷：369
• 期：1-3
• 页码：230-238
• 文件大小：186 K

摘要

We develop a fully polynomial-time approximation scheme (FPTAS) for minimizing the weighted total tardiness on a single machine, provided that all due dates are equal. The FPTAS is obtained by converting an especially designed pseudopolynomial dynamic programming algorithm.