机器带有周期维护和准备时间且工件可中断的混合平行机调度问题.pdf
《机器带有周期维护和准备时间且工件可中断的混合平行机调度问题.pdf》由会员分享,可在线阅读,更多相关《机器带有周期维护和准备时间且工件可中断的混合平行机调度问题.pdf(9页珍藏版)》请在咨信网上搜索。
1、收稿日期:2 0 2 2 1 0 2 5基金项目:国家自然科学基金资助项目(7 1 6 7 2 1 1 7);辽宁省自然科学基金资助项目(2 0 2 0-B S-2 6 3)。作者简介:谢 谢(1 9 8 1),女,辽宁沈阳人,教授,博士。第3 5卷 第5期2 0 2 3年 1 0月沈阳大学学报(自然科学版)J o u r n a l o fS h e n y a n gU 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.3 5,N o.5O c t.2023文章编号:2 0 9 5-5 4 5 6(2 0 2 3)0 5-0 3 8 8-
2、0 9机器带有周期维护和准备时间且工件可中断的混合平行机调度问题谢 谢1 a,都基宇1 b,郑勇跃2(1.沈阳大学a.装备制造综合自动化重点实验室,b.信息工程学院,辽宁 沈阳 1 1 0 0 4 4;2.辽宁省检验检测认证中心 事业发展中心,辽宁 沈阳 1 1 0 0 3 2)摘 要:从义齿加工厂隐形义齿和氧化锆全瓷牙这两种义齿的生产流程中,提炼出一类混合平行机生产调度问题。在这个问题中,一部分机器带有准备时间,剩余的机器将会设置对应的周期维护,在机器维护过程中不再进行工件加工,目标是最小化最大完工时间。在前人研究的基础上,对于机器只考虑准备时间或只考虑周期维护的特殊情况这2个问题提出了机器
3、具有准备时间和周期维护的混合平行机调度问题,以注水模型为基础,结合每种机器的不同情况,通过分类讨论提出了两个多项式时间内可解的最优算法。关 键 词:混合平行机;可中断;准备时间;周期维护;注水模型中图分类号:T P 3 0 1.6 文献标志码:AAH y b r i dP a r a l l e lM a c h i n eS c h e d u l i n gP r o b l e m W i t hP e r i o d i cM a i n t e n a n c e,R e a d yT i m ea n dI n t e r r u p t i b l eJ o b sX I EX
4、i e1 a,DUJ i y u1 b,ZHENGY o n g y u e2(1.a.K e yL a b o r a t o r yo fM a n u f a c t u r i n gI n d u s t r i a la n dI n t e g r a t e d A u t o m a t i o n,b.S c h o o lo fI n f o r m a t i o nE n g i n e e r i n g,S h e n y a n g U n i v e r s i t y,S h e n y a n g1 1 0 0 4 4,C h i n a;2.C e n
5、t e ro fC a r e e rD e v e l o p m e n t,L i a o n i n gI n s p e c t i o n,E x a m i n a t i o n&C e r t i f i c a t i o nC e n t r e,S h e n y a n g1 1 0 0 3 2,C h i n a)A b s t r a c t:Ac l a s so fh y b r i dp a r a l l e lm a c h i n es c h e d u l i n gp r o b l e m w a se x t r a c t e df r o
6、 mt w o-t y p ep r a c t i c a lp r o d u c t i o np r o c e s s e si nad e n t u r ep r o c e s s i n gp l a n t:i n v i s i b l ed e n t u r ea n dz i r c o n i aa l l-c e r a m i cd e n t u r e.I n t h i s c a s e:s o m em a c h i n e sh a da s e t-u p t i m e,w h i l e t h e r e s t o ft h em a
7、c h i n e sw e r es e tu pf o rp e r i o d i cm a i n t e n a n c e,n ow o r k p i e c em a c h i n i n gw a sc a r r i e do u td u r i n gm a c h i n em a i n t e n a n c e,w i t ht h eg o a lo fm i n i m i z i n gt h em a x i m u mc o m p l e t i o nt i m e.O nt h eb a s i so fp r e v i o u sr e s
8、 e a r c h,t h eh y b r i dp a r a l l e lm a c h i n es c h e d u l i n gp r o b l e m w i t hp r e p a r a t i o nt i m ea n dc y c l em a i n t e n a n c eo f t h em a c h i n ew a sp r o p o s e d f o r t h e s p e c i a l s i t u a t i o no fm a c h i n eo n l yc o n s i d e r i n gp r e p a r
9、a t i o nt i m eo rc y c l em a i n t e n a n c e,a n db a s e do nt h ew a t e ri n j e c t i o n m o d e la n d c o m b i n i n gt h e d i f f e r e n ts i t u a t i o n s o fe a c h m a c h i n e,t w o o p t i m a la l g o r i t h m st h a tc o u l db es o l v e di np o l y n o m i a lt i m ew e
10、r ep r o p o s e dt h r o u g hc l a s s i f i c a t i o nd i s c u s s i o n.K e y w o r d s:h y b r i dp a r a l l e lm a c h i n e;i n t e r r u p t i b l e;r e a d yt i m e;p e r i o d i cm a i n t e n a n c e;w a t e ri n j e c t i o nm o d e l调度问题是探讨在满足各种约束条件下如何尽可能有效地分配资源,以实现最大化产品利润并最小化总完成时间等目
11、标的过程。这一过程伴随着各种任务的有效排序,具有重要的理论和应用意义。机器的周期维护就是机器和设备在长时间连续运行中可能发生故障崩溃,从而降低了生产效率,所以在经过一段时间的的运行后,机器必须要处于停机状态,然后根据相应的周期设置维护时间,减少机器在工作过程中的故障率。而机器因为预防性维护以及设备自身的调整而花费的时间称为实际生产的机器准备时间。机器准备时间还包括机器在具体操作之前需要一定步骤进行准备所花费的时间。机器准备时间是不可或缺的,它保障了生产线以及设备运转的正常。本文从义齿加工厂同时加工隐形义齿和氧化锆全瓷牙这两种义齿的生产过程,提炼出一类混合平行机生产调度问题。生活中常见的义齿材料
12、有全口义齿、全瓷牙、烤瓷牙及钴铬烤瓷牙等,其中患者选择最多的就是隐形义齿和氧化锆全瓷牙。而隐形义齿和氧化锆全瓷牙这2种义齿制作过程中都需要经过工作人员的入场登记、消毒和活动蜡型石膏修型后,经过2种不同的生产线进行加工制作。在隐形义齿的制作中,机器要先加热隐形胶,待其冷却再投入生产线经过注塑、成品修复、抛光打磨完成出货,具体流程见图1。氧化锆全瓷牙的制作在投入生产线后要进行扫描切割、上瓷修型、上釉等,在这期间,氧化锆全瓷牙要不断进行周期性的加热冷却,具体流程见图2。图1 义齿加工厂加工隐形义齿的生产过程F i g.1 P r o d u c t i o np r o c e s so f i n
13、 v i s i b l ed e n t u r ep r o c e s s i n g f a c t o r y图2 义齿加工厂加工氧化锆全瓷牙的生产过程F i g.2 P r o d u c t i o np r o c e s so f z i r c o n i aa l l c e r a m i c t e e t h i nd e n t u r ep r o c e s s i n g f a c t o r y f a c t o r y可将以上2种义齿制作流程看作生产调度问题中平行机的调度问题,将生产线看作调度问题中的机器,义齿看作工件,隐形义齿生产线的最开始的加热冷
14、却看作机器的准备时间,氧化锆全瓷牙的周期加热冷却看作是机器的周期维护。本文基于以上实际提出一类需要周期维护和有准备时间的混合型平行机调度问题。L i a o等1是最早在调度领域引入周期维护的中国学者,2 0 0 3年,他们研究了单机调度问题,一台需要周期维护的机器,目标是完成时间的最大延误问题,并给出一个分支定界算法。C h e n2与S b i h i等3分别给出了一个启发式算法和一个分支定界算法,他们的算法更精准简洁,只是研究的问题依然是单机。S u n等4研究了2台需要同时进行周期性维护的平行机的调度问题,他们基于F F D(f i r s tf i td e c r e a s i n
15、 g)算法提出了一个启发式算法,并且证明了此启发式算法在规定条件下最坏情况比为2。2 0 1 0年,程贞敏等5讨论了2台需要周期维护的机器的调度问题,目标函数是最小化时间表长,他们将T设为维护周期,机器每一次的维护时间为t,证明了当t3T时,在这个问题中应用L P T(l o n g e s tp r o c e s s i n gt i m e f i r s t)算法得到的最坏误差界为2。2 0 1 4年,王婷6在R o o t7研究的具有损失函数的调度问题的基础上研究了机器维护时长是随着机器的负载量可变的单机调度问题,该问题被其证明是N P-难的。2 0 1 7年,L i等8考虑了一个平
16、行机器调度问题,对经典的L P T和L S(l i s ts c h e d u l i n g)算法进行了最坏情况的分析,在此基础上,提出了2种改进的启发式算法。2 0 1 8年,程贞敏等9研究了工件不可中断的机器带周期维护且加工速度不同的平行机调度问题,采用了注水模型并且给出求解的4个算法。以上文献这些研究大部分针对的是单机或者有限数量的平行机问题研究,而本文将这类问题推广为数量不限的平行机调度问题。以上的研究是工件在不可中断条件下的机器带周期维护的平行机调度问题,当工件可以中断时,往往会让问题变得简单。在经典的调度问题中,针对机器带周期维护工件可中断的最大完工时间问题,H o r v a
17、 t h等1 0给出了一个中断次数不超过m-1次的最优算法。而对于恒速机,G o n z a l e z等1 1给出了求解调度问题的最优算法。他们的算法较之前学者的更加高效,中断次数更少,中断的次数为2(m-1)次。谢谢等1 2将带有不可用区间的单机生产调度问题与运输调度问题结合在一起研究,并提出了解决此问题的启发式算法。在工件可中断的周期维护混合平行机调度问题上,程贞敏等1 3给出了基于注水983第5期 谢 谢等:机器带有周期维护和准备时间且工件可中断的混合平行机调度问题模型下的最优算法。在恒速机需要周期维护的调度问题研究中,周菊等1 4给出了MWA(m o d i f i e dw r a
18、 pa r o u n da l g o r i t h m)算法。以上研究主要针对机器都需要周期维护的条件下进行研究,并没有研究带准备时间的机器的混合平行机调度问题。而对于机器带准备时间的平行机调度问题。L e e1 5展示了最长处理时间算法,即L P T算法,求出了一个最坏情况比为23-12m。L i n等1 6进一步研究了m台机器都带准备时间的同速机调度问题,基于以上的证明和推理可以发现渐进最优解是L P T算法,同时在分析的过程中还针对这一算法设置了紧参数最坏情况界。研究人员还尝试了多种类型的机器模型调度问题,这些机器模型都有相应的准备时间。孙志慧1 7和李海霞等1 8主要研究的对象是
19、2种类型的调度问题,一种是分析排序,另一种是具有及时准备时间。研究的内容都是同速机以及同类机的结合。S h e n等1 9主要分析的是设备,具有准备时间以后,如何在进行设备调度的过程中尽可能地减小成本。K a a b i等2 0研究了具有不同准备时间的同类机上考虑工件具有不同的类型和性能,并设计了启发式算法。曹丽萍2 1研究了机器带准备时间工件可中断的调度问题,并设计了中断次数为m-1次的最优算法。由此可见,将周期维护和机器具有准备时间这2种机器组合在一起的混合平行机的调度问题,研究的学者还比较少。总结以上文献,发现这些研究大部分针对的是单一条件下,即机器带周期维护或者是机器带准备时间的平行机
20、问题研究。因此本文在前人研究的基础上,提出了在工件在加工过程中可以中断且机器具有准备时间和周期维护的混合平行机调度问题,目标是最小化最大完工时间,以当前使用较为广泛的周期维护算法为指导,结合单种机器环境运行要求,设计了加入准备时间机器环境的中断次数最多为(k+1)(m-m1)+m的新算法。该算法可以最优求解本文研究的问题。1 问题描述给定m台混合平行机,其中有m1台机器都有固定的准备时间,记为r,而余下的m-m1台机器需要周期维护,设机器Mm1+1,Mm1+2,Mm需要周期维护,机器的维护周期相同,记为T,维护时长也相同,记为w,机器M1,M2,Mm1具有准备时间(因为所有工件加热时间相近且维
21、护时长远小于维护周期,即rwm)个加工时长都为p的工件放在这m台机器上加工,工件在加工的过程中可以中断,目标函数是最小化最大完工时间。符号说明:n所有被加工的工件总数;m所有加工的机器总数;m1具有准备时间的机器总数;m-m1需要周期维护的机器总数;Pj加工工件Jj所消耗的加工时间;r机器的准备时间;T机器的维护周期;w机器每次的维护时长;Cm a x最大完工时间;Mj第j台机器;k需要周期维护的机器加工完成的完整维护次数;M1,M2,Mm1具有准备时间的机器;Mm1+1,Mm1+2,Mm需要周期维护的机器。2 2种特殊情况2.1 没有需要周期维护的机器当m1=m时,即m台机器中没有机器需要维
22、护,所有机器都有固定的准备时间,因为所有机器的准备时间同为r,所以可以看成当r时间过后,所有工件在机器上加工的最小时间表长问题,关于此问题,唐恒永等2 2给出了先求出问题下界再进行排序的最优算法。093沈阳大学学报(自然科学版)第3 5卷算法1步骤1 计算C=pjm+r=n pm+r。步骤2 将n个工件按任意顺序排为一排,并且平均分成m个部分,第1部分为0,C,第m部分为(m-1)C,mC。步骤3 把第i(i=1,m)部分相应放在处理机Mi上进行加工。定理1 对于调度问题p m,r pj=p,p r m pCm a x由上述算法得到的时间表长为最小时间表长,Cm a x=n pm+r。证明 存
23、在nm代表着工件数量大于机器数量,所以满足1)工件在相同时刻下不可能出现在不同的机器上;2)所有的机器在同一时刻下只能对于这一种工件进行加工。接着考虑到n pm+r时刻之前所有的机器都处于忙碌状态,排序为无耽搁排序,进一步可以判断上面所提出的算法就是最优算法。2.2 全部机器都需要进行周期维护如果所有的机器都需要进行周期维护,机器的数量为m,那么m1=0,这个数值代表着所有的机器中没有机器设置了对应的准备时间,另外,考虑到所有机器的维护间隔和机器的维护时长保持一致,所有的工件在加工过程中都允许中断,因此将这部分机器看作不需要维护的设备,同时,针对每一台机器都设置对应的时间段,在一个时间段中设置
24、固定的时间单位,在经过这一时间段以后,机器再次进行加工,直到所有的工件加工完毕。因为所有机器都同时维护,且维护时间相同,工件可以中断,这种情况并不改变工件的排序方式,去除机器的准备时间后,算法1就可以实现这种条件下的最优排序。步骤1 计算C=n pT+ww+n pm。步骤2 将n个工件按任意顺序排位一列,并且平均分成m部分,第一部分0,C,第m部分为(m-1)C,mC。步骤3 把第i(i=1,m)部分相应放在处理机Mi上进行加工。此算法证明与定理1相同。3 一般情况下的讨论此时的问题为总数m台机器中有准备时间的机器有m1台,需要进行周期维护的机器有m-m1台,工件可中断加工且工件所需要加工的时
25、长都为p。赵传立等2 3已经给出了当n pmT时的经典平行及调度问题的算法,而且已经证明是最优算法。故本文中以下考虑的情况都假设n pmT。另外对于只有1台和2台需要周期维护的机器的情况,X u等2 4已经给出了一个多项式时间最优算法。在该问题中,由于工件可中断,学者们提出了注水模型,即工件的加工时长为p,所以加工的工件就可以是看作pm l的水,把机器看作容器,把水倒入容器中,水平面的高度就是最优时间表长的下界。张家宝2 5通过研究确定了工件的数量不大于机器数量的情况下对应的最优时间表长Cm a x,并且指出混合周期维护机器且工件可中断的平行机调度问题是多项式时间可解的,不是N P难问题。然而
- 配套讲稿:
如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。