(完整版)智能算法在柔性车间调度中的应用

智能算法在柔性作业车间调度中的应用摘要：为提高企业生产效率，合理的流水车间生产调度显得尤为重要。本文介绍了三种智能算法(蚁群算法、遗传算法、改进粒子群算法)在车间生产调度中的应用，主要介绍了算法的基本思想、模型结构、算法实现以及运用前景。对智能算法在生产调度中的应用做出总结。关键字：智能算法；蚁群算法；遗传算法；改进粒子群算法；生产调度0.前言柔性作业车间调度问题(Flexiblejob-shopsche-dulingproblem,JSP)是传统作业车间调度问题的扩展，是实际生产中迫切需要解决的一类问题。在传统的作业车间调度问题中，工件的每道工序只能在一台确定的机床上加工。而在柔性作业车间调度问题中，每道工序可以在多台机床上加工，并且在不同的机床上加工所需时间不同。柔性作业车间调度问题减少了机器约束，扩大了可行解的搜索范围，增加了问题的难度。作业车间的主要特点是：n个工件需要在m台机器上进行加工，每个工件都有其独特的加工步骤，但无明显的顺序约束，并且加工时间是已知的，调度的目标是在不允许两个工件同时在同一台机器上加工的前提下，如何安排工件在每台机器上的加工［f呢、一■—ifkeallowed上日1禺林虬工止0crhei^ise其中，P是个系数，1P表示在时间t和t+1之间信息素的蒸发，Q为常数，Tk为完成所有加工步骤后最短的总加工时间。初始时刻t(0)=c(c为常ij数)。这个规则包含了两个方面：(1)图1中所有边缘上的信息素都要蒸发；(2)完成所有的加工后要将该解的效果加到各边缘上。蒸发可以防止搜索局限在局部最小的邻域中，另一方面又能根据已有解的效果好坏来更新信息素，进行增强学习。另一个关键的问题就是如何保证蚂蚁按照工件的工艺路线产生一组可行解。这里用到3个集合：顺序使这些工件能够尽快加工完毕［1］。对每个蚂蚁k,首先要有集合Gk顺序使这些工件能够尽快加工完毕［1］。k的节点集合；S「表示根据技术路线下一步允许访k1.蚁群算法在作业车间的应用［2］问的节点集合；还需要一个禁忌表，存放已经访问过的节点。在我们的例子中，G1.蚁群算法在作业车间的应用［2］k以3个工件2台机器的问题作为例子，如图1。1-All.Oil"5-4>m,1-On,5—Chi.4Ok其中.a叢云利始节点"硕中】为工件的类型.j为工件的该步捉柞在第几台机器上进行「图1三个工件两台机器的JSP问题为确定先对哪个工件进行加工，需要设置一个初始节点00，所有的蚂蚁最初都放置在00。图1中除与00相连的有向弧表示同一个工件的加'工顺序，工件必须按照该顺序进行加工。其它则为无向弧。每个弧与表示节点间信息素的量和启发式距离的一对值｛a,d｝有关。d通常为对节点j的第i步ijijij操作的加工时间，t使用蚁周方式进行更新：ij5，6｝，S=｛1,2,3｝。转移概率是通过下式计k算的：ifkifkealicmvdkT为工件i在机器j上的加工时间。每选择一个节ij点，该节点就被追加到禁忌表中并从G和S中删kk除；如果被选的节点不是工件的最后一步，那该工件中紧邻的下一个节点会被加到Sk中。该过程一直重复到G=©。最后禁忌表中得到的节点的排列k顺序就是蚂蚁k找到的解。参数a和B决定了算法的收敛速度并对解的性能好坏有重要影响，同时蒸发常数也需要进行适当的调整以使搜索能在好的搜索空间中进行，并防止陷入局部最优的邻域中。蚁群算法已经被成功地运用于10个工件、10台机器和10个工件、15台机器的JSP例子中，该算法总能得到最优解的10%以内的解，只是该方法的计算复杂性占用了部分执行时间，但我们仍可以认为这是一个比较有希望的结果。遗传算法在作业车间调度中的应用遗传算法编码和解码［3］编码与解码是指染色体和调度解之间进行相互转换，是遗传算法成功实施优化的首要和关键问题。对于传统的作业车间调度问题，大多数研究采用基于工序的编码。但是柔性作业车间调度问题不仅要确定工序的加工顺序，还需为每道工序选择一台合适的机器，仅采用基于工序的编码方法不能得到问题的解。因此，对于柔性作业车间调度问题，遗传算法的编码由两部分组成，第一部分为基于工序的编码，用来确定工序的加工先后顺序；第二部分为基于机器分配的编码，用来选择每道工序的加工机器。融合这两种编码方法，即可得到柔性作业车间调度问题的一个可行解。基于工序的编码这部分编码染色体的基因数等于工序总数，每个工件的工序都用相应的工件序号表示，并且工件序号出现的次数等于该工件的工序数。根据工件序号在染色体出现的次序编译，即从左到右扫描染色体，对于第k次出现的工件序号，表示该工件的第k道工序。对表1所表示的柔性作业车间调度问题，一个基于工序编码的基因串可以表示为［12213123］，其中1表示工件J1，2和3意义相同。基因串中的3个1依次表示工件J1的3个工序，分别为工序1、工序2和工序3。2.1.2基于机器分配的编码设工序总数为l,工序号分别用1,2,3,…，l表示。对于这l道工序，形成l个可选择机器的子集｛S1,S2,S3,…，Sl｝，第i个工序的可加工机器集合表示为Si,Si中元素个数为ni,表示为｛mi1,mi2,…，mni｝。基于机器分配的编码基因串的长度为l，表示为［g1,g2,…,gi,…,gl］。其中第i个基因gi为［1,ni］内的整数，是集合Si中的第gi个元素mgi，表示第i个工序的加工机器号。具体地说，若第1道工序有三台机器作为可选择机器，则n1=3。设S1=｛M11,M12,M13｝，则第1道工序有M11,M12,M13这3台机器作为可选机器，根据g1的值从集合S1中确定加工第1道工序所用的机器。若g1=1，则机器M11为加工第1道工序所用的机器。以此类推，确定加工第2,3,…，l道工序所用的机器。对于表1所示的柔性作业车间调度问题，总共有8道加工工序，假设基于机器分配编码的基因串为［21231232］，则表示这8道工序的加工机器号分别为［22352344］。解码时先根据基于机器分配编码的基因串选择每道工序的加工机器，然后按基于工序编码的基因串确定每台机器上的工序顺序。但是确定每台机器上的工序顺序时，按一般解码方式只能得到半主动调度，而不是主动调度。这里介绍一种插入式贪婪解码算法，能保证染色体经过解码后生成主动调度。该解码算法描述如下：按照工序在该序列上的顺序进行解码，序列上第1道工序首先安排加工，然后取序列上第2道工序，将其插入到对应机器上最佳可行的加工时刻安排加工，以此方式直到序列上所有工序都安排在其最佳可行的地方。交叉操作交叉操作是将种群中两个个体随机地交换某些基因，产生新的基因组合，期望将有益的基因组合在一起。染色体中两部分基因串的交叉分别进行，其中第一部分基于工序编码基因串的交叉操作采用张超勇等［8］提出的P0X交叉算子，第二部分基于机器分配编码基因串的交叉采用一种新提出的多点交叉方法。基于工序编码基因串的交叉这部分交叉操作的过程为：将所有的工件随机分成两个集合J1和J2,染色体子代1/子代2继承父代1/父代2中集合J1内的工件所对应的图2基于工序编码的交叉基因，子代1/子代2其余的基因位则分别由父代2/父代1删除已经继承的基因后所剩的基因按顺序填充，交叉操作过程如图2所示。基于机器分配编码基因串的交叉这部分基因串采用一种新的多点交叉的方法，交叉操作的过程为：首先随机产生一个由0、1组成与染色体长度相等的集合RandO_l,然后将两个父代中与RandO_l集合中0位置相同的基因互换,交叉后得到两个后代。图2显示了两个父代基因父代1/父代2交叉后得到的两个子代基因子代1/子代2的过程。此外,对于部分柔性作业车间调度问题,当交叉产生的机器号大于对应工序可利用的机器总数时,在该工序加工机器中随机选择一台机器加工(加工时间短的优先选择)。子吒1213>31123223132*ttt1tt1121I23112J12S232RaiidO1010011D100I1011父代221323111J2Ii1JJiI14!于tv21L23211i113233图3基于机器分配编码的交叉变异操作变异操作的目的是改善算法的局部搜索能力,维持群体多样性,同时防止出现早熟现象。对于改进遗传算法,基于工序编码和基于机器分配编码的变异分别设计如下。2.3.1基于工序编码的变异这部分基因实施插入变异,即从染色体中随机选择一个基因,然后将之插入到一个随机的位置。2.3.2基于机器分配编码的变异由于每道工序都可以由多台机器完成,所以随机选择两道工序,然后在执行这两道工序的机器集合中选择一台机器,并将选择的机器号置入对应的基于机器分配编码的基因串中,这样得出的解能确保是可行解。基于机器分配编码的变异由于每道工序都可以由多台机器完成,所以随机选择两道工序,然后在执行这两道工序的机器集合中选择一台机器,并将选择的机器号置入对应的基于机器分配编码的基因串中,这样得出的解能确保是可行解。选择操作在遗传算法中,选择是根据对个体适应度的评价从种群中选择优胜的个体,淘汰劣质的个体。在改进遗传算法中,选择操作采用最佳个体保存和锦标选择两种方法。最佳个体保存方法就是把群体中适应度高的个体不进行配对交叉而直接复制到下一代中，DEJ0NG［9］最早对这种方法作了定义。在本文的改进遗传算法中,最佳个体保存方法是将父代群体中最优的1%个体直接复制到下一代中。锦标选择是由GOLDBERG等［10］提出的，它是从种群中随机选择两个个体，如果随机值(在0〜1之间随机产生)小于给定概率值r(概率值r是一个参数，一般设置为0.8)，则选择优的一个，否则就选择另一个；被选择的个体放回到种群，可以重新作为一个父染色体参与选择。2.5基于柔性作业车间调度问题的改进遗传算法在传统遗传算法求解调度问题时，交叉产生的子代总是被接受，这可能造成优良解被丢失或破坏,因此传统遗传算法易于早熟且收敛慢。求解柔性作业车间调度问题比传统调度问题更复杂，它首先确定工序的加工顺序，接着为每道工序选择一台加工机器；前者由染色体中基于工序编码的基因串确定,后者由基于机器分配编码的基因串确定，结合这两个基因串可得到一个可行解。针对柔性作业车间调度问题的这些特点，提出一种双层子代产生模式的改进遗传算法，它的交叉操作过程为：对于两个父代中基于工序的编码的基因串交叉n次，基于机器分配编码的基因串交叉nXk次；具体地说，基于工序的编码的基因串每交叉一次产生两子代，基于机器分配编码基因串就交叉k次，这样能为这两子代分配更合适的机器，使子代能更好地继承父代的优良特征。这样两个父代相当于交叉了nXk次，从所有后代中选择最优的两个染色体存入下一代。测试结果显示该方法求解柔性作业车间调度问题比传统遗传算法更有效。改进遗传算法的步骤如下。初始化随机产生P个染色体个体，P为种群规模。评价每个个体适应度值。判断是否达到终止条件，若满足则输出最优解；否则转步骤4。将1%最优个体直接复制到下一代中。按选择策略选取下一代种群。(6a)若两父代个体适应度不相等并满足交叉概率Pc，基于双层子代产生模式对两父代个体进行交叉，即基于工序编码的基因串交叉n次，基于机

