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

富晓双，赵玉芳，田 野

(1.沈阳师范大学 数学与系统科学学院，辽宁 沈阳 110034；2.北京市第五中学通州校区，北京 101100)

0 引言

在大多数经典的排序问题中，假设工件的加工时间是常数.然而，在实际的生产过程中，当机器连续加工工件时，可能会出现退化现象，即工件在排序中的开始加工时间越晚，它的实际加工时间越长，例如钢铁生产、消防、资源分配等.Jatinder N.D.Gupta和Sushil K.Gupta[1],Browne和Yechiali[2]分别提出了退化工件的概念，工件j的实际加工时间为aj+bjt,bj>0,aj是工件j的基本加工时间，bj是退化率，t是工件j的开始加工时间，对于最大完工时间的问题，他们证明了工件按aj/bj不减顺序排序可以得到最优解.Mosheiov[3]研究了带有简单线性退化的单机排序问题，工件j的实际加工时间为pj=αjt,αj是退化率，t>0是工件j的开始加工时间，目标函数分别为最大完工时间、流程时间、总延误、延误工件数等，证明了这些问题都是多项式时间可解的.Bachman等[4]研究了带有退化工件的单机排序问题，目标为极小化总加权完工时间，证明了这个问题是NP-难的.王吉波等[5]研究了具有恶化效应和可控加工时间的单机排序问题，目标是确定工件的最优排序、最优资源分配和共同工期(松弛工期)，使所有工件的排序费用(包括提前时间、延误时间、共同工期(松弛工期))和资源的消耗费用的线性加权和最小,证明了此问题可以在多项式时间内求解.Ji和Cheng[6]研究了带有退化工件的平行机排序问题，目标为极小化总完工时间，对于这个NP-难问题，提出了一个FPTAS.此后，带有退化工件的问题受到了越来越广泛的关注.

在大多数的排序问题中，通常假设所有工件都必须在机器上加工，然而在实际的生产过程中，由于资源有限或考虑经济效益，决策者可能会选择这些工件中的一个子集来加工，而可能对未被加工的工件产生一些惩罚，即拒绝惩罚.Bartal等[7]首先提出了带有拒绝的排序问题，目标为极小化接受工件的最大完工时间与拒绝工件的总惩罚之和.对于m台平行机的情况，考虑离线问题：当m固定时，提出了一个FPTAS；当m任意时，提出了一个多项式时间近似策略(PTAS).Zhang等[8]研究了带有拒绝的平行机排序问题，目标为极小化总加权完工时间与拒绝工件总惩罚之和，给出了一个伪多项式时间的动态规划算法和一个FPTAS.Li和Yuan[9]讨论了带有退化工件和拒绝的同速机排序问题，含3个目标函数，分别为接受工件的最大完工时间与拒绝工件的总拒绝惩罚之和,接受工件的总加权完工时间与拒绝工件的总拒绝惩罚之和，以及接受工件的总完工时间与拒绝工件的总拒绝惩罚之和.对于前两个目标，当机器的数量固定时，分别提出两个FPTAS.对于后一个目标，当所有工件的退化率相同时，提出了时间复杂性为O(n2)的动态规划算法.Wu和Luo[10]研究了带有退化工件和拒绝的恒速机排序问题，其中工件的加工时间是它开始加工时间的简单的线性函数，目标是极小化接受工件的总完工时间与拒绝工件的总惩罚之和，给出了一个FPTAS.

在经典的排序问题中，经常假设机器一直可用.然而在许多实际情况中，由于机器发生故障或者维护期间无法加工工件，即产生了机器的不可用区间.Ji等[11]考虑了带有简单线性退化工件和不可用区间的单机排序问题，目标分别是极小化最大完工时间和总完工时间，证明了这两个问题都是NP-难的，并且分别提出伪多项式时间最优算法.此外，对于最大完工时间问题，提出一个FPTAS；对于总完工时间问题，提出了一种启发式算法.Zhao和Tang[12]研究了带有退化工件和不可用区间的平行机排序问题，目标是极小化总加权完工时间，提出了一个动态规划算法，对于其中一台机器上有一个不可用区间的特殊情况，给出了一个FPTAS.闫力君[13]研究了带有退化工件、拒绝和不可用区间的两台同速机排序问题，其中工件的加工时间为开始加工时间的简单的线性递增函数，目标为极小化接受工件的总加权完工时间与拒绝工件的总惩罚之和，对于这个NP-难问题，提出了一个FPTAS.

笔者考虑带有退化工件、拒绝及第一台机器带有一个固定的不可用区间的两台恒速机排序问题,目标是极小化接受工件的总完工时间与拒绝工件的总拒绝惩罚之和.对于这个NP-难问题，给出了一个FPTAS.

1 问题描述

2 修改目标函数

1)在机器M1上不可用区间T1之前工件的完工时间为：

……

……

2)在机器M1上不可用区间T2之后工件的完工时间为：

……

……

3)在机器M2上工件的完工时间为：

C[2,1]=t0+p[2,1]=t0+b[2,1]t0/s=t0(1+b[2,1]/s),

……

……

(1)

