带有退化维护活动和工件可拒绝的非同类机排序问题.pdf

OperationsResearchTransactionsSep.,2023Vol.27No.320233年9 月运筹学学报第2 7 卷第3 期DOI:10.15960/ki.issn.1007-6093.2023.03.011带有退化维护活动和工件可拒绝的非同类机排序问题*高洁1邹娟1隋玉康1张玉忠2，摘要本文研究了带有退化维护活动和工件可拒绝的非同类机排序问题。每台机器至多执行一次退化维护活动，退化维护活动的维护时长是其开始时刻的线性非减函数。工件或者被加工并支付生产成本，或者被拒绝并支付拒绝成本。目标是确定每台机器上退化维护活动的位置与所有接受工件的加工顺序使所有接受工件的排序指标、生产成本及所有拒绝工件的拒绝惩罚之和达到最小。当排序指标为最大完工时间时，我们给出一个最坏性能比为2 的近似算法。当排序指标为总完工时间、机器总负载及完工时间的总绝对偏差时，我们指出这三个问题都是在多项式时间内可解的。关键词排序，非同类机，退化维护活动，近似算法中图分类号0 2 2 1.72010数学分类号9 0 B35Unrelated parallel-machine scheduling withdeteriorating maintenance activitiesand job rejection*GAO JielZOU JuanlSUI YukanglZHANG Yuzhong2,AbstractWe study unrelated parallel-machine scheduling problems with deteri-orating maintenance activities and job rejection.Each machine has at most one dete-riorating maintenance activity throughout the scheduling horizon.The duration of themaintenance activity increases linearly with its starting time.Each job is either pro-cessed and it incurs a production cost,or is rejected with a penalty cost.The objectiveis to find the position of the maintenance activity of each machine and the sequence ofthe accepted jobs such that the scheduling cost of all accepted jobs plus the total cost ofrejecting and processing jobs is minimized.When the scheduling cost is the makespan,we provide an approximation algorithm with worst-case ratio of 2.When the schedulingcosts are the total completion time,the total machine load and the total absolute devia-tion of completion times,we show that the three versions of the scheduling problem canbe optimally solved in polynomial time.Keywordsscheduling,unrelated machine,deteriorating maintenance activity,approximation algorithmChinese Library Classification0221.7收稿日期：2 0 2 2-0 1-18*基金项目：国家自然科学基金（No.12271295)1.曲阜师范大学数学科学学院，山东曲阜2 7 316 5；Schoolof Mathematical Sciences，Q u f u No r ma lUniversity,Qufu 273165,Shandong,China2曲阜师范大学运筹学研究院，山东日照2 7 6 8 2 6；Institute of OperationResearch，Q u f u No r ma lUniversity,Rizhao 276826,Shandong,China十通信作者E-mail:13827卷高洁，邹女娟，隋玉康，张玉忠2010 Mathematics Subject Classification 90B35在实际生产环境中，由于预防性维护和机器故障的存在，机器在加工工件的过程中并不是始终可用的。机器的维护活动对于提高机器生产效率或产品质量有着重要作用。近年来，机器具有维护活动的排序问题获得了越来越多学者的关注。Lee 和Leonl1考虑了有速率修正维护活动的单机排序问题。对于一些传统的排序指标，Lee和Leon1给出了对应排序问题的多项式时间算法或拟多项式时间算法。Kubzin和Strusevich2研究了具有维护活动的两台处理机作业排序问题，目标是最小化最大完工时间。在他们的模型中，维护活动的维护时长依赖于维护活动的开始时刻。他们证明了对于自由作业（open shop）模型，排序问题是多项式时间可解的，而对于流水作业（flow shop）模型，排序问题是NP-难的。Mosheiov和Sidney3研究了有退化维护活动的单机排序问题。对于几个传统的排序指标，如最大完工时间、总完工时间、最大延迟等目标，他们给出了相应排序问题的多项式时间算法。Wang等人4研究了具有退化维护活动的非同类机排序问题，目标是最小化总完工时间，他们证明了该问题是多项式时间可解的。Zou和Yuan5证明了在单机环境下几类不同维护活动的等价性，并分析了最小化加权误工工件数的时间复杂性。关于具有维护活动的排序问题的更多结果，读者可参见文献6-10。在经典排序问题中，通常假设每个工件都必须安排在机器上加工。但是在实际生产过程中，为了获得更大的利润，生产商往往会选择拒绝一部分工件或者外包给第三方，与此同时，需要支付一定的拒绝费用或外包费用。这类问题，我们称为工件可拒绝的排序问题。Bartal等人11于2 0 0 0 年首次考虑了工件可拒绝的平行机排序问题，问题的目标为最小化接受工件的时间表长与拒绝工件的总拒绝成本之和。他们同时考虑了在线和离线的情形。对于离线情形，他们给出了（2 一孟)-近似算法与一个多项式时间近似方案；而对于在线情形，他们给出了竞争比为与+的在线算法。Shabtay等人12 给出了工件可拒绝2的离线排序问题的全面总结。Zhang和Lul13考虑了工件可拒绝且工件有到达时间的平行机排序问题，目标是使所有接受工件的最大完工时间与所有拒绝工件的惩罚之和达到最小。当机器数量为固定常数时，他们给出了这个问题的伪多项式时间算法和全多项式时间近似方案。当机器数量取值任意时，他们给出了问题的一个2-近似算法。Liu和Lul14对单机和平行机环境下工件可拒绝的排序问题提出了一个新的近似算法。更多可拒绝排序相关的成果，读者可参考文献15,16。然而到目前为止，只有较少的文献将这两类排序问题结合起来进行研究。当工件可拒绝且机器具有退化维护活动时，Li和Chen17研究了目标是最小化所有接受工件的排序成本与所有拒绝工件的拒绝惩罚之和的单机排序问题。针对一些传统的排序指标，他们分别给出了相应问题的多项式时间算法与伪多项式时间算法。当工件可拒绝且机器可用时间不同时，Jiang和Tan18研究了目标是使所有接受工件的最大完工时间、生产成本与所有拒绝工件的拒绝成本之和达到最小的非同类机排序问题。针对这个问题，他们给出了一个最坏性能比为2 的启发式算法。本文中，机器维护活动的开始时刻是可选择的且维修活动的时长是其开始时刻的线性非减函数。我们将 Jiang和 Tan18提出的模型进行推广并研究了在非同类机环境下更多目标函数的排序问题。本文结构如下：在第1节，对所研究的排序问题进行描述；在第2 节，给出排序指标为最大完工时间的排序问题的一个2-近似算法；在第3节，证明排序指标分别为总完工时间、机器总负载及完工时间的总绝对偏差的排序问题均可在多项式时间内求解。最后，总结全文并提出未来的研究方向。表139带有退化维护活动和工件可拒绝的非同类机排序问题3期1问题描述本文考虑机器具有退化维护活动且工件可拒绝的非同类机排序问题，该问题可描述如下：给定工件集N=1,2,.,n)和m台非同类平行机M=1,2,，m)。工件j或者被接受并将其安排到某台机器上进行不中断的加工，或者被拒绝并支付e；的拒绝成本。若工件在机器i上加工，则需要pi的加工时间与ui的生产成本。令A与R分别表示接受工件集与拒绝工件集，n；表示分配到机器i上的工件数量，i=1，m。为方便起见，我们将机器i上的接受工件集记为A，i=1,2，.，m。显然，A，可以为空集，I A,|=ni,A,nAj=(ij)且A=AiUA2 U.UAm。为了提高机器的生产速率，可以安排每台机器执行维护活动。根据文献3，不妨设每台机器i上的维护活动MA；是退化的，即维护活动的维护时长T；是其开始时刻的线性非减函数，表示为T;=ti+it,其中ti0为基本维护时间，,0 为维护系数，t为退化维护活动的开始时刻。每台机器至多执行一次退化维护活动，且机器在执行退化维护活动期间不可加工任何工件。对于一个给定的排序，C（）表示接受工件j在元下的完工时间，L;（）表示在元下机器i上的负载，TADC;（元）表示在元下机器i上工件完工时间的总绝对偏差且TADC;()=ICil-Cik)|。不失一般性，用Cj,L和TADC;分别代替C;(),L;()nil=1 k=l和TADC;(元)。我们的目标是寻找合适的退化维护活动的位置与接受工件的一个加工顺序使所有接受工件的排序指标、生产成本与所有拒绝工件的拒绝成本之和达到最小。本文考虑接受工件的排序指标分别为最大完工时间Cmax(A)=maxC,ljEA)、总完工时间Cj、机器总负载L及完工时间的总绝对偏差mZTADCi。jEA=11依据经典的三参数表示法，我们将本文研究的问题表示如下：T=ta+Sit,pij=(bij,as)I Cmax(A)+ZVij+2ej;m(P1)Rm|rej,i=ljeAiJERi,T=ti+it,pij=(bij,ai)/C,+2ui+ej;m(P2)Rm/rej,jEAi=1jeAijERm(P3)Rm|rej，T=t a+Si t,Pi j=(b i j,a n s)1 Li+2 v s +e j;1i=ljEA;jERmm(P4)Rm|rej，T =t i +d i t，Pi j =(b i j,a i)IT A D C;+ZUij+Zej,1i=1jEAijER其中rej表示工件可拒绝，T=t；+i t 表示机器i上的维护时长，Pij=（b i j,a i）分别示基础加工时间与缩短加工时间。2最大完工时间在本节中，我们给出问题Rmr e j，T=t;+Si t，Pi=（b i j,a i）丨Cmax(A）+is+=ej的最坏性能比为2 的近似算法。mi=1jEAijER参考Mosheiov和Sidney3分析的单机情况下此排序指标关于最优性的两种选择：或者在0 时刻执行退化维护活动，或者不执行退化维护活动。因此，我们对排序问题(P1)14027卷高洁，邹娟，隋玉康，张玉忠进行如下分析。令Q表示执行了退化维护活动的机器集合，则：aij，iEQ;Pibij,iEMQ。我们将问题页（P1）表述为下面的一个0-1整数规划，记为P。mnnminCmax+ZuVijCi+ejyj(1)i=1 j=1j=1ns.t.Cmax ti+pijti,ViEQ;(2)j=1CmaxZpijti,ViEMQ;(3)j=1maij+yj=l,VjEN;(4)1nai1,ViEQ;(5)j=1CijE(O,1),ViEM;VjEN;(6)yj E(0,1),VjEN。(7)在这个0-1整数规划中，二元变量ai=1表示工件5被安排到机器i上加工，否则二元变量ai=0；变量yi=1表示工件i被拒绝，否则变量yi=0；变量Cmax表示所有接受工件的最大完工时间，是由约束（2）与约束（3）定义的。约束（4）说明了任一工件或者被拒绝，或者被安排到某台机器上加工。约束（5）说明了如果机器i执行退化维护活动，那么至少有一个工件在机器讠上加工，否则，退化维护活动的执行无意义。因为Q是M的任一子集，且一个Q对应一个上述形式的0-1整数规划，所以0-1整数规划的数量为C%+Cm+Cm=2m。进一步可以知道排序问题（P1）的最优解必然对应着这2 m个0-1整数规划中某一个规划的最优解。下面，我们对0-1整数规划P进行松弛，得到对应于该规划P的松弛模型，记为CP。mnnminCmax+VijLi+ejyji=1 j=1j=1ns.t.Cmaxti+pijai,ViEQ;j=1nCmaxpijti,ViEMQ;j=1Cij+yj=l,ViEN;=1TijO,ViEM;VjEN;yiO,ViEN。1413期带有退化维护活动和工件可拒绝的非同类机排序问题与P相比，在松弛模型CP中,约束(5被删掉，0,1)整数变量松弛为线性变量。由于每个0-1整数规划都对应于一个松弛问题，因此共有2 m个松弛问题。通过求解这2 m个线性松弛问题，从中选择具有最小目标函数值的松弛问题，并将这个松弛问题的最优解记为（Cmxig，j)），最优值记为Cmx+言igi+含ejuj。令mi=1j=13=1mnZ*表示问题(P1)的最优目标函数值，显然，有Cmax+nUiji+ejyZ*成立。i=1j=1j=1在解向量（Cmax,ij,i）中，与工件j相关的变量共m+1个，分别为1j，mj,j若工件i对应的+1个变量中存在一个变量取值为分数，那么我们称这个工件为变量取值是分数的工件；若工件j对应的m+1个变量取值只有0 或1，那么我们称这个工件为变量取值是整数的工件。为方便起见，假设在最优解（Cmax,ai，y）中，变量取值是分数的工件集为 1,，1)。自然地，余下n1个工件构成变量取值为整数的工件集。引理 119 在最优解（Cmaxi，u）中，取非零值的变量i与y，的总数量不超过n+m-1。引理2在最优解（Cmaxij,yj）中，变量取值是分数的工件的总数量以m1为上界。证明假设在最优解（Cmaxig，3）中，变量取值是分数的工件共1个。若工件j为m变量取值是分数的工件，则由约束ai+yj=1知，在工件j对应的m+1个变量中至1少有两个变量取值是分数。显然，其余的n1个工件为变量取值是整数的工件。若工件j为变量取值是整数的工件，则由约束ai+yj=1知，在工件j对应的m+1个变量m1中只有一个变量取值非零，且该变量一定取值为1。因此，在最优解（Cmax，i，9）中，取值非零的变量至少有2 l+1(n-l)=n+l个。由引理1,我们有n+ln+m=1,从而得到lm-1。下面，给出问题(P1)的近似算法A。算法A步骤1对于每个子集QCM，将问题（P1)描述为一个0-1整数规划，并将其松弛为一个线性规划。步骤2 从2 个线性松弛问题中选择具有最小目标函数值的松弛问题，并将这个松弛问题的最优解记为（Cmax,i,i)。步骤3由松弛问题的最优解（Cmax，i g，u）构造变量取值是整数的工件集的部分排序，记为S1=（1,R1,Q )。若变量y=1,则工件被拒绝；若变量a=1,则将工件j安排到机器i上。从而得到部分排序S1=（,R1,Q ）=（A i,A 2，A m,R1,Q )。步骤4通过枚举法构造变量取值是分数的工件集的部分排序，记为S2=（,R,Q2)。对于任意给定的QM,任一工件i(1jI)都有m+1种选择：工件i在机器i(1im）上加工；工件i被拒绝。由于子集Q共有2 m种可能的取法，所以对于工件集 1,1，共有2(m+1)个可能的排序。从所有的可能排序中选择具有最小目标函数值的排序，并将这个排序记为 S2=（,R2,Q2）=（A,A 2,：，A,R2,Q 2)。步骤5依照下述方式将部分排序S1=（1,R1,Q）与部分排序S2=（2,R,Q2)组合，得到问题(P1)的一个可行排序S=（,R,Q)：（1)拒绝工件集R=RiUR2；(2)机器i(i=1,，m）上接受工件集A;=A,UA?且工件以任意序排列；（3)执行退化维护活动的机器集合Q=Q1UQ?。14227卷高洁，邹女娟，隋玉康，张玉忠定理1算法A是问题Rm|rej,T,=ti+it,Pij=(bij,ai)/Cmax(A)+Vi+i=1jEA;e;的一个2-近似算法，并且可以在O(2m(m+1)m-1)时间内求解。jER证明首先，证明算法A是排序问题（P1）的一个2-近似算法。断言 1 Cmax()Cmax(l)+Cmax()。令L，L与L分别表示在排序，1与元下机器i上的负载。情形1：在排序元1与元2 下，机器i上均有工件加工。我们分析下面三种情形。情形1.1：当i生Q1且iQ?时，有iQ。对于这种情况，我们有L;=LI+L Cmax(l)+Cmax(2)。情形1.2:当iEQ1且iQ?时，有iEQ。对于这种情况，我们有Li=ti+jEAjEAjEA?jEA3对于iQ1且iEQ?的情况，则有类似的分析与同样的结论。情形1.3：当iEQ1且iEQ?时，有iEQ。对于这种情况，我们有Li=ti+Zai+Zais(t+)Zai)+(t;+)+ais)=Li+LCmax(l)+Cmax(2)jeA1jeA?jE.A1jEA?情形2：仅在排序元1下，机器i上有工件加工。对于这种情况，我们有L;=L;Cmax(l)Cmax(l)+Cmax(r)。若机器i仅在排序元2 下有工件加工，则有类似的分析与同样的结论。综合上述情形，对于每台机器iEM，均有不等式L;Cmax（）+Cma x(2）成立。因此,我们有Cmax()=max(Li)Cmax(l)+Cmax(2)。iEM断言2 Cmax()+2vii+2ej2Z*。mi=ljEAijERmax（）i=1jEAijER首先，分析在步骤3与步骤4中得到的部分排序S1与S2。由于S1只是由最优解（Cmaxaig，）得到的一个部分排序，故Cmax(l）+.i+，j Cma x+mi=1jEAljER1mnnijai+ejuZ*。而我们取得的部分排序S2是2 m(m+1)个可能的排序中1j=1j=1m具有最小目标函数值的那个排序，因此，我们有Cmax(2)+Z Z,vij+Z,ej Z*。i=1jEA?jER21433期带有退化维护活动和工件可拒绝的非同类机排序问题由此，我们可以得到：mCmax()+)ij+ej=Cmax(r)+)Uiei=ljEAijERi=1 jEA;UA?jERIUR2mm=Cmax(元)+)Ui+Uii+Dej+ei=1jEAli=1jEA?jER1jER2mCmax(（元ii+eii=1 jEA;jER1m(Cmax(a2)+Zuis+eii=1 jeA?jER2Z*+Z*=2Z*。由断言1和断言2，证明了算法A是排序问题（P1）的一个2-近似算法。下面，我们分析算法A的时间复杂性。由于每个线性规划都可以在O(n3.5ZI）时间内求解2 0，其中Z表示输入问题的规模，所以求解2 m个松弛问题所需的时间复杂性为O(2mn3.5|Z)。而从2 m个线性松弛问题中选择具有最小目标函数值的松弛问题所需时间复杂性为O(2m)。因此，步骤2 所需时间复杂性为0(2 mn3.5|Z|+2m)。由引理2,我们知道变量取值为分数的工件数量lm1。因此，构造出部分排序S2所需时间以2m(m+1)m-1为上界。因此，步骤4所需时间复杂性为O(2m(m+1)m-1)。其余步骤的时间复杂性均为常数。从而得到，算法A是可以在O(2m(m+1)m-1）时间内求解问题mRm|rej，T;=t i +Si t,Pi j =(b i j,a i s)|Cm a x(A)+U i j +e j 的一个2-近似i=1jEAiJER算法。口3总排序指标在本节中，我们将研究所有接受工件的排序指标、生产成本与所有拒绝工件的拒绝成本之和最小化的排序问题。考虑的排序指标分别为总完工时间、机器总负载及完工时间的总绝对偏差。我们将证明这三个排序问题均可在多项式时间内求得最优解。首先，定义机器i上退化维护活动的位置，若机器i上退化维护活动（MA）恰好在第h；个位置上的工件开始加工之前执行完成，那么称机器i上退化维护活动的位置为hi（1 h i n i+1，i=1,，m)。特别地，h=ni+1表示机器i不执行MAi，h i=1表示机器i在0 时刻执行MAi。如果工件i在机器i的第s个位置上加工，则其实际加工时间为：bij，shi;Pijs=aij，shio由于考虑了工件可拒绝的情况，故添加一台虚拟机器+1，用来安排所有被拒绝的工件。令P(n,m+1)=（n 1，n m，n m+1)表示工件分配向量，其中n；表示被分配到机器14427卷高洁，邹女娟，隋玉康，张玉忠m+1i(i=1,m,m+1)上的工件数量,0 nin且 ni=n。令Q(n,m)=(h1,hm)1表示机器维护活动的位置向量，其中h,表示机器i(i=1,，m）上维护活动的位置，且1hna+1。假设i=(Jalu),Ji(h-),T,Jihal,Jinal)表示机器i(i=1,m)上的工件加工序列。令Cis）表示在机器的第：个位置上加工工件的完工时间。为了求解这类排序问题，我们首先给出一个重要的结论。引理 32 1 1满足不等式h1+h2+.+hmn的非负整数解的数量为C(m+n,n)=(mta,且c(m+n,n)以m为上界。m!n!m!3.1总完工时间在本小节中，我们考虑问题Rmr e j，T；=t i+Si t，Pi i=（b i j,a i）丨Cj+jEAmui+ej，并证明这个排序问题可以在多项式时间内求解。i=1jEA;jER首先，给出机器i上工件总完工时间的表达式：三 C(0=bi1)+(bi1+bi2+(bi1+.+bh-1)ni8=1+bi1+.+bihi-1+t+0;(bi1+.+bih;-)+aih +.+bi1+.+bihi-1+t+;(bi1+.+bihi-1)+aih;+.+ainahi-1hi-1hi-12(hi-s)bi(0+(ni-hi+1)(t:+0;bis)+(n-h+1)2 bils)s=18=1$=1ni+Z(ni-s+1)ais)s=hihi-1=(ni-hi+1)ta+(n-8+1)+(ni-hi+1);bi0)+2(n;-8+1)ai)。ni8=1s=hi因此，所有接受工件的总完工时间为：mmm hi-1Z.Cj=ZCia=ni(ni-hi+1)ti+2(ni-$+1)+(ni-hi+1)o;bia)jEAi=1s=11i=1s=1mni+Z(ni-$+1)ails)。i=1s=hi令变量is=1表示工件被安排到机器i的第。个位置，否则ijs=0;令wijs表示工件i被安排到机器i的第s个位置时的权重，其中i=1，m,m+1，j=1,，n且8=1.,ni。对于任意给定的工件分配向量P(n,m+1)=（n 1,n m，n m+1）和维护活动的位置向量Q(n,m）=（h 1，h m），我们可以将问题（P2）重新描述为下面的指145带有退化维护活动和工件可拒绝的非同类机排序问题3期派问题，记为APi(ni,nm,nm+1,hi,.,hm)m+1nnimminWijsaijs(ni-hi+1)t;i=1 j=1 s=11m+1niS.t.aijs=1,j=1,2,.,n;(8)i=1 s=1aijs=1,i=1,2,.,m,m+1;8=1,2,.,ni;(9)j=1Cijs E0,1,i=1,2,.,m,m+1;j=1,2,.,n;s=1,2,.:,ni,其中三(ni-hi+1)t；是常数，权重wijs取值如下：(ni-$+1)+(ni-hi+1)o;bij+ij,i=1,2,.,m;s=1,2,.,hi-1;Wijs=(ni-s+1)aij+Vij,i=1,2,.:,m;s=hi,hi+l,.,ni;ej,i=m+1。约束（8）说明任一工件或者被接受并被安排到某台机器上进行不中断的加工，或者被拒绝。约束(9)说明机器i(i=1,m,m+1)上的第s（s=1,n i）个位置一定有一个工件被安排。问题 Rm|rej,T,=ti+it,Pij=(bij,ai)|Cj+Uij+ejm定理2 间jEAi=1jEAijER可以在O(n2m+3)时间内求解。证明对于任意给定的工件分配向量P(n,m+1)=（n 1，n m，n m+1）和维护活动的位置向量Q(n,m）=（h 1，,hm)，我们均可以得到一个在O(mn）时间内求解的指派问题2 2。由于机器i上加工工件的数量ni共有n+1个可能的取值，且当前m台机器上加工工件的数量已知时，机器m十1上的工件数量可以被唯一确定。因此工件分配向量P(n,m+1)=(n1,nm，n m+1）的数量以（n+1)为上界。又由引理3知，维护活动的位置向量Q(n,m）的数量以(2n)m为上界。因此，问题Rmrej，T;=t i+Si t,m!mPij=（b i j，a i s）|Cj+U i+e,可以在O(n2m+3）时间内求解。口jEAi=ljeAijER3.2机器总负载在本小节中，我们考虑问题Rmr e j，T；=t i+Si t，Pi i=（b i j,a i）丨L;+1mUi+ej，并证明这个排序问题可以在多项式时间内求解。i=ljEA;jER首先，计算机器i上的负载：L;=bi1+.+bin-+t;+;(bi1+.+bih-1+aiha+.+ainahi-1hi-1ni2bia+ti+;2bia+2ails8=1S=1s=hihi-1ni=t:+(1+0)2bi0)+2ais。8=1s=hi以在Un-可可闪水。14627卷高洁，邹女娟，隋玉康，张玉忠因此，机器总负载为：mmmhi-1mnL;=ta+22(1+0.)bi(s)+22ais。=11i=1 s=1i=1s=hi变量ijs和权重wijs的定义与第3.1节中的定义相同。对于任意给定的工件分配向量P(n,m+1)=(n1,.nm,nm+1）和维护活动的位置向量Q(n,m)=(h1，,h m)，我们可以将问题(P3）重新描述为下面的指派问题，记为AP2(n1,，n m，n m+1,h i，.，h m)：m+1nimminWijsaijstii=1 j=1 s=1=1m+1nis.t.Cijs=1,j=1,2,.,n;i=1 s=1naijs=1,i=1,2,.,m,m+1;s=1,2,.,ni;3=1aijsE0,1,i=1,2,.,m,m+1;j=1,2,.,n;s=1,2,.,ni,m其中三t是常数，权重Wijs取值如下：-1(1+,)bij+Uij,i=1,2,.,m;s=1,2,.,hi-1;Wijs=aii+Vij,i=1,2,.,m;s=hi,hi+1,.,ni;ej,i=m+1。每个约束与第3.1节中的意义相同。由引理3，我们可以得到以下结论。m问题Rm|rej,T=ti+it,Pij=(bij,ai）|Li+U j+Ze,可m定理31i=ljEAJER3.3完工时间的总绝对偏差在本小节中，我们考虑问题Rm|rej，T,=t；+i t，Pi i=（b i j,a i s）丨TADC;+m=1ui+=ej，并证明这个排序问题可以在多项式时间内求解。mi=1jEAiJER首先，计算机器i上完工时间的总绝对偏差：niTADCi=2Cil-Ca(klll=1 k=lni(2l-ni-1)Cil)1=1hi-1hi-1ni2(2-ni-1)bi)+2(2l-ni-1)tis=1 l=sl=hi可以在0(n2m+3)时间内求解。定147带有退化维护活动和工件可拒绝的非同类机排序问题3期+(1+6:)(2-n;-1)b(g)+(2l-ni-1)ais)hi-1ninis=1l=his=hil=snihi-1hi-1(2-n-1)t+“2(2l-n-1)+(1+8:)(21-ni-1)bil)nil=his=1l=sl=hinini+(2l-ni-1)ais。s=hil=s因此，所有机器上工件完工时间的总绝对偏差为：mmnTADC;=222Ci-C(kl1i=1l=1k=lmnim hi-1hi-1,(2l-ni-1)ti+22(21-ni-1)i=1l=hi=1 s=1l=snim+(1+:)(21-ni-1)big)+2(21-ni-1)ai。ni=hii=1s=hil=s变量aijs和权重wijs的定义与第3.1 节中的定义相同。对于任意给定的工件分配向量P(n,m+1)=(n1.,nm,nm+1)和维护活动的位置向量Q(n,m)=(h1,hm),我们可以将问题(P4)描述为下面的指派问题，记为APs(n1,.，n m，n m+1,h 1，.，h m)：m+1imniminWijsaijs(2l-ni-1)tii=1 j=1 s=1i=1l=him+1niS.t.Cijs=1,j=1,2,.,n;i=1s=1naijs=1,i=1,2,.,m,m+1;s=1,2,.,ni;j=1CijsE0,1,i=1,2,.,m,m+l;j=1,2,.,n;s=1,2,.,ni,m其中(2l-ni-1)t；是常数，权重wijs取值如下：nii=1l=hihi一1(2l-ni-1)+(1+a)(2l-ni-1)bij+vij,ni1=sl=hii=1,2,.,m;s=1,2,.,hi-1;Wijs(2l-ni-1)aij+Uij,l=si=1,2,.,m;s=hi,hi+l,.,ni;ei，i=m+1。每个约束与第3.1 节中的意义相同。由引理3，我们可以得到以下结论。m问题Rm|rej,T,=ti+it,pij=(bij,ais)ITADCi+Uij+ejm理4=1i=1iEAiER148高洁，邹娟，隋玉康，张玉忠27卷4结论和展望本文研究了工件可拒绝且机器具有退化维护活动的非同类机排序问题。退化意味着维护活动的维护时长是其开始时刻的线性非减函数。维护活动的执行可以提高机器的生产速率，减少工件的加工时间。我们研究的目标是使所有接受工件的排序指标于、生产成本与所有拒绝工件的拒绝成本之和达到最小，其中排序指标f涉及Cmax(A)、C j、jEAmmZLi、TADC。当排序指标f为Cmax(A)时，我们设计了一个2-近似算法；当排序1=1mm指标fEZCj,ZLi,TADC时，我们证明了这些问题都是多项式时间可解的。JEA1=1在后续工作中，我们将进一步研究在不同维护类型以及其他机器环境下此类排序问题的复杂性分析及其近似算法。参考文献1 Lee C Y,Leon V J.Machine scheduling with a rate modifying activity J.European Journalof Operational Research,2001,128:119-128.2 Kubzin M A,Strusevich V A.Planning machine maintenance in two-machine shop schedulingJ.Operations Research,2006,54:789-800.3 Mosheiov G,Sidney J B.Scheduling a deteriorating maintenance activity on a single machineJ.Journal of the Operational Research Society,2010,61:882-887.4 Wang L Y,Huang X,Ji P,et al.Unrelated parallel-machine scheduling with a deterioratingmaintenance activity to minimize the total completion time J.Optimization Letters,2014,8(1):129-134.5 Zou J,Yuan J J.Equivalence of some different maintenance activities in single-machinescheduling J.Journal of the Operations Research Society of China,2018,6:545-556.6 Chung T P,Gupta J N D,Qiu M.Single machine scheduling problem with batch setupsinvolving positional deterioration effects and multiple rate-modifying activities J.EngineeringOptimization,2019,51:1743-1760.7 Delorme M,Iori M,Mendes N F M.Solution methods for scheduling problems with sequence-dependent deterioration and maintenance events J.European Journal of Operational Re-search,2021,3:823-837.8 Mosheiov G,Daniel O.A note on scheduling a rate modifying activity to minimize total latework J.Computers&Industrial Engineering,2021,154:107138.9 Yu T S,Han J H.Scheduling proportionate fow shops with preventive machine maintenanceJ.International Journal of Production Economics,2020,231:107874.10 Zou J,Yuan J J.Single-machine scheduling with maintenance activities and rejection J.Discrete Optimization,2020,38:100609.11 Bartal Y,Leonardi S,Spaccamela A M,et al.Multiprocessor scheduling with rejection J.SIAM Journal on Discrete Mathematics,2000,13:64-78.149带有退化维护活动和工件可拒绝的非同类机排序问题3期12 Shabtay D,Gasper N,Kaspi M.A survey on ofline scheduling with rejection J.Journal ofScheduling,2013,16:3-28.13 Zhang L Q,Lu L F.Parallel-machine scheduling with release dates and rejection J.4OR-AQuarterly Journal of Operations Research,2016,14:165-172.14 Liu P,Lu X.New approx