改进遗传算法解决柔性作业车间调度问题.pdf

发布时间：2022-05-30 发布人：admin 分类：说明书资料大小：0.54M 资料格式：pdf 举报版权申诉

weixin_38584148-12102761-16359647455596998167.pdf-第1页.png

第1页 / 共10页

weixin_38584148-12102761-16359647455596998167.pdf-第2页.png

第2页 / 共10页

weixin_38584148-12102761-16359647455596998167.pdf-第3页.png

第3页 / 共10页

weixin_38584148-12102761-16359647455596998167.pdf-第4页.png

第4页 / 共10页

weixin_38584148-12102761-16359647455596998167.pdf-第5页.png

第5页 / 共10页

weixin_38584148-12102761-16359647455596998167.pdf-第6页.png

第6页 / 共10页

weixin_38584148-12102761-16359647455596998167.pdf-第7页.png

第7页 / 共10页

weixin_38584148-12102761-16359647455596998167.pdf-第8页.png

第8页 / 共10页

文本预览

中国科技论文在线 http://www.paper.edu.cn 改进遗传算法解决柔性作业车间调度问题# 田旻，刘人境** （西安交通大学管理学院，西安 710049） 10 5 摘要：柔性作业车间调度问题是经典作业车间调度问题的深入和扩展，为生产过程中作业车间调度的资源受限问题提供了更加切实可行的方案。针对柔性作业车间调度问题自身的特点，本文提出了一种基于多精英灾变策略的遗传算法。其中，引入了一种动态调整交叉概率和变异概率的方法，使其变化更加符合算法搜索的规律；采用了一个精英组来存放种群中最优的基因，并在算法陷入局部最优时，根据不同的收敛状态对精英基于采取不同的灾变策略；通过实验的方法确定了触发灾变的参数取值，既全局最优解最大的不变代数。最后通过一系列标准测试算例进行计算，验证了算法的有效性。关键词：柔性作业车间调度；灾变策略；精英组；遗传算法中图分类号：TP18 15 Flexible Job-Shop Scheduling Problem using Improved Genetic Algorithm TIAN Min, LIU Renjing (School of Management, Xi'an Jiaotong University, Xi'an 710049) 20 25 30 Abstract: Flexible job-shop scheduling problem is the deepening and extension of classic JSP, which provides a more practical scheme for the resources limited job-shop scheduling problem. This paper proposes a improved genetic algorithm based on multi-elite catastrophic strategy according to the characteristics FJSP. Introduce an approach of dynamic adjusted crossover probability and mutation probability, make its changes more in line with rules during search of GA. Use an elite group to store the most excellent genes, and select different catastrophe strategy for elites according to different state of convergence when algorithm falls into local optima. Determine the parameter value used to trigger catastrophic strategy by experiment, which is also the largest times that the optimal value doesn’t change. Finally, the validity of the improved algorithm is demonstrated by a series of standard examples. Key words: flexible job-shop scheduling problem; catastrophic strategy; elite group; genetic algorithm 0 引言作业车间调度问题(Job-Shop Scheduling Problem, JSP)是所有生产调度中最复杂、最困难，也是最具有普遍性的问题之一，是典型的 NP-hard 问题。作业车间调度相应的优化是先 35 进制造技术和现代管理技术的核心，国内外很多学者进行了研究，但是多数研究是针对经典作业调度问题的优化[1-2]。在传统的作业车间调度问题中，每个工件的加工工序是预先确定的，并且每一道工序的加工机器和加工时间也是预先确定的。然而在实际的生产活动中，每道工序的加工机器往往是不确定的。每个工件的每一道工序可以在多个可选择的机器上进行加工，并且选择不同的加工机器所需要的加工时间也不相同。这类问题就是柔性作业车间调 40 度问题(Flexible Job-Shop Scheduling Problem, FJSP)。FJSP 不仅减少了对机器约束，而且扩大了可行解的搜索范围, 增加了问题的难度。基金项目：教育部博士点基金(20120201110068）；作者简介：田旻（1986-），女，陕西西安人，西安交通大学博士研究生；主要研究方向：作业调度，算法优化通信联系人：刘人境（1966-），男，教授，博士生导师，主要研究方向：知识管理，战略管理，资源调度. E-mail: renjingl@mail.xjtu.edu.cn - 1 -

