面向柔性作业调度问题的启发性规则改进遗传算法

本资料包含pdf文件1个，下载需要1积分

A Hybrid Genetic Algorithm for Flexible Job-Shop Scheduling ProblemShuai Qi .Yao Xi.fan(1.Guangdong Institute of Science and Technology，Zhuhai 519090，China；2.School of Mechanical&Automotive Engineering，South China University of Technology，Guangzhou 510640，China)Abstract：The flexible job-shop scheduling problem(FJSP)is addressed and a hybrid genetic algorithm(GA)is proposed to solve this problem.A heuristic is used to create a set of relatively good schedules forthe problem，from which the initial population is created by selecting the relatively good ones.Further-more，priority rules are integrated into crossover，mutation，exchange，and selection to avoid that it con-verges to a local optimum.In this way，a better solution can be obtained.Benchmark FJSPs are used totest the proposed method and comparison with some existing approaches is done.Results show that it is ef-fective and eficient f0r solving FJSPs。

Key words：flexible job-shop scheduling problem；heuristic；genetic algorithm柔性作业调度问题 (flexible job-shop problem，FJSP)是制造系统研究中的热点之-。FJSP属于NP.Hard问题，随着问题规模的增大，如何减少计算量，同时保证收敛，得到优化解是求解较大规模 FJsP所需要解决的问题↑年来对于 FJsP求解方法主要集中于粒子群改进算法 也j、改进遗传算法 引、混合算法 墙 等进化算法。FJSP由于工序机床选择的多样性存在大量可行解。利用传统粒子群或基因算法进行求解，难以避免搜索过程中的大量无效搜索，直接影响了求解效率及求解稳定性，对于较大规模复杂的FJsP问题求解困难。文献[9]按照求解难度对调度问题的规镍行优化，划为若干批量进行求解。以上文献都只是对 15×10及以下批量问题进行了求解。在调度问题求解中将启发式规则与进化收稿日期：2012-02-22基金项目：国家863计划资助项目(2007AA04Z111)作者简介：帅旗(1974.)，男，江西省人，讲师，硕士，主要研究方向为数控和机械制造32 工 业 工 程 第 l6卷算法结合能提高求解效率及求解稳定性。文献[10]验证了将启发式规则与遗传算法结合在流水线加工问题求解中能提高计算效率，同时能得到较好的求解结果。文献[11]将启发规则与遗传算法进行结合对工作流动态调度问题进行了求解。文献[10]将启发式规则应用于初始解的产生，文献[11]将启发式规则应用于染色体适应值大小的比较，而对于遗传算法中其他操作如变异、交换操作中的启发性规则的应用以上文献并未介绍。本文对柔性作业调度求解 ，利用基于启发式规则产生初始解，同时采用改进遗传算法应用启发性规则对算法中的交换、变异操作加以引导，对 25×10及 23×10较大型问题进行求解，同时将此方法与其他求解方法进行比较。

1 FJSP问题描述在 Job.shop多机生产系统 中，设定有 个工件需加工，有 个待延工机床，每个工件 (i1，2，3，， )有 G 个工序，G 个工序之间有工艺上的先后要求，工件的每道工序可由 台机床中的日台机床加工(M≥日≥1)。总工序数N∑G ，调度的任务是为每道工序选择合适的机床。为了简化问题，现假设：①所有机床在 t0时刻都可用；②所有工件在t0时刻都可被加工；③所有工件的工艺计划是固定不变的，即工序的先后顺序不能变动；④加工是非抢占式的，即工序的加工过程不允许中断，在给定时间段内，机床同时只能加工-个工件，只有当前工序结束后才能开始加工别的工序H 。

调度的目标为mi，m ax，(C )， (1)M mi ， (2)klmi.ma蔓，( )。 (3)式(1)-(3)分别为工件总完工时间(用 makes。

pan表示，c 为工件， 的完工时间)、机床加工总负M荷(用∑ 表示， 为机床k的加工负荷时间)，间 GS ，同时确定工序的完工时间 GE 工序的调度求解在本文分为 2阶段，第 1阶段产生初始解，第2阶段对初始解进行优化计算得到最终优化解。由于启发式规则具有计算效率高的特点，本文采用启发性规则进行初始调度的产生。其具体方式如下：由于工序需要按工艺顺序加工，从启动时间 t：0开始，只有工件的下-个未进行分配工序(在此简称为紧后工序)才能进行机床的选龋其对机床选壬按指标大续行，用 g ， 来表示工序 0 选择机床进行加工的指标值。

