基于关键工序的全局随机机器选择和改进GA求解FJSP

徐文星，王琴,2，边卫斌,2，王万红,2，董轶群



基于关键工序的全局随机机器选择和改进GA求解FJSP

徐文星1，王琴1,2，边卫斌1,2，王万红1,2，董轶群1

（1北京石油化工学院信息工程学院，北京 102617；2北京化工大学信息科学与技术学院，北京 100029）

以FJSP的最大完工时间作为优化目标，在考虑同一工件的工序顺序约束的同时，为提高初始种群的多样性，针对FJSP的机器选择问题采用堆栈方式存储工序。P-FJSP中只有一台机器可选的关键工序能直接影响机器总负荷和工件加工时间，进而提出了一种基于关键工序的全局随机选择（GRS）初始化方法。为了避免基本遗传算法在求解FJSP时陷入局部极优而停滞，在GA算法中加入再激活（re-activation）机制，旨在重新激活种群，增加种群的多样性。最后，针对FJSP基准测试算例进行数值分析，通过初始机器选择部分的性能对比实验、不同初始方式下遗传算法求解FJSP对比实验分别验证了GRS初始化机制的有效性和所提改进算法的可靠性。

柔性作业车间调度；优化；种群多样性；机器选择；GRS初始化机制；再激活机制；遗传算法；数值分析

引 言

关于柔性作业车间调度（flexible job-shop scheduling problem, FJSP）的研究具有很重要理论意义和实际应用价值。国内外学者采用不同的求解算法对FJSP做了深入研究，如禁忌搜索算法[1-3]、文化算法[4-5]、蜂群算法[6-7]、混合和声搜索算法[8]、粒子群算法[9-10]、细菌觅食优化算法[11]、遗传算法[12-28]等。智能优化算法各有优劣，而遗传算法作为一种鲁棒性强、通用性好、计算性能稳定的智能优化算法，近年来在FJSP中得到了广泛应用[28]。国内外关于应用遗传算法求解FJSP的研究主要在于其编码方式、遗传操作算子、解码方法以及与其他智能算法的结合等，而对种群初始化方法的研究成果不多。由于种群初始化能直接影响算法在整个进化过程的收敛速度和全局搜索能力，因而是智能进化算法中关键问题。目前，大多数的进化算法还都是采用随机方法进行种群初始化，这样会增加种群大小和迭代次数，从而导致算法的复杂度高、计算负荷大。张国辉等[24-27]提出了一种GLR(global local random)机器选择方法，其中GS(global selection)和LS(local selection)主要是综合考虑机器负荷和工序加工时间，尽可能均衡机器的利用率，从而缩短工序的最大完工时间。GLR初始化方法的提出，由于集中了不同机器选择方式的优点，因此改善了初始种群的质量，缩短了算法的优化时间。赵诗奎等[28]分析出极限调度时间能在很大程度上影响机器选择链初始种群的质量，提出了基于文献[24-27]中GLR初始化方法的改进机器选择初始化方法，综合考虑最大机器负荷和最大工件加工时间以优化FJSP的最大完工时间。张国辉等[24-27]提出的机器选择GLR初始化方法在选择工序时，是在既定的工件下，依次选择该工件的全部工序，这样会导致机器选择段的多样性不足。不同于张国辉等[24-27]的GLR初始化方法，赵诗奎等[28]所提出的初始化方法并未考虑同一工件中的工序顺序约束，而着重于增加种群的多样性，但所增加的初始种群并不能全部得到改善。

在考虑同一工件的工序顺序约束的同时，为提高初始种群质量和迭代过程中种群多样性，本文采用堆栈方式提出了一种基于关键工序的全局随机选择（global random selection, GRS）初始化方法及再激活机制，并通过对比实验以证明该方法在提高初始种群中机器选择段质量的同时，能够获得更加可靠的FJSP求解结果。

1 柔性作业车间调度问题的描述