中国科技论文在线 http://www.paper.edu.cn FJSP 是经典 JSP 的扩展，它不仅需要确定工序加工的顺序，还要给每个工序分配机器，因此是比 JSP 更加复杂的 NP-hard 问题[3]。目前，解决的方法主要分为两类：精确方法和近似方法。精确方法用来求解小规模的 FJSP 问题，包括分支定界法、整数规划法等。近似方 45 法主要采用启发式算法在较快的时间内得到问题的较优解，目前常用的方法有模拟退火（SA）[4]、禁忌搜索（TS）[5]、粒子群算法（PSO）[6]和遗传算法（GA）[7-9]。由于遗传算法具有通用性强，计算性能优良，具有隐含并行性和较好的全局搜索能力等特点，因此在 FJSP 的求解中得到了较多应用。杨晓梅等[10]和 Wang Y M 等[11]在遗传算法的染色体编码上进行了改进；张超勇等[12]在遗传算法的流程逻辑上进行了改进；陈刚等[13]在遗传算 50 法求解的关键路径上进行了改进。然而遗传算法在运行中随着多样性的丢失，仍存在着爬山能力差，局部搜索能力差，容易陷入早熟收敛等缺点。本文对 FJSP 采用了遗传算法编码求解，针对遗传算法在迭代过程中多样性逐渐降低的特点，引入了一种动态调整交叉概率和变异概率的方法，使其在陷入局部时能增加个体变化的力度；采入了多精英主体来存放最优的种群基因，并在算法陷入局部时，根据不同的情况对精英主体的编码采取不同的灾变策略使 55 其以更大的概率跳出局部最优解；最后通过一系列的基准算例验证了算法的有效性。 1 柔性作业车间调度问题的描述柔性作业车间调度问题可描述如下：个需要被加工的工件为，需要在台机器上进行加工。每个工件包含一道或多道加工工序，工序顺序是预先已经确定的，每道工序可以在不同的机器上加工，工序加工的时间随加工机器的不同而不同。调 60 度的目标是为每道工序选择最合适的机器、确定每台机器上各个工件的最佳加工顺序以及开工时间，使整个系统的某些指标达到最优。此外，在加工的过程中还需满足以下约束条件。 (1) 同一台机器在同一时刻只能加工一个工件。 (2) 同一工件的同一工序只能在同一时刻被一台机器加工。 (3) 每个工件的每道工序一旦开始就不能中断。 65 (4) 不同工件之间没有优先级之分，不同工件的工序之间也没有先后约束。 (5) 同一工件的工序之间有先后约束，只有其紧前工序完成且请求加工的机器空闲新的工序加工才能开始。 (6) 所有工件均可在零时开始加工。一个 3 个工件在 5 台机器上加工的柔性作业车间调度实例如表 1 所示，其中“-”表示不 70 能选择对应的机器进行加工或不存在对应加工工序。本文考虑以下两个常用的性能指标：最大化完工时间（Makespan）最小，使得加工的任务尽快完成；最大化机器负荷（Workload）最小，防止某一个机器加工太多而过度损耗。表 1 柔性作业车间调度问题加工时间表 Fig.1 Flexible job shop scheduling problem processing schedule 工件工序加工时间 M1 M2 M3 M4 M5 O11 O12 O13 O21 3 - 1 - J1 J2 5 2 4 - 4 9 2 - 6 - 3 - - 3 3 2 - 2 - n1{,}nJJ,m1{,,}mMMmaxCmaxW

