![点击分享此内容可以赚币 分享](/master/images/share_but.png)
带有退化、拒绝和不可用区间的单机排序问题_何欣怡.pdf
《带有退化、拒绝和不可用区间的单机排序问题_何欣怡.pdf》由会员分享,可在线阅读,更多相关《带有退化、拒绝和不可用区间的单机排序问题_何欣怡.pdf(8页珍藏版)》请在咨信网上搜索。
1、 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)摘要:【目的】考虑带有退化工件、拒绝和不可用区间的单机排序问
2、题。【方法】假设工件有不同的基本加工时间和相同的退化率,工件可以被拒绝,被拒绝的工件需要支付拒绝惩罚,机器在给定的时间区间内是不可用的且工件不可恢复。目标是极小化接受工件的总完工时间与被拒绝工件的总拒绝惩罚之和。【结果】对于这个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当前有关排序问题的理
3、论研究已经涉及到很多实际生产环境中,例如在轧钢调度问题中,铸锭在等待加工时温度会下降,因此它需要被重新加热,让温度达到一定要求再进行轧制,由此导致轧制时间增加;而轧制过程中机器也可能因故障或检修等原因而不可用,此时工厂为了节约成本或按时交货,可能会选择外包一部分货品,进而支付一定费用。事实上,加工过程中由于中途维修机器或者更换工具等原因,导致一台机器在此时不可用的情形在工业中很常见,因此带有不可用区间约束的问题受到了广泛关注。L e e1定义了两种情况:可恢复和不可恢复。当工件在不可用区间之前没有完工,机器再次可用时继续加工,则称为可恢复的,反之为不可恢复的。M a等人2对带有机器不可用区间的
4、问题进行了综述。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研究了两个目标函数为最大延误的单机排序问题,且工件带有释放时间,其中一个问题是机器在一个给定的区间中不可用,另一个问题是与操作员有关的不可用区间,他们分别给出了
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年有关工件加工时间可变的排序问题进行了综述。机器由于磨损、升温等原
6、因,导致工件的加工时间与开始加工时间有关,开始加工时间越晚,加工时间就越长,这种现象称为退化效应。有很多文献研究了线性退化工件的模型。此外还有一种有相同退化率的模型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研究了带有机器不可用区间,工件有
7、相同退化率的单机排序问题,目标是极小化总完工时间,构造了一个拟多项式时间动态规划算法和一个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)第一作者简介:何欣怡,女,研究方向为组合最优化、随
8、机运筹学,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次提出带有拒绝的排序问题,他们研究了多机排序问题,目标是极小化接受工件的
9、最大完工时间与拒绝惩罚之和。此后得到了学者们的广泛关注。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研究了带有机器不可用区间和拒绝的单机排序问题,目标是极小化接受工件的总加权完工时间与拒绝工件的总拒绝惩罚之和,给出了问题的动态规划算
10、法和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=J
11、1,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表示机器上一个固定
12、的不可用区间,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
13、,第一个工件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构造
14、求解问题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之前加工工件
15、的总加工时间,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
16、,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(
17、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)j(u,v)=(i=1,2),其中u,v不是非负整数。对于j=2,依次计算可得:F2(2,2 1)=m i nF(1)2(2,2 1),F(2)2(2,2 1),F(3)2(2,2 1)=3 2,F
18、2(2,0)=m i nF(1)2(2,0),F(2)2(2,0),F(3)2(2,0)=6,F2(3,2 0)=m i nF(1)2(3,2 0),F(2)2(3,2 0),F(3)2(3,2 0)=3 2,F2(0,8 1)=m i nF(1)2(0,8 1),F(2)2(0,8 1),F(3)2(0,8 1)=1 1 9,F2(0,2 0)=m i nF(1)2(0,2 0),F(2)2(0,2 0),F(3)2(0,2 0)=3 3,F2(3,0)=m i nF(1)2(3,0),F(2)2(3,0),F(3)2(3,0)=9,F2(0,2 1)=m i nF(1)2(0,2 1),F
19、(2)2(0,2 1),F(3)2(0,2 1)=3 6,F2(0,0)=m i nF(1)2(0,0),F(2)2(0,0),F(3)2(0,0)=1 0。J3,J4类似。最后经过计算可得F4(5,0)=4 5为问题的最优值;加工工件为J4,拒绝工件集为J1,J2,J3。下面分析动态规划算法(D P)的算法复杂度。因为j=1,2,n,0uT1,0vT2(1+b)n+Dn,因此算法共有O(n T1(T2(1+b)n+Dn)种状态,对于固定的j,u,v,计算Fj(u,v)的复杂度为O(1),所以算法D P的复杂度为O(n T1(T2(1+b)n+Dn)。定理1 动态规划算法(D P)的算法复杂度
20、为O(n T1(T2(1+b)n+Dn)。3 F P T A S接下来构造问题1,h n r-a,pj=aj+b t,r e jSCj+Sej的一个F P T A S。假设工件按照S P T序编号,使得a1a2an,引入变量xj,j=1,2,n,令:xj=1,如果工件Jj在T1之前加工,2,如果工件Jj在T2之后加工,3,如果工件被拒绝。假设X为所有向量x=(x1,x2,xn)组成的向量集,其中xj=k,j=1,2,n,k=1,2,3。定义关于X的初始函数和递推函数如下:f10(x)=0,f20(x)=T2,g0(x)=0;01重庆师范大学学报(自然科学版)h t t p s:/c q n u
21、 j.c q n u.e d u.c n 第4 0卷fkj(x)=fkj-1(x)+aj+b fkj-1(x),xj=k,k=1,2;fij(x)=fij-1(x),xj=i,ik;gj(x)=gj-1(x),xj=k,k=1,2;gj(x)=gj-1(x)+ej,xj=3;F0(x)=0;Fj(x)=Fj-1(x)+fkj(x),xj=k,k=1,2;Fj(x)=Fj-1(x)+ej,xj=3;P0(x)=0;Pj(x)=Pj-1(x)+aj+b Pj-1(x),xj=1;Pj(x)=Pj-1(x),xj1,xX。式中:fkj(x)(k=1,2)分别表示工件Jj在T1之前加工和在T2之后加工
22、的完工时间,gj(x)表示工件J1,J2,Jj的总拒绝惩罚,Fj(x)表示工件J1,J2,Jj的目标函数值,Pj(x)表示J1,J2,Jj中在T1之前加工工件的总完工时间,而且只需要关注使得Pj(x)T1的向量x,则该向量x对应J1,J2,Jj的一个可行排序。值得注意 的 是,fkj(x),gj(x),Fj(x)和Pj(x)都 与xj+1,xj+2,xn无 关。因 此,问 题1,h n r-a,pj=aj+b t,r e jSCj+Sej可以简化成下面的问题:m i nFn(x),s.t.Pn(x)T1,xX。接下来介绍K o v a l y o v等人2 6提出的过程划分(A,h,),其中A
23、X,h是关于X的一个非负整数函数,0(1+)h(x(1)的i1。如果不存在满足条件的i1,那么令Ahkh=Ah1=A并停止。将向量x(i1+1),x(i1+2),x(i2)分配到集合Ah2中,直到找出满足h(x(i2)(1+)h(x(i1+1)和h(x(i2+1)(1+)h(x(i1+1)的i2。如果不存在满足条件的i2,那么令Ahkh=Ah2=A-Ah1并停止。继续上述操作,直到存在某个kh,使得x(A)包含于Ahkh。过程划分将A中向量按照h(x)非减顺序排列需要O(Al o gA)时间,产生一个划分需要O(A)时间。下面的引理将在F P T A S中使用。引理52 6 对于x,x Ahj
24、,j=1,2,kh,有h(x)-h(x)m i nh(x),h(x)。引理62 6 对于01,h(x(A)1,有khl o gh(xA)+2。引理7 对于0 0,因此f(x)是凸函数。又因为f(0)=0,f(1)=1+1nn-3T1,则从Yj中删除x。则有:fkj(x)=fkj-1(x)+aj+b fkj-1(x),xj=k,k=1,2;fij(x)=fij-1(x),xj=i,ik;11第3期 何欣怡,等:带有退化、拒绝和不可用区间的单机排序问题gj(x)=gj-1(x),xj=k,k=1,2;gj(x)=gj-1(x)+ej,xj=3;Fj(x)=Fj-1(x)+fkj(x),xj=k,k
25、=1,2;Fj(x)=Fj-1(x)+ej,xj=3。若j=n,则令Yn=Yn,转到第3步。若jn,则令=2(n+1),继续下面的计算。用函数fij将Yj分成互不相交的集合Yfi1,Yfi2,Yfiki,记为划分(Yj,fij,),i=1,2;用函数gj将Yj分成互不相交的集合Yg1,Yg2,Ygkg,记为划分(Yj,gj,);用函数Fj将Yj分成互不相交的集合YF1,YF2,YFkF,记为划分(Yj,Fj,)。将集合Yj划分成互不相交的子集Y123=Yf11Yf22Yg3YF,1=1,2,k1,2=1,2,k2,3=1,2,kg,=1,2,kF。在每一个非空子集Y123中,选出向量x(123
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 带有 退化 拒绝 可用 区间 单机 排序 问题
![提示](https://www.zixin.com.cn/images/bang_tan.gif)
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【自信****多点】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【自信****多点】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。