器分配编码的基因串交叉nXk次，从所有后代中选择两个最优的染色体作为下代。(6b)按变异概率Pm,进行变异操作生成新个体。(7)生成新一代种群，返回到步骤(3)。粒子群算法在柔性作业车间中的应用⑷FJSP描述FJSP问题可以描述为:作业车间存在M种工件在N台机器上加工，工件Mi各有Ji道工序(不指定工序的加工机器，允许工序从被选机器中任意选择)。工件的工序是预先确定的，每道工序可以在一台或多台不同的机器上加工。R和X为决策ijegkijk变量。'I0「件的第it匚序和工件喲第髓匸序、在机器吐执伉若I［序itJ'-匚序说.o淇他)Lcr.ft的第逍匸庁任机器也执疔)调度目标是为每道工序选择合适的机器，以及确定每台机器上各工序的最佳加工顺序，使系统的总目标达到最优。并且加工过程需要满足以下假设和约束条件：所有机器一开始均处于空闲状态；在零时刻，所有的工件都可被加工;工序一旦进行，不能中断;不同工件的工序之间没有先后约束，工件之间具备相同的优先级;各工件的准备时间和移动时间计入加工时间；同一工件工序间的加工顺序约束;同一机器上一个加工任务完成后才能开始另一个任务的加工资源约束。FJSP多目标优化模型本文面向的柔性作业车间多目标调度考虑3个优化目标(T,C,D)。T、C、D分别表示制造工期、加工成本和工件提前/拖期惩罚值。