柔性作业车间调度问题可通过如下方式描述：台机器需要加工个工件，第个工件的工序数为()，而每个工件的任何工序可以在台机器集的子集中的任意一台机器上加工，并且对应的加工时间随着加工机器的不同而不同。柔性作业车间调度问题的目标是在工序约束和设备能力约束的前提下，对所有工序进行机器分配和排序组合，以达到调度系统的优化目标最佳状态。

1.1 约束条件

（1）所有机器在=0时刻都处于可选用状态。

（2）任意时刻同一台机器只能对一个工件加工。

（3）同一时刻下，同一道工序只能在唯一机器上进行加工。

（4）每一工件的每道工序开始加工后中途不能中止。

（5）不同工件的优先级别相同。

（6）同一工件的工序之间有严格的先后约束关系，而不同工件之间不存在任何先后约束关系。

1.2 目标函数

本文中柔性作业车间调度问题的目标是优化调度系统最大完工时间。完工时间是指每台机器结束加工工序的最晚时间，其最大值即为最大完工时间。

数学表达式如下

2 改进遗传算法求解FJSP

2.1 遗传算子设计

2.1.1 FJSP的编码准则 针对FJSP两大子问题的强耦合性，本文采用集成整数编码方式，用整数表示染色体个体中的每个基因值，每一个体分为两部分：机器选择部分(machine selection，MS)和工序排序部分(operation sequencing，OS)。染色体的总长度为调度系统的工序总数的两倍，机器选择部分MS和工序排序部分OS的长度均为调度系统的工序总数。表1显示的是P-FJSP(partial FJSP)某一案例有关数据，表格中的数值表示工序在对应机器上的加工时间。图1对应于表1案例的一种染色体编码方案。

表1 P-FJSP实例

Note: “—” indicates that operation can’t be processed by corresponding machine.

（1）机器选择部分 机器选择部分MS是按工序排列的机器编码，将所有工件的所有工序选择的机器在其可选机器集里的位置序号，而不是机器号，按照各工件既定的先后约束关系从左到右依次存放在MS的相应位置。

以表1所示的P-FJSP为例说明MS段编码方式。该案例=2、=5、To=5，染色体MSOS的长度为10，MS和OS长度分别为5。MS段从左到右依次表示工序1112212223所选择的加工机器在可选机器集中的位置序号。如MS染色体中11对应位置存放的基因值4，表示11在其可选机器集{12345}中选择的机器4在其可选机器集中的位置序号是4。MS染色体中12对应位置存放的基因值1，表示12在其可选机器集{24}中选择的机器2在其可选机器集中的位置序号是1。如图1左半部分所示。

（2）工序排序部分 工序排序部分的每一数字代表一个工件号，而该工件号在OS段出现的次数则代表该工序是对应工件的第道工序。以表1所示的P-FJSP为例说明OS段编码方式。OS段的长度为工序总数To=5。OS段的数值依次为2、2、1、1、2，表示加工工件的顺序是22112，加工工序的顺序是2122111223。如图1右半部分所示。

2.1.2 初始化机制 在考虑同一工件的工序顺序约束的同时，为提高初始种群的多样性，本文采用堆栈的存储方式将所有工序依次存放在个数组中，每个数组表示一个工件，并从上至下依次存放工序数由小变大的工序。随机选择一类工件，选取该数组当前存放的第1道工序，对该工序进行机器选择，并存放在MS相应的基因位置处，随后删除该工序。循环进行，直至所有工序的机器选择完毕为止。

本文将只有一台可选机器的工序称之为关键工序。考虑到关键工序对机器负荷和工件加工时间有很重要的影响，本文提出了全局随机选择GRS初始化机制优先对关键工序进行机器选择。GRS初始化机制的算法步骤如下。

（1）基于堆栈的思想，将所有工序依次存放在类数组中，每类数组含两个cell数组：J-only和J-muti。J-only中存放该工件只有一台可选机器的工序，J-muti存放该工件中有多台可选机器的工序。两者的存放规则都是从上到下依次存放工序数变大的工序。