3 FPTAS

Ji和Cheng[6]说明了Pm|pj=αjsj,rj=t0|∑Cj是NP-难的，因此问题(1)至少是NP-难的.当不考虑拒绝时，对于Pm|pj=αjsj,rj=t0|∑Cj，每台机器上的工件按{αj}不减顺序排序是最优的.因此有以下引理：

下面介绍变量xj(j=1,2,…,n),如果工件Jj在机器M1的T1之前加工，令xj=1；如果工件Jj在机器M1的T2之后加工，令xj=2；如果工件Jj在机器M2上加工，令xj=3；如果工件Jj被拒绝，令xj=0.令X为所有向量x=(x1,x2,…,xn)的集合，其中xj∈{0,1,2,3},j=1,2,…,n,下面定义X上的初始和递归函数：

如果工件Jj被拒绝，则有:

gj(x)=10jkgj-1(x)+10jkej,xj=0;gj(x)=10kgj-1(x),xj≠0.

min{F(x)|x∈X}.

下面介绍由Kovalyov和Kubiak[15]给出的过程划分(A,h,δ),A⊆X,h(x)是X上的一个非负整数函数,且0<δ≤1,下面的描述给出划分(A,h,δ)的细节.

过程划分(A,h,δ):

以上过程划分(A,h,δ)需要O(|A|log|A|)时间，下面的过程划分(A,h,δ)的主要性质将在FPTAS中使用.

引理3[15]kh≤logh(x|A|)/δ+2，这里h(x|A|)≥1,0<δ≤1.

对于问题(1)的FPTAS的正式描述在下面给出.

算法Aε：

步骤二(产生集合Y1,Y2,…,Yn) 对集合Yj-1中的每个向量的第j个分量添加k(k=0,1,2,3)，产生新的4个向量，来组成新的向量集Y′j，对于每个x∈Y′j，计算如下：

步骤三(求解) 选择向量x0∈Yn,满足

F(x0)=min{F(x)|x∈Yn}=min{gn(x)+fn(x)|x∈Yn}.

定理1 对于问题(1)，算法Aε在O(n9L6/ε5)时间内找到一个解x0∈X，使得F(x0)≤(1+ε)F(x*).

|fj(x*[j])-fj(x(c1,c2,c3,d,e))|≤δfj(x*[j]),

且 |gj(x*[j])-gj(x(c1,c2,c3,d,e))|≤δgj(x*[j])成立.

令δ1=δ，考虑

因此，有:

(2)

(3)

也就是:

(4)

(5)

(6)

(7)

通过式(2)和式(6),有:

(δ+δ1(1+δ))fj+1(x*[j+1]).

类似地，有:

|gj+1(x*[j+1])-gj+1(x(a1,a2,a3,b,c))|≤(δ+δ1(1+δ))gj+1(x*[j+1]).

令δk=δ+δk-1(1+δ),k=2,3,…,n-j+1,有:

|fj+1(x*[j+1])-fj+1(x(a1,a2,a3,b,c))|≤δ2fj+1(x*[j+1]),|gj+1(x*[j+1])-gj+1(x(a1,a2,a3,b,c))|≤δ2gj+1(x*[j+1]).

对j+2,j+3,…,n重复论证，有x′∈Yn,使得:

|fn(x′)-fn(x*)|≤δn-j+1fn(x*),|gn(x′)-gn(x*)|≤δn-j+1gn(x*).

又通过引理4，有

因此，可以得到:

fn(x′)≤(1+δn-j+1)fn(x*)≤(1+ε)fn(x*),gn(x′)≤(1+δn-j+1)gn(x*)≤(1+ε)gn(x*).

综上所述,有

F(x′)=gn(x′)+fn(x′)≤(1+ε)F(x*).

因此，在算法Aε的第三步中，向量x0被选择满足F(x0)≤(x′)≤(1+ε)F(x*).

kC1≤2(n+1)log(T1)/ε+2≤2nL/ε+2，kC2≤2(n+1)log(T2(Bmax)n)/ε+2≤2n2L/ε+2，kC3≤2(n+1)log(t0(Bmax)n)/ε+2≤2n2L/ε+2，kf≤2(n+1)log(10nkt0n(Bmax)n)/ε+2≤2n2L/ε+2，kg≤2(n+1)log(10nknemax)/ε+2≤2nL/ε+2.

4 结论

笔者研究的是带有退化工件、拒绝和一个固定的不可用区间的两台恒速机排序问题.目标是极小化接受工件的总完工时间与拒绝工件的总惩罚之和.首先根据Kovalyov和Kubiak[15]提出的过程划分的要求，对目标函数进行了修改，然后说明该问题是NP-难的，进而利用过程划分的方法给出了一个FPTAS,最后确定了其时间复杂性为O(n9L6/ε5).由于机器带有不可用区间以及拒绝惩罚同时存在的现象很普遍，因此，进一步研究机器带有不可用区间以及拒绝惩罚的排序问题具有广泛的应用价值和实际意义.对于具有其他退化效应的函数问题以及机器具有不可用区间的其他种类机器的排序问题，还有待进一步研究.