1.武汉理工大学机电工程学院，武汉，4300702.数字制造湖北省重点实验室，武汉，430070
关键词：绿色柔性作业车间调度；多目标优化；环境污染；人工蜂群算法
减少环境污染，实现绿色制造，是现代制造业迫切需要解决的问题之一[1]。生产调度是制造系统的一个重要环节，高效的调度方法能有效地改善制造过程中的环境污染情况，达到节能减排的效果[2]。
多目标柔性作业车间调度问题(multi-objectiveflexiblejob-shopschedulingproblem,MFJSP)是复杂的NP-hard问题，相较于基础的车间调度问题更符合实际情况，求解难度也相对较高。MFJSP现有的研究主要集中在智能优化算法的求解上，XU等[8]提出了一种有效的蛙跳算法用于解决多目标柔性作业车间的调度优化问题，同时基于已知问题的数值模拟和比较验证了所提算法的有效性；CHIANG等[9]讨论了以最小化生产周期、总工作量和最大工作量为目标的MFJSP，并提出了一种多目标进化算法；LIU等[10]介绍了一种混合元启发式变邻域粒子群优化算法用于解决MFJSP；WANG等[11]为避免在解决MFJSP时出现的过早收敛和局部搜索能力较差等缺陷，提出了一种基于Pareto的分布估计算法。
本文提出的MGFJSP主要研究n个工件在m台机器上加工，每一台机器的加工速度可供选择，每个工件均有多道工序，同一工件的各道工序的先后关系不能发生改变。同时，还需要满足以下约束：①每道工序在同一时刻只能被一台机器加工；②每道工序均可在一组相容机器的任意一台机器上加工；③每台机器在加工工件时，加工速度一旦确定就不能进行随意变更；④每一道工序的加工过程一旦开始，便不可以被中断。
表1符号含义
Tab.1Themeaningofsymbols
将生产过程中产生的废弃物、噪声及总碳排放量的综合影响值定义为总环境属性值，并将总环境属性值的大小作为评价环境污染程度的依据。由此，目标函数可表示为
f=min(Cmax,A)
(1)
约束条件为
Cmax=max(Fini)i=1,2,…,n
(2)
人工蜂群(ABC)算法是KARABOGA[14]提出的一种受生物行为启发的优化算法，该算法主要通过模拟蜜蜂的觅食来解决实际问题。由于ABC算法具有搜索速度快、精度高、鲁棒性强等优点，故已在车间调度领域得到了广泛的应用。但是，ABC算法只适用于求解连续型问题，而MGFJSP是离散型问题，ABC算法很难对其进行有效的求解，因此，本文提出了一种改进的人工蜂群(IABC)算法，其整体流程如下。
(1)进行种群初始化操作。通过计算种群中个体的拥挤距离和种群中非支配Pareto解的数量来更新档案集。假设N为当前迭代次数，G为最大迭代次数，令N=0。
(2)若N (3)雇佣蜂操作。通过拥挤距离和种群中非支配Pareto解的数量来更新档案集。 (4)跟随蜂操作。通过拥挤距离和种群中非支配Pareto解的数量来更新档案集，N←N+1。 (5)判断是否有需要放弃的蜜源，若有，则转至步骤(6)；否则，转至步骤(2)。 (6)侦查蜂操作。判断当前迭代次数N是否超过最大迭代次数G,若是，则转至步骤(7)；否则，转至步骤(2)。 (7)输出档案集中的内容。 根据MGFJSP问题特性，本文设计了一种三维向量编码的方法，即每个可行解均由3个部分组成，分别是工序编码向量(OV)、机器编码向量(MV)和速度编码向量(SV)，3个向量的长度均等于所有工件的工序数之和。 可行解的编码方式如图1所示。OV中用每个工件对应的索引号来表示该工件的工序，该索引号第几次出现就代表是该工件中的第几道工序；MV中对应的索引号表示对应工序所选择的机器序号；同理，SV中对应的索引号表示对应工序所选择的加工速度挡位。 图1编码示意图 Fig.1Codingdiagram 为了得到具体的调度方案，还需要对可行解的编码进行解码操作，本文采用左移策略，即从左至右依次安排OV中的工序，在满足约束的前提下使工序尽可能早地被安排加工。 本文在IABC算法中采用一个固定容量的档案集用于维护搜索过程中找到的非支配解的多样性[15]，通过对非支配解进行拥挤距离大小的排序来确定档案集中的内容。个体拥挤距离的计算步骤如下[16]：①按照每个目标函数值从大到小的顺序对种群进行排序；②选出目标函数值最小的个体和目标函数值最大的个体，将这两个个体的距离设置为无穷大；③将其他解的距离定义为其相邻两个解的函数值的归一化差值；④将每个个体在各个目标下的距离值的总和作为其拥挤距离；⑤按照拥挤距离从小到大的顺序对种群中的所有个体进行重新排序；⑥依次向档案集中添加重新排序后的个体，若个体数量大于档案集的容量，那么当档案集被填满时则不再向档案集中添加个体。 采用交叉与变异相结合的方法对雇佣蜂的搜索操作进行了改进。首先，从种群中选出一个父代X1，同时随机选出另外一个父代X2(X2要求不同于X1)用于与父代X1的OV向量进行交叉操作，本文选用已广泛使用的POX交叉方法[17]，其具体操作过程如下：①将工件序号随机地分配到两个非空且互补的集合Q1和Q2中；②从父代X1中选出包含在集合Q1中的工件序号，保持各工件序号的位置不变并复制到子代X′中；③从父代X2中选出包含在集合Q2中的工件序号，并将选出的工件序号按顺序依次插入到子代X′的空缺处；④按照步骤②和步骤③的操作，从父代X1中选出包含在集合Q2中的工件序号，保持各工件序号的位置不变并复制到子代X″中，从父代X2中选出包含在集合Q1中的工件序号，并将选出的工件序号按顺序插入到子代X″的空缺处；⑤从子代X′和X″中选出较优的个体作为交叉后的子代。 图2为利用POX交叉方式生成的一个子代X′的示意图。 图2POX交叉操作示意图 Fig.2DiagramofPOXcrossoperation 若进行POX交叉操作后子代优于父代X1，则用该子代代替父代X1，若子代并不优于父代，则在该子代的基础上针对MV向量进行变异操作，即在MV向量中随机选择一个位置，并选择一个合理的机器序号进行替换，同时为该机器随机选择合理的加工速度挡位，进而得到新的子代个体。图3给出了MV向量的变异操作示意图。 注：“*”表示该序号是不合理序号。 图3MV向量变异操作示意图 Fig.3DiagramoftheMVvectorvariationoperation 将进行MV向量变异操作后产生的新子代与父代进行比较，若产生的新子代更优，则用该子代代替父代，否则在该子代的基础上针对SV向量进行变异操作，即在SV向量中随机选择一个位置并对其速度挡位进行合理的替换，若产生的子代更优，则用该子代代替父代。 为了提高算法的局部搜索能力，本文引入动态邻域搜索(dynamicneighborhoodsearch,DNS)机制来改进跟随蜂的搜索操作。共包含4种邻域结构：交换邻域结构、插入邻域结构、分配邻域结构和变异邻域结构。 交换邻域结构是将个体OV向量中任意指定的两个位置进行交换得到新的个体；插入邻域结构是指定个体OV向量中的某一元素插入到该OV向量的任意指定位置；分配邻域结构是给个体的指定工序随机分配合理的机器和速度挡位；变异邻域结构采用轮盘赌选择的方式，以一定的概率决定此时对指定工序进行仅机器序号的合理变异还是同时进行机器和速度挡位的合理变异。 基于DNS改进跟随蜂的搜索操作过程如下：在每一次邻域结构操作后都会进行新个体和原始个体的比较，若新个体优于原始个体，则新个体取代原始个体，且无需进行后续的邻域结构操作；若未得到优于原始个体的新个体，则需要进行后续的邻域结构操作，以得到更优的个体，如图4所示。 侦查蜂阶段选用的是产生新食物源替换策略，而不是传统的随机挑选食物源，即挑选出一个更新次数超过规定限制次数最多的个体，并将该个体进行替换，替换的方法是从档案集中随机选择一个个体，并对该个体进行替换操作。 图4跟随蜂搜索操作流程图 Fig.4Thesearchoperationflowchartoffollowbee 表2测试算例数据 Tab.2Dataoftestinginstances 算法的运行环境为:2.50GHz，6GBRAM，Windows7，64位操作系统的个人计算机，编程语言为C#。 影响IABC算法性能的参数主要有3个，分别为：种群规模PS，最大迭代次数G，档案集容量SA。为寻求IABC算法较优的运行参数组合，本文采用正交试验法对参数进行了优化配置，因素水平表见表3。 由于正交表中没有完全对应的三因素五水平的标准正交表，因此选用六因素五水平L25(56)的标准正交表来设计本文试验，如表4所示。需要说明的是，L25(56)标准正交表的纵列数比试验因素的个数多，则表4中的第1～3列对应试验的3个因素，并将第4～6列置空。同时为简化表4，故表4中只列出了本试验所对应的3个因素列。其中，和分别表示当前因素在水平1～5下运行结果的平均值 表3因素水平表 Tab.3Factorleveltable 因数种群规模PS最大迭代次数G档案集容量SA水平1500305024002540330020304200152051001010 本文选用算例MK05作为正交试验的测试算例，算法均在每种参数组合下独立运行30次，可得到各参数组合下的非支配解集，同时将每种参数组合下得到的非支配解集聚集起来即可得到新的非支配解集，此处称为参考集，将各参数组合下得到的非支配解集占参考集中的数量作为实验结果，如表4所示。 为了更加直观地反映表4中因素与水平之间的内在规律，以每个因素的实际水平取值顺序绘制出相应的趋势图，分别见图5～图7。可以看出，当PS=500，G=10，SA=20时，算法的实验效果最佳。 为进一步验证算法的有效性，本文分别选择多目标粒子群优化(multi-objectiveparticleswarmoptimization,MOPSO)算法[19]、混合差分进化(hybriddifferentialevolution,HDE)算法[20]和改进的非支配排序遗传算法(non-dominatedsortinggenetic 表4正交试验表 Tab.4Orthogonaltable 试验号种群规模PS最大迭代次数G档案集容量SA实验结果150030500.55703250025400.50867350020300.49210450015200.51634550010100.40829640030400.49013740025300.48021840020200.51487940015100.409141040010500.449871130030300.432121230025200.417201330020100.403211430015500.450691530010400.490271620030200.408171720025100.401271820020500.386951920015400.423652020010300.425712110030100.309272210025500.370682310020400.390212410015300.416792510010200.47237Ⅰ-0.4964860.4393440.443044Ⅱ-0.4688440.4356060.460586Ⅲ-0.4386980.4374680.449386Ⅳ-0.4091500.4433220.465790Ⅴ-0.3918640.4493020.386236极差0.1046220.0136960.079554最优方案水平1水平5水平4 图5种群规模因素水平趋势图 Fig.5Factorleveltrenddiagramofpopulationsize 图6最大迭代次数因素水平趋势图 Fig.6Factorleveltrenddiagramofmaximumnumberofiteration 图7档案集容量因素水平趋势图 Fig.7Factorleveltrenddiagramofmaximumnumberofiteration algorithm-Ⅱ,NSGA-Ⅱ)[21]来开展对比实验研究，以反世代距离(IGD)和错误率(ER)为评价指标，IGD和ER的值越小，表明算法的性能越优。 表5算法对比测试结果 Tab.5Theexperimentalresultsofalgorithmcomparison 算例IABCMOPSOHDENSGA-ⅡIGD值ER值IGD值ER值IGD值ER值IGD值ER值MK010.00280.006613.13090.975022.02271.000018.06770.9243MK020.02530.01335.11380.968110.18400.97868.62021.0000MK030034.08411.000055.69061.000042.24121.0000MK040.00120.000811.21791.000019.84700.996316.58640.8964MK050.00080.000416.35671.000026.84231.00009.64530.9863MK060.00130.000716.34741.000025.58831.000021.62690.9654MK070046.59111.000079.61071.000066.16861.0000MK080.00250.002343.00601.000055.25220.926546.83710.8975MK090080.00921.000083.62730.963280.62420.9785MK100.00180.001945.06191.000059.44441.000051.15920.7623 图84种算法的IGD对比结果 Fig.8ThecomparisonresultsofIGDforfouralgorithms 图94种算法的ER对比结果 Fig.9ThecomparisonresultsofERforfouralgorithm (2)针对MGFJSP问题特点，提出了一种改进的人工蜂群算法，并通过编码和解码方案设计、混合初始化策略、多种交叉和变异方法、动态邻域搜索等操作来提高所提算法的寻优能力。 (3)基于标准算例进行了扩展，并将所提算法与常用算法进行了对比实验，有效地验证了所提算法改进机理的合理性和解决MGFJSP问题的有效性。 参考文献： [1]刘飞,曹华军,何乃军.绿色制造的研究现状与发展趋势[J].中国机械工程,2000,11(1):105-110. LIUFei,CAOHuajun,HENaijun.OnState-of-the-artofGreenManufacturing[J].ChinaMechanicalEngineering,2000,11(1):105-110. [2]王凌,王晶晶,吴楚格.绿色车间调度优化研究进展[J].控制与决策,2018,33(3):385-391. WANGLing,WANGJingjing,WUChuge.AdvancesinGreenShopSchedulingandOptimization[J].ControlandDecision,2018,33(3):385-391. [3]潘全科,王文宏,朱剑英.面向绿色制造的一类模糊调度模型及其算法[J].中国机械工程,2006,17(13):1371-1374. PANGQuanke,WANGWenhong,ZHUJianying.Decision-makingModelforJobShopSchedulingwithFuzzyProcessingParametersinGreenManufacturing[J].ChinaMechanicalEngineering,2006,17(13):1371-1374. [4]MANSOURISA,AKTASE,BESIKCIU.GreenSchedulingofaTwo-machineFlowshop:Trade-offbetweenMakespanandEnergyConsumption[J].EuropeanJournalofOperationalResearch,2016,248(3):772-788. [5]蒋增强,左乐.低碳策略下的多目标柔性作业车间调度[J].计算机集成制造系统,2015,21(4):1023-1031. JIANGZengqiang,ZUOLe.Multi-objectiveFlexibleJob-shopSchedulingBasedonLow-carbonStrategy[J].ComputerIntegratedManufacturingSystems,2015,21(4):1023-1031. [6]刘清涛,蔡宗琰,刘晓婷,等.一种面向绿色制造的多目标车间调度方法[J].长安大学学报(自然科学版),2011,31(2):106-110. LIUQingtao,CAIZongyan,LIUXiaoting,etal.Multi-objectiveOptimizationforJobShopSchedulinginGreenManufacturing[J].JournalofChang’anUniversity(NaturalScience),2011,31(2):106-110. [7]齐晓宁,汪永超,贾婧,等.基于遗传算法的面向绿色制造的车间调度优化[J].组合机床与自动化加工技术,2012(10):16-18. QIXiaoning,WANGYongchao,JIAJing,etal.TheSchedulingofMachineforGreenManufacturingBasedonGeneticAlgorithm[J].ModularMachineTool&AutomaticManufacturingTechnique,2012(10):16-18. [8]XUY,WANGL,WANGS.AnEffectiveShuffledFrog-leapingAlgorithmfortheFlexibleJob-shopSchedulingProblem[C]∥2013IEEESymposiumonComputationalIntelligenceinControlandAutomation(CICA).Singapore,2013:128-134. [9]CHIANGTC,LINHJ.ASimpleandEffectiveEvolutionaryAlgorithmforMulti-objectiveFlexibleJobShopScheduling[J].InternationalJournalofProductionEconomics,2013,141(1):87-98. [10]LIUH,ABRAHAMA,GROSANC.ANovelVariableNeighborhoodParticleSwarmOptimizationforMulti-objectiveFlexibleJob-shopSchedulingProblems[C]∥2ndInternationalConferenceonDigitalInformationManagement.Lyon:IEEE,2007:138-145. [11]WANGL,WANGS,LIUM.APareto-basedEstimationofDistributionAlgorithmfortheMulti-objectiveFlexibleJob-shopSchedulingProblem[J].InternationalJournalofProductionResearch,2013,51(12):3574-3592. [12]雷德明.基于新型教学优化算法的低碳柔性作业车间调度[J].控制与决策,2017,32(9):1621-1627. LEIDeming.NovelTeaching-learning-basedOptimizationAlgorithmforLowCarbonSchedulingofFlexibleJobShop[J].ControlandDecision,2017,32(9):1621-1627. [13]LUC,GAOL,LIXY,etal.AMulti-objectiveApproachtoWeldingShopSchedulingforMakespan,NoisePollutionandEnergyConsumption[J].JournalofCleanerProduction,2018,196:773-787. [14]KARABOGAD.AnIdeaBasedonHoneyBeeSwarmforNumericalOptimization[R].Kayseri:ErciyesUniversity,2005. [15]ZOUW,ZHUY,CHENH,etal.SolvingMulti-objectiveOptimizationProblemsUsingArtificialBeeColonyAlgorithm[J].DiscretedynamicsinNatureandSociety,2011(11):1-37. [16]XIANGY,ZHOUY,LIUH.AnElitismBasedMulti-objectiveArtificialBeeColonyAlgorithm[J].EuropeanJournalofOperationalResearch,2015,245(1):168-193. [17]张国辉,高亮,李培根，等.改进遗传算法求解柔性作业车间调度问题[J].机械工程学报,2009,45(7):145-151. ZHANGGuohui,GAOLiang,LIPeigen,etal.ImprovedGeneticAlgorithmfortheFlexibleJob-shopSchedulingProblem[J].JournalofMechanicalEngineering,2009,45(7):145-151. [18]BRANDIMARTEP.RoutingandSchedulinginaFlexibleJobShopbyTabusearch[J].AnnalsofOperationsResearch,1993,41(3):157-183. [19]SINGHMR,SINGHM,MAHAPATRASS,etal.ParticleSwarmOptimizationAlgorithmEmbeddedwithMaximumDeviationTheoryforSolvingMulti-objectiveFlexibleJobShopSchedulingProblem[J].TheInternationalJournalofAdvancedManufacturingTechnology,2016,85(9/12):2353-2366. [20]ZHANGR,SONGS,WUC.AHybridDifferentialEvolutionAlgorithmforJobShopSchedulingProblemswithExpectedTotalTardinessCriterion[J].AppliedSoftComputing,2013,13(3):1448-1458. [21]陈辅斌,李忠学,杨喜娟.基于改进NSGA2算法的多目标柔性作业车间调度[J].工业工程,2018,21(2):55-61. CHENFubin,LIZhongxue,YANGXijuan.Multi-objectiveFlexibleJobShopSchedulingBasedonImprovedNSGA2Algorithm[J].IndustrialEngineeringJournal,2018,21(2):55-61. LIYibing1,2HUANGWeixing1WURui1 1.SchoolofMechanicalandElectronicEngineering,WuhanUniversityofTechnology,Wuhan,4300702.HubeiKeyLaboratoryofDigitalManufacturing,WuhanUniversityofTechnology,Wuhan,430070 Abstract:Aimingatthecharacteristicsofmulti-objectivegreenflexiblejob-shopschedulingproblem(MGFJSP),threeindicatorsofcarbonemissions,noisesandwasteswereproposedtoevaluatethedegreeofenvironmentalpollutioncomprehensively.AMGFJSPmodelwasestablishedwiththeoptimizationgoalsofminimizingthemakespanandthedegreeofenvironmentalpollution.AndtheimprovedABCalgorithmwasproposedtosolvethismodel.Thespecificimprovementsofalgorithmincluded:athree-dimensionalvectorcodingschemneandthecorrespondingdecodingschemeweredesigned,aneffectivedynamicneighborhoodsearchoperationwasintroducedtoimprovethelocalsearchabilityofthealgorithminthefollowbeesearchstage,andastrategyforgeneratingnewfoodsourceswasproposedtoincreasethediversityofthepopulationinthebeedetectionstage.Finally,theexperimentalstudyandalgorithmcomparisonwerecarriedouttoverifythevalidityoftheestablishedmodelandtheproposedalgorithm. Keywords:greenflexiblejob-shopscheduling;multi-objectiveoptimization;environmentalpollution;artificialbeecolony(ABC)algorithm 中图分类号：TP18 DOI：10.3969/j.issn.1004-132X.2020.11.011 开放科学(资源服务)标识码(OSID)： 收稿日期：2019-02-20 基金项目：国家自然科学基金资助项目(51705384，51875430) (编辑胡佳慧) 作者简介：李益兵，男，1978年生，教授。研究方向为车间调度与优化算法、机械设备故障诊断。出版专著1部，发表论文20余篇。E-mail：ahlyb@whut.edu.cn。吴锐(通信作者)，男，1989年生，博士研究生。研究方向为车间调度及优化算法。发表论文5篇。E-mail：wurui@whut.edu.cn。