中文摘要：

考虑的是机器需要维护,且需要对若干个退化工件进行加工的单机排序问题。所谓退化情况是指每个工件的加工时间是关于它本身的开始时间的一个线性单增函数。该问题中工件允许被拒绝,如果工件被拒绝,那么需要支付拒绝惩罚;如果被加工,那么工件被排在机器上（机器需要在某一个固定的时间段内进行维修以提高其加工速度,且在这段时间内机器不能加工任何工件）进行加工。目标是寻找一个最优排序使得被加工工件的总完工时间与被拒绝工件的总惩罚之和最小。对于单机情形,利用划分程序的方法给出了一个全多项式近似方案,并得出该近似方案的时间复杂性,说明该问题是一般意义下NP难的。

英文摘要：

In this paper we consider the scheduling problem of scheduling n deteriorating jobs on a single machine. Each jobs processing time is a linear non-decreasing function of its start time and jobs can be rejected. A job is either rejected, in which case a rejection penalty has to be paid, or accepted and processed on a single machine （requires a fixed time interval during which the machine is turned off and production is stopped）. The objective is to minimize the total completion time of the accepted jobs plus the total penalty of the rejected jobs. We give a fully polynomial time approximation scheme （FPTAS） for the case with a single machine and the time complexity, thus indicating that the problem is NP--hard in the ordinary sense only.