共享制造环境下的同类机排序问题.pdf
《共享制造环境下的同类机排序问题.pdf》由会员分享,可在线阅读,更多相关《共享制造环境下的同类机排序问题.pdf(9页珍藏版)》请在咨信网上搜索。
1、D O I:1 0.3 9 6 9/j.i s s n.1 0 0 1-5 3 3 7.2 0 2 3.4.0 1 5*收稿日期:2 0 2 2-0 7-2 1基金项目:国家自然科学基金(1 2 2 7 1 2 9 5,1 2 0 0 1 3 1 3);山东省自然科学基金(Z R 2 0 2 2 MA 0 1 9);山东省大学生创新创业训练计划项目(S 2 0 2 2 1 0 4 4 6 0 1 8).第一作者:宋嘉欣,女,1 9 9 8-,硕士研究生;研究方向:组合最优化;E-m a i l:1 5 0 0 0 2 5 5 8 9q q.c o m.通信作者:苗翠霞,女,1 9 7 6-,博
2、士,教授,硕士生导师;研究方向:组合最优化、近似算法及次模优化;E-m a i l:m i a o c u i x i a 1 2 6.c o m.共享制造环境下的同类机排序问题*宋嘉欣,孔凡雨,霍雨佳,苗翠霞,赵韵杰(曲阜师范大学数学科学学院,2 7 3 1 6 5,山东省曲阜市)摘要:考虑了共享制造环境下的同类机排序问题.在共享制造环境中,每个工件Jj都有一个可以加工的机器集Mj,Jj可以被分别给Mj的某一台机器加工,也可以一定服务成本分配给其他剩余机器进行加工.该文的目标是最小化工件的最大完工时间加总服务成本.对于机器台数是固定常数情况,该文对经典加工模型和简单退化加工模型分别提出了基于
3、程序划分的全多项式时间近似方案.对总服务成本不超过给定上界的限制下最小化最大完工时间问题,给出了其整数规划模型.关键词:排序;共享制造;同类机;全多项式时间近似方案中图分类号:O 2 2 4 文献标识码:A 文章编号:1 0 0 1-5 3 3 7(2 0 2 3)0 4-0 0 1 5-0 90 引 言排序论是组合优化的一个重要分支,其中的平行机排序是常见的排序问题之一.一般情况下,每个工件可以被安排在任何一台机器上进行加工,而在食品加工等环境G l a s s和M i l l s1,每个工件可能只允许在某些规定机器上加工,这类平行机排序问题被称之为处理集限制排序问题.处理集限制排序类型可分
4、为嵌套处理集、包含处理集、区间处理集和树状分层处理集以及与之相关的模型有批处理模型、资源约束模型和具有协调机制的模型等.G l a s s和K e l l e r e r2考虑了工件具有分配限制的平行机排序问题.关于处理集为包含处理集的平行机排序问题,O u等3首次给出了该问题的多项式时间近似方案,L i和W a n g4将其拓展到工件具有到达时间的情况,并且给出了相应的多项式时间近似方案.E p s t e i n和L e v i n5考虑了处理集为包含处理集的同类机排序问题,并给出了多项式时间近似方案.L e u n g和N g6考虑了两种处理集下同类机排序问题的快速近似算法.M u r
5、a t o r e等7以及E p s t e i n和L e v i n8给出了处理集为嵌套处理集的平行机排序问题的多项式时间近似方案.L e u n g和L i9,1 0在2 0 0 8年对于不同类型处理集限制的在线和离线排序问题,给出了详细的综述,并在2 0 1 6年对此文献进了更新和补充.在经典排序问题中通常假设工件的加工时间是固定的,但在实际生产生活中,工件可能会因为加工过程的中断和耽搁而导致加工时间发生变化,因而产生了工件具有退化效应的排序问题.G u p t a等1 1首次考虑了工件具有退化效应的排序问题.简单线性退化的排序模型中工件的加工时间为pj=bjt,其中bj和t分别表示工
6、件的退化率和开始加工时间.M o s h e i o v1 2首先研究了简单退化模型.为建立健全资源节约型社会,现代排序又拓展到了共享制造领域.B r a n d t1 3首次提出了共享制造的概念,T a o和Z h a n g等1 4结合新兴的先进技术和制造模式,提出了新的制造模型.J i等1 5首次考虑了共享制造环境下处理集受限制的平行机排序问题,给出了解决该问题的全多项式时间近似方案.本文考虑了共享制造环境下处理集受限制的同类机排序问题,工件加工模型同时考虑了经典加工模型和简单退化加工模型.第4 9卷 第4期2 0 2 3年1 0月 曲阜师范大学学报J o u r n a l o f Q
7、 u f u N o r m a l U n i v e r s i t y V o l.4 9 N o.4O c t.2 0 2 3 文章的结构安排如下:第1部分对文章所研究的主要问题进行了描述,第2和第3部分主要对经典加工模型提出的模型给出了一个全多项式时间近似方案,同时给出了了总服务成本不超过给定上界的限制下最小化最大完工时间的整数规划模型,第4部分考虑了简单线性退化问题的一个全多项式时间近似方案,第5部分对文章进行了总结并提出有待解决的问题.1 问题描述和预备知识n个工件J=J1,J2,Jn 在m台同类机M=M1,M2,Mm 上加工,机器Mi(i=1,m)一次最多只能加工一个工件且加工
8、速度为si.假设经典加工模型所有工件在0时刻就绪而简单退化模型所有工件在1时刻就绪,且加工过程中工件不允许中断.每个工件Jj都有一个处理机器集MjM,如果它被分配到Mj中的任何一台机器上加工,除时间成本之外不产生任何费用,工件的加工时间为pj(pj=bjt),如果被分配到机器MiM Mj上,则加工时间为pi j(pi j=bi jt),并且产生额外的服务成本wi j,其中pj、pi j、bj、bi j和wi j均为正整数.本文的目标是找到一个最优排序,使得工件的最大完工时间和总服务成本之和最小,或者是在总服务成本不超过给定上界Q的限制下使得最大完工时间达到最小.该问题用G r a h a m等
9、1 6提出的三参数表示法可记为(Q m|Mj,SM|Cm a x+S)、(Q m|Mj,SM,SQ|Cm a x)及(Q m|Mj,SM,pj=bjt|Cm a x+S),其中SM表示共享制造环境,S为总服务成本.令ni为机器Mi上加工工件的个数,Ji,j为机器Mi上第j个位置的工件,显然对于i1,2,m,ni1,2,n,有mi=1ni=n成立.给出m台同类机的一个排序,令Ci,j为工件Ji,j的完工时间,令pi,j为工件Ji,j的加工时间.机器Mi上被安排工件的完工时间如下:Ci,1=pi,1si,Ci,2=pi,1+pi,2si,Ci,j=pi,1si+pi,2si+pi,jsi=ju=1
10、pi,usi.全多项式时间近似方案 设最小化问题有一族算法A.若对于任意0,问题的每一个实例I都存在FA(I)F*(I)1+,并且算法A 的运行时间是关于给定实例I的输入大小I和-1的多项式.不失一般性,假设01.文章设计的全多项式时间近似方案是基于K o v a l y o v和K u b i a k1 7,1 8提出的程序划分,其中涉及的函数要求为非负整数函数.对于本文研究的同类机排序问题,在不影响排序的前提下,必须修改原始目标函数来满足这个约束,参考L i u等1 9运用的方法,原始目标函数的修改过程如下:对于i1,2,m,j1,2,n,定义=m i npjsi,pi jsi.假设为有限
11、小数,对于任意正整数k,都有1 0k为正整数.因为Ci,j=ju=1pi,usi,故1 0kCi,j为正整数.在共享制造环境中数据总存在一定的误差,如果误差足够小则越接近于实际值,故可以将目标函数转换为K Cm a x+S,其中K=1 0k.转换后的目标K Cm a x+S为非负整数.2 问题(Qm|Mj,SM|Cm a x+S)的全多项式时间近似方案由J i等1 5讨论的N P-难(P m|Mj,SM|Cm a x+S)可知问题(Q m|Mj,SM|Cm a x+S)也是N P-难的,并且受他们的启发,下面提出对应的同类机问题的全多项式时间近似方案.首先,引入变量xj,j=1,2,n.如果工
12、件Jj被分配到机器Mi(i1,2,m)上加工,则xj=i.令61 曲阜师范大学学报(自然科学版)2 0 2 3年X=x:x=(x1,x2,xn).对J1,J2,Jn 以及xX,假设fij(x)为工件Jj被安排在机器Mi上时机器的最大载重,gj(x)为服务成本函数.边界条件为fi0(x)=0(i=1,2,m)和g0(x)=0.下面不妨假设工件Jj被安排在机器Mi上.若MiMj,则fij(x)=fij-1(x)+Kpjsi,i=xj,fij(x)=fij-1(x),ixj,gj(x)=gj-1(x);若MiM Mj,则fij(x)=fij-1(x)+Kpi jsi,i=xj,fij(x)=fij-
13、1(x),ixj,gj(x)=gj-1(x)+wi j.令F(x)=m a xi=1,2,mfin(x)+gn(x).求解问题(Q m|Mj,SM|K Cm a x+S)就等价于m i nF(x).为解决上述问题,引入了K o v a l y o v和K u b i a k1 7,1 8提出的程序划分(A,e,),其中AX,e为X上的非负整 数 函 数,并 且0(1+)e(x(1).如果i1不存在,那么令Aeke=Ae1=A,并且停止.将向量x(i1+1),x(i1+2),x(i2)分配给集合ae2,其中i2满足e(x(i2)(1+)e(x(i1+1)以及e(x(i2+1)(1+)e(x(i1
14、+1).如果i2不存在,那么令aeke=ae2=A-ae1,并且停止.步骤3 重复上述构造,直到x(|A|)被分配到aeke中.性质1 对于x,x Aej,都有|e(x)-e(x)|m i ne(x),e(x)成立,其中j=1,2,ke.性质2 对于01和1e(x|A|),都有ke l o ge(x(|A|)/+2成立.下面设计问题(Q m|Mj,SM|K Cm a x+S)的全多项式时间近似方案A.算法A步骤1(初始化)令Y0=(0,0,0),并且j=1.步骤2(生成集合Y1,Y2,Yn)对于集合Yj-1,通过向其第j个位置添加xj生成集合Y j,xj=1,2,m.对任意xY j,假设xj=
15、i,进行如下计算.若MiMj,则fij(x)=fij-1(x)+Kpjsi,i=xj,fij(x)=fij-1(x),ixj,gj(x)=gj-1(x);若MiM Mj,则fij(x)=fij-1(x)+Kpi jsi,i=xj,fij(x)=fij-1(x),ixj,gj(x)=gj-1(x)+wi j.若j=n,则令yn=Y n,并且执行步骤3.若jn,则令=2(n+1),进行如下计算.调用程序划分(Y j,fij,)(i=1,2,m),将Y j划分为不相交的子集Yfij1,Yfij2,Yfijkfij.71第4期 宋嘉欣,等:共享制造环境下的同类机排序问题 调用程序划分(Y j,gj,)
16、,将Y j划分为不相交的子集Ygj1,Ygj2,Ygjkgj.将集合Y j分成如下子集Ya1a2amb=Yf1ja1Yfmjamygjb,a1=1,2,kf1j;a2=1,2,kf2j;am=1,2,kfmj;b=1,2,kgj.对每个非空子集ya1a2amb,选择向量x(a1a2amb),使得m i nxYa1a2ambm a xi=1,2,mfij(x)+gj(x).步骤3(生成解)选择向量x0Yn,使得F(x0)=m i nF(x)|xYn.令x*=(x*1,x*2,x*n)为最优解,并且设L=kl o g1 0+l o gn+l o g(pm a x)+l o g(wm a x),其中
17、pm a x=m a xpjsi,pi jsi,wm a x=m a xj=1,2,nwi j|MiM Mj.定理1 对于问题(Q m|Mj,SM|K Cm a x+S),算法A在O(nm+2lm+2m+1)内找到了一个解x0X满足F(x0)(1+)F(x*).证明 假设存在一个部分最优解,(x*1,x*2,x*j,0,0)Ya1a2ambY j.假设在下面的迭代中算法A选择了x(a1a2amb)而非(x*1,x*2,x*j,0,0).由性质1可得|fij(x*)-fij(x(a1a2amb)|fij(x*),i=1,2,m,|gj(x*)-gj(x(a1a2amb)|gj(x*).考虑第j+
18、1个 工 件,(x*1,x*2,x*j,x*j+1,0,0)和 向 量x(a1a2amb)=(x(a1a2amb)1,x(a1a2amb)2,x(a1a2amb)j,x*j+1,0,0).令1=,假设xj=i,则MiMj时,有|fij+1(x*)-fij+1(x(a1a2amb)|=fij(x*)+Kpj+1si-fij(x(a1a2amb)+Kpj+1si=|fij(x*)-fij(x(a1a2amb)|1fij(x*)1fij+1(x*).MiM Mj时,有|fij+1(x*)-fij+1(x(a1a2amb)|=fij(x*)+Kpi j+1si-fij(x(a1a2amb)+Kpi j
19、+1si=|fij(x*)-fij(x(a1a2amb)|1fij(x*)1fij+1(x*).因此|fij+1(x*)-fij+1(x(a1a2amb)|1fij+1(x*).同样地,当ixj时,有|fij+1(x*)-fij+1(x(a1a2amb)|1fij+1(x*).由上述两式可得fij+1(x(a1a2amb)(1+1)fij+1(x*),i=1,2,m.(1)对于服务成本函数gj(x),同样有如下过程.当MiM Mj时,|gj+1(x*)-gj+1(x(a1a2amb)|=|gj(x*)-gj(x(a1a2amb)|1gj(x*)1gj+1(x*).当MiM Mj时,|gj+1(
20、x*)-gj+1(x(a1a2amb)|=|gj(x*)+wi j+1-(gj(x(a1a2amb)+wi j+1)|=|gj(x*)-gj(x(a1a2amb)|1gj(x*)1gj+1(x*).因此gj+1(x(a1a2amb)(1+1)gj+1(x*).假设x(a1a2amb)Yc1c2cmdY j+1,在第j+1步迭代中,算法A选择了向量x(c1c2cmd)Yc1c2cmd,则|fij+1(x(a1a2amb)-fij+1(x(c1c2cmd)|fij+1(x(a1a2amb)(1+1)fij+1(x*).有如下关系成立|fij+1(x*)-fij+1(x(c1c2cmd)|fij+1
21、(x*)-fij+1(x(a1a2amb)|+|fij+1(x(a1a2amb)-fij+1(x(c1c2cmd)|(1+(1+1)fij+1(x*)=(+1(1+)fij+1(x*).即81 曲阜师范大学学报(自然科学版)2 0 2 3年|fij+1(x*)-fij+1(x(c1c2cmd)|(+1(1+)fij+1(x*).(2)同样地,对于成本函数gj(x)如下关系成立:|gj+1(x(a1a2amb)-gj+1(x(c1c2cmd)|gj+1(x(a1a2amb)(1+1)gj+1(x*)和|gj+1(x*)-gj+1(x(c1c2cmd)|gj+1(x*)-gj+1(x(a1a2am
22、b)|+|gj+1(x(a1a2amb)-gj+1(x(c1c2cmd)|(1+(1+1)gj+1(x*)=(+1(1+)gj+1(x*).即|gj+1(x*)-gj+1(x(c1c2cmd)|(+1(1+)gj+1(x*).(3)令l=+(1+)l-1,其中l=2,3,n-j+1.由(2)式得|fij+1(x*)-fij+1(x(c1c2cmd)|2fij+1(x*).由(3)式得|gj+1(x*)-gj+1(x(c1c2cmd)|2gj+1(x*).对j+1,n重复上述过程,可以证明总是存在x Yn,有下式成立|fin(x*)-fin(x)|n-j+1fin(x*),i=1,2,m,(4)
23、|gn(x*)-gn(x)|n-j+1gn(x*).(5)其中n-j+1由以下递归过程得到n-j+1=+n-j(1+)nj=0(1+)j()=(1+)n+1-1=(1+2(n+1)n+1-11+22-1.则(4)式可写为fin(x)(1+)fin(x*),i=1,2,m.同样的(5)式可写为gn(x)(1+)gn(x*).因而F(x)=m a xi=1,2,mfin(x)+gn(x)m a xi=1,2,m(1+)(fin(x*)+(1+)gn(x*)=(1+)m a xi=1,2,mfin(x*)+gn(x*)=(1+)F(x*).由算法A的步骤3知,对于选择的向量x0,下式成立F(x0)F
24、(x)(1+)F(x*).下面分析算法A的时间复杂性.在原始划分程序(A,e,)的第2步中,在O(|A|l o g|A|)时间内,按照e(x)非递减顺序排列A中的向量,并且在O(|A|)时间内提供一个划分.由此可知,在调用我们的划分程序(Y j,fij,)时,时间复杂性为O(|Y j|l o g|Y j|).由Y j+1的构造知,|Y j+1|m|Yj|mk(f1j)k(fMj)k(gj),且由性质2知k(fij)2(n+1)l o g(Kn(pm a x)+2On L,k(gj)2(n+1)l o g(n(wm a x)+2On L.因此,得到|Y j|=Onm+1Lm+1m+1以及O(|Y
25、 j|l o g|Y j|)=Onm+1Lm+2m+1.综上所述,算法A的时间复杂性为Onm+2Lm+2m+1.91第4期 宋嘉欣,等:共享制造环境下的同类机排序问题 3 问题(Qm|Mj,SM,SQ|Cm a x)的整数规划模型工件Jj在机器Mi上加工,若MiMj,则工件Jj在机器上的运行时间为pjsi,若MiM Mj,则工件的实际加工时间为pi jsi,且产生的服务成本为wi j.引入决策变量xi j和Yi j满足xi j=1,如果 Mi Mj,0,其它,Yi j=1,如果 Mi M Mj,0其它.那么问题(Q m|Mj,SM,SQ|Cm a x)的整数规划模型可表示如下:m i nf=m
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 共享 制造 环境 同类 排序 问题
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【自信****多点】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【自信****多点】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。