带有退化、拒绝和不可用区间的恒速机排序

Uniform machine scheduling problem with deteriorating jobs,rejection and a fixed non-availability interval

考虑带有退化工件、拒绝和不可用区间的2台恒速机排序问题,其中一台机器上带有一段固定的不可用区间。该问题以实际生产环境为背景来研究机器的工件调度问题。在此模型中,每个工件的实际加工时间与它的基本加工时间、退化率和开始加工时间有关,工件的实际加工时间是其开始加工时间的线性递增函数,工件可以被拒绝,被拒绝的工件需要支付惩罚成本,在不可用区间内,机器无法加工工件。目标是极小化接受工件的最大完工时间与被拒绝工件的总拒绝惩罚之和。对于这个NP-难问题,在不可用区间前、后及另一台机器上,工件按{aj/bj}不减顺序排列可以得到最优解,通过过程划分的方法,提出了一个完全多项式时间近似策略(FPTAS),最后确定了其时间复杂性为O(n^(6)L^(4)/ε^(3))。

In this paper we consider scheduling deteriorating jobs on two uniform-machines with rejection and a fixed non-availability internal.This problem studies the scheduling of jobs in the background of actual production environment.In the model,the actual processing time of each job is related to its basic processing time,deteriorating rate and its starting time,the actual processing time of a job is a linear increasing function of its starting time,jobs can be rejected by paying penalties.The machine cannot process the job in the non-availability internal.The objective is to minimize the sum of the makespan of the accepted jobs and the total penalty of the rejected jobs.For the NP-hard problem,the optimal solution can be obtained by sequencing in nondecreasing order of{aj/bj}of the job before,after the unavailable interval and another machine.Then,according to the procedure partition,we present a fully polynomial-time approximation scheme(FPTAS).The time complexity of the FPTAS is O(n^(6)L^(4)/ε^(3)).