1、考虑运输时间的分布式绿色柔性作业车间调度协同群智能优化王凌*,王晶晶清华大学自动化系,北京 100084*E-mail:收稿日期:2021-08-06;接受日期:2021-09-06;网络版发表日期:2022-04-08国家自然科学基金(批准号:61873328)和国家杰出青年科学基金(编号:61525304)资助项目摘要当今环境问题日益严峻,绿色制造备受关注.同时,全球化的发展令分布式制造模式日趋普遍.分布式绿色调度研究旨在推进企业在分布式制造模式下经济指标和绿色指标的协同优化.由于生产过程中工件在不同机器间的运输时间难以忽略,因此本文研究考虑运输时间的分布式绿色柔性作业车间调度问题,以最小
2、化最大完工时间和加工过程总能耗为优化目标,提出一种协同群智能算法.首先,将问题分解为工序排序和机器分配两个子问题,设计多种针对两子问题的搜索操作;其次,采用多种规则协同初始化种群;进而,对种群进行分层协同优化,即基于信息交互的工序排序搜索和基于Q-learning的机器分配搜索,并采用基于分解的解替换原则平衡种群的收敛性和多样性;最后,对精英解进行局部增强搜索,并对所得非支配解执行能耗调整.通过基于不同数据集的仿真实验,验证了算法各环节的有效性,同时与现有算法的对比结果也表明了所提算法能够更有效求解考虑运输时间的分布式绿色柔性作业车间调度问题.关键词分布式制造,绿色调度,柔性作业车间调度,协同
3、群智能优化1引言为应对全球范围内日益严重的环境问题,现代化生产对绿色制造模式的关注日趋加强1.随着不可再生能源的快速消耗,能源价格不断提高,节能成为绿色制造的关键内容2.然而,仅依靠技术设备和设计水平实现节能增效的成本高且提升空间有限.与之相比,高效的调度优化方法能够以低成本协同优化企业的经济指标和能耗指标,实现节能、增效、减排、降耗3,因此受到学者的广泛关注和研究.近些年关于绿色车间调度的研究越来越多,面向的车间类型主要包括:单机调度、流水线调度、作业车间调度和柔性车间调度.针对单机调度问题,Mou-zon和Yildirim4提出了一种节能调度框架优化总能耗和总拖期.Liu等人5则研究了一种
4、优化完工时间和能耗的决策模型.Zhang等人6,7分别针对单工厂和多工厂流水线调度问题,提出在实时电价下的能效调度方法.针对混合流水线调度问题,Luo等人8提出了一种蚁群算法以提高生产效率并优化分时电价下的电费.针对分布式流水线调度问题,Wang等人9提出了一种引用格式:王凌,王晶晶.考虑运输时间的分布式绿色柔性作业车间调度协同群智能优化.中国科学:技术科学,2023,53:243257Wang L,Wang J J.A cooperative memetic algorithm for the distributed green flexible job shop with transpor
5、tation time(in Chinese).Sci Sin Tech,2023,53:243257,doi:10.1360/SST-2021-0355 2022 中国科学杂志社中国科学:技术科学2023 年第 53 卷第 2 期:243 257SCIENTIA SINICA T群体智能激发汇聚及应用专辑论 文基于知识的协同优化算法最小化最大完工时间(make-span)和总能耗.针对分布式焊接工厂中的流水线能效调度问题,Wang等人10提出一种多目标鲸鱼群算法.针对作业车间能效调度问题,Masmoudi等人11和May等人12分别提出一种数学模型和遗传算法优化.针对柔性作业车间调度问题(f
6、lexible job shop schedulingproblem,FJSP),Yin等人13提出一种数学模型和低碳调度方法优化生产效率、能耗和噪音指标.Gong等人14则考虑在动态电价的情况下,优化能效、完工时间和劳动力成本等指标.由于绿色车间调度在定义绿色指标的同时,需平衡经济指标和绿色指标,故相比传统调度更复杂,求解难度更大.现有的绿色车间调度研究主要考虑能耗、碳排放等指标,在调度方法上大多沿用经典算法框架,采用权重法转换为单目标或通过Pareto支配关系寻求非支配解.通过多操作、多策略、多目标等的协同模式,结合群智能与问题特性的搜索操作,实现经济指标与绿色指标协同优化的高效算法仍有待
7、研究.面对日益激烈的市场竞争和频繁多变的产品需求,柔性制造成为众多企业的选择15.在此背景下的柔性作业车间调度问题取得众多研究成果1620.与此同时,全球化的生产背景下,分布式制造成为一种现代化制造模式趋势21.分布式制造通过不同企业或工厂间的资源共享及合理的分工与协作,能够充分利用资源,有效降低成本和管理风险22.分布式制造背景下的分布式调度能够通过合理的工件分配和操作排序优化特定的调度目标.因此,结合分布式制造模式和FJSP的分布式FJSP(distributed FJSP,DFJSP)受到学者的广泛关注与研究.区别于FJSP的单一生产车间,DFJSP具有多个制造工厂,称为柔性加工单元(f
8、lexiblemanufacturing unit,FMU).每个FUM均为一个柔性作业车间,多个FMU需协同来完成给定的生产任务.此外,各FMU可能具有不同数量及不同加工能力的机器,使其加工容量及加工效率各不相同.因此,DFJSP比FJSP更加复杂,具有三个不同的子问题,包括工件到工厂的分配、工序到机器的分配、工序的排序问题.De Giovanni等人23提出一种改进的遗传算法求解DFJSP以最小化makespan.Meng等人24针对DFJSP提出多种混合整数规划和约束模型.Wu等人25则研究多种针对DFJSP的编码方法,并提出一种仅表示工序顺序的编码方法,通过工厂和机器分配规则解码为调度
9、方案.Ziaee26提出了一种快速启发式构造方法.Wu等人27针对带装配环节的DFJSP提出一种改进的差分进化算法.已有的DFJSP研究大多考虑同构工厂的生产环境,将完工时间作为性能指标,而考虑异构工厂环境和绿色指标的优化更具现实意义.大多实际生产制造过程中,工件在机器间需要通过起重机或AGV搬运28.因此,考虑运输时间的分布式绿色柔性作业车间调度(distributed green FJSP withtransportation time,DGFJSPT)研究更具应用价值.Du等人29针对DGFJSPT提出一种混合分布估计算法(es-timation of distribution algo
10、rithm and variable neighbor-hood search,EDA-VNS)优化makespan和加工过程总能耗.进一步考虑工厂或生产线间的交互,Luo等人30则针对允许工件在工厂间转换和运输的情况,提出一种混合群智能算法(effective memetic algorithm,EMA),同时优化makespan、最大工厂负荷以及总能耗.综上所示,DGFJSPT的研究还相对较少,大多算法是在经典进化算法框架下对已有遗传算法算子进行改进.此外,由于分布式制造环境带来的大规模特性和多子问题耦合特性,以及绿色调度的多目标优化特性,传统算法具有收敛缓慢和缺乏多样性等不足.源于自然界
11、和社会系统广泛的协同现象,协同群智能算法在种群进化搜索结合局部增强搜索的框架中,加入通过一定的机制和策略的多个对象协同搜索,有望在复杂调度问题上取得更好的效果31.区别于传统进化算法,挖掘问题知识特性,与群体智能有机融合,协同多种搜索机制和策略以平衡全局勘探和局部开发是提升算法性能的关键.目前,协同群智能优化已在诸多问题上取得了良好的效果9,31.基于此动机,本文针对考虑运输时间的分布式绿色柔性作业车间调度问题,提出一种协同群智能算法(cooperative memetic algorithm,CMA),通过多操作协同、基于信息交互和Q-learning的双层协同优化、局部增强搜索和能耗调整策
12、略,获得优质调度方案集,协同优化最大完工时间和总能耗指标.2分布式绿色柔性作业车间调度问题2.1多目标优化问题多目标优化问题32(multi-objective optimizationproblem,MOP)一般可以描述为王凌等:考虑运输时间的分布式绿色柔性作业车间调度协同群智能优化244()fff xxxxMinimize()=(),(),(1)p1T其中,f1,f2,.,fp是p个冲突的优化目标,为解向量的非空集合.在MOP中,通常采用支配性判断两个解的优劣.对于两个解a和b,若fflpab()(),1,2,ll且fflpab()0,0,(21)j ik r,xy0,1,0,1,(22)
13、j i k rj i k k,其中,式(2)为优化目标函数;式(3)(5)表示每道工序仅能同时在一台机器上加工且一台机器同时仅能加工一道工序;式(6)(11)表示每道工序必须分配到某一可行表 1DGFJSPT示例中4个工件的各工序加工时间Table 1The processing times of every operation of 4 workpieces inDGFJSPT工件操作F1F2M1,1M1,2M2,1M2,2M2,3J1O1,14,55,6O1,24,75,57,5J2O2,16,55,66,7O2,23,65,66,5O2,34,66,7J3O3,14,66,57,5O3,
14、25,64,86,7J4O4,14,65,73,56,7O4,24,65,67,56,6表 2DGFJSPT示例中各机器间的运输时间Table 2The transportation times between the machines in DGFJSPT工厂机器F1F2M1,1M1,2M2,1M2,2M2,3F1M1,1022.73.52.5M1,220354F2M2,12.73021M2,23.55201.5M2,32.5411.50dk234.554图 1(网络版彩图)DGFJSPT甘特图Figure 1(Color online)Gantt chart for the DGFJSPT
15、.王凌等:考虑运输时间的分布式绿色柔性作业车间调度协同群智能优化246机器上加工且工件必须按照顺序加工;式(12)(15)表示各工序的完工时间包括加工时间和机器间的运输时间;式(16)表示最大完工时间为所有工件的完工并运输到库房/顾客的时间;式(17)(19)分别为机器加工时、空闲时、运输过程的总能耗;式(20)为总能耗;式(21)和(22)为决策变量取值范围.3协同群智能算法3.1编码和解码DGFJSPT需确定工件到工厂的分配、工序在机器上的分配以及工序的排序问题,由于工件可在FMU间运输,可以将工厂分配和机器分配合并为一个子问题,即所有工厂的可用机器的分配问题.故采用分别表示工序排序(op
16、eration sequence,OS)和加工设备选择(machine assignment,MA)的两个向量(OSV,MAV)对解进行编码,如图2所示.OSV的每个元素为工件号,第p次出现表示该工件的第p道工序,MAV的每个元素对应于OSV中相应位置工序的加工机器.为保证解的可行性,MAV中每个元素的取值必须从对应的OSV工序的可加工机器集合中选取.为得到解的最大完工时间和总能耗指标,需将编码解进行解码为调度方案.将OSV中的工件工序按顺序安排到对应的MAV中的机器上,并按最早可加工时间安排,以得到唯一调度方案.基于第2.3节给出的例子,按照图2的编码解通过上述解码过程即可得到图1的调度方案.3.2搜索算子为提高搜索效率和解的质量,分别针对编码中的操作排序和机器分配设计多种有效搜索操作,并在算法中采用合理的机制和策略协同使用以下操作.3.2.1针对OS的操作设计为增加OS序列的多样性,采用交叉操作POX33保留解的部分信息,并产生新的工序排列.具体操作如下:对当前解x,选择一个与其交叉的解y;随机选择若干待保留工件Jr;新解x继承x中属于Jr的工序,其余工件按照解y中OSV的顺序依次