（2）随机产生1～中的某个数字，即为工件号，选该工件号J-only数组中的第1个元素作为当前操作工序，并从该J-only数组中删除该工序。由于J-only数组中的工序可选机器唯一，则在MS段所选工序的基因位置处直接赋值为1。按照张国辉等[24-27]提出的GS初始化方法计算当前的机器负荷数值，机器负荷数组MT不清零。循环步骤（2）直到对类J-only中的工序进行机器选择完毕为止。

（3）随机产生1～中的某个数字，即为工件号，选该工件号J-muti数组中的第1个元素作为当前操作工序，并从该J-muti数组中删除该工序。按照张国辉等[24-27]提出的GS初始化方法计算当前的机器负荷数值，为当前工序选择最优机器，并存放在MS相应的基因位置处，机器负荷数组MT不清零。循环步骤（3）直到对类J-muti中的工序进行机器选择完毕为止。

针对FJSP中机器选择部分和工序选择部分的强耦合性，本文采用GRS方法对所有工序进行机器选择，随机方法对所有工序进行排序，这样就完成了染色体MS段和OS段的初始化。

2.1.3 再激活机制 基本遗传算法具有很强的全局搜索能力，但是在多次循环迭代过程中，很可能陷入局部极优而停滞。为了有效避免这种情况发生，本文在基本遗传算法中加入再激活（re-activation）机制，即当种群最优陷入停滞时，重新调用初始化，旨在再次激活种群，增加种群的多样性。

再激活机制将进行一次初始化激活、遗传操作到局部最优值停滞的这段时间称为局部更新迭代周期。遗传算法在m次迭代过程中可有多个局部更新迭代周期，每个局部更新迭代周期的局部最优值需要单独记录，该数值与迭代过程中的全局最优值无关，与各个局部更新迭代周期间的局部最优值也无关。

再激活机制的具体运行步骤如下。

（1）记录局部更新迭代周期内的最优值。

（2）根据局部更新迭代部分最优值的停滞情况设置再激活的标志位，若停滞次数达到10，则该标志位设为1；否则将该标志位设置为0。

（3）当标志位为1时，在算法加入一次GRS初始化，并将上一局部更新迭代周期的数据清零，进入下一个局部更新迭代周期。否则，循环执行步骤（1）和步骤（2）直到达到再激活要求。

2.2 改进遗传算法求解FJSP

在求解FJSP的改进遗传算法中，机器选择部分采用GRS初始化机制生成，工序排序部分采用随机方法生成。选择更新采用锦标赛选择策略；交叉更新中机器段采用均匀交叉[25]方式，工序段采用POX交叉[25]方式；变异更新中机器段采用单点变异[25]方式，工序段采用基于领域搜索变异[25]方式；利用插入解码[25]方式进行解码。整体算法步骤如下。

（1）FJSP问题输入。

（2）种群初始化。机器段采用GRS初始化机制，工序段采用随机初始方法。

（3）计算并评价适应度值，记录全局最优值。

（4）判断是否满足终止条件。若满足，则输出优化结果，否则，进入步骤（5）。

（5）判断是否陷入局部极优。若是，则进入步骤（6），否则，进入步骤（7）。

（6）启动再激活机制。

（7）选择操作。采用锦标赛选择方法。

（8）交叉操作。机器段采用均匀交叉，工序段采用POX交叉。

（9）变异操作。机器段采用单点变异，工序段采用基于领域搜索变异。

（10）循环步骤（3）～步骤（9），直到满足终止条件。

3 数值实验与分析

为了验证本文针对FJSP的机器选择问题提出的基于关键工序的全局随机选择GRS初始化机制和改进遗传算法的有效性，以Brandimarte[1]和Kacem等[29-30]设计的基准实例（可通过网址http://www.idsia.ch/~monaldo/fisp.html进行下载）作为测试问题，设计了两类实验：一类是运用全局随机选择初始化方式得到FJSP机器选择部分的初始种群，对比分析初始种群的质量；一类是利用加入了GRS初始化机制和再激活机制的改进遗传算法求解FJSP实例。旨在通过这两类实验来验证本文提出的GRS初始化机制在FJSP中的有效性，并在结果表格中用黑体字表示所统计的最优结果。