g ， 1× "4-W2 X( - )，W1W21。 (4)式中，T1max(JF ，GE -1)-GE - ，表示如果工序 O 选择机床 加工，工序 O 与其前-工序Of.- 。之间的加工等待时间，当 1时为 GE 0，JF 为机床 Mk当前工序完成时间；。

为工序 D 可选择最短的机床加工时间，Tid，k为工件的第 工序在机床 上加工所需要的时间； 和W：为加权系数。如有某机床 ，使式(4)取值最小，则此工序就以机床 作为选择 目标。各工件都有其紧后工序，用式(4)进行机床选取时，可能存在不同工件的工序选择了相同的机床 ，且加工时间重叠情况，此问题可用优先权的方式进行解决。以工件最小的可能剩余加工时间Is 为指标进行选择。如工件.， 已有J-1个工序完成了机床及加工时间分配，其加工工序共有G 个，则GiS qm × min(T/，fl，， ，fI2，， lf'M)。(5)fJ式中，qi，h为修正系数(h表示修正次数)，其计算见式(7)。S 数值大的工件可优先选择此机床。如工件工序 O 选择了机床 进行加工，则GS max(JF ，GE -1)，GE，fmax(JF ，GE ，-1) ，f. 。

此时对JF 值进行更新，有JF GE 。综上所述 ，初始调度过程可以看作从 t0开始，利用式(4)和式(5)按顺序对工序的加工机床选取，直至所有工序都选择到相应加工机床，O 所选择的加工机床用表示。

以及单个机床负荷最校2 初始调度过程描述 3 优化过程描述初始调度过程是基于工序的局部取优过程，其对于FJSP问题，其加工工序D (表示工件 第加工工序)可选择的加工机床不为唯-，调度安排需分配工序 D 的加工机床 及工序的开始加工时初始调度结果需要进-步优化。对于初始调度结果的优化搜索，利用改进遗传算法的交叉、变异、交换规则进行。

第 1期 帅 旗，姚锡凡：面向柔性作业调度问题的启发性规则改进遗传算法 333.1 染色体编码构成以表 1中有6个工序 3×4调度问题为例，其某种调度结果可由染色体编码组 P 和 P 表示，P 为各工件的加工顺序。如P 3，1，2，1，3，3，表示表 1中所有6个工序的加工顺序为0 .。，01.1，0 . ，0 -2，O3-2，03.3。P2为工件工序所延工机床，如P23，1，1，2，3，1表示 k3.13，k1.11，k2.11，k， 2，k3.：3，k， 1。P。和P 中各有 6个代码，可确定各工件工序的加工顺序及加工机床。如果调度问题有 Ⅳ个加工工序，则P 1.1， -2'， 。。

，P： .1 .2， . ，整个基 因串表示为 P。，P 。而用YY：.。，Y -2，，Y . 表示按工件编号及工序先后排序，工序所选的加工机床集合。对应于基因代码 P 3，1，2，1·，3，3，P 3，1，1，2，3，1，则 Y的集合为 Yk1.1，k1'2，k2，1，k3.1，k3.2，k3，3 1，2，1，3，3，1。

表 1 3×4柔性作业调度Tab.1 3×4 FJSP3.2 初始种群选定由初始调度过程可知，通过设定不同的参数 W和W 值可得到不同的初始调度解。W。和W 值可按式(6)进行计算。

Wt1-i/n，W2b， i0，， 。 (6)当n大小确定后，i：(0，，I)可产生 n1组W 、W：，将其代入式(4)和式(5)可产生到 n1个初始调度解。由于式(5)中s 的计算是基于假定基础上，即每个加工工序都选择加工时间最短的机床进行加工。在初始调度产生过程中可采用修正系数qi，h对其进行修正，第 h次初始调度 g 为C，i Giq啪∑(GE l1-Gs 1)/∑min( ，fIl，f Z f 1.f12，，TilfI肘)。 (7)式中，GE 与 GS ， 分别为第 h-1次已排初始调度中工件 在第 f工序的完工时间与开始加工时间。采用修正系数g 可使W 和W：在某区域变化不大时，增加初始调度的多样性。

将所得 n1个初始调度解相互进行比较，比较分为指标值比较与相似性比较。第 个初始调度其指标为3 3g ∑WoF ，∑ 。1。 (8)其中， (1≤O≤3)为加权系数，具体数值的确定可根据决策者的偏好及调度问题实际需要来确定。

式中，maxfo与 mi 分别为所有调度解归档得到的第 。个求解 目标最大指标及最小指标 .。为第 i个初始调度对应的目标 O的指标值▲行相似性比较时引入欧氏距离 ，第 i个染色体与第 染色体，其染色体之间的欧氏距离为厂 -------- ---- d J/∑△ ， ∑△ ；h1 h1f1，， l， ≠ ， l， ，Ax1，h 10， ： ；fl，)，，2， ≠"，2， ，AY2，h i0，y啦 。

