| 一种带拒绝费用的排序问题研究 |
| |
| 引用本文： | 武光华,丽苑华.一种带拒绝费用的排序问题研究[J].洛阳工业高等专科学校学报,2010,20(1). |
| |
| 作者姓名： | 武光华 丽苑华 |
| |
| 作者单位： | 曲阜师范大学运筹与管理学院,山东,日照,276826 |
| |
| 基金项目： | 国家自然科学基金资助项目(10671108) |
| |
| 摘 要： | 主要研究了一种带拒绝费用的排序问题。目标函数是在不超过总拒绝费用阀值的前提下使最大完工时间最小。首先,证明了该问题是N P-难的;然后我们针对这个问题设计出了伪多项式时间的动态规划算法,并给出了FPTAS。
|
| 关 键 词： | 近似算法 可拒绝排序 动态规划 FPTAS |
One Scheduling Problem with Rejection |
| |
| WU Guang-hua,YUAN Li-hua.One Scheduling Problem with Rejection[J].Journal of Luoyang Technology College,2010,20(1). |
| |
| Authors: | WU Guang-hua YUAN Li-hua |
| |
| Institution: | College of Operations Research and Management Science/a>;Qufu Normal University/a>;Rizhao 276826/a>;China |
| |
| Abstract: | In this paper,we mainly consider the scheduling with rejection.The objective function is to minimize the maximum 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 work out the FPTAS. |
| |
| Keywords: | approximation algorithm scheduling with rejection dynamic rules |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
|
