| 平行机上一种带拒绝费用的排序问题研究 |
| |
| 引用本文： | 武光华. 平行机上一种带拒绝费用的排序问题研究[J]. 青岛大学学报(自然科学版), 2014, 0(2): 14-16 |
| |
| 作者姓名： | 武光华 |
| |
| 作者单位： | 潍坊科技学院,潍坊262700 |
| |
| 摘 要： | 主要研究了一种平行机上的排序问题。目标函数是使总完工时间最小但不能超过总拒绝费用的阀值。提出了该问题是NP一难的证明。针对该排序问题给出了伪多项式时间的动态规划算法且设计出了FPTAS。
|
| 关 键 词： | 近似算法 可拒绝排序 动态规划 FPTAS |
One Scheduling Problem with Rejection on Identical Parallel Machines |
| |
| WU Guang-hua. One Scheduling Problem with Rejection on Identical Parallel Machines[J]. Journal of Qingdao University(Natural Science Edition), 2014, 0(2): 14-16 |
| |
| Authors: | WU Guang-hua |
| |
| Affiliation: | WU Guang-hua (Weifang University of Science and Technology, Weifang 262700, China) |
| |
| Abstract: | In this paper, we consider the scheduling with rejection. The objective function is to minimize the total completion time of the processed ones when the total compression cost is given. Firstly. We prove that the problem is NP-hard. Then, we design a pseudo-polynomial time dynamic algorithm and FPTAS. |
| |
| Keywords: | approximation algorithm scheduling with rejection dynamic programming FPTAS |
| 本文献已被 维普 等数据库收录！ |