中国科技论文在线 O22 - O31 O32 O33 J3 2 - - 2 http://www.paper.edu.cn - - 3 2 - 5 - - 5 - - - 6 - - 6 - - 4 - 设是工件的完工时间，是机器上的负荷，相应生产能力约束条件下柔性作 75 业车间调度问题的目标函数如公式（1）和（2）所示：（1）（2）其中，（1）式表示在多次求解该问题后 n 个工件中完成时间最大的一个的最小值，（2）式表示多次求解该问题后 m 个机器中负荷最大的一个的最小值。 80 2 改进遗传算法求解柔性车间作业调度问题 2.1 编解码设计 1）扩展的基于工序的编码正确的编码是遗传算法能够成功实施优化的首要和关键。传统的 JSP 采用基于工序的编码，具有任意置换染色体后总能得到可行调度、避免死锁和对解空间表征具有完全性等优点。 85 基于工序编码的染色体中每个工件的工序都用相同的工序号表示，从左到右扫描染色体，第 k 次出现的工序号就表示该工件的第 k 道工序。然而，FJSP 不仅需要确定工序的加工顺序，还需要为每道工序选择一台合适的机器，所以仅采用基于工序编码的方法并不能得到问题的解。因此，本文采取了基于工序和机器相结合的编码方法。该编码由两部分组成，一部分是基于工序的编码，用来确定工序加工的先后次序；第二部分为基于机器的编码，用来选择每 90 道工序的加工机器。其中，基于机器的编码并没有与基于工序的编码相对应，而是按照每个工件的加工次序排列，这种编码方式一方面有利于交叉后能产生可行解，同时也便于工序确定其加工机器。综合这两种编码方式，就得到了 FJSP 的一个可行解。图 1 是一个扩展了的基于工序编码的染色体，该染色体由基于工序编码的基因和基于机器编码的基因组成。其中基于工序的编码基因决定工件的加工顺序，基于机器的编码基因决 95 定加工工序所选择的机器。图 1 中所表示的加工顺序以及加工机器序列为（O11，M1），（O21， M2），（O31，M2），（O12，M2），（O22，M5），（O32，M3），（O33，M1），（O13， M4）。 100 2）解码图 1 扩展的基于工序的编码 Fig. 1 extended coding based on process order 解码是将基于工序编码和基于机器编码的染色体转换为可行的调度解的过程。设为一个包含了工序编码和机器编码的染色体，其中某一个工序为，加工时间为，且工序的 - 3 - iCiJjWjM1minmax,1,2,,ifCin2minmax,1,2,,jfWjm1231233112425231Job1Job3Job2基于机器编码的基因串基于工序编码的基因串uijOup

中国科技论文在线 http://www.paper.edu.cn 紧前工序为，请求机器的紧前加工工序为，若该工序开始加工的时间为， 105 则完工时间为，其中由和结束时间的最大值决定。所有工件均可以从 0 时刻开始加工，解码过程中的开始加工时间如公式（3）所示。如果请求加工工序不存在紧前工序或者请求机器的紧前加工工序，则对应项为 0。此外，本文还采用一种插入式贪婪解码方法。首先将已经解码的染色体的工序的开始和 110 结束时间在时间轴上进行排列，将新来的工序插入到该工序可选加工机器上的最佳可行加工时段，如此直到所有工序都安排在最佳可行加工时刻为止。假设此时请求的机器上有一个空闲时间段为，其中且，既该请求机器上的空闲时间段满足请求工序加工的时间长度且开始时间不早于其紧前工序的完成时间，则将该工序请求插入机器空闲时间段之间，重复此过程，直至产生满足生产约束的主动调度解。（3） 115 2.2 遗传算子 1）选择算子遗传算法根据对个体适应度的评价，选择优异的个体进行繁殖，淘汰劣质个体。由于本文的适应度值是关于最小值的求解，因此传统遗传算法关于适应度值最大的轮盘赌选择方式并不适合。因此，本文采用另一种锦标选择的方式，既随机的从种群中选择两个个体并产生 120 一个之间的随机数，如果（其中为提前设置的选择概率，一般设置为 0.8），则选择适应度值较小的一个个体，否则选择适应度值较大的一个个体。此种选择是有放回选择，能在保证种群多样性的前提下较多地选择较优个体。重复此过程，直到产生个个体为止。 2）交叉算子 125 传统的遗传算法的交叉算子是对两两配对的染色体以一定概率按某种方式互相交换部分基因，从而形成新的个体。这种方法在算法执行不同阶段都采用相同的交叉概率，降低了算法跳出局部解的力度；另一方面，互相交换部分基因的方法并不适合本文研究问题，因为这样会产生大量的非有效解。鉴于以上两个原因，为了使算法能在搜索时期稳定进行，陷入局部最优的时期可以尽量跳出，本文采用了一种动态调整交叉概率的策略。既每次经历一轮选 130 择、交叉、变异后，比较当前的最优解是否小于全局最优解，如果是，就将交叉的概率设置为一个预先确定的初始值；否则就适当的调整交叉的概率，使其在原来的基础上增大一些（如果已经到上限，则不再增加），交叉概率的调整范围为[0.8，0.95]。详见图 2，其中代表交叉概率，代表变异概率，代表全局最优解最大不变次数计数器，代表全局最优解，代表当前最优解。 - 4 - []JPu[]MPuuSTuuSTpuST[]JPu[]MPuu[][][]max,uJPuMPuMPuJPuSTSTpSTp[,]abubap[]JPuJPuaSTp[,]ab(0,1)randsrandpspncpmpglbCounterbestValuetmpFitness

