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

One Scheduling Problem with Rejection on Identical Parallel Machines

主要研究了一种平行机上的排序问题。目标函数是使总完工时间最小但不能超过总拒绝费用的阀值。提出了该问题是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.