3.1 初始机器选择部分的性能对比分析

为验证本文提出的GRS初始化机制的优越性，对文献[28]中不同初始方式得到的初始种群关于极限调度完工时间limit和调度完工时间max两项指标做了相应的对比实验。

3.1.1 极限调度完工时间 本次实验将采用文献[28]中的4种机器选择初始化方式Z-GS、Z-LS、I-GS、I-LS和本文提出的GRS初始化方式，对Brandimarte[1]的mk02（P-FJSP，partial-FJSP）和Kacem等[29-30]的15×10（T-FJSP, total-FJSP）实例初始化1000条机器选择MS段染色体，通过计算其min(limit)和AV(limit)来对比分析初始种群的质量（limit的计算方法见文献[28]）。

不同的初始化方式得到的机器选择段种群关于指标min(limit)和AV(limit)的统计结果如表2所示。图2对应于表2。由图2可以看出，本文提出改进后的GRS初始方式对比于文献[28]中的4种初始化方式，min(limit)和AV(limit)基本上都有了很大程度的降低。其中，mk02的min(limit)和AV(limit)指标值明显优于其他4种初始方式，由此可说明，本文提出的GRS初始机制对FJSP（尤其是P-FJSP）中机器选择段limit性能有很大程度的提升。

表2 不同初始方式下FJSP机器选择段Climit结果统计

3.1.2 调度最大完工时间 为了进一步比较初始种群机器选择段的质量，本实验采用相同的遗传算法对15×10和mk02两个实例分别以调度最大完工时间最小化为目标函数进行对比实验。遗传算法的参数设置如下：种群大小=1000，最大迭代次数m=100，连续运行次数COT=10，采用以上说明的5种不同机器选择初始方式得到1000条机器选择种群，工序排序段种群则通过随机方法得到。为了提高测试的准确性，机器选择部分MS的交叉和变异概率均设置为0，工序排序部分OS的交叉概率和变异概率分别设置为0.80和0.05。

表3为不同的初始化方式下机器选择段种群关于指标max的统计结果，其中包括连续运行10次过程中第1代种群的调度最大完工时间的最优值max的平均值和第100代种群的调度最大完工时间的最优值max的平均值。图3对应于表3。由图3可见，针对于T-FJSP和P-FJSP，本文提出的GRS初始方式相较于其余4种初始方式在第1代的平均max能达到中间水平，而最后一代的平均max明显更优。由此说明，本文提出的GRS初始方式对求解FJSP的种群最优解有明显的改善功能。

表3 不同初始方式下FJSP机器选择段Cmax结果统计

3.2 求解FJSP基准算例

3.2.1 对比实验一 为验证本文所提出的方法具有更强的可靠性，本次实验将在相同的规模下求解FJSP。种群规模大小为100，最大迭代次数为200，交叉概率为0.8，变异概率为0.01，每个算例连续运行10次。文献[28]中的初始化方法和张国辉等[24-27]的初始化方法全局选择、局部选择、随机选择的比例为0.45:0.45:0.1。

由表4可以看出，在种群规模和最大迭代次数相同的情况下，本文的方法与张国辉等[24-27]的方法和文献[28]中的方法相比，在11个算例中，有10个算例得到了更优解，有9个算例的平均最优值更好，有10个算例得到的最优解的最差值最小，有7个算例的最优值方差更佳。由此可以证明，本文提出的加入GRS初始化机制和再激活机制的改进遗传算法在求解FJSP时有更强的可靠性。

3.2.2 对比实验二 基于遗传算法求解Brandimarte[1]和Kacem等[29-30]设计的基准实例，由对比文献[28]中直接得到相应的max和AV(max)指标的统计结果，与本文提出基于GRS初始化机制和改进遗传算法综合求解的结果进行对比。文献[28]中，种群规模大小为500，最大迭代次数为100，交叉概率为0.8，变异概率为0.05，当全局最优值连续30次不变时，结束循环，这样连续运行10次得到调度最大完工时间max的指标统计结果见表5。

