基于改进飞蛾扑火算法的集成调度仿真.pdf
《基于改进飞蛾扑火算法的集成调度仿真.pdf》由会员分享,可在线阅读,更多相关《基于改进飞蛾扑火算法的集成调度仿真.pdf(12页珍藏版)》请在咨信网上搜索。
1、系统仿真学报系统仿真学报Journal of System Simulation第 35 卷第 10 期2023 年 10 月Vol.35 No.10Oct.2023基于改进飞蛾扑火算法的集成调度仿真基于改进飞蛾扑火算法的集成调度仿真张天瑞,牛慧媛*,谢薇(沈阳大学 机械工程学院,辽宁 沈阳 110044)摘要摘要:针对制造型企业成本上升等问题,建立生产与运输集成调度的数学规划模型,提出一种双自适应权重飞蛾扑火算法(double adaptive weights for moth flame optimizer,DAWMFO)进行求解。提出了一种双自适应权重机制;使用螺旋函数更新种群,提高了算
2、法的收敛速度和精度。采用改进算法对基准函数进行了测试,结果表明:DAWMFO不仅能够快速收敛且不易陷入局部最优,寻优能力较其他算法也有所提升。通过对生产与运输集成调度的数据集做仿真实验,验证了改进算法在求解此类问题时可行高效。关键词关键词:作业车间调度;螺旋函数;双自适应权重飞蛾扑火算法;生产和运输;集成调度中图分类号:TP391.9 文献标志码:A 文章编号:1004-731X(2023)10-2170-12DOI:10.16182/j.issn1004731x.joss.23-FZ0806引用格式引用格式:张天瑞,牛慧媛,谢薇.基于改进飞蛾扑火算法的集成调度仿真J.系统仿真学报,2023,
3、35(10):2170-2181.Reference format:Zhang Tianrui,Niu Huiyuan,Xie Wei.Integrated Scheduling Simulation Based on Improved Moth Flame OptimizerJ.Journal of System Simulation,2023,35(10):2170-2181.Integrated Scheduling Simulation Based on Improved Moth Flame OptimizerZhang Tianrui,Niu Huiyuan*,Xie Wei(Sc
4、hool of Mechanical Engineering,Shenyang University,Shenyang 110044,China)Abstract:Aiming at the rising cost of manufacturing enterprises,a mathematical programming model of integrated scheduling of production and transportation is established,and a double adaptive weights for moth flame optimizer(DA
5、WMFO)is proposed.A double adaptive weight mechanism is proposed.The spiral function is used to update the population,which improves the convergence speed and accuracy of the algorithm.The benchmark function is tested by the improved algorithm.The results show that the improved algorithm can converge
6、 quickly and not easily fall into local optimum.Compared with other algorithms,the optimization ability is also improved.Through the simulation experiment on the data set of integrated production and transportation scheduling,it is verified that the improved algorithm is feasible and efficient in so
7、lving such problems.Keywords:job shop scheduling;spiral function;double adaptive weights for moth flame optimizer;production and transportation;integrated scheduling0引言引言随着中国制造2025的公布,我国制造业由“制”到“智”进行转型。生产调度是调度的一个重要方面,已成为制造业快速响应定制化需求的有效途径。企业也开始向按单生产模式(make-to-order mode,MTO)转变。其本质是将生产与分销协同进行,实现协同最优化,
8、使其更科学收稿日期:2023-07-02 修回日期:2023-08-24基金项目:国家自然科学基金面上项目(52075088);辽宁省研究生教育教学改革研究资助项目(LNYJG2022490)第一作者:张天瑞(1985-),男,副教授,博士,研究方向为车间调度和智能算法。E-mail:通讯作者:牛慧媛(1999-),女,硕士生,研究方向为车间调度和智能算法。E-mail:第 35 卷第 10 期2023 年 10 月Vol.35 No.10Oct.2023张天瑞,等:基于改进飞蛾扑火算法的集成调度仿真http:/www.china-高效地提升订单生产的效益,减少企业综合成本。因此,研究生产与运
9、输集成调度更具有实际意义。越来越多的学者关注作业车间调度问题,研究内容主要为动态作业车间、柔性车间调度。在生产调度方面,Caldeira等1提出一种多目标的生产调度优化方法,使其解决降低能耗、最小化最大完工时间的多目标问题。Firat等2主要关注工厂型制造业,研究了一种混合整数线性计划,该模型可以通过订单接受决策来寻找工作负荷相关的规划水平。在运输调度方面,陈魁等3针对考虑运输时间的柔性作业车间调度问题,提出一种小生境粒子群优化算法求解该模型。Hidri等4针对具有运输时间的混合流水车间调度问题,提出两阶段的启发式方法解决此类问题。以上研究可以看出,大多数学者是分开研究生产调度和运输调度的优化
10、,没有把生产和运输阶段联系起来。随着研究的深入,一些学者开始研究考虑生产与运输结合的集成调度。Geismar等5将短期库存的产品特性纳入到生产与运输协调调度中,使得制造和交货的周期最短。Mohammadi等6针对解决具有时间窗的集成生产调度和车辆路线问题,建立了双目标混合整数模型,以达到产品与运输计划的费用和交货时间最小的目的。Gharaei等7研究双代理在集成生产调度和分配问题中的应用,并针对问题提出混合整数线性规划公式求解。Moazami等8针对生产和分销计划的集成问题,提出混合整数线性规划公式,以最大限度减少延误和运输成本为目标来解决集成问题。梁春华等9以多个企业为例,对多个企业和客户进
11、行生产与分配优化问题进行研究,将独立最优和协同最优的方法进行对比,得到更优的结果。刘玲等10构建了以最短完成时间为优化目标的制造车辆运输协调规划的数学模型。霍思云11对不同权重的产品在不同容量平行机上的排序问题进行分析,将生产与运输的集成规划划分为两个子问题进行求解。吴倩云等12以最优的运输效率为目标,建立了一个考虑时间窗和最佳载荷限制的汽车路线分配模式。飞蛾扑火算法(moth flame optimization,MFO)是Mirjalili13提出的一种新型智能优化算法,算法可行性强,目前在解决函数优化14、图像分割15、预测模型16等问题上取得了较好的效果。文献17采用MFO针对预测问题
12、求得高质量解。综上所述,目前国内外针对作业车间和流水车间为基础的调度问题研究已较为成熟,但对于复杂车间环境的研究还需进一步深入。另一方面,在生产和配送环节会根据目标建立相应模型,在分销过程中,由于目标的差异,会形成相应的模式。在制造环节,资源包括原材料、加工设备等。而在运输环节,资源包括运输车辆、成品产出等。各单位在制订规划时,往往会顾及本部门的利益,而忽视其他部门或总体的利益。因此,本文着眼于生产与运输集成调度问题,同时考虑最大完工时间和成本两个优化目标,设计了一种双自适应权重飞蛾扑火算法(double adaptive weights for MFO,DAWMFO)。1问题描述与建模问题描
13、述与建模1.1 问题描述问题描述生产与运输集成调度模型描述:含有g台机器和n个客户,制造商接收n个顾客的订单Dn,顾客分散在各地,厂家接到订单后,向供应商采购原材料,供应商提供多种原材料,一种原材料可以生产出多种产品。如果交货时间超过时间窗限度,则产生罚款费用。本文以运输成本和违反时间窗成本组成的总分配成本最小化为目标,通过合理安排机器上的物品处理顺序,交货路线和车辆的出发时间,以实现成本和最大完工时间的性能达到整体最优的目的。本文针对所建模型,做出以下假设:(1)原材料充足且满足生产需求;(2)厂商租赁车辆的种类和数量已确定;2171第 35 卷第 10 期2023 年 10 月Vol.35
14、 No.10Oct.2023系统仿真学报Journal of System Simulationhttp:/www.china-(3)忽略各工序在机器上加工准备时间和加工装卸时间;(4)假定运送材料的时间记为0;(5)不考虑交通状况和运输中的设施等;(6)按批量生产方式生产同类产品。1.2 数学模型数学模型为建立总成本最小的生产与运输集成调度模型,给出以下符号说明。pi:客户i的加工工序;si:客户i项目的大小;rij:在客户 i 和客户 j 的目的地之间的运输时间;qk:车辆k的最大承载量;li,i:项目交货时间窗;Ck:单位时间车辆k的运输成本;cp:工件p的生产成本;cpt:单位时间工件
15、p的加工成本;tpi:加工工件pi的时间;ce:单位时间内提前罚款成本;ct:单位时间内延误惩罚成本;tEkai:第a次运输成品i的k号车到达最后一位客户的时刻;Ci:客户i成品生成的产品完工时间;Fk:车辆k交付产品的最大完成时间;Di:客户i收到产品时的交货时间;Ei:客户i提前交货时间;Ti:客户i延迟交货时间;oim:如果订单 i 被分配给机器 m 则为 1,否则为0;yik:如果车辆k交付订单i则为1,否则为0;xijm:如果订单i在订单j之前被机器m加工为1,否则为0;zijk:如果订单i先于订单j被车辆k配送交货为1,否则为0。本文以生产成本、运输成本和违反时间窗的惩罚成本组成的
16、,以总分配成本最小化和最小化最大完工时间为优化目标建立模型,其目标函数为minC=cp+ckiNjNkVrijzijk+ceiN 0Ei+ctiN 0Ti(1)min(max(fk+Ci)(2)约束条件(1)订单分配阶段每个订单都被分配给其中一台机器:mKoim=1 iN 0(3)每个订单要么直接先于另一个订单,要么直接接受另一个订单:oim=jNxijm iN 0 ij mK(4)jNxijm=jNxijm iN 0 ij mK(5)最多可将一个订单作为每台机器的第一个作业进行处理:jN 0 x0jm1 mK(6)项目i的完成时间不小于其前身的完成时间加上其处理时间pi:cicj+pi-M(
17、1-xijm)iN 0 jN ij mK(7)(2)物品交付阶段每个物品只能由一辆车交付:kVyik=1 iN 0(8)在每个客户位置只有一辆车到达和离开:y0kyik iN 0 kV(9)jNzijk=jNzijkiN 0 ij kV(10)确保在每辆车的运输负荷不超过车辆的装载能力:iN 0siyikqk kV(11)(3)物品运输阶段保证每辆车交付的物品最长时间不小于该车辆运输的物品的最大完成时间:fkci-M(1-yik)kViN 0(12)2172第 35 卷第 10 期2023 年 10 月Vol.35 No.10Oct.2023张天瑞,等:基于改进飞蛾扑火算法的集成调度仿真htt
18、p:/www.china-确保每辆车的出发时间不小于其车辆运输物品的最长时间:dkfk kV(13)车辆k每个项目交付时间不小于车辆出发时间dk与上订单i目的地和工厂之间的行驶时间r0i的和:Di dk+r0i-M(1-z0ik)i N 0 k V(14)计算了提前时间和延迟时间:Eili-Di iN(15)CiEi Ti0 iN(16)决策变量的结构域:yik oim xijm zijk0 1 kVmK i jN ij(17)dk fk0 kV(18)2双自适应权重飞蛾扑火算法双自适应权重飞蛾扑火算法MFO是一种元启发式算法,在搜索空间中寻找最优的个体,同时保留最优的位置,分配到火焰上,使飞
19、蛾朝最佳的火焰靠近,从而达到全局最优。搜索空间中火焰为F=f11f12f1df21f22f2dfn1fn2fnd(19)飞蛾运动轨迹的螺旋函数:S(MiFj)=|Fj-Mi|ebtcos(2t)+Fj(20)式中:Mi,i=1,2,n为第i个飞蛾的位置,其中,Mi代表机器加工的顺序,n代表种群规模;Fj为第j个火焰的位置,它的值即适应度函数值,也就是本文所求的工序在机器上的完工时间;|Fj-Mi|为从飞蛾到火焰的距离,代表机器加工的最优方式;b为对数螺旋常数;t-1 1为距离参数。MFO在不同时期没有特定的搜索策略,使飞蛾在寻找最优火焰位置时易陷入局部最优,因此,需要提高全局搜索能力。本文提出
20、一种双自适应权重机制,可以避免不必要的局部搜索和全局搜索。当使用螺旋函数更新飞蛾种群时,根据不同的搜索周期,给予更临界位置更高的权重,从而提高改进算法的收敛速度和精度。2.1 双自适应权重机制双自适应权重机制原MFO算法中重要的一部分是飞蛾的螺旋函数S,由飞蛾在飞行中建造,它反映了飞蛾靠近火的过程。改进算法针对不同阶段的收敛性,在原算法中增加了w1和w2权重,使其在迭代过程中,按照该方法找到火焰的最优位置,即加工产品最大完工时间的最小值。w1=(1-K T)1-tan(rand-0.5)ST(21)w2=(2-2K T)1-tan(rand-0.5)ST(22)式中:K 为当前迭代次数;T 为
21、最大迭代次数;rand生成0,1中均匀随机数。在复杂问题中,算法必须显示更多的渗透行为,随机元素通常会带来更多的随机搜索模式,以便找到工序完工时间的最优解。2.2 双自适应权重飞蛾扑火算法的模型双自适应权重飞蛾扑火算法的模型当 MFO 算法迭代更新时,判断当前飞蛾位置i与火焰数nf lame之间的关系。当小于nf lame时,Fj式(20)将对第一个飞蛾 i 的适应度值排序进行迭代;当i数值大于nf lame时,式(20)将在适应度值排序中选取第B个飞蛾进行迭代。用于迭代的螺旋函数是不变的。双自适应权重将在这2种情况下给出两部分不同的权重,使迭代搜索更加准确。当i nf lame时,螺旋函数中
22、双权重w1和w2的位置为S(Mi Fj)=|Fj-Mi|ebtcos(2t)+w2Fj(23)S(Mi Fj)=w1|Fj-Mi|ebtcos(2t)+Fj(24)当i nf lame时,螺旋函数中双权重w1和w2的位置为S(Mi Fj)=w2|Fj-Mi|ebtcos(2t)+Fj(25)S(Mi Fj)=|Fj-Mi|ebtcos(2t)+w1Fj(26)2173第 35 卷第 10 期2023 年 10 月Vol.35 No.10Oct.2023系统仿真学报Journal of System Simulationhttp:/www.china-2.3 双自适应权重飞蛾扑火算法流程双自适应
23、权重飞蛾扑火算法流程本文对原算法做了相应的策略改进,引入了双自适应权重w1、w2,分情况地讨论了如何更新飞蛾S的螺旋函数位置更新,根据不同的情况向目标函数中加入2个权重的位置,以此解决前期容易造成局部最优和后期不必要的全局最优问题,增加寻找最优解可能性,其具体改进算法流程如图1所示,步骤如下。初始化种群Mi,i=1,2,n,用飞蛾位置Mi表示机器加工顺序,最大迭代次数T参数,种群规模n(机器数量),维数d(产品任务的机器分配);While lT 根据nf lame公式更新火焰位置;计算每个飞蛾的适应度值OM;利用式(19)计算火焰的数量(产品完工时间集合);若当前迭代次数k=1,则根据OF=s
24、ort(OM),F=sort(M)更新火焰种群;否则根据OF=sort(Mk-1,OMk),F=sort(Mk-1,Mk)更新火焰种群;记录第一个火焰最优位置(产品最大完工时间最小值);for i=1:n 更新b、t;若飞蛾i nf lame,则根据式(23)和(24)更新螺旋函数;否则根据式(25),(26)更新飞蛾螺旋函数;判断飞蛾位置是否超出了搜索空间的上下限(调度问题的可行解范围);若飞蛾跳出边界线,则重新返回初始化位置;end forend While输出最优解,即得到产品最大完工时间的最小值。3仿真实验仿真实验本文采用经典测试函数和生产与运输集成调度实例进行仿真实验测试算法的有效性
25、。所有算法均在MATLAB2018a中编码,并在Intel Core i7、1.80 GHz、8 GB、Windows10操作系统的计算机上运行。i n开始初始化M,N,T,t,nf lame等参数在搜索空间中随机生成飞蛾位置,评估飞蛾对应的适应度更新火焰搜索选取适应度值更优的空间位置更新火焰计算自适应权重w1,w2j d更新b,ti nf lameK/T 0.5K/T 0.5更新飞蛾位置式(23)更新飞蛾位置式(24)更新飞蛾位置式(25)更新飞蛾位置式(26)K TReturn F best结束否是否是否否是是否是否是图1 双自适应权重飞蛾扑火算法流程图Fig.1 Flowchart of
- 配套讲稿:
如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。