中国科技论文在线 http://www.paper.edu.cn 135 图 2 交叉概率、变异概率的动态调整策略伪代码 Fig. 2 Crossover probability, mutation probability dynamically adjust strategy pseudocode 基于工序编码的染色体采用常见的基于优先序的交叉操作。具体方法是先把工件划分为 140 两个集合，第一个子代的第一部分基因位来自于第一个工件集所对应的第一个父代里的基因位，第二部分来自于第二个工件集所对应的第二个父代基因的顺序填充。第二个子代正好相反，详见图 3。基于机器编码的染色体采用多点交叉操作。具体方法是产生一个长度和机器编码基因串一样长的随机 0、1 串，然后遍历该串，对于第一个子代，为 0 的地方来自于第一个父代基因，为 1 的地方来自于第二个父代基因；对于第二个子代，为 1 的地方来自于第 145 一个父代基因，为 0 的地方来自于第二个父代基因。图 3 基于优先序的工序基因串交叉操作图 Fig.3 crossover fig based on prioroty order gene cluster 3）变异算子 150 变异是为了维持群体的多样性，防止早熟现象而进行的一种操作，实际上是子代基因按某一确定的小概率产生基因突变的现象。然而在实际算法运行中，如果在迭代初期或者寻找局部最优的时候变异概率较大，就会破坏目前已经找到的最优解；如果在迭代中已经找到了局部最优或者陷入了局部最优，还采用较小的变异概率，则就很难跳出局部，甚至会陷入局部最优解。为了使种群在迭代过程中能根据迭代情况的不同更好的调整变异的力度，从而达 155 到对多样性更好的控制，本文设计了和交叉概率调整策略相似的调整方法，详见图 2。此外，基于工序编码的染色体采用随机交换两个不同基因位的方式产生变异；基于机器编码的染色 - 5 - cmiftmpFitnessbestValuebestValuetmpFitnessglbCounter0; = 0.8; = 0.05;glbCounterglbCounter+10.950.01;0.10.01;cccmmmppelseifpppendifpppendend ；；1231233113321213P1：P2：1331223113321213C1：C2：第一个集合{J1}，第二个集合{J2,J3}

