带到达时间、不可用区间、拒绝工件的单机排序问题

Single Machine Scheduling Problem with Release Dates,Rejection and an Unavailable Interval

考虑的是带有到达时间、拒绝工件、不可用区间的单机排序问题。若工件被拒绝加工,厂家必须支付一定的拒绝惩罚;若工件被接受,则把工件放在机器上进行加工。机器带有不可用区间,在不可用区间内不能加工工件,并且在同一时刻至多加工一个工件。本文的目标函数是极小化所有接受工件的时间表长与所有拒绝工件的拒绝惩罚之和。首先给出了一个近似算法,并通过引理1证明出此算法是3-因子算法;其次提出了一个动态规划算法,然后通过修改这个动态规划算法的执行过程来减少运行时间,进而得到了一个全多项式时间近似方案,证明出该方案的时间复杂性为O(n2/ε)

In this paper, we consider the single machine scheduling problem with release dates, rejection and an unavailable inter val. A job is either rejected, in which a rejection penalty has to be paid, or accepted and processed on the machine. The machine is unavailable between T~ and 7＂2 and it can process most one job at a time. The objective is to minimize the sum of the makespan of the accepted jobs and total rejection penalty of the rejected jobs. Firstly we propose a 3-approximation algorithm by lemma 1. Sec- ondly we give a dynamic programming algorithm and reduce the running time by modifying the execution of the dynamic program- 2 ming algorithm. Finally we obtain a fully polynomial-time approximation scheme for this problem, its running time is （O JB（ SX n 2 ε SX） JB .