带有退化、拒绝和不可用区间的单机排序问题_何欣怡.pdf

2 0 2 3年5月重庆师范大学学报(自然科学版)M a y2 0 2 3第4 0卷 第3期J o u r n a l o fC h o n g q i n gN o r m a lU n i v e r s i t y(N a t u r a lS c i e n c e)V o l.4 0 N o.3运筹学与控制论D O I:1 0.1 1 7 2 1/c q n u j 2 0 2 3 0 3 0 8带有退化、拒绝和不可用区间的单机排序问题*何欣怡,赵玉芳,陈状状(沈阳师范大学 数学与系统科学学院,沈阳1 1 0 0 3 4)摘要:【目的】考虑带有退化工件、拒绝和不可用区间的单机排序问题。【方法】假设工件有不同的基本加工时间和相同的退化率,工件可以被拒绝,被拒绝的工件需要支付拒绝惩罚,机器在给定的时间区间内是不可用的且工件不可恢复。目标是极小化接受工件的总完工时间与被拒绝工件的总拒绝惩罚之和。【结果】对于这个N P-难问题,在不可用区间前、后,工件按照基本加工时间aj的非减顺序排列可以得到最优解,给出一个拟多项式时间动态规划算法和一个完全多项式时间近似策略。【结论】推广了已有文献的模型。关键词:单机排序;退化;拒绝;不可用区间中图分类号:O 2 2 3文献标志码:A 文章编号:1 6 7 2-6 6 9 3(2 0 2 3)0 3-0 0 0 8-0 8当前有关排序问题的理论研究已经涉及到很多实际生产环境中,例如在轧钢调度问题中,铸锭在等待加工时温度会下降,因此它需要被重新加热,让温度达到一定要求再进行轧制,由此导致轧制时间增加;而轧制过程中机器也可能因故障或检修等原因而不可用,此时工厂为了节约成本或按时交货,可能会选择外包一部分货品,进而支付一定费用。事实上,加工过程中由于中途维修机器或者更换工具等原因,导致一台机器在此时不可用的情形在工业中很常见,因此带有不可用区间约束的问题受到了广泛关注。L e e1定义了两种情况:可恢复和不可恢复。当工件在不可用区间之前没有完工,机器再次可用时继续加工,则称为可恢复的,反之为不可恢复的。M a等人2对带有机器不可用区间的问题进行了综述。Z h a o等人3研究了两台平行机排序问题,其中一台机器有一段固定的不可用区间,给出了这个问题的完全多项式时间近似策略(f u l l yp o l y n o m i a l t i m ea p p r o x i m a t i o ns c h e m e,F P T A S)。Z h a o等人4研究了平行机的情况,每台机器都有一个固定的不可用区间,提出了一个拟多项式时间动态规划算法。K a c e m等人5研究了两个目标函数为最大延误的单机排序问题,且工件带有释放时间,其中一个问题是机器在一个给定的区间中不可用,另一个问题是与操作员有关的不可用区间,他们分别给出了这两个问题的多项式时间近似策略(p o l y n o m i a l-t i m ea p p r o x i m a t i o ns c h e m e,P T A S)算法。金苗苗等人6研究了机器具有不可用区间且工件可拒绝下的单机重新排序问题,目标为极小化接受工件的总加权完工时间、总拒绝费用及加权最大延误之和,给出了拟多项式时间动态规划算法和F P T A S。此外,在传统的研究中工件的加工时间总是固定的。但在实际生产过程中,工件的加工时间可能会随着时间发生变化,G a w i e j n o w i c z7对近4 0年有关工件加工时间可变的排序问题进行了综述。机器由于磨损、升温等原因,导致工件的加工时间与开始加工时间有关,开始加工时间越晚,加工时间就越长,这种现象称为退化效应。有很多文献研究了线性退化工件的模型。此外还有一种有相同退化率的模型8-1 0。当机器持续可用时,C h e n g等人1 1研究了单机排序问题,目标是极小化工期与提前惩罚、误工惩罚之和,他们给出了求最优解的多项式时间算法。对于上述的目标函数,C h e n g等人1 2还研究了平行机排序问题,证明了这个问题是N P-难的,并给出求近似最优解的遗传算法。L e e等人1 3研究了带有释放时间的单机极小化最大完工时间问题,构造了一个分支定界算法。Z h a o等人1 4研究了带有机器不可用区间,工件有相同退化率的单机排序问题,目标是极小化总完工时间,构造了一个拟多项式时间动态规划算法和一个F P T A S,还研究了平行机的情况,给出了拟多项式时间动态规划算法。王吉波等人1 5研究了带有学习效应、恶化效应和公共工期指派的单机排序问题,目标函数为工件的*收稿日期:2 0 2 2-0 3-2 0 修回日期:2 0 2 3-0 1-0 8 网络出版时间:2 0 2 3-0 6-1 5 T 1 7:1 3资助项目:国家自然科学基金青年项目(N o.1 2 1 0 1 4 1 7);辽宁省教育厅科学研究项目(N o.L FW 2 0 2 0 0 1)第一作者简介:何欣怡,女,研究方向为组合最优化、随机运筹学,E-m a i l:1 2 2 6 2 3 7 5 4 9q q.c o m;通信作者:赵玉芳,女,副教授,博士,E-m a i l:y f z h a o 2 0 0 41 6 3.c o m网络出版地址:h t t p s:/k n s.c n k i.n e t/k c m s 2/d e t a i l/5 0.1 1 6 5.N.2 0 2 3 0 6 1 5.1 3 2 0.0 0 6.h t m l提前、延误和公共工期的加权费用和,证明了该问题是多项式时间可解的。B a r t a l等人1 6第1次提出带有拒绝的排序问题,他们研究了多机排序问题,目标是极小化接受工件的最大完工时间与拒绝惩罚之和。此后得到了学者们的广泛关注。E n g e l s等人1 7研究了带有拒绝的单机排序问题,目标函数为接受工件的总加权完工时间与拒绝工件的总拒绝惩罚之和,证明了该问题是N P-难的,并给出了动态规划算法和F P T A S。C h e n g等人1 8考虑了带有退化和拒绝的单机排序问题,目标函数为接受工件的最大完工时间与拒绝工件的总拒绝惩罚之和,证明了该问题是一般意义N P-难的,给出了拟多项式时间的动态规划算法。Z h a o等人1 9研究了带有机器不可用区间和拒绝的单机排序问题,目标是极小化接受工件的总加权完工时间与拒绝工件的总拒绝惩罚之和,给出了问题的动态规划算法和F P T A S。L i等人2 0研究了带有释放时间、退化、不可用区间和拒绝的单机排序问题,目标是极小化接受工件的最大完工时间和拒绝工件的总拒绝惩罚,给出一个F P T A S算法。国峰等人2 1研究了带有拒绝和学习效应的资源约束排序问题,对线性和凸资源分配函数的两种模型给出了最优求解算法,时间复杂度分别为O(n4)和O(n3)。徐晨等人2 2研究了工件可拒绝的单机多任务排序问题,目标是极小化最大完工时间、总完工时间和总加权完工时间,对上述3个问题都给出了拟多项式时间动态规划算法。林凌等人2 3以及张玉忠2 4都对工件可拒绝问题的研究进行了综述。1 问题描述假设有n个互相独立的工件J=J1,J2,Jn 在一台机器上加工。所有工件0时刻可用,每个工件Jj有一个基本加工时间aj和退化率b(aj,b0),工件Jj的实际加工时间为pj=aj+b t,其中t是工件Jj的开始加工时间。工件Jj的拒绝惩罚为ej,同一时间机器只能加工1个工件。T1,T2)为机器的不可用区间(T1T2),工件不可恢复。工件Jj要么被加工,要么被拒绝,加工工件集为S,拒绝工件集为S,则J=SS。假设aj,b,T1,T2和ej都是整数。目标是极小化总完工时间与拒绝惩罚之和。本文研究问题可以表示为:1,h n r-a,pj=aj+b t,r e jSCj+Sej,式中:Cj是工件Jj的完工时间,h表示机器上一个固定的不可用区间,n r-a表示任何接受工件都是不可恢复的。2 动态规划算法首先给出一些有用的引理。当不考虑拒绝时,问题1,h n r-a,pj=aj+b tCj被证明是N P-难的1 4,显然考虑拒绝之后,问题1,h n r-a,pj=aj+b t,r e jSCj+Sej至少是N P-难的,则有下列结论。引理1 问题1,h n r-a,pj=aj+b t,r e jSCj+Sej是N P-难的。为了叙述方便,引入下列术语。S P T序 按照aj的非减顺序排列工件。引理22 5 对于问题1pj=aj+b tCm a x,将工件按S P T序排列可以得到一个最优排序。对于某个排序=J1,J2,Jn,第一个工件J1的开始加工时间为t0,则最大完工时间Cm a x=t0(1+b)n+nj=1aj(1+b)n-j。引理31 4 问题1,h n r-a,pj=aj+b tCj存在一个最优排序,使得T1之前的工件按照S P T序排列,T2之后的工件按照S P T序排列。由上述引理,对于问题1,h n r-a,pj=aj+b t,r e jSCj+Sej有如下结论。引理4 问题1,h n r-a,pj=aj+b t,r e jSCj+Sej存在一个最优排序,使得T1之前接受工件按照S P T序排列,T2之后接受工件按照S P T序排列。假设工件按照S P T序排列,使得a1a2an,基于引理4构造求解问题1,h n r-a,pj=aj+b t,r e jSCj+Sej的动态规划算法。根据引理4,工件已经按照S P T序排列,因此工件J1要么是T1之前的第1个加工工件,要么是T2之后的第1个加工工件,要么被拒绝。如果工件J1是T1之前的第1个加工工件,则工件J2要么是T1之前的第2个9第3期 何欣怡,等:带有退化、拒绝和不可用区间的单机排序问题加工工件,要么是T2之后的第1个加工工件,要么被拒绝。不失一般性,对于任意给定集合Sj=J1,J2,Jj(j=1,2,n),工件Jj要么是T1之前的最后一个加工工件,要么是T2之后的最后一个加工工件,要么被拒绝。设u表示集合Sj中在T1之前加工工件的总加工时间,v表示集合Sj中在T2之后加工工件的总加工时间,Fj(u,v)表示对于当前状态(u,v),Sj中工件的目标函数值。给定一个状态(u,v),如果工件Jj是T1之前的最后一个加工工件,那么它的完工时间为u,它的开始加工时间为(u-aj)/(1+b),则Fj(u,v)=Fj-1(u-aj)/(1+b),v)+u;如果工件Jj是T2之后的最后一个加工工件,那么它的完工时间为T2+v,开始加工时间为(T2+v-aj)/(1+b),则Fj(u,v)=Fj-1(u,(v-aj-b T2)/(1+b)+(T2+v);如果工件Jj被拒绝,则Fj(u,v)=Fj-1(u,v)+ej。设F(1)j(u,v)=Fj-1(u-aj)/(1+b),v)+u,F(2)j(u,v)=Fj-1(u,(v-aj-b T2)/(1+b)+(T2+v),F(3)j(u,v)=Fj-1(u,v)+ej。由上述分析可得动态规划算法如下。动态规划算法(D P)1)初始条件:F1(a1,0)=a1,F1(0,a1+b T2)=a1+(1+b)T2,F1(0,0)=e1,否则F1(u,v)=;F(i)j(u,v)=(i=1,2),其中u,v不是非负整数。2)对于j=2,3,n,0uT1,0vT2(1+b)j+Dj,其中Dj=jk=1ak(1+b)j-k,有:Fj(u,v)=m i nF(1)j(u,v),F(2)j(u,v),F(3)j(u,v)。3)目标函数的最优值F=m i nFn(u,v),其中0uT1,0vT2(1+b)n+Dn。例 考虑问题1,h n r-a,pj=aj+b t,r e jSCj+Sej,J=J1,J4,aj=2,3,4,5,ej=6,4,3 0,3 5,T1,T2)=6,9)。初始条件:F1(2,0)=2,F1(0,2 0)=2 9,F1(0,0)=6,否则F1(u,v)=;F(i