为第 i个染色体 P 组段中第 h位编码，Yi 为第 个染色体所对应的 集合第 位编，1，h Y h码。式中欧氏距离较大则两调度染色体相似性较校比较后保留其中日个指标较优解，同时此 日个解之间的染色体距离限定为不能小于 RM(RM为-设定的最小欧氏距离)。此日个解构成初始种群。

3.3 关键工序设定在进行基因操作计算前 ，首先将各工序按启发式规则区分为关键工序及非关键工序。对于某次初始调度其完工时间为makespan.m (C )，此调度关键工件集合设为JM：JM l-， 满足 C makespan，关键工件对应的所有工序 0 ( 1，2，，G )都为关键工序。

3.4 算法操作过程3.4.1 选择操作种群中每代染色体依据其适应度概率大小，采用轮盘赌法，随机选择进行基因的交叉、交换、变异操作～加权系数 代入式(8)计算种群中每个染色体个体的加权指标g ～染色体个体之间进行欧氏距离计算，并求出各染色体个体的适应度大小 ，其计算式为34 工 业 工 程 第 16卷 II k ×g 。

O1(o≠)式中， 为修正系数，表示为f ，/f(d .

当两染色体之问欧氏距离小于最小设定 RM值时，通过引入修正系数 降低指标较小个体的适应度。第 i个染色体个体选择操作概率值为pr ，pr Ⅳ/∑F 。对种群中的染色体个体按各自的概率值，通过轮盘赌法选择进行交叉、交换、变异操作。

3.4.2 交换操作对进行交换操作的染色体中的 Ⅳ个工序代码，按关键工序及非关键工序进行分类，赋予关键工序更大操作概率，依据轮盘赌法选定交换位。文中取关键工序交换概率定为非关键工序的5倍换过程首先按概率及轮盘赌法确定-组工序代码 及。。 其次搜寻另-组工序代码Xl及 2 ，，k k max/z f满足：(， 2， )八( ≠ 1.f)(Z

如能搜索到工序代码 X1，k及 . ，则代码 ，X2， i与代码 ㈨，。

进行位置交换。为了不破坏工件工序之间先后约束关系，需要判断是否有工序代码 ㈨ l-l，k

3.4.3 变异操作将进行变异操作染色体中的Ⅳ个工序代码，按关键工序及非关键工序进行分类，赋予关键工序更大操作概率，依据轮盘赌法选择变异位。如选定 及 X2，i作为变异代码，在变异过程中 Ct，i及 X2，i在 P及P 中的位置保持不变，只对 ：. 的数值进行变异，即改变工序的加工机床。变异过程按概率大小依据轮盘赌法随机确定。如代码 及 . 对应于工序0 ，变异过程中机床 的选择概率P 为P ： k≠ 2. ， (9)∑i1r1/ ，其他； pm/r ，当( ≤ ，J，X2，1)八( ≤m kespan)。

如工序Ohj加工机床变异为 使得 >makespan，则变异后调度结果的指标 l及指标 3都将变大。式中，设定 pm>1，为放大倍数，以此增大加工时间短及机床总负载小的机床的变异选择概率。

单个变异操作染色体操作次数为numberrandom(1，ceil(0.1×Ⅳ))。

3.4.4 交叉操作通过选择操作选择 2个不同染色体 P ，P l及P ，P 进行交叉操作叉过程为随机确定-工序 O ， random(1，L)， random(1，G )。找到此工序对应在基因P ，P：及P ，P 中的代码位置K， 。如果kk ，则将两基因中的工序加工机床对调：f 2 2。

2 ， 2，， t。如果k≠lc 首先将两基因Oi加工机床进行对调，其次将基因 ，，j P P位置为 k的代码 。， ，。

与位置为 k 的代码 及X2，k'进行位置交换，同时也将基因P。 ，P： 中代码。

t2， 与 ，、 ，进行交换换过程如前述，在保证工件工序加工顺序的前提下，进行平移交换。

染色体 交叉操作次数 由式 number random(1，ceil(0.15 XⅣ))确定。

3.4.5 染色体存储对于染色体，构造存档编码与计算编码存储。当有 日个染色体个体的初始种群产生后，将此日个染色体个体作为最初的存档编码存储。P ，P 表示第 i个染色体个体的存档编码。对存档编码 P ，P 进行交换、交叉或变异操作，则产生计算编码，P ，P 表示第 i个染色体个体的第 h代计算编码。当每代计算编码产生后，将加权系数 (1≤o≤3)代入式(8)计算其加权指标g ，与染色体个体 i对应的存档编码加权指标g 进行比较。如果g >g 叭，则有 p ：p ，将存档编码进行更新。如果kdxg”1)，为防止计算基因搜索过程偏离较优区域转向较差区域，出现无效搜索现象，令 P P P ，将计算编码用存档编码进行替换。存储过程及整个算法的流程图如图 1所示。

第 1期 帅 旗，姚锡凡：面向柔性作业调度问题的启发性规则改进遗传算法 35随机产生加权参数 。， ，0)3，计算各染色体的适应度及概率，轮盘赌选出操作染色体搜索此染色体的关键工件及关键工序赋予关键工序较大概率值，对所选择染色体进行交换、变异、交叉操作产生下-代计算编码将计算编码与此个体对应的存档编码进行染色体标比较 ，以决定是否更新存档编码或替换计算编否 叁 图1 算法的流程图Fig.1 Flowchart of HIGA4 调度求解对于 FJsP问题的求解步骤如下。