<1制造I：期丁此中凡一匚件任机器啲亢|［叶间式(】威示机器啲完匸时间取决r在其上加匚的所有工件中彊后-个工件的完工时间.◎血I匚成本cMJ,N

minCUmin^工VG上帝⑵1I.—I成中G——匸件帕第适丁序衽机器加丄成本门就前施期惩罚值1>i［ib1'^V|«=］萼巾感⑴Ei-\\}|(3)通过工厂日历、订单交货期和车间加工情况分析确定工件i的最早交货期D'i和最晚交货期时间Di，Ei是工件i的完工时间。同时根据工件的交货优先级确定不同工件的提前惩罚系数ri和拖期惩罚系数wi。(4闕束条件顺用约範工件的当前匚庁完■后才能开始后道匸序的加T(IV奄1^ii}o=U(4)资源约束;在机罄k上开始个新任务必须在『任务完成后.%—Mg"(\=尬=1I)<5)式中码人——［件帕第适丁序衽机器町：的抓匚时间冊——L件的第血匚序在机器k|［的完丨.时间CDMOPSO算法在MOPSO运算过程中，各粒子向所经历的某个非支配的历史位置(Pb)学习，同时从外部种群中按照一定规则选择一个解作为引导者(Gb),在外部种群中存储从开始到结束运行时粒子群所发现的非支配解。在运算过程中不断更新外部种群，在运行结束时其中的解基本就是最终输出结果。MOPS0算法位置更新公式仍相似于单目标优化，即Vj=^rl‘一$画咄i）〔1饗-W）-聲=耳1十呼⑺式中—速度—粒子位置'J懺性从IJ-tV——丿川速1人仃创诚]h^Iid（2j——1|QIJ间的随机数3.2.1编码和解码FJSP问题的解包含机器选择和工序调度，因此编码也要反映这两方面的内容，为此使用基于工序和机器的两层编码方案[15]。粒子的位置向量用2个相互对应的L维向量Xp[L]和Xm[L]来表示，L是工件的总工序数。表1所示是一个3X4的FJSP粒子编码。解码时，先通过粒子的Xm[L]向量值确定工序的加工机器，同时将对应的Xp[L]向量转换为一个有序的操作表，向量中的顺序决定了工序调度的优先级。然后根据该表，将工序按其调度的优先顺序在指定的机器上以最早允许加工时间进行加工，产生调度方案。表1某一粒子前编码TM1CcdhSofa粒子L123斗567萄1|2L323123和||41133J2计算位置和速度粒子的速度矢量也由2部分组成，即Vp[L]和Vm[L]来表示，分别根据式（6）来计算。Xp[L]和Xm[L]根据式（7）来计算。由于FJSP是满足优先权约束的整数规划问题，因而粒子在更新时还需进行修正。对计算得到的新值X'p[L]的各分量先按升序排列，再根据排序结果重新排列Xp[L]的各分量。粒子的位置更新过程如表2和表3所示。

表2按阳更新公式计算后xjq2l[ftFtcruPdaticiRTOC\o"1-5"\h\z^I'l2I32312JX；[】}3I22J44.5J.8255.218表3排序更新后的新Xp（]|Tfib3X]l|aftt-'r塔|]}L4].S22251I3.845512Xr|1}3112322因为町SP中工序存在机器约束的情况，在Xm[L]的粒子更新时需要进行修正:①若该分量所对应的工序只存在一台机器能够加工，则选择该工序所对应机器序号更新Xm[L]的分量值。②若存在l台机器能够加工该分量对应的工序，其Xm[L]的分量对应值为k1，k2,…,kl,Xm[L]的分量值x在计算后得到x，，则对|ki-x'|（i=l,2，…，1）进行排序，选出其最小值k*，该分量值更新为x=k*。多目标粒子群算法的改进PSO应用于多目标问题时最重要的操作是保持Pareto最优解集的多样性和更新粒子群的全局最优值。本文提出的CDMOPS0算法，借鉴密集距离计算方法对个体按密集距离排序，同时采用精英策略保留进化过程中的优势个体，从而保持Pareto集的多样性和更新全局最优值，并引入小概率的变异机制增强算法的全局寻优能力。主要采用如下：策略：（1）外部种群更新和缩减在多目标进化算法中，精英策略是在外部种群中存储每代进化过程中产生的非支配优势个体，并排除外部种群中可能产生的劣势个体，从而有利于保证多目标进化算法的收敛性和多样性。本文采用精英策略保留每代进化过程中产生的非支配个体。设内部粒子群为P,外部优势种群为A,在粒子群完成一代飞行后，首先选出P中的非支配个体，然后将所有非支配个体拷贝到A,并且删除A中的重复个体和被支配个体。若A中个体数超过其种群规模S,基于Deb在NSGAII中提出的个体密集距离计算方法[17]，计算A中所有个体的密集距离并按降序排列。仅保留前S个个体，删除多余的最密集个体。否则，不对A进行缩减操作。该方法既通过精英策略保留运算过程中的优良粒子，同时保证了外部种群的规模，避免了运算过程中随着循环代数的增加非支配个体数增多，从而保证

