平行机上一种带拒绝费用的排序问题研究  

One Scheduling Problem with Rejection on Identical Parallel Machines

作　　者：武光华[1] 

机构地区：[1]潍坊科技学院,潍坊262700

出　　处：《青岛大学学报（自然科学版）》2014年第2期14-16,共3页Journal of Qingdao University(Natural Science Edition)

摘　　要：主要研究了一种平行机上的排序问题。目标函数是使总完工时间最小但不能超过总拒绝费用的阀值。提出了该问题是NP-难的证明。针对该排序问题给出了伪多项式时间的动态规划算法且设计出了FPTAS。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.

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

分 类 号：O223[理学—运筹学与控制论]