基于改进变邻域NSGA-II的绿色跨单元调度问题.pdf

计算机时代 2023年 第9期0 引言单元制造系统服务于多品种、小批量的制造业企业，区别于传统生产车间，单元制造系统必须考虑运输对于生产过程的影响。于是跨单元调度问题(Inter Cell Scheduling Problem,ICSP)产生。有关的研究从各个角度解决ICSP问题，如Subhaa等1人提出了集成单元形成和跨单元调度的模型，降低了产品在单元间的流动时间，同时为每个工序分配合适的机器。Feng2为了减少产品可重入路径，为设备划分不同单元，同时解决后续生产过程的调度问题。上述文献研究了单元划分和调度问题，但在实际生产中针对各种类产品组成布局单元需要大量成本，因此，从调度方向解决跨单元问题更贴切企业实际情况。Li等3发现，加工过程中存在冗余的运输路径，从降低路径的角度，设计了一种基于智能体的调度方法以优化时间目标。刘兆赫4在跨单元问题中增加运输能力约束，设计了超启发式算法以降低运输时间对于系统的影响。吕洁5对多批量产品进行批量分割，通过合理分配不同批次的加工路径以到达总加工成本的优化目的。也有研究发现，复杂网络中的出入度满足单元制造系统的特征表达，邹萌邦等6提出了单元模块度的概念，通过降低模块度消除了加工过程中冗DOI:10.16644/33-1094/tp.2023.09.015基于改进变邻域NSGA-II的绿色跨单元调度问题*李嘉曜，倪静(上海理工大学管理学院，上海 200093)摘要：针对绿色背景下跨单元调度存在加工效率低和能源消耗高等问题，建立了以最小化完工时间和全局能耗的多目标数学模型。提出了一种改进变邻域NSGA-II算法求解模型。首先引入三层编码表达问题特征，然后设计了考虑运输时间的解码方法，提出一种基于Sigmoid函数的自适应交叉变异率以保证种群多样性，最后构建了三种变邻域结构融入改进后的NSGA-II算法来增强局部搜索能力。实验表明，改进后的算法能有效求解模型，运输时间能够协调完工时间和能耗关系。关键词：跨单元调度；跨单元运输时间；改进NSGA-II算法；全局能耗中图分类号：TP301文献标识码：A文章编号：1006-8228(2023)09-69-06Intercell green scheduling problem based on improved variable neighborhood NSGA-IILi Jiayao,Ni Jing（Business School,University of Shanghai for Science&Technology,Shanghai 200093,China）Abstract：Aiming at the poor processing efficiency and high energy consumption in intercell scheduling under green background,amulti-objective mathematical model is established to minimize the completion time and global energy consumption,and an improvedvariable neighborhood NSGA-II algorithm is proposed to solve the model.Firstly,a three-layer coding is introduced to express theproblem characteristics.Then,a decoding method considering transportation time is designed,and an adaptive crossover mutationrate based on Sigmoid function is proposed to ensure the population diversity.Finally,three kinds of variable neighborhoodstructures are constructed and integrated into the improved NSGA-II algorithm to enhance the local search ability.The experimentsshow that the improved algorithm can solve the model effectively,and the transportation time can coordinate the relationshipbetween the completion time and energy consumption.Key words：intercell scheduling;intercell transportation time;improved NSGA-II algorithm;global energy consumption收稿日期：2023-04-12*基金项目：国家教育部人文社会科学基金资助项目（19YJAZH064）作者简介：李嘉曜（1998-），男，上海人，硕士研究生，主要研究方向：车间调度与智能算法。通讯作者：倪静（1972-），女，上海人，博士，副教授，硕导，主要研究方向：企业信息化、生产调度和优化算法。69Computer Era No.9 2023余路径。近年来国家推崇低碳绿色的生产环境以减轻能源消耗对自然环境的影响，因此降低制造业能耗的需求日益明显7，有关的研究如徐晨昕8在企业间合作产生的网络化多单元系统背景下，分析了加工和运输等碳排放对生产过程的影响，目前针对绿色低碳背景的跨单元调度的研究较少。改进的NSGA-II算法已被广泛运用于求解车间调度问题，王亚昆等9针对带有运输约束的柔性车间改进了解码方式并为算法设计了学习机制的最优解生成法，保证种群进化的有效性。张洪亮等10设计了一种适用于分布式柔性车间的NSGA-II算法以求解带有能耗目标的调度问题，改进了交叉和变异以保证迭代个体的多样性。Paolo等11为NSGA-II建立一种基于开关策略的插入式解码方式，运用该策略降低了加工过程中空闲能耗。综上所述，跨单元调度问题通常以单元形成和降低跨单元运输时间的方向优化目标，当前很少有研究同时考虑完工时间和总能耗的跨单元调度问题，也少有学者改进NSGA-II求解该问题，本文建立了考虑时间和能耗的多目标 ICSP的数学模型，将问题描述为(Inter Cell Green Scheduling Problem,ICGSP)，同时提出了适用于模型的改进非支配排序算法NSGA-II，混合了变邻域搜索算法为ICGSP提供新思路，实验结果表明：提出的改进算法能有效的求解ICGSP；改变运输时间可以调节完工时间和能耗间的协调关系。1 问题描述与数学模型1.1 模型建立ICGSP的机器被划分于多个单元内，具体可描述为：工件集合J J1,J2,Jn个工件具有工序集合O O1,O2,Oh需要在单元集合U U1,U2,Uc中的机器集合M M1,M2,Mk上加工，每道工序可选择一台或多台设备来加工。设备具有柔性，即每道工序有若干台机器可以选择，调度的意义就是给所有工序合理排序以及分配机器以达到目标调度的最优，在ICGSP在中每个工件至少有一道工序需要跨单元生产，工件的前后工序会在单元间流动，因此运输时间不可避免，图1为ICGSP问题的示意图，其中R1和R2分别为两条路径，J1如果选择R1则需要在U1中的M1加工第一道工序后在同一单元内的M3加工后道工序。R2路径中J1的第一道工序加工完后需要从U2的M1转移至U1中的M4，产生5的运输时间，如图1所示。图1IGCSP路径示意图ICGSP需要满足以下约束件：任一工序在任一时刻只能在一个单元的一台机器上加工；同一工件的工序需要满足紧前后条件；任一机器在任一时刻只能加工一道工序；工序间不允许抢占；加工过程不考虑中断情况；所有单元的运输能力充足且相同。1.2 数学模型本文以完工时间f1和总能耗f2两个函数共同组成ICGSP多目标优化模型。该优化目标具体表达如下：最终完工时间：最终完工时间指整个系统中最后一道工序的结束时间，完工时间越小代表整体加工效率越高。f1=minCmax=minCMm 全局能耗：全局能耗包含所有加工能耗、机器空闲能耗以及单元间运输能耗，在实际生产中三者对于加工过程影响较大，降低总能耗有利制造企业节约成本。式、式和式分别为加工能耗、空闲能耗和运输能耗。f2=minET=min(Ep+Ei+Et)Ep=u=1ck=1mpij*peku*xijkuEi=u=1ck=1m()sij-wlku*iekuEt=i=1nj=1htuu*teu*qi(j+1)ICGSP的约束条件如下：k=1mxijku=1 i,j,kk=1myijij=1i,i,j,j,ksij+pij*xijku ciji,j,k,ucij-cij piji,i,j,jsi(j+1)-cij tuui,j,u,uwlku sij-ciji,i,j,j70计算机时代 2023年 第9期sij 0,cij 0,i,jCMku=maxu=1ck=1mckuk,uxijku=1,j被分配到单元u的机器k0,其他yijij=1,Oij在Oij之前加工0,其他qij(j+1)=1,Oij在Oi(j+1)跨单元加工0,其他约束式表示一道工序在同一时间只能在一个单元内的一台机器上加工；约束式表示工序间必须满足紧前后关系；约束式表示工序开始加工后无法中断，其中sij为工序开始时间，pijku为工序的加工时间；式代表一台机器一次只能选择一道工序，cij和cij表示一台机器上的前后两道不同工序；约束式代表紧前后工序在转移到下一单元加工后才能进行加工，tuu为单元间运输时间，si(j+1)表示需要跨单元加工的工序；约束式为机器某一时刻的负载量，wlku表示机器负载；约束式表示时间变量为正数；约束式定义了完工时间；约束式式为决策变量。2 改进变邻域NSGA-II算法本文的IVNSGA-II算法是在NSGA-II基础上对各部分进行改进以适合求解提出的模型，对交叉变异后的解集非支配排序、精英保留策略获得新种群，再融入变邻域结构增强算法能力，具体流程图如图2所示。图2IVNSGA-II流程图2.1 初始化初始化机制影响着解得质量，本文采用随机法，生成N个解集作为初始种群。2.2 编码编码是算法求解问题的基础，ICGSP需同时考虑工序、机器和单元的选择及排序问题，双联式编码无法体现单元特征，因此选择一种三层编码方法12。工序层中相同的数字表示同一个工件，相同工件序号出现的次数表示工件的工序；机器层中的数字表示对应的工序可用加工机器的序号；单元层表示机器所属单元。以图3为例，三层编码的第一位表示工件3的第三道工序在单元1上的第一台可行机器上加工。图3三层式编码2.3 解码解码是将染色体模拟实际加工过程的步骤，根据跨单元特性设计考虑运输时间的贪婪插入解码法。该解码方式可有效减少过程中的空闲时间，具体解码过程可分为同单元插入和跨单元插入两种方式。图4同单元插入图4为同单元插入方式，Mck和Mcm为同单元的不同机器，Oi,j具有两段可插入空闲区间T1idle和T2idle，选择T1idle内的空闲段产生较小的开始时间Si,j，因此T1idle为同单元插入的最佳区间。Oi,j的开始时间为Si,j=Ci,j-1。图5跨单元插入图5为跨单元插入方式，Mck和Mci处于两个不同71Computer Era No.9 2023单元内，Oi,j在经过运输后具有两段可插入空闲区间T1idle和T2idle，插入空闲段T1idle内将产生较小的开始时间Si,j，因此，T1idle为跨单元插入的最佳区间。Oi,j的开始时间为Si,j=Ci,j-1+tuu。2.4 交叉和变异优秀的交叉变异可以增加算法收敛性，迭代前期种群质量较差应给予高交叉变异率提高种群质量，在迭代后期，种群质量相对优秀，应适当降低交叉变异率。因此本文设计了一种基于sigmoid函数的自适应交叉变异率，具体公式如下：Pc=0.1*1Pcm+efitb()n-fitavgfitmax-fitavg+0.9fit(n)fitavg0.9fit(n)fitavgPm=0.1fit(n)fitavg0.1*(1-1Pkm+efit()n-fitavgfitmax-fitavg)fit(n)fitavg式中Pcm基础交叉率取值范围为0.5,1，fit(n)为当前个体适应度值，fitavg为种群适应度均值，fitmax和fitmin分别为种群适应度值最大和最小值fitb(n)为两个父代中较大的适应度值，通常交叉率最优范围在0.9,113，当适应度值大于均值时，表示新生成的子代解较差，应当较大的交叉率，反之则为0.9。式(18)中Pkm为基础变异率，范围为0.05,0.1，变异率最佳取值范围是0,0.113，自适应变化原理与交叉率相同。交叉操作选择工序层(OS)和机器层(MS)交叉，并选用多点交叉方式如图6和图7所示。图6OS交叉操作图7MS交叉操作OS交叉中父代1和父代2交换工序位置生成子代1和2；MS交叉中首先对父代1和父代2分别选择随机位置，将父代1所选位置顺序插入子代1中，剩余位置插入子代2中。父代2同理。在MS交叉中机器变化的同时单元层也会随之改变，因此对MS操作进行修复如图8所示。图8单元层修复过程采用多点变异对工序层(OS)和机器层(MS)进行变异操作，OS变异中，父代1的两个位置转变为其他工序序号生成子代1；MS变异对父代1中机器层选定位置的序号变为其他可行机器序号生成子代1，具体过程如图9所示。图9OS和MS变异操作2.5 变邻域搜索算子交叉变异具有盲目性，由于精英保留机制，新生成的子代质量可能不如父代，无法保证种群向指定的位置进行移动，因此本文设计了三种变邻域结构对交叉变异后的个体进行邻域变换，分别是考虑运输时间的关键路径邻域算子NS1、运输时间降低邻域算子NS2和机器负载降低邻域算子NS3。以此帮助算法向理想位置更新，三种邻域结构如下。邻域结构NS1采用N5关键路径的邻域结构14调整工序OS部分，关键路径在车间调度问题中已经获得广泛运用，在改变关键路径中的关键工序块上同时工序满足紧前后约束，同时如果工序块的变换涉及到运输时间，则需要判断前道跨单元加工工序的运输完成时间。算法每次只对一个关键工序块中的路径进行位置交换以防止生成大量非法解集。选择支配等级最高的个体Xi，确定个体调度的关键路径，选择关键工序块进行交换，具体方法如下：方法：若起始关键工序块包含二道或以上工序则交换块中末尾两道工序。方法：若中间关键工序块中包含三道或以上工序则交换其块首的相邻工序，如果前两道工序进行了72计算机时代 2023年 第9期跨单元运输则对后续影响到的工序进行右移。方法：若尾部关键工序块中包含两道或以上工序则交换块尾的相邻两道工序。如果邻域结构中存在同一关键工序块上需要交换的相邻工序为同一工件中的两道工序的情况，则不进行交换，否则将破坏工序间约束。邻域结构NS2对所有加工工件中跨单元运输时间最长的工件进行邻域变换。根据解码结果选择运输时间的工件Jn中最后需要运输的前后两道工序，根据前道工序判断后道工序是否能在同一单元的一台机器上加工，如果可行则选择一台可行机器，若不满足则再选择工件Jn-1，直到满足要求。邻域结构NS3对所有机器中负载量最高的设备进行邻域变换，根据解码选定负载最大的单元中负载量最大的机器，将机器上最后一道工序转移到另一台可行机器上，若不存在则更换一道工序直到满足要求。3 数值实验和分析3.1 算例构造和评价指标分析IVNSGA-II实验环境为Matlab2016，AMDRyzen53600X，3.8GHz，内存为8g的计算机上实现。参数设置为：种群规模Pop=150代，最大迭代次数Maxgen=200，基础交叉概率Pcm=0.5，基础变异概率Pkm=0.08。由于暂无跨单元调度的基准算例，本文选取基准算例集的Brandimarte 中 的 MK01 和 MK03 以 及 Hurink 中 的LA16作为实验对象，对三个算例进行单元划分，算例信息如表1所示。机器单位加工能耗pek 8,15kW，机器单位空闲能耗iek 1,5kW，单元间的单位运输能耗teu=5kW。表1算例信息算例MK01-2MK03-3LA16-4工件数101520工序数5,65,89,12加工时间1,61,635,95设备数6810单元数234运输时间820,3020,25,303.2 算法性能对比表 2为 IVNSGA-II、NSGA-II和 IWOA 算法在三个算例的运行结果。对每个算例运行10次得到三个指标，max为最差值,min为最优值，avg为均值。根据对比可得，IVNSGA-II均取得了最优结果，对于MK01-2算例，IVNSGA-II算法在完工时间目标上优势并不高，但在全局能耗上远低于其他两种算法；在MK03-3算例上，IVNSGA-II的求解结果优秀程度较为明显，在LA16-4上，算法在全局能耗目标上得到了最好的效果，本文算法运行时间也取得了最优。通过观察每一代的目标值分析算法性能，如图10所示。算例MK01-2Mk03-3La16-4优化目标CmaxETCmaxETCmaxETINSGA-VNSmax4437.07210.00351.581085.001753.70avg4335.93206.68347.091058.261745.31min4235.55202.00339.421046.001723.07NSGA-IImax4763.56265.00402.811189.001820.04avg45.6765.31238.42396.841247.631837.70min4568.71226.00388.231237.001836.65IWOAmax5752.48261.00368.651213.001895.35avg55.6749.88243.00367,.901173.261864.66min5447.38234.00365.521146.001843.51运行时间/s40/41/52200/252/231954/1008/976表2算法对比结果图10MK03-3迭代图图10中，实线表示算法每一代最优值，虚线表示每一代最优值的均值，完工时间的最优值在76代达到最优收敛，其均值在100代也迭代到最低；总能耗在110代已接近收敛，之后能耗值继续降低，验证了变邻域结构能帮助算法跳出了局部最优。3.3 运输时间相关性运输时间会影响总体加工效率和全局能耗，具体表现为：当运输时间tuu增加时，在机器Mk上的工序Oij如果无法进行左移插入，则空闲时间和空闲能耗随之增加，但对于一台负载量较大的机器，增加一段运输时间可能会帮助工序Oij转移到一台较为空闲的机器73Computer Era No.9 2023Mc上，因此该工序的完成时间反而降低，为了验证这一点，本文将运输时间映射为跨单元运输次数与总能耗和负载量的关系，如图11所示。图11设备负载和总能耗比率图图11中负载比率为总运输时间和机器总负载的比率，能耗比率为总运输时间和总能耗的比率。由此可以看出，跨单元在后期会上升，原因是在调度后期部分机器负载量较高，工序选择了较为忙碌的机器加工，使得机器的负载量升高。能耗部分由于工序无法插入到空闲时间内导致空闲能耗增加，因此决策者可以通过调节运输时间来协调完工时间和能耗，从而决定合理的优化结果。4 结束语本文针对ICGSP跨单元调度问题，首先建立了考虑完工时间和全局能耗的调度模型。提出一种IVNSGA-II求解该模型。引用了一种三层编码表达工序、机器和单元层的具体关系，设计了考虑运输时间的贪婪解码法以降低空闲时间在调度过程中的影响，提出一种自适应交叉变异率增加算法寻优能力，融入了三种变邻域搜索结构来提高算法的局部搜索能力。最后通过算例验证了改进算法的有效性，同时分析了运输时间与两个优化目标的关系，为单元制造系统提供了新思路。在后续研究中将考虑将运输工具作为实际约束加入到模型中，以及动态情况跨单元调度中的求解算法，探讨解决跨单元调度问题的新思路。参考文献(References):1 SubhaaR,JawaharN,Ponnambalam SG.An improveddesignforcellularmanufacturingsystemassociatingscheduling decisionsJ.Sdhan,2019,44:1-23.2 Feng H,Xia T,Da W,et al.Concurrent design of cellformationandschedulingwithconsiderationofduplicate machines and alternative process routingsJ.Journal of Intelligent Manufacturing,2019,30:275-289.3 Li D,Wang Y,Xiao G,et al.Dynamic parts scheduling inmultiple job shop cells considering intercell moves andflexibleroutesJ.Computers&OperationsResearch,2013,40(5):1207-1223.4 刘兆赫,李冬妮,王乐衡,等.考虑运输能力限制的跨单元调度方法J.自动化学报,2015,41(5):885-898.5 吕洁,王洁.基于批量分割的虚拟单元制造系统多阶段动态调度J.江苏科技大学学报(自然科学版),2014,28(3):292-297.6 邹萌邦,刘琼,尹勇.基于改进小世界遗传算法的网络环境下跨单元调度J.计算机集成制造系统,2019,25(8):1991.7 周济.智能制造是“中国制造2025”主攻方向J.企业观察家,2019(11):54-55.8 徐晨昕.网络环境下面向低碳的跨单元调度优化D.湖北:华中科技大学,2018.9 王亚昆,刘应波,吴永明,等.改进NSGA-II算法求解考虑运输约束的柔性作业车间节能调度问题J/OL.计算机集成制造系统,2023(3):1-22.10 张洪亮,徐公杰,鲍蔷,等.考虑运输时间的分布式柔性作业车间绿色调度J.中国机械工程,2022,33(21):2554-2563,2645.11 Renna P,MateriS.Switch off policies in job shopmanufacturing systems including workload evaluationJ.InternationalJournalofManagementScienceandEngineering Management,2021,16(4):254-263.12 Feng Y,Li G,Sethi S P.A three-layer chromosomegeneticalgorithmformulti-cellschedulingwithflexibleroutesandmachinesharingJ.InternationalJournal of Production Economics,2018,196:269-283.13 姜一啸,吉卫喜,何鑫,等.基于改进非支配排序遗传算法的多目标柔性作业车间低碳调度J.中国机械工程,2022,33(21):2564-2577.14 任玺悦,王修贤,耿娜,等.考虑多急件到达的作业车间重调度研究J.工业工程与管理,2022,27(3):74-83.CE74