两台平行机环境下加工时间退化的可拒绝排序问题

Parallel-machine Scheduling Problem with Deteriorating Jobs and Rejection

研究两台平行机环境下加工时间线性退化的可拒绝排序问题,工件的实际加工时间是关于该工件开始加工时间的线性函数,每个工件都有一个独立的截止工期,在截止工期之前或之后完工的任务将分别受到提前和误工工件惩罚。工件允许被拒绝,如果工件被拒绝则需要支付一定的拒绝费用。目标是分别确定接受工件和拒绝工件的任务集合,找到接受任务的最优排序和每个被接受工件的最优任务工期最小化工期、误工工件惩罚、总完工时间以及被拒绝工件的惩罚费用之和。证明了此NP难问题可以通过动态规划方法求得最优解,并通过动态规划运用简化执行空间的方法给出了复杂度为O n5 D2/ε()2的全多项式近似策略(FPTAS),其中n表示工件的数量,ε是允许误差界。

In this paper,we study parallel-machine due-date assignment problem and scheduling with linear deteriorating jobs,the actual processing time of each job is a linear function of the starting time.Each job has an independent due-date;jobs completed before or after the due-date are penalized according to their earliness or tardiness values.Rejection is allowed in this problem,if a job is rejected,a certain amount of rejection fee must be paid.The objective is to determine the optimal scheduling and due-date of the accepted jobs to minimize the sum of due-dates,the weighted number of tardiness jobs,the total completion time and the rejection cost.We show that the NP-hard problem can be solved by a dynamic programming,finally,a fully polynomial-time approximation scheme in O（n5 D2/ε2）is given for the problem,where nis the number of the jobs,εis the error bound,D=max{lnamax,ln（1＋b）}.