问题1|dj=d|ΣwjTj的一个全多项式近似方案
MINIMIZING THE SUM OF THE TOTAL COMPLETION TIME AND BATCHING COSTS ON BATCH PROCESSING MACHINE

本文对具有相同工期的单机最小化加权总误工问题进行了讨论.利用强NP-困难问题1||ΣwjTj的一个O(n2)时间的近似算法,把该算法得到的目标值作为问题1|dj=d|ΣwjTj的一个上界,对问题1|dj=d|ΣwjTj给出全多项式近似方案(FPTAS).已知问题1|dj=d|ΣwjTj是一般意义下的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 problem 1||ΣwjTj 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|ΣwjTj a full polynomial time approximation scheme (FPTAS).For the problem of 1|dj=d|ΣwjTj,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