了运算的效率;同时,当外部种群个体数超过其规模时,删除多余的最密集个体,保留分散个体,从而有效保证了Pareto前沿的均匀分布。全局最优值更新完成外部种群A的更新和缩减之后，需更新内来。②对Xm［L］进行基于机器选择的变异，把可加工该道工序的所有机器放进一个集合，进行变异时则从该工序对应的机器集合中随机选择一个机器来替换原有机器，再将变异前后适应度值较优的个体保留部粒子群P的全局最优值。Gb从A中选择一个下来。删除險隼的雪余牛低.保持」1■个悴数対M,离肢婕钛萌區横运霾计尊删除險隼的雪余牛低.保持」1■个悴数対M,离肢婕钛萌區横运霾计尊A中个悴的密隼距离井按降序排列吏新毎牛粒子的片输出外部种群儿抚得挝优前诰执冇基于丁錚駅序和堆•］•机書选择的竟异处于最分散区域的个体，引导粒子群向Pareto最优前沿分散区域的进化。Gb的更新分为两种情况：①当A中仅包含边界个体时，即A中所有个体的密集距离为无穷大，Gb则从中随机选择一个边界个体。②当A中包括若干个密集距离不为无穷大的个体时，则随机选择一个密集距离较大的个体作为Gd，其计算公式为A讣讥应叫|⑴.丫忙｝)(S)式屮rn一外部种群/冲包含个休数呈°—种胖/冲按密菠距离降序排列时订个密集蹈离不为无芳人的个体序号I且nl0.I<ni眄保证逸择范懵在费集距离粒大的个体区间内.在该区问内随机选样「个个体作为G呻％q》——|%引之间一个随机整数的