1)设定 n值，由式 (4)、(5)和(6)应用启发式规则产生 几1个初始调度解。

2)对于n1个初始调度解，进行指标 比较及相似性比较，保留其中日个解构成初始种群。

3)对种群中各染色体按启发式方法搜索关键工序，并按算法操作过程进行优化搜索操作，并更新操作染色体存档编码或计算编码。

结合文献[12]的8×8和 10 X 10问题以及文献[15]中的 15×10问题进行实例求解。对于 8×8、10×10、15×10问题的求解 ，取 10.5，c，20.2，∞ 0.3首用启发式规则产生200个初始解，进行比较后得到规模 H30的初始种群，迭代次数设为200，对种群中染色体进行优化搜索。应用本文方法计算 10×10、15×10、8×8问题的求解结果如图2～图4所示 ，与其他方法计算结果比较如表2-表5所示。其他方法所用比较数据都为在相应文献中的引用数据。其中CGA法表示复合遗传算法 12]；PSOTS1 表示禁忌粒子群复合算法；PSOGAl6 表示粒子群基因混合算法；MIGA3 表示混合遗传算法。本文算法命名为 HIGA(heuristic improved genetic algo-rithm)。对于更复杂 FJsP问题求解，本文将 15×10问题与8×8问题组合成23×10共83工序的调度问题，其中原 8×8问题中的 8个工件在此调度中编号为 16-23，原 8 X 8问题所有工件工序对机床 M。及M 。都设定为不可使用。而将 15×10与10×10问题组合成25×10共 86工序的调度问题，其中原 10×10问题中的 l0个工件在此调度中编号为 16～25。

2个组合后的调度问题，用 HIGA方法进行计算。在计算中用启发式规则产生 300个初始解，进行指标及相似性比较后得到规模 H40的染色体种群，迭代次数选为 300，平均计算时间分别为22 S与20 S。

