问题1dj =dΣwj Tj 的一个全多项式近似方案

摘要

本文对具有相同工期的单机最小化加权总误工问题进行了讨论。利用强NP -困难问题1kΣwjTj 的一个O(n2)时间的近似算法，把该算法得到的目标值作为问题1|dj =d|ΣwjTj 的一个上界，对问题1|dj =d|Σwj Tj 给出全多项式近似方案(FPTAS)。已知问题1|dj =d|Σwj Tj 是一般意义下的NP-困难问题，并且已经有人对该问题给出了拟多项式时间算法，本文对已有结果进行了扩充。%The article is about the single machine scheduling problem with common due date to minimize total weighted tardiness. It’s also known that the problem1kΣwj Tj is strongly NP-hard and there is a O(n2) time approximation algorithm for this problem. The article took the objective value of this algorithm as the upper bound of our problem 1|dj =d|ΣwjTj and gave the problem 1|dj =d|Σwj Tj a full polynomial time approximation scheme (FPTAS). For the problem of 1|dj =d|Σwj Tj , it’s known that it is NP-hard in the ordinary sense. And it has been provided a pseudo-polynomial algorithm. The results have been expanded by this article.