表4 相同规模不同初始方式求解FJSP所得Cmax指标统计结果对比

表5 不同规模不同初始方式FJSP机器选择段Cmax指标统计结果对比

本文采用加入GRS的初始化机制和再激活机制的改进GA求解FJSP，遗传种群规模大小为100，最大迭代次数为200，交叉概率为0.8，变异概率为0.01，连续运行10次得到调度最大完工时间max的指标统计结果见表5。由表5的统计结果可以看出，虽然由本文提出改进算法的种群规模大小和最大迭代次数的乘积明显小于文献[28]中的参数，但是本文GRS初始方式下11组算例的AV(max)有9组算例明显优于文献[28]的结果，有8组算例得到了更好的最优解，进一步验证了本文提出算法的有效性和可靠性。

4 结 论

针对FJSP的机器选择问题，为提高初始种群质量，并增加迭代过程中种群多样性，本文提出了基于关键工序的全局随机选择初始化机制和再激活机制，并通过实验分析得到以下结论。

（1）不同初始方式下对FJSP机器选择部分的极限调度完工时间limit和调度最大完工时间max的实验结果表明本文提出的GRS初始化机制能提高FJSP机器选择部分的初始种群质量。

（2）不同初始方式下，不同规模和相同规模下，FJSP机器选择段max指标统计结果可证明加入GRS初始化机制和再激活机制的改进遗传算法在求解FJSP时有较强的可靠性。

（3）本文提出的改进算法并未对所有算例的最优解产生更好的改善，对此还需要作更深入的优化研究。

符 号 说 明

AV(Cmax)——最大完工时间的平均值 Climit——极限调度完工时间 Cmax——调度系统的最大完工时间 COT——连续运行次数 Gm——最大迭代次数 h(j)——第j个工件的工序总数 Jj——第j个工件 j——工件序号，j=1,2,3, …,n k——机器序号，k=1,2,3,…,m LB——最优值的下界 l——工序序号，l=1,2,3, …,h(j) Mk——第k台机器 Max(Cmax)——最大完工时间的最差值 MT(k)——每k台机器的最大完工时间 m——机器总数 n——工件总数 Ojl——第j个工件的第l道工序 P——种群大小 To——工序总数， Var(Cmax)——最大完工时间的方差

References

[1] BRANDIMARTE P. Routing and scheduling in a flexible job shop by tabu search[J]. Ann. Oper. Res., 1993, 41(3): 157-183.

[2] MASTROLOLLI M, GAMBBARDELLA L M. Effective neighborhood functions for the flexible job shop problem[J]. Journal of Scheduling, 2002, 3(1): 3-20.

[3] LI J Q, PAN Q K, SUGANTHAN P N,A hybrid tabu search algorithm with an efficient neighborhood structure for the flexible job shop scheduling problem[J]. International Journal of Advanced Manufacturing Technology, 2011, 52(52): 683-697.

[4] HO N B, TAY J C. GENACE: an efficient cultural algorithm for solving the flexible job-shop problem[C]// Proceedings of the 2004 Congress on Evolutionary Computation. Washington, D.C,USA: IEEE, 2004: 1759-1766.

[5] 李铁克, 王伟玲, 张文学. 基于文化遗传算法求解柔性作业车间调度问题[J]. 计算机集成制造系统, 2010, 16(4): 861-866. LI T K, WANG W L，ZHANG W X. Solving flexible Job Shop scheduling problem based on cultural genetic algorithm[J]. Computer Integrated Manufacturing Systems, 2010, 16(4): 861-866.

[6] 李修琳, 鲁建厦, 柴国钟, 等. 混合蜂群算法求解柔性作业车间调度问题[J]. 计算机集成制造系统, 2011, 17(7): 1495-1500. LI X L, LU J S, CHAI G Z,. Hybrid bee colony algorithm for flexible job shop scheduling problem[J]. Computer Integrated Manufacturing System, 2011, 17(7): 1495-1500.