23×10问题调度结果如图 5所示，makespan18，W166，max( )18小于合并前的15×10与8×8时间 l 2 3 4 5 6 7 8 9 1O ll 12机亲 l l I I I I l I I l I I l 1.1I 2.1 1 l1.2l 8.2 l 8.3 ll 兰： k：三l弭 匝圆 AA 10 l 6.1 1 A卯 匝圈 摆 囡 5.1 l5 6.2 I6.3I 10 3 1l t2.2l 2.3 I图2 10×10调度问题(HIGA)Fig.2 Optimization solution of 10×10 FJSP(HIGA)时间 l 2 3 4 5 6 7 8 9 l0 l1棚 器 I J I l I l l I l l IM 14.1 l 1.1I 7.41.216.2I 10.2J)L 13.1 1 3.3 l7.2l 13.4 l1 10.4 lI 9.2 I 2.2 l1.3l l3.4l 8.3 l 5.4 l 4.1 l4.2l 12.2 l 4rl 5l 4l l 5.2 91.2l4.3l 15 2 I 12.3 I肋7 3.18.1l1.1l 5.3 l 9.3 l 12.4 l招 12I 1 I8.2l 15.1I 14.3l I 5.113.2I 14.2 l1.3 I 1 4 IMO 9.1[10.4 13.2 l 13.3 I4.412.31o.3I 9.4 l图 3 15×10调度问题(HIGA)Fig.3 Optimization solution of 15×10 FJSP(HIGA)36 工 业 工 程 第 16卷日寸问 1 2 3 4 5 6 7 8 9 10 ll 12 13 1机密 l l l l l I I I l l l I I I l 5.1 l 8 1 lA I 8.2 I 6.3 I 6.1l 7.1 l 2.1 l 4.3 l r .4 I拼 1.1 l 3.2 l 2.2 l l 7.3 ll 1.2 l I 2.4 I拓 I 4.2 l 1.3 l I 5.3 I卯 j ll I 5.2 12.3l r 5.4]A擂 I 6.2 l 7.2 l8.7图4 8×8调度问题(HIGA)Fig.4 Optimization solution of 8×8 FJSP(HIGA)表 2 8 x8问题结果比较Tab.2 Comparison of results on problem 8×8表3 10×10问题结果比较Tab.3 Comparison of results on problem 10×10表4 15×10问题结果比较Tab.4 Comparison of results on problem 15×10问题的 makespan之和。25×10问题其计算结果为makespan14，W134，max( )14，也小于合并前 15×10与 10×10问题的 makespan之和，如图 6所示。由于启发式规则的引入，使得求解稳定性也得到了保证。以较复杂的 15×10，23×10，25×10问题为例。采用 HIGA方法计算 15×10问题 10次有 7次结果指标收敛于(11，11，91)；计算 25×10问题l0次也有7次收敛于(14，134，14)；计算23×10问题 10次有 6次收敛于(18，166，18)。

以上计算在 2.0G CPU上完成，计算时间对比如表 5所示 。

表5 平均计算时间比较Tab.5 Comparison of computing time s 1 2 3 4 5 6 7 8 9 10 l1 12 13 l4 15 16 l7 l8 19 2Cl l l I I I l l l I I I I l l I I I I ll 14.1 l1I1l 201 l10.271I 231l6.2l 2I 8.3 8 4lA 13.1 l9jI6.1 3.3 I 21 3 I7 2I 23 2 I13.4 IA 2117 1 I 2 1 l 9.2 I 15 3 I 11 3 I l13l 19.3 lM4 l1 7l2 I 20.2 I 18 2 I 2 3l4IMs 4.14 2I 12 2 l 16 2 l 14 4 I 15 4 l l7.4 3 I 5.2 l4.3I 19.2 I1 4 20 3 l16 3 l 5 4 I18 1 l3 12 1l 5.3 I8.17j 9.3 l 20 4 I 12 4IM8 15 1 I 21 2 I 14 3 18.2I 22 2 l 羽 b2I l4 2 I 15 2 I 12 3 l I 1.4 I 1l4 I 1O 12 1 J9.10 Il 4 2.2 J 13 2 J 13 3 J2.3144oj 9.4 J 10 4 l图5 23×10调度问题 (HIGA)Fig.5 Optimization solution of23×10 FJSP(HIGA)时间1 2 3 4 5 6 7 8 9 10 11 12 13 14 15机 l l I l l l I I l I I l I l I 1 17.1川1 l41 I2.1l 7l1l 2 l6.2161I 13.42 6.1 l13.1 I 23 2 I 3 3 I 23.3 I 19.2 l7l2l1 4l 3 25.1I 2 4 15.2 l 9.2[2 2l 2.2 l1 3 17.3 I 4 21 l 72J 25 3 I 2j 8 3 l3.416 19 20j23l l41[4 2l 12.2 I 15.4 l 14.4 f 6 21.1 I 5，2 I 15.3 l12[4 3l 12.3 l 5.4 I卯 3 1 8 1 3 2H 5.3 I 9 3 I 12.4 I招 15.1 f 19.I 20 2 H2 21.2 I 21.3Il4IM9 5.119 4 2010.2I 14.2 I 21.2 21j l 4 lM1O 9.118 41 o1I 13.2 I 13.3 I10j 10.4 l2.314 4I 94 I图6 25×10调度问题(HIGA)Fig.6 Optimization solution of 25×10 FJSP(HIGA)5 结论实际工作环境中FJSP问题常常规南大，同时对调度方法的求解速度及稳定性要求较高。本文提第 1期 帅 旗，姚锡凡：面向柔性作业调度问题的启发性规则改进遗传算法 37出了-种基于启发性规则的改进基因的求解方法。

通过实例验算表明，将启发性规则引入基因算法可大大减少传统基因算法的无效搜索现象，求解效果好，求解结果稳定。