%0 Journal Article
%T 问题1|dj=d|ΣwjTj的一个全多项式近似方案<br>MINIMIZING THE SUM OF THE TOTAL COMPLETION TIME AND BATCHING COSTS ON BATCH PROCESSING MACHINE
%A 作者
%A 张喆
%A 李文华
%J 数学杂志
%D 2015
%X 本文对具有相同工期的单机最小化加权总误工问题进行了讨论.利用强NP-困难问题1||ΣwjTj的一个O(n2)时间的近似算法,把该算法得到的目标值作为问题1|dj=d|ΣwjTj的一个上界,对问题1|dj=d|ΣwjTj给出全多项式近似方案(FPTAS).已知问题1|dj=d|ΣwjTj是一般意义下的NP-困难问题,并且已经有人对该问题给出了拟多项式时间算法,本文对已有结果进行了扩充.<br>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
%K 相同工期 加权总误工 全多项式近似方案&lt
%K br&gt
%K common due date total weighted tardiness FPTAS
%U http://sxzz.whu.edu.cn/sxzz/ch/reader/view_abstract.aspx?file_no=20150432&flag=1