[7] GAO K Z, SUGANTHAN P N, CHUA T J,. A two-stage artificial bee colony algorithm scheduling flexible job-shop scheduling problem with new job insertion[J]. Expert Systems with Applications, 2015, 42(21): 7652-7663.

[8] YUAN Y, XU H, YANG J D. A hybrid harmony search algorithm for the flexible job shop scheduling problem[J]. Applied Soft Computing, 2013, 13(7): 3259-3272.

[9] 宋存利. 求解柔性作业调度问题的协同进化粒子群算法[J]. 计算机工程与应用, 2013, 49(21): 15-18.SONG C L. Co-evolution particle swarm optimization algorithm for flexible job-shop scheduling problem[J]. Computer Engineering and Applications, 2013, 49(21): 15-18.

[10] SINGH M R, MAHAPATRA S S. A quantum behaved particle swarm optimization for flexible job shop scheduling[J]. Computers & Industrial Engineering, 2016, 93: 36-44.

[11] 吴秀丽, 张志强, 杜彦华, 等. 改进细菌觅食算法求解柔性作业车间调度问题[J]. 计算机集成制造系统, 2015, 21(5): 1262-1270. WU X L, ZHANG Z Q, DU Y H,. Improved bacteria foraging optimization algorithm for flexible job shop scheduling problem[J]. Computer Integrated Manufacturing Systems, 2015, 21(5): 1262-1270.

[12] 董蓉, 何卫平. 求解FJSP的混合遗传-蚁群算法[J]. 计算机集成制造系统, 2012, 18(11): 2492-2501.DONG R, HE W P. Hybrid genetic algorithm-ant colony optimization for FJSP solution[J]. Computer Integrated Manufacturing Systems, 2012, 18(11): 2492-2501.

[13] ISHHIKAWA S, KUBBOA R, HORIO K. Effective hierarchical optimization by a hierarchical multi-space competitive genetic algorithm for the flexible job-shop scheduling problem[J]. Expert Systems with Applications, 2015, 42(24): 9434-9440.

[14] 赵诗奎. 求解柔性作业车间调度问题的两极领域搜索混合算法[J]. 机械工程学报, 2015, 14: 175-184.ZHAO S K. Bilevel neighborhood search hybrid algorithm for the flexible job shop scheduling problem[J]. Journal of Mechanial Engineering, 2015, 14: 175-184.

[15] CHANG H, CHEN Y, LIU T,. Solving the flexible job scheduling problem with makespan optimization by using a hybrid taguchi-genetic algorithm[J]. Access IEEE, 2015, 3: 1740-1754.

[16] LI X, GAO L. An effective hybrid genetic algorithm and tabu search for flexible job shop scheduling problem[J]. International Journal of Production Economics, 2016, 174: 93-110.

[17] ZHOU W, YAN-PING B U, ZHOU Y Q. An improved genetic algorithm for solving flexible job shop scheduling problem[C]// Control and Decision Conference. 2013: 4553-4558.

[18] CHANG H C, TAI H T, LIU T K. Application of genetic algorithm to optimize unrelated parallel machines of flexible job-shop scheduling problem[C]// IEEE International Conference on Control & Automation. IEEE, 2014: 596-599.

[19] MOGHADAM A M, WONG K Y, PIROOZFARD H. An efficient genetic algorithm for flexible job-shop scheduling problem[C]// IEEE International Conference on Industrial Engineering and Engineering Management. IEEE, 2015: 1031-1044.

[20] XU L, SUN W, MING H. Flexible job shop scheduling based on multi-population genetic-variable neighborhood search algorithm[C]// International Conference on Computer Science and Network Technology. IEEE, 2015: 244-248.

[21] ZHANG M, WU K. An improved genetic algorithm for the re-entrant and flexible job-shop scheduling problem[C]// Chinese Control and Decision Conference. IEEE, 2016: 3399-3404.

[22] REN H, XU H, SUN S. Immune genetic algorithm for multi-objective flexible job-shop scheduling problem[C]// Chinese Control and Decision Conference. IEEE, 2016.

