一种带拒绝费用的排序问题研究  

One Scheduling Problem with Rejection

作　　者：武光华[1] 丽苑华[1] 

机构地区：[1]曲阜师范大学运筹与管理学院,山东日照276826

出　　处：《洛阳理工学院学报（自然科学版）》2010年第1期61-64,共4页Journal of Luoyang Institute of Science and Technology：Natural Science Edition

基　　金：国家自然科学基金资助项目(10671108)

摘　　要：主要研究了一种带拒绝费用的排序问题。目标函数是在不超过总拒绝费用阀值的前提下使最大完工时间最小。首先,证明了该问题是N P-难的;然后我们针对这个问题设计出了伪多项式时间的动态规划算法,并给出了FPTAS。In this paper, we mainly consider the scheduling with reiection. 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.

关 键 词：近似算法 可拒绝排序 动态规划 FPTAS 

分 类 号：I223[文学—中国文学]