中国科技论文在线 http://www.paper.edu.cn 体采用随机找到一个基因位，并把该基因位的机器替换成一个新的可选项的方式进行变异操作。 2.3 基于精英保留的灾变策略 160 当算法在迭代过程中不断的经历选择、交叉和变异操作时，有很大可能在中间某个步骤把优质解丢失。而这样的优质解有可能不止一个，他们以不同的形态围绕在最优解周围，所以一些文献中提出了在遗传算法中采用精英组来保存最优解的方法[14]。本文算法亦采取了一个精英组，用来记录种群中最优的数个个体。每当算法迭代一轮之后，根据目前种群的适应度值以及之前保留的精英组的适应度值，选择最优的个体更新精英组。这样不仅可以有效 165 地保留种群的最优个体不受迭代过程的影响而丢失，同时也可以尽量多的保存较优的个体而增加种群的多样性。灾变策略是模拟自然界中的物种灭绝现象[15]，为更优秀的物种提供繁衍机会的策略。由于遗传算法极易陷入局部最优解，因此在局部搜索已经充分时，增加种群的多样性，保留当前物种中的部分个体，消灭其他个体并重新生成新个体的灾变方式有利于局部最优解的跳 170 出和全局最优解的进一步查找。本文算法中，精英基因组在迭代过程中不断更新，保存了当前搜索到的全局最优的数个基因，是种群中最敏感的群体。考虑到灾变是毁灭性的，如果涉及的范围太大，则之前搜索到的结果都失去效用，灾变范围太小又起不到增加多样性的效果。因此本文算法考虑对精英组在一定的条件下进行相应的灾变操作。精英组代表了种群最好的一组状态，即使发生了较大的变化，由于种群的其他基因的记忆也会逐渐回复到一个较优的 175 状态；同时，对精英组进行灾变，种群最优的个体如果由于新基因的到来产生了更好的搜索结果，则会战胜其他基因的记忆而继续保持最优。本文算法为灾变条件设置了一个计时器，当全局最优解的值连续数代不变时，则触发灾变，灾变过程分两种情况：第一种是如果此时全局最优解的最大完工时间和最大机器负荷不相等时，则仅仅对精英组中基于工序的基因进行灾变，因为最大完工时间还可能取到更优的值，基于工序的基因还有在当前机器序列周围 180 继续探索的必要；否则如果全局最优解的最大完工时间和最大机器负荷相等时，就意味着算法已经在目前的机器序列中找不到更优的解了，此时需要对精英组进行更彻底的灾变，不仅需要对精英组中基于工序的基因进行灾变，还要对精英组中基于机器的基因进行灾变。常用的灾变方式有增大变异概率或重新生成等方法。精英组中基于工序的基因采取增加变异概率的方式进行灾变，基于机器的基因采取重新生成的方式进行灾变。详见图 4，其中代表 185 最优解的机器负荷的最大值，代表触发灾变的最优解的最大不变的代数。图 4 灾变策略伪代码 Fig. 4 Catastrophe strategy pseudocode - 6 - macWKif glbCounter > K; if != bestValue 1 else 1 endendmacmacWW计算以概率对精英组中基于工序的基因进行变异；将精英组机器的基因重替换为机器负荷最小的一组基因；以概率对精英组中基于工序的基因进行变异；