[23] WU X L, LI S J. Mass variety and small batch scheduling in the flexible job shop[C]// International Conference on Biomedical Engineering and Informatics, Bmei 2009. Tianjin, China, 2009: 1-7.

[24] 张国辉, 高亮, 李培根, 等. 改进遗传算法求解柔性作业车间调度问题[J]. 机械工程学报, 2009, 45(7): 145-151. ZHANG G H, GAO L, LI P G,. Improved genetic algorithm for the flexible job-shop scheduling problem[J]. Journal of Mechanial Engineering, 2009, 45(7): 145-151.

[25] 张国辉. 柔性作业车间调度方法研究[D]. 武汉: 华中科技大学, 2009. ZHANG G H. Research on methods for flexible job shop scheduling problems[D]. Wuhan: Huazhong University of Science and Technology, 2009.

[26] ZHANG G H, GAO L, SHI Y. An effective genetic algorithm for the flexible job-shop scheduling problem[J]. Expert Systems with Applications, 2011, 38(4): 3563-3573.

[27] SHI Y, ZHANG G H, GAO L,. A novel initialization method for solving flexible job-shop scheduling problem[C]//Proceedings of International Conference on Computers & Industrial Engineering. Washington, D, C, USA: IEEE, 2009.

[28] 赵诗奎, 方水泉, 顾新建. 基于极限调度完工时间最小化的机器选择及FJSP求解[J]. 计算机集成制造系统, 2014, 20(4): 854-865. ZHAO S K, FANG S Q, GU X J. Machine selection and FJSP solution based on limit scheduling completion time minimization[J]. Computer Integrated Manufacturing Systems, 2014, 20(4): 854-865.

[29] KACEM I, HAMMADI S, BORNE P. Approach by localization and multi-objective evolutionary optimization for flexible job-shop scheduling problem[J]. IEEE Transactions on Systems, Man and Cybernetics, Part C: Applications and Reviews, 2002, 32(1): 1-13.

[30] KACEM I. Genetic algorithm for the flexible job-shop scheduling problem[J]. IEEE International Conference on Systems Man and Cybernetics, 2003, 4: 3464-3469.

Improved GA and global random machine selection based on key operation to solve FJSP

XU Wenxing1, WANG Qin1, 2, BIAN Weibin1, 2, WANG Wanhong1, 2, DONG Yiqun1

(1College of Information Engineering, Beijing Institute of Petrochemical Technology, Beijing 102617, China;2College of Information Science and Technology, Beijing University of Chemical Technology, Beijing 100029, China)

In order to improve the diversity of initial population and consider the operation sequence constraints of the same artifact at the same time, the stack was used to storage all operations in the view of the FJSP machine selection problem, in which the makespan was the optimization objective. Global random initialization method based on the key operation was proposed to solve the machine selection problem of FJSP, in which the key operation containing the only optional machine can directly affect the total load machine and processing time. To avoid the basic genetic algorithm trapped in local optimum when solving FJSP, re-activation mechanism was added to the GA algorithm, by which the diversity of population can be increased. Finally, in the view of the FJSP benchmark examples, the effectiveness of the GRS initialization mechanism and the reliability of the proposed improved algorithm were verified respectively by analyzing the performance comparison of the initial machine selection parts and the experimental results of solving FJSP by the genetic algorithm with different initializations.

flexible job-shop scheduling; optimization; species diversity; machine selection; GRS initialization mechanism; re-activation mechanism; genetic algorithm; numerical analysis

10.11949/j.issn.0438-1157.20161625

TP 301.6；TP 278

A

0438—1157（2017）03—1073—08

国家自然科学基金项目（61304217）；北京市教育委员会科技计划项目（KM201510017003）。

2016-11-16收到初稿，2016-11-26收到修改稿。

联系人：董轶群。第一作者：徐文星（1982—），女，博士，副教授。

2016-11-16.

DONG Yiqun, dongyq@bipt.edu.cn

supported by the National Natural Science Foundation of China (61304217)and the Scientific Research Common Program of Beijing Municipal Commission of Education (KM201510017003).