| 摘要: |
| 本文对具有相同工期的单机最小化加权总误工问题进行了讨论.利用强NP-困难问题1||ΣwjTj的一个O(n2)时间的近似算法,把该算法得到的目标值作为问题1|dj=d|ΣwjTj的一个上界,对问题1|dj=d|ΣwjTj给出全多项式近似方案(FPTAS).已知问题1|dj=d|ΣwjTj是一般意义下的NP-困难问题,并且已经有人对该问题给出了拟多项式时间算法,本文对已有结果进行了扩充. |
| 关键词: 相同工期 加权总误工 全多项式近似方案 |
| DOI： |
| 分类号:O221.7 |
| 基金项目:国家自然科学基金资助(11401604;11401605);国家天元基金资助(11326191);河南省自然科学基金资助(132300410392). |
|
| MINIMIZING THE SUM OF THE TOTAL COMPLETION TIME AND BATCHING COSTS ON BATCH PROCESSING MACHINE |
|
ZHANG Zhe1, LI Wen-hua2
|
|
1.College of Science, Zhongyuan University of Technology, Zhengzhou 450007, China;2.Department of Mathematics, Zhengzhou University, Zhengzhou 450001, China
|
| Abstract: |
| 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. |
| Key words: common due date total weighted tardiness FPTAS |
