带有不可用区间及拒绝的最大完工时间单机排序问题

Scheduling Problem with Non-availability Interval and Rejection to Minimize the Makespan on a Single Machine

研究带有退化效应、拒绝工件及不可用区间的单机排序问题。该问题中,工件可以被排在机器上进行加工,也可以被拒绝,但是需要支付一定的拒绝惩罚。加工工件的开始加工时间越晚,则工件的实际加工时间越大。机器带有不可用区间,在此区间内任何工件都不能被加工。目标函数为所有拒绝工件的拒绝惩罚与接受工件的最大完工时间之和。首先给出了拟多项式时间的动态规划算法,最后得到了一个全多项式近似方案。

In this paper, we consider a single machine scheduling problems with a deteriorating effect, rejection penalty and an availa- bility interval. In this model, the processing time of a job is related with its starting time and jobs can be rejected. A job is either processed on the machine, or rejected, in which case a rejection penalty has to be paid. The machine can＇t process any job in the non-availability interval. The objective is to minimize the total rejection penalty of all the rejected jobs and the sum of the make span of the accepted jobs. First, we propose a pseudo-polynomial time dynamic programming algorithm. And then, we design a fully polynomial-time approximation scheme to solve the problem.