中国科技论文在线 2.4 改进遗传算法的流程设计 http://www.paper.edu.cn 190 结合以上描述的各点，改进遗传算法解决 FJSP 的具体步骤如下： Step1：初始化。包括种群规模 N，迭代次数 M，精英个数 EN，要解决的具体问题，触发灾变的最优解的最大不变代数等。初始化阶段需要针对具体问题产生规模为 N 的基因组（包括 N 个基于工序的基因和相应的 N 个基于机器的基因），并计算对应的适应度值，将其最优的 EN 个个体赋给精英组。其中最优的个体的适 195 应度值记为 bestValue，glbCounter 为全局最优解最大不变次数计数器，初始为 0。 Step2:判断迭代中止的条件是否满足，若满足则结束迭代，转入 step6；否则开始进行种群基因的选择、交叉和变异过程。 Step3:判断是否达到灾变的条件，如果达到，则进行灾变，详见图 4。 Step4:判断全局最优解是否改变，并进行相应的变量和参数的更新，详见图 2。 200 Step5:更新精英组的基因为目前阶段的所有个体中最优的一组基因。转到 step2。 Step6:计算全局最优解对应的最大完工时间和最大机器负荷，并记入数组 Cmax 和 Wmax。 Step7:在多次执行 step1-step6 后，求最小的最大完工时间 min{Cmax}和最小的最大机器负荷 min{Wmax}，并求其平均值，一起作为最后结果的输出。 3 计算结果与分析 205 为了验证改进遗传算法求解 FJSP 的性能，本文采用 Windows 7 系统，CPU 主频为四核 2.79GHz，内存 4.00GB，在 Matlab R2012a 上编写改进遗传算法程序，寻找最优解的调度方案。本文选取了比较普遍的 Brandimarte 标准测试算例进行了实验，其中包括 10 个测试问题（MK01-MK10），工件数 10 到 20 个之间，机器数 4 到 15 个之间[9]。实验的参数设置为：交叉概率的范围是[0.8,0.95]，变异概率的范围是[0.05,0.1]。实验分 210 为两组：第一组用来确定触发灾变的最大不变代数的取值，选取 MK01 测试算例进行分析；第二组用来验证改进算法的优越性，选取 MK01-MK10 所有算例进行计算，并和几个同类文献的相同算例计算结果进行分析和对比。 3.1 的确定算法运行过程中，种群规模 N=100，最大迭代次数设置为 100，精英基因取 10 个，K 215 取 1-10，每次不同的 K 算法运行 10 次，求最大完工时间和最大机器负荷的最小值和平均值，结果如表 2 所示。由表 2 可以看出，K=7 时算法的收敛结果是最好的。除个别值的少量波动外，在 1-7 之间，结果大体是递减的趋势，7-10 之间又有增大的趋势。K=7 时最大完工时间和最大机器负荷的最小值和平均值都达到最小，因此本文算法在后面的测试中令 K=7。图 5 是 K=7 的 220 时候 Mk01 函数计算的调度结果绘制的甘特图，其中横轴代表时间，纵轴代表调度的机器。每一个具体的工序都以“工件号+工序号”的形式标在下方，例如“101”就代表第十个加工工件的第一道工序，“95”就代表第九个加工工件的第 5 道工序。 225 - 7 - KKK

中国科技论文在线 http://www.paper.edu.cn 表 2K 值变化时 MK01 函数测试结果 Tab. 2 result tested by MK01 function with differnt k Cmax Wmax avg(C) avg(W) 40 41 40 40 40 40 40 41 41 42 36 37 36 36 37 36 36 37 36 42 41.7 41.7 41.6 41.5 41.7 41.5 41 41.8 41.8 42.3 40.9 41.5 40.9 40 41 40 39.3 41 40.8 42.1 K 1 2 3 4 5 6 7 8 9 10 230 图 5 Mk01 测试函数甘特图 Fig.5 gantt chart of Mk01 test function 3.2 改进算法结果分析 235 算法运行过程中，种群规模 N=300，最大迭代次数 300，精英基因选取 30 个，算法运行 30 次，并分别和标准遗传算法（SGA）以及文献[8]中算法的结果做比对，如表 3 所示。由表 3 可知，本文提出的改进遗传算法在解决生产能力约束条件下柔性作业车间调度问题时全面优于传统的标准遗传算法（SGA），对于 MK03，Mk09 问题的算例比文献[8]更好，对于 MK05 问题，本文改进算法找到了更优的解。图 6 是 Mk05 测试函数最优计算结果所对 240 应的甘特图，横轴代表调度的时间，纵轴代表调度的机器，每道工序以“工件号+工序号”的形式标在图上。由图 6 看以看出，在 173 个时间单位的调度中，四个机器的总调度时间相差不大，第四个机器调度时间最长，没有空闲时间段，其调度时间 173 为调度总时间。 - 8 -

分享到：

赞收藏

资料库

改进遗传算法解决柔性作业车间调度问题.pdf

相关推荐

开发技术

热门标签

最新资料