搜索
智能算法在柔性作业车间调度中的应用摘要：为提高企业生产效率，合理的流水车间生产调度显得尤为重要。本文介绍了三种智能算法（蚁群算法、遗传算法、改进粒子群算法）在车间生产调度中的应用，主要介绍了算法的基本思想、模型结构、算法实现以及运用前景。对智能算法在生产调度中的应用做出总结。关键字：智能算法；蚁群算法；遗传算法；改进粒子群算法；生产调度0.前言柔性作业车间调度问题(Flexiblejob-shopsche-dulingproblem,FJSP)是传统作业车间调度问题的扩展，是实际生产中迫切需要解决的一类问题。在传统的作业车间调度问题中，工件的每道工序只能在一台确定的机床上加工。而在柔性作业车间调度问题中，每道工序可以在多台机床上加工，并且在不同的机床上加工所需时间不同。柔性作业车间调度问题减少了机器约束，扩大了可行解的搜索范围，增加了问题的难度。作业车间的主要特点是：n个工件需要在m台机器上进行加工，每个工件都有其独特的加工步骤，但无明显的顺序约束，并且加工时间是已知的，调度的目标是在不允许两个工件同时在同一台机器上加工的前提下，如何安排工件在每台机器上的加工顺序使这些工件能够尽快加工完毕[1]。1.蚁群算法在作业车间的应用[2]以3个工件2台机器的问题作为例子，如图1。图1三个工件两台机器的JSP问题为确定先对哪个工件进行加工，需要设置一个初始节点O0，所有的蚂蚁最初都放置在O0。图1中除与O0相连的有向弧表示同一个工件的加工顺序，工件必须按照该顺序进行加工。其它则为无向弧。每个弧与表示节点间信息素的量和启发式距离的一对值{αij,dij}有关。dij通常为对节点j的第i步操作的加工时间，τij使用蚁周方式进行更新：其中，ρ是个系数，1−ρ表示在时间t和t+1之间信息素的蒸发，Q为常数，Tk为完成所有加工步骤后最短的总加工时间。初始时刻τij(0)=c（c为常数）。这个规则包含了两个方面：(1)图1中所有边缘上的信息素都要蒸发；(2)完成所有的加工后要将该解的效果加到各边缘上。蒸发可以防止搜索局限在局部最小的邻域中，另一方面又能根据已有解的效果好坏来更新信息素，进行增强学习。另一个关键的问题就是如何保证蚂蚁按照工件的工艺路线产生一组可行解。这里用到3个集合：对每个蚂蚁k，首先要有集合Gk，表示没有访问过的节点集合；Sk表示根据技术路线下一步允许访问的节点集合；还需要一个禁忌表，存放已经访问过的节点。在我们的例子中，Gk={1，2，3，4，5，6}，Sk={1，2，3}。转移概率是通过下式计算的：Tij为工件i在机器j上的加工时间。每选择一个节点，该节点就被追加到禁忌表中并从Gk和Sk中删除；如果被选的节点不是工件的最后一步，那该工件中紧邻的下一个节点会被加到Sk中。该过程一直重复到Gk=φ。最后禁忌表中得到的节点的排列顺序就是蚂蚁k找到的解。参数α和β决定了算法的收敛速度并对解的性能好坏有重要影响，同时蒸发常数也需要进行适当的调整以使搜索能在好的搜索空间中进行，并防止陷入局部最优的邻域中。蚁群算法已经被成功地运用于10个工件、10台机器和10个工件、15台机器的JSP例子中，该算法总能得到最优解的10%以内的解，只是该方法的计算复杂性占用了部分执行时间，但我们仍可以认为这是一个比较有希望的结果。2.遗传算法在作业车间调度中的应用2.1遗传算法编码和解码[3]编码与解码是指染色体和调度解之间进行相互转换，是遗传算法成功实施优化的首要和关键问题。对于传统的作业车间调度问题，大多数研究采用基于工序的编码。但是柔性作业车间调度问题不仅要确定工序的加工顺序，还需为每道工序选择一台合适的机器，仅采用基于工序的编码方法不能得到问题的解。因此，对于柔性作业车间调度问题，遗传算法的编码由两部分组成，第一部分为基于工序的编码，用来确定工序的加工先后顺序；第二部分为基于机器分配的编码，用来选择每道工序的加工机器。融合这两种编码方法，即可得到柔性作业车间调度问题的一个可行解。2.1.1基于工序的编码这部分编码染色体的基因数等于工序总数，每个工件的工序都用相应的工件序号表示，并且工件序号出现的次数等于该工件的工序数。根据工件序号在染色体出现的次序编译，即从左到右扫描染色体，对于第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道工序，将其插入到对应机器上最佳可行的加工时刻安排加工，以此方式直到序列上所有工序都安排在其最佳可行的地方。2.2交叉操作交叉操作是将种群中两个个体随机地交换某些基因，产生新的基因组合，期望将有益的基因组合在一起。染色体中两部分基因串的交叉分别进行，其中第一部分基于工序编码基因串的交叉操作采用张超勇等[8]提出的POX交叉算子，第二部分基于机器分配编码基因串的交叉采用一种新提出的多点交叉方法。2.2.1基于工序编码基因串的交叉这部分交叉操作的过程为：将所有的工件随机分成两个集合J1和J2，染色体子代1/子代2继承父代1/父代2中集合J1内的工件所对应的图2基于工序编码的交叉基因，子代1/子代2其余的基因位则分别由父代2/父代1删除已经继承的基因后所剩的基因按顺序填充，交叉操作过程如图2所示。2.2.2基于机器分配编码基因串的交叉这部分基因串采用一种新的多点交叉的方法，交叉操作的过程为：首先随机产生一个由0、1组成与染色体长度相等的集合Rand0_1，然后将两个父代中与Rand0_1集合中0位置相同的基因互换，交叉后得到两个后代。图2显示了两个父代基因父代1/父代2交叉后得到的两个子代基因子代1/子代2的过程。此外，对于部分柔性作业车间调度问题，当交叉产生的机器号大于对应工序可利用的机器总数时，在该工序加工机器中随机选择一台机器加工(加工时间短的优先选择)。图3基于机器分配编码的交叉2.3变异操作变异操作的目的是改善算法的局部搜索能力，维持群体多样性，同时防止出现早熟现象。对于改进遗传算法，基于工序编码和基于机器分配编码的变异分别设计如下。2.3.1基于工序编码的变异这部分基因实施插入变异，即从染色体中随机选择一个基因，然后将之插入到一个随机的位置。2.3.2基于机器分配编码的变异由于每道工序都可以由多台机器完成，所以随机选择两道工序，然后在执行这两道工序的机器集合中选择一台机器，并将选择的机器号置入对应的基于机器分配编码的基因串中，这样得出的解能确保是可行解。2.3.2基于机器分配编码的变异由于每道工序都可以由多台机器完成，所以随机选择两道工序，然后在执行这两道工序的机器集合中选择一台机器，并将选择的机器号置入对应的基于机器分配编码的基因串中，这样得出的解能确保是可行解。2.4选择操作在遗传算法中，选择是根据对个体适应度的评价从种群中选择优胜的个体，淘汰劣质的个体。在改进遗传算法中，选择操作采用最佳个体保存和锦标选择两种方法。最佳个体保存方法就是把群体中适应度高的个体不进行配对交叉而直接复制到下一代中，DEJONG[9]最早对这种方法作了定义。在本文的改进遗传算法中，最佳个体保存方法是将父代群体中最优的1%个体直接复制到下一代中。锦标选择是由GOLDBERG等[10]提出的，它是从种群中随机选择两个个体，如果随机值(在0～1之间随机产生)小于给定概率值r(概率值r是一个参数，一般设置为0.8)，则选择优的一个，否则就选择另一个；被选择的个体放回到种群，可以重新作为一个父染色体参与选择。2.5基于柔性作业车间调度问题的改进遗传算法在传统遗传算法求解调度问题时，交叉产生的子代总是被接受，这可能造成优良解被丢失或破坏，因此传统遗传算法易于早熟且收敛慢。求解柔性作业车间调度问题比传统调度问题更复杂，它首先确定工序的加工顺序，接着为每道工序选择一台加工机器；前者由染色体中基于工序编码的基因串确定，后者由基于机器分配编码的基因串确定，结合这两个基因串可得到一个可行解。针对柔性作业车间调度问题的这些特点，提出一种双层子代产生模式的改进遗传算法，它的交叉操作过程为：对于两个父代中基于工序的编码的基因串交叉n次，基于机器分配编码的基因串交叉n×k次；具体地说，基于工序的编码的基因串每交叉一次产生两子代，基于机器分配编码基因串就交叉k次，这样能为这两子代分配更合适的机器，使子代能更好地继承父代的优良特征。这样两个父代相当于交叉了n×k次，从所有后代中选择最优的两个染色体存入下一代。测试结果显示该方法求解柔性作业车间调度问题比传统遗传算法更有效。改进遗传算法的步骤如下。(1)初始化随机产生P个染色体个体，P为种群规模。(2)评价每个个体适应度值。(3)判断是否达到终止条件，若满足则输出最优解；否则转步骤4。(4)将1%最优个体直接复制到下一代中。(5)按选择策略选取下一代种群。(6a)若两父代个体适应度不相等并满足交叉概率Pc，基于双层子代产生模式对两父代个体进行交叉，即基于工序编码的基因串交叉n次，基于机器分配编码的基因串交叉n×k次，从所有后代中选择两个最优的染色体作为下代。(6b)按变异概率Pm，进行变异操作生成新个体。(7)生成新一代种群，返回到步骤(3)。3.粒子群算法在柔性作业车间中的应用[4]3.1.1FJSP描述FJSP问题可以描述为:作业车间存在M种工件在N台机器上加工,工件Mi各有Ji道工序(不指定工序的加工机器,允许工序从被选机器中任意选择)。工件的工序是预先确定的,每道工序可以在一台或多台不同的机器上加工。Rijegk和Xijk为决策变量。调度目标是为每道工序选择合适的机器,以及确定每台机器上各工序的最佳加工顺序,使系统的总目标达到最优。并且加工过程需要满足以下假设和约束条件:所有机器一开始均处于空闲状态;在零时刻,所有的工件都可被加工;工序一旦进行,不能中断;不同工件的工序之间没有先后约束,工件之间具备相同的优先级;各工件的准备时间和移动时间计入加工时间;同一工件工序间的加工顺序约束;同一机器上一个加工任务完成后才能开始另一个任务的加工资源约束。3.1.2FJSP多目标优化模型本文面向的柔性作业车间多目标调度考虑3个优化目标(T,C,D)。T、C、D分别表示制造工期、加工成本和工件提前/拖期惩罚值。通过工厂日历、订单交货期和车间加工情况分析确定工件i的最早交货期D′i和最晚交货期时间Di,Ei是工件i的完工时间。同时根据工件的交货优先级确定不同工件的提前惩罚系数ri