改进灰狼优化算法求解机器人 作业车间调度问题.pdf

第 卷第期年月计算技术与自动化C o m p u t i n gT e c h n o l o g ya n dA u t o m a t i o nV o l ,N o J u n 收稿日期:基金项目:重庆市技术创新与应用示范类基金资助项目(c s t c j s z x c y z d X )作者简介:晏晓凡(),男,重庆渝中人,本科,助理工程师,研究方向:智能制造,信息化项目规划及建设.通信联系人,E m a i l:y a n x i a o f a n c q c y c o m文章编号:()D O I:/j c n k i j s j s y z d h 改进灰狼优化算法求解机器人作业车间调度问题晏晓凡(重庆川仪自动化股份有限公司执行器分公司,重庆 )摘要:针对物料机器人指派和作业车间的联合调度问题,设计了一种改进灰狼优化算法进行求解.根据机器人作业车间调度和灰狼优化算法的各自特点,提出一种面向机器人转移工序的编码方式.解码时,考虑工件运输的前提是工件在当前机器的工序已加工,提出融合间隙解码方法的驱动解码方法.为避免算法陷入局部最优,在灰狼个体位置更新后加入个体变异方法.最后,通过与其他智能优化算法及同类算法进行比较,验证了所提灰狼优化算法的有效性.关键词:机器人;作业车间调度;灰狼优化算法;集成调度;间隙解码中图分类号:T P 文献标识码:AA nI m p r o v e dG r e yW o l fO p t i m i z a t i o nA l g o r i t h mf o rR o b o t i cJ o bS h o pS c h e d u l i n gP r o b l e mYANX i a o f a n(A c t u a t o rF i l i a l e,C h o n g q i n gC h u a n y iA u t o m a t i o nC o,L t d,C h o n g q i n g ,C h i n a)A b s t r a c t:A i m i n ga t t h ep r o b l e mo fm a t e r i a l r o b o t a s s i g n m e n t a n d j o i n t s c h e d u l i n go f t h ew o r kw o r k s h o p,a n i m p r o v e dg r a yw o l fo p t i m i z a t i o na l g o r i t h mi sd e s i g n e dt os o l v ei t A c c o r d i n gt ot h er e s p e c t i v ec h a r a c t e r i s t i c so ft h er o b o t j o bs h o ps c h e d u l i n ga n dt h eg r a yw o l f o p t i m i z a t i o na l g o r i t h m,a c o d i n gm e t h o d f o r t h e r o b o t t r a n s f e rp r o c e s s i sp r o p o s e d Wh e nd e c o d i n g,t h ep r e m i s eo f t h ew o r k p i e c e t r a n s p o r t a t i o n i s c o n s i d e r e d t h a t t h e j o bh a sb e e np r o c e s s e d i n t h e c u r r e n tm a c h i n eo p e r a t i o n,a n dt h ed r i v i n gd e c o d i n gm e t h o do f t h e f u s i o ng a pd e c o d i n gm e t h o d i sp r o p o s e d I no r d e r t oa v o i dt h ea l g o r i t h mf a l l i n gi n t o l o c a l o p t i m i z a t i o n,t h e i n d i v i d u a l v a r i a t i o nm e t h o d i sa d d e da f t e r t h e i n d i v i d u a l p o s i t i o no f t h eg r a yw o l f i su p d a t e d F i n a l l y,t h ee f f e c t i v e n e s so f t h ep r o p o s e dg r a yw o l f o p t i m i z a t i o na l g o r i t h mi sv e r i f i e db yc o m p a r i n gw i t ho t h e r i n t e l l i g e n t o p t i m i z a t i o na l g o r i t h m sa n ds i m i l a ra l g o r i t h m s K e yw o r d s:r o b o t;j o bs h o ps c h e d u l i n g;g r a yw o l fo p t i m i z a t i o na l g o r i t h m;i n t e g r a t e ds c h e d u l i n g;g a pd e c o d i n gm e t h o d随着物联网技术和人工智能技术的深度融合,物料机器人因其能有效提高生产效率、降低人工成本,开始被大量运用于加工车间中,以实现智能化生产.然而,S a w i k指出,制造系统中机器人和机器之间缺乏适当的协调可能会产生严重后果.因而,机器人车间调度问题成为近年来工业应用和学术研究的热点问题.机器人作业车间调度问题的求解因其解空间结构复杂,现有研究多采用智能优化算法求解.杨煜俊等针对作业车间多机器人制造单元调度问题,提出了基于三层编码的遗传算法进行求解.陈魁等结合竞争机制和随机重启机制提出了一种第 卷第期晏晓凡:改进灰狼优化算法求解机器人作业车间调度问题混合粒子群优化算法.成丽新等人采用基本表达式 编 程 的 方 法 求 解 单AGV车 间 调 度 问 题.Z h e n g等人针对大型调度问题提出了一种下限计算方法.全燕鸣等人引入亲和度函数,提出了一种克隆选择算法进行迭代求解.李峥峰等人考虑了机器人充电约束,通过虚拟设备设计了工件分配和AGV运输任务两段染色体编码的改进遗传算法进行求解.胡晓阳等人采用工序穿和机器穿双层编码对问题模型进行求解,提出了一种融合贪心启发式规则的改进迭代局部搜索算法.高效的智能优化算法对于问题的求解有着极其重要的作用.灰狼优化算法(g r e yw o l fo p t i m i z a t i o na l g o r i t h m,GWO)是模仿狼群等级制度和捕食行为而提出的一种新型群智能优化算法,该算法原理简单、易于实现,已成功应用于多种优化问题中,已有部分学者将其应用于求解车间调度问题.顾九春等人利用离散灰狼优化算法求解作业车间节能调度问题.姜天华 提出了一种求解低碳车间调度问题的灰狼优化算法.因而,本文将采用灰狼优化算法进行求解.问题描述和模型建立 问题描述机器人作业车间调度问题(r o b o t i cj o bs h o ps c h e d u l i n gp r o b l e m,R J S P)可以描述如下:现有工件(JJ,Jn)需 要在m台 机 器(MM,Mm)上加工生产,在生产过程中,由r个单爪机器人负责工件在机器间运输.每个工件Ji有hi个加工工序Oi k并需按一定顺序在相关机器k上加工,加工时间为pi j,工序Oi k和Oi(k)之间的转移工序由机器人Ri负责,将工件Ji由机器Mi k的输出缓冲区转移至机器Mi(k)的输入缓冲区,转移时间为TMi k,Mi(k),装/卸站(L/U)分别作为未加工工件的分发中心和已完工工件的收集中心.在进行加工前,假设所有工件和机器人都在L/U站,加工完成后,机器人和工件都返回L/U站,图为B i l g e提出的机器人作业车间布局,每个布局由四台机器、两个单爪机器人和一个L/U站组成.模型建立本问题目标是求解一个可行的调度方案,使得最大完工时间最小化,建立如下数学模型:m i nCm a x m i nm a xi,n(Ci)()CiCi dTM d,L/U()Ci dSi dPi d()Si jCi(j)C Ti jS Ti j()S Ti j m a xrRiXRii j(ARiTVAR j,Mi(j),Ci(j)()C Ti jS Ti jTMi(j),Mi j()rRiXRii j()Cki jPi jQ(Yi j,a b)Cka b()Si j,Ci j,S Ti j()其中,Ci为工件i完成所有加工工序并进入L/U站的时间;Si d/Ci d分别为工序Oi d的开完工时间;Si d/Ci d/Pi d分别表示工序工件i最后加工工序的开工时间/完工时间/加工时间;TMd,L/U表示工件i完 成 加 工 并 进 入L/U站 的 运 输 时 间;C Ti j/S Ti j分别表示加工工序Oi j前的转移完成/开始时间;ARi表示机器人Ri的最早可用时刻;VAR i表示机器人在ARi时刻的位置;XRii j为变量,若加工工序Oi j前的转移工序指派给机器人Ri,XRii j,否则,XRii j;Cki j表示工序Oi j在机器k上加工的完工时间;Yi j,a b为变量,如工序Oi j在Oa b后加工,Yi j,a b,否则,Yi j,a b;Q为一个极大的正数.图种机器人作业车间布局式()为目标函数;约束()和约束()定义了最大完工时间目标;约束()、约束()和约束()表示同工件的各工序先后约束关系;约束()表示一个机器人一次只能处理一个工件;约束()表示同一机器上加工工序的时间约束.计算技术与自动化 年月求解R J S P的改进灰狼优化算法机器人作业车间调度问题是作业车间调度问题的扩展,是更困难的约束组合优化问题和典型的N Ph a r d问题,它可以看作是两个子问题:机器人调度问题和工序排序问题.为更好地匹配这一问题结构及调度特点,本文设计了一种改进灰狼算法(GWO),该算法是M i r j a l i l i 从灰狼狼群围猎行为中受到启发而提出的,通过模拟灰狼狼群搜索、包围和攻击猎物的狩猎过程实现优化搜索的目的,其主要思想是不断更新种群中最好的个解:最好解、次好解和第三好解,并利用它们来引导其他解的进化搜索.与其他优化算法相比,GWO具有收敛速度快、鲁棒性强等特点.编码GWO最初用于解决连续优化问题,因此单个位置向量由一系列实数组成.然而,在机器人作业车间中,每台机器上的工序排列和机器人指派都需要一种典型的离散调度解决方案.因此,解决方案表示和转换机制对于GWO在R J S P中的应用都非常重要.在此提出了一种面向机器人运输的编码方式.如图(a)所示,本文设计的编码长度为整个机器人车间系统中的运输次数,编码长度L的计算如下:Lni(hi)()以图中的布局为例,设现有个待加工工件,每个工件有道待加工工序,那么系统的总运输次数L().在编码中,个体位置向量X的各元素为连续值,且在预定范围内取值.如图(a)中编码取值范围为,按固定的顺序存储,每个元素对应一道转移工序,其中V T 表示工件的第一道转移工序,V TE表示机器人将工件从L/U站转移至工件的第一道工序的加工机器的输入缓冲区.图个体位置向量及转换方式 驱动解码为将连 续 形 式 转 化 为 离 散 形 式,本 文 采 用R OV规则来解决灰狼优化算法连续个体位置向量和机器人作业车间调度问题离散调度解间的编码转换,图(b)展示了基于R OV规则的转换过程,首先将个体位置向量的元素值按升序排序,然后根据新的顺序,将元素值与其转移工序重新对应,最后对所对应的转移工序进行调整,调整后的工序排序如图(c)所示.在编码转换之后,对转换后的编码进行直接解码,基于间隙挤压法设计了一种针对机器人作业车间调度问题的驱动型解码算法,该解码方法能够在解码过程中驱动工序加工,故称其为驱动解码方法,具体解码步骤如下:步骤自左向右读取个体位置向量转换后的转移工序V Ti j,判断j是否大于,若j,转步骤,否则,转步骤.步骤获取工序Oi(j)的加工时间Pi j和工序Oi(j)的完工时间Ci(j),若j,Ci(j);寻找设备上所有可用时间 S Mk,E Mk、S Mk,E Mk分别为空闲开始时间与结束时间,按式()计算工序Oi(j)的最早开始时间:Si j m a x(Ci,(j),S Mk)()步骤获取工序Oi(j)的完工时间Ci(j),按式()得到机器人Ri进行此转移工序V Ti j的最早开始时间S Ti j,选择能最早 操作转移工 序V Ti j的机器人Rd作为此.S TRii jCi(j)TVA R i,Mi(j),ARiCi(j)TVA R i,Mi(j)ARi,ARiCi(j)TVA R i,Mi(j)()Rda r gm i n(S TRii j)()步骤重复步骤,直至所有工序均安排完毕.种群初始化对于基于种群的算法,初始解的质量在很大程度上影响算法的计算性能.目前的初始化种群的研究主要以启发式规则、主动调度、随机生成等方式为主.根据本文采用的算法特点,本文采用启发式规则和随机生成相结合的方式来生成初始种群,采用 剩 余 工 作 量 最 大(m o s t w o r kr e m a i n i n g,MWR)和最短加工时间(s h o r t e s tp r o c e s s i n g t i m e,S P T)两种对完工时间比较有效的启发式规则.选择转移工序时,生成一个随机数R,),当R第 卷第期晏晓凡:改进灰狼优化算法求解机器人作业车间调度问题 时,选用规则MWR;当 R 时,选用规则S P T;否则,选用随机规则,生成如图(c)所示的个体位置向量序列,从左到右依次随机生成升序位置向量的各元素,再反向重排为如图(a)所示的个体位置向量.个体位置更新方法GWO以种群中历史最优的三个解、作为引导,让其他个体w完成靠近、包围和攻击等行为,最终达到捕食猎物的目的.基本GWO算法中的、虽处于不同等级,但在引导过程中并未发挥不同的领导作用,个体位置更新采用的权重系数相同,对此,本文改变了、在引领个体更新时的权重系数,该过程可以表示为:DCXp(t)X(t)()X(t)Xp(t)AD()Aa ra()Cr()DCX(t)X(t)()DCX(t)X(t)()DCX(t)X(t)()XX(t)AD()XX(t)AD()XX(t)AD()X(t)XXX()f(t)F(t),f(t)F(t),f(t)F(t)()F(t)f(t)f(t)f(t)()其中,D表示猎物与灰狼之间的距离;t表示当前迭代次数;A和C表示协同系数向量;Xp表示猎物位置向量;X表示灰狼的个体位置向量;a中元素在迭代过程中由线性递减到;r、r均表示随机向量.由式()式()计算出个体与、的距离,通过式()和()计算个体更新的权重系数,然后由式()确定个体向猎物移动的方向.个体变异方法GWO采用头狼引领机制,可以加快收敛速度快速缩小包围圈,但这种快速聚集的方式也容易陷入局部最优.本文在个体位置更新后设计了一种个体变异方式,用于协助GWO跳出局部最优,增加种群的多样性.变异操作如下:对每个个体位置更新后的个体中的各元素以极小的概率进行变异.变异操作公式如下:Xi(t)Xi(t)r a n dK()其中,是一个很小的正数,可取 ,r a n dj,Kj,Kj取值如下:Kj,rj,rj()其中,为一个极小的正数,可取 .实验实验平台为个人P C计算机,处理器:I n t e l(R)C o r e(TM)i G C P U GH z GH z,机带R AM:G B,操作系统为W i n d o w s 专业版,采用P y t h o n 进行编程,编译软件版本为P y C h a r m专业版 .实验设计本文的 实 验 相 关 参 数 设 置 如 下:狼 群 规 模P o p_s i z e ,最大迭代次数TMA X .本文采用B i l g e等人设计的算例进行实验,该算例考虑了机床的不同布局对调度结果的影响,四种布局如图所示.算例编号以“E X”开头,后跟两个数字,第一个数字表示工件集编号,第二个数字表示车间布局,如“E X ”表示待调度工件集J o b s e t,车间布局 选 择 图(a)所 对 应 的 布 局.为 验 证 所 提GWO在求解机器人作业车间调度问题的有效性,将其与文献 所提MA S(m u l t i a g e n ts y s t e m)算法、文献 所提的采用三阶段编码形式的改进灰狼算法(I GWO)进行对比,算例中,机器人数量均为.算例运行结果见表,表中指标B e f用来对本文的算法性能进行打分,B e f越高表示算法的寻优效果越好,B e f的计算公式如下:B e fZZZm i n()其中,Z表示本文算法求解当前算例的最优解;Z为所有对比算法中的最优解;Zm i n表示本文算法和对比算法中的最优解.种算法算例结果对比如图所示,由表可知,本文提出的GWO在测试算例中有 优于MA S算法,优于文献 中所提的同类灰狼优化算法,此外,通过B e f指标可以看出,本文提出的算法在算例“E X ”“E X ”和“E X ”上都取得了十分显著的寻优效果,这三者的B e f值分别为 、和 .本文在发挥灰狼算法优良的寻优性能同时,设计的编码解码方式极大地促进了算法的寻优,能更好地跳出局部最优,进行全局搜索,寻优能力较好.计算技术与自动化 年月表算例对比结果编号算例MA SI GWO本文GWOB e fE X E X E X E X E X E X E X E X E X E X E X E X E X E X E X E X E X E X E X E X E X E X E X E X E X E X E X E X E X E X E X E X E X E X E X E X E X E X E X E X 图算例对比图图、图分别为算例“E X ”“E X ”的调度甘特图,其中“M”表示机器,“R”表示机器人,“”表示工件.填充相同的表示同一加工工件,在机器人的调度甘特图中,填充为空白的表示该段时间机器人空载.图算例“E X ”调度甘特图图算例“E X ”调度甘特图上述实验对象为两个机器人的车间调度,但实际生产中,机器人的数量并非只有两个,为进一步探索机器人数量与调度之间的关系,在各种车间布局中分别取一个算例进行灵敏度分析,这里我们取“E X ”“E X ”“E X ”“E X ”来进行下列实验,使机器人的数量从递增到,实验结果如图所示.完工时间随机器人数量的增加逐渐减小,且递减速度逐渐放缓,这种现状符合边际效应的递减规律.在车间中,应根据成本、效率等诸多因素确定合理的机器人数量.图完工时间随机器人数量的变化图结论对机器人作业车间调度问题进行了数学建模,并针对问题特点设计了灰狼优化算法进行求解.第 卷第期晏晓凡:改进灰狼优化算法求解机器人作业车间调度问题通过实验结果可以看出,本设计面向工件运输的编码方式,通过R OV转换和驱动解码方式在寻优上具有极大优势,不仅优于其他智能优化算法,与同类灰狼算法相比,也表现出极好的优势,由此可以看出本文所提灰狼优化算法具有较高的可靠性和鲁棒性.此外,研究了机器人数量对完工时间的影响,完工时间随机器人数量的增加逐渐减小,且减小速度逐渐放缓.同时,由于在编码时没有考虑机器人的选择问题,在少数算例中也暴露出计算能力不足的缺点.这些问题有待于今后的深入研究和解决.参考文献S AW I KTAm u l t i l e v e lm a c h i n ea n dv e h i c l es c h e d u l i n g i naf l e x i b l em a n u f a c t u r i n gs y s t e mJM a t h e m a t i c a la n dC o m p u t e rM o d e l l i n g,():杨煜俊,龙传泽,陶宇,等作业车间类型多机器人制造单元调度算法J计算机集成制造系统,():陈魁,毕利,王文雅,等柔性作业车间A GV与机器双资源集成调度研究J系统仿真学报,():成丽新,唐秋华,张利平,等基于基因表达式编程的单A G V加工车间调度规则生成J现代制造工程,():Z HE N GY,X I A OYJ At a b us e a r c ha l g o r i t h mf o r s i m u l t a n e o u sm a c h i n e/A GVs c h e d u l i n gp r o b l e mJ I n t e r n a t i o n a lJ o u r n a l o fP r o d u c t i o nR e s e a r c h,:,全燕鸣,何一明多机器人任务分配调度的克隆选择算法J华南理工大 学学报:自 然科学版,():李峥峰,刘阳阳考虑充电的多A GV的作业车间调度问题J计算机集成制造系统,():胡晓阳,姚锡凡,黄鹏,等改进迭代局部搜索算法求解多A GV柔性作业车 间调度问题J计算机集 成 制 造 系 统,():顾九春,姜天华,朱惠琦,等多目标离散灰狼优化算法求解作业车间节能调度问题J计算机集成制造系统 ,():姜天华基于灰狼优化算法的低碳车间调度问题J计算机集成制造系统,():M I R J A L I L IS G r e yw o l fo p t i m i z e rJA d v a n c e s i nE n g i n e e r i n gS o f t w a r e,:E R O LR,S AH I NC,B AY KA S O G L UA,e t a l Am u l t i a g e n tb a s e da p p r o a c ht od y n a m i cs c h e d u l i n go fm a c h i n e sa n da u t o m a t e dg u i d e dv e h i c l e si n m a n u f a c t u r i n gs y s t e m sJA p p l i e dS o f tC o m p u t i n gJ o u r n a l,():徐逸凡,张利平,唐秋华,等求解带A GV柔性作业车间调度问题的改进灰狼算法J工业工程,():(上接第 页)参考文献李明,任清华,吴佳隆基于有限零和博弈和变换域优选的智能抗干扰策略研究J信号处理,():GA I A R I NS,D ARF,D ERN,e t a l E x p e r i m e n t a l d e m o n s t r a t i o no fn o n l i n e a rf r e q u e n c yd i v i s i o n m u l t i p l e x i n gt r a n s m i s s i o nw i t hn e u r a ln e t w o r kr e c e i v e rJ J o u r n a lo fL i g h t w a v eT e c h n o l o g y:AJ o i n tI E E E/O S AP u b l i c a t i o n,():T I ANY,L I A ORM u l t i n o d ec o l l a b o r a t i v e i m a g ec o m p r e s s i o na l g o r i t h mf o rw i r e l e s sm u l t i m e d i as e n s o rn e t w o r k sb a s e do nL B TJ I E E Es e n s o r sj o u r n a l,():谢添,高士顺,赵海涛,等基于强化学习的定向无线通信网络抗干扰资源调度算法J电波科学学报,():王桂胜,黄国策,王叶群,等基于认知驱动的变换域通信智能抗干扰方法J系统工程与电子技术,():李夏昭,任清华,孟庆微频谱失配下的变换域通信系统基函数优化设计J信号处理,():宋佰霖,许华,蒋磊,等一种基于深度强化学习的通信抗干扰智能决策方法J西北工业大学学报,():谢文旺,孙云莲,黄雅鑫基于改进随机森林的电力线通信优化算 法 研 究 J电 力 系 统 保 护 与 控 制,():张晓博,王海,冯智斌,等基于主动诱导机制的中继通信智能抗干扰方法J南京邮电大学学报(自然科学版),():ME J I AJ,O C HOA Z E Z Z A T T IA,C RU Z ME J I AO,e ta l P r e d i c t i o no f t i m es e r i e su s i n gw a v e l e tG a u s s i a np r o c e s sf o rw i r e l e s ss e n s o rn e t w o r k sJW i r e l e s sn e t w o r k s,():周恒杰,孙闽红,钟华,等基于不完全信息动态博弈的多信道无线网络抗干扰传输J电信科学,():盖建新,薛宪峰,吴静谊,等基于深度卷积神经网络的协作频谱感知方法J电子与信息学报,():殷璐一种基于正交设计的通信抗干扰性能试验与评估方法J火力与指挥控制,():冉雨,程郁凡,陈大勇,等采用B P神经网络的智能抗干扰决策引擎研究J信号处理,():孙艺夫,安康,朱勇刚,等基于智能反射面的无线抗干扰通信方法J电波科学学报,():