带学习策略的遗传算法求解柔性作业调度问题

王公堂，许化强

（山东师范大学 物理与电子科学学院，山东 济南 250014）

传统的作业调度问题中，作业的每一道工序都是预先知道的，而且工序的加工机器和时间也是预先确定好的。而在柔性作业调度问题中，工序的加工机器是不确定的。作业的每一道工序都可以在多个加工机器上加工，而且不同的加工机器所需要的加工时间也不相同。在处理此类问题上，不仅要处理作业之间的调度问题，而且要考虑每一道工序面临可选择机器的问题，使问题更难以解决。针对柔性车间调度问题的特点，笔者在Yasuhiro Tsujimura[1]等人提出的主从共生遗传算法的基础上进行改进，加入学习策略，在进化过程中发掘并保留种群中的优秀特征，并指导后代的进化，加快收敛速度，提高搜索效率。

1 带操作柔性的作业调度问题描述

具有操作柔性（OF）的柔性车间调度问题（Flexible Job-Shop Scheduling Problem，FJSP）是指同一个操作（或工序）可以在不同的机器上运行。FJSP假定加工系统中有M台机器和N个作业，每个作业包括一道或多道操作，操作顺序是预先确定的，每道操作可以选择在多台不同的设备上加工，操作的加工时间随加工设备的不同而变化。例如，表1是FJSP的一个例子，共有2个作业，3个加工机器，每道工序可以选择在不同机器上以不同的加工时间加工。调度目标是为每道工序选择最合适的加工设备，以及每台设备上各工序的最佳加工顺序，使所有作业的流通时间最短。该问题所需满足的约束条件[2]是:1）所有作业在初始时刻都可加工；2）工序在可供选择的若干机器上加工的时间已确定；3）每台加工机器在固定的时间段内只能加工一个作业；4）每个作业在固定时刻只能在一台机器上加工。

表1 一个FJSP的实例 2×3Tab.1 An example of the FJSP 2×3

2 共生遗传算法设计

柔性车间调度可分成两个子问题，一是为操作选择加工机器，二是类似经典车间调度问题，给作业一个合适的排序，得到最优调度。可将这两个子问题看作是共生机制中的两个不同的物种，进而用不同的种群来表示，一个种群为控制种群，为工序选定合适的加工机器；另一个种群为调度种群，在控制种群的限制下优化调度。

2.1 编码设计

将柔性车间调度问题分为两个子问题，对应两个不同类的种群，其个体分别称为控制染色体和调度染色体，每个种群的个体都应该有自己的编码方式[3]。

控制染色体编码方法：将所有的操作按照其所属的作业号和其在作业中的加工顺序依次排列，并将其选择的加工机器放在工序对应的位置上。即是控制染色体采用基于作业的编码方式，将每个作业的所有工序选择的加工机器的顺序排列作为控制染色体的一个基因块。例如，对表1中所示例子，可以有控制染色体12321，其中基因块123为作业1（J1）的各个操作选择的加工机器：操作 O1，1选择的加工机器为 M1，O1，2选择的加工机器为M2，O1，3选择的加工机器为M3；基因块21为作业2（J2）的操作所选择的加工机器排序序列。

调度染色体编码方法：调度染色体采用基于操作的编码方式，并把操作按照加工机器的不同分为不同的基因块。因此，如果有m台加工设备，则调度染色体有m个基因块。如果某个设备基因块中包含同一个作业的多个操作，则这个基因块中的所有操作排序时，必须注意同一个作业的多个操作之间的先后约束关系，即先加工的操作必须排列在后加工的操作的前面。 例如作业 1 有 3 个操作 O1，1，O1，2，O1，3；作业 2 有2 个操作 O2，1，O2，2。 假设这 5 个操作选 取 的加工 机器分别为M1，M2，M3，M2，M1。 则在机器 M1上加工的操作一个可能的排列为O1，1O2，2，这个字符串为调度染色体编码的一个基因块；同理，在机器M2上加工的操作可能的排列为O1，2O2，1；在M3上加工的操作可能的排列为O1，3。按照机器序号，将这些基因块组合到一块，则组成了调度染色体 O1，1O2，2O1，2O2，1O1，3。 这种编码方式的一个优点就是可以将对染色体的操作提高到基因块的级别上。

2.2 进化过程中的学习

进化过程是基于随机自然选择和基因重组。如果不考虑保留种群中优秀的特性而进行种群进化，则可能需要很长的时间才能找到全局最优解。针对控制种群和调度种群，分别设立学习机制，用于学习、记录以及指导后代种群的进化，提高搜索质量和效率。设立两个信息存储空间，即染色体空间和操作空间[4]。

染色体空间：具有最大适应度值的不同染色体之间具有很多相似的特征[5]，如果当某个调度染色体中出现了最优解的一些排序特征，就应该及时把它保存下来，希望多个调度中的不同的最优特征经过交叉之后能够在进化机制的帮助下逐渐集中，就可以使算法很快向最优解收敛。染色体空间中存储的是前几代中挑选出来的最好的染色体。进化到当前代时从当前种群中选择一定数量的适应度最高的染色体，每一个选出的染色体要与染色体空间中的染色体做比较。染色体空间中k个具有最高相似度的染色体将被复制到当前代种群中。采用基于染色体中操作的差异来定义两个染色体的相似度。相似度可以用下面的公式计算：

其中M表示调度染色体中设备基因块的个数，Qi表示设备基因块i中操作的个数。Chm1和Chm2表示调度染色体，Opt1、Opt2 表示 Chm1、Chm2 中的操作，Opt1（i，j）表示染色体Chm1 中设备基因块 i中第 j个操作。 如果 Opt1（i，j）、Opt2（i，j）表示的两个操作相同则操作符返回0，否则返回1。S越小，则表示两个染色体Chm1、Chm2越相近。染色体空间主要用来保存以前代中的优秀染色体，用来提高后代交叉的效果。

操作空间：在进化过程中为作业的工序选择最合适的加工机器。如图1所示，其全部信息是要加工的作业以及作业的全部操作和操作对应的可选加工机器集合，作业对应的加工机器各自都有一个参考数据，该数据表示在以往的优秀染色体中，该加工机器被选中加工此操作的情况，重新选择加工机器时可以根据这个信息选择最可能合适的机器。该空间数据在进化过程中每隔n代更新一次。图1中展示的共有N个作业，其中作业3有x个操作，操作O3，3有3个机器可以选择M1M2M3，其中机器M1以往较优染色体中选中率为30%，M2以往选中率为20%，M3被以往被选中的概率为50%。当对控制染色体执行变异操作时，如果为某个操作重新选择加工机器，可以在此空间数据的指导下选择最可能合适的加工机器。

图1 操作空间示例Fig.1 Example of operational memory

2.3 算法设计

对FJSP问题来说，因为不同的子问题有其本身的特征，因而在进化过程中，应该考虑到不同的种群的地位和进化速度也应该不同，适当搭配不同物种之间的进化速度会获得比较好的结果。因为调度种群是在控制种群的指导下进化的，调度种群的进化结果影响控制种群中染色体的适应度，因而，在进化速度方面，调度种群应该比控制种群要快得多。笔者将控制种群作为进化主过程，调度种群作为从过程，改进后的共生遗传算法如下：

1）主进化过程：控制染色体的适应度取其控制下的调度种群进化后最优调度染色体的适应度。

Step 1：生成初始种群，大小为pop_size；

Step 2：种群中的每一个控制染色体都对应一个调度种群，使用2）从进化过程对调度种群进化，依次得到每个控制染色体的适应度fc。

Step 3：统计控制染色体的最大适应度fcmax和平均适应度fcavg。

Step 4：如果连续m代最大适应度没有变化或者达到最大进化代数，则算法结束。否则继续执行Step 5。

Step 5：选择：对控制染色体种群执行轮盘赌选择操作[6]。

Step 6：交叉，变异：根据操作空间的信息指导变异操作：

Step 7：更新：选出一定数目的最优控制染色体，对操作空间进行更新。转到Step 2）继续。

2）从进化过程：调度染色体的进化。

Step 1：初始化调度种群。根据控制染色体为操作选定的加工机器，生成初始种群。

Step 2：计算调度种群中每个染色体p的最早完工时间MS，同时计算适应度值=1/MS。

Step 5：对调度染色体种群进行选择操作。选择出来的部分染色体还要和染色体空间中的染色体做比较，并将染色体空间中最相似的k个染色体插入到当前种群中。

Step 6：交叉变异操作。

在红磷及其三卤化物或氯化亚砜的催化下，脂肪酸的a-H可被氯、溴取代生成a-卤代酸，此反应被称为Hell-Volhard-Zelin-Sky反应，反应机理如下：

Step 7：更新：每隔k代更新染色体空间。转Step 1继续。

3 遗传算子设计

3.1 交叉算子

对控制染色体的交叉操作采用染色体中多点交换操作。随机决定发生交换的染色体中基因的个数和位置，并将两个父个体中对应位置的基因交换，生成新的个体。对调度染色体的交叉操作采用基于设备基因块交叉法。两个调度染色体可能会发生与设备基因块数目M相同多的多点交叉。

3.2 变异算子与学习引导

控制染色体变异主要针对某个作业的全部操作。因此，首先应该选中需要变异的作业。如果选中某个作业变异，则这个作业的所有操作都要重新选择加工机器。这样控制染色体会发生与作业数目N相同的多点变异。有两种选择方式，一种是在可选机器集合中随机选择，一种是在操作空间的指导下选择，方法如下：

Step 0：对作业Ji中每个操作Oi，j重新选择加工机器：

找出Mk机器：Mk机器目前用来加工Oi，j。找出可以加工操作 Oi，j的机器集合 P（Oi，j）。

Step 1：产生一个随机数字 r∈[0，1]：

如果 r＜=0.5，则使用随机变异操作：从 P（Oi，j）中随机选择一个机器加工操作Oi，j。否则，操作空间中的机器选择信息对变异算子施加影响：如果 P（Oi，j）仅包含 Mk，则仍然使用 Mk来加工Oi，j，否则，根据操作空间中机器被选择情况的概率，以轮盘赌方式从 P（Oi，j）中选择一个机器来加工操作 Oi，j。

Step 2：转到 step 0。

调度染色体的变异操作，主要是对不合理基因块执行变异，对操作排序做一些改动。因此首先选中执行变异操作的设备基因块，然后对基因块执行两点易位法。这样，调度染色体会发生与设备基因块数M（设备数目）相同的多点变异。

4 实验仿真及分析

这里采用文献[7]中的不同规模的柔性车间调度问题的数据作为测试数据。为了更加准确，对于要测试的每一种规模的问题数据，分别运行10次，然后取这10次运行结果的最好值以及平均值。表2给出了实验结果，共有6列。第一列给出了问题规模，第二列是文献[7]中的方法获取的最优调度结果，右边4列是通过使用本文给出的方法仿真得出的数据，分别是只用共生遗传算法得出的最好值和平均值，加入学习策略后得到的最好值和平均值。

表2 仿真实验结果Tab.2 Simulation experimental results

由表2可以看出，使用本文提出的方法在其中3种规模的柔性车间调度问题中可以取得较好的效果，有明显改进，每次运行中都能取得比原来好的调度值。但在10×10规模的问题上，结果不如原来优秀。第3列中是同等条件下仅使用基于共生机制的遗传算法获取的结果。总体来看，加入学习策略之后能获取质量更高的结果。

5 结 论

根据柔性作业调度问题的特点，将该问题分为两个子问题，看作是共生遗传算法中两个相互影响，共同进化的不同类种群。根据子问题的特点，设定两个不同类种群有不同的进化角色和进化速度。在进化过程中，加入学习策略，使遗传算法能够在进化过程中不断学习，将染色体中的优秀特征保留下来指导后代的进化。实验证明，加入学习策略后对提高解的质量有一定的效果。

[1]Tsujimura Y， Mafune Y， Gen M.Effects of symbiotic evolution in genetic algorithms for job-shop scheduling[C]//Proceeding of the 34th Hawaii International Conference on System Sciences.[S.1.]:the IEEE Computer Society，2001:3026－3032.

[2]杨晓梅，曾建潮.遗传算法求解柔性job shop调度问题[J].控制与决策，2004，19（10）：1197－1200.

YANG Xiao-mei，ZENG Jian-chao.Solving flexible job shop scheduling problem using genetic algorithm[J].Control and Decision，2004，19（10）:1197－1200.

[3]张维存，郑丕谔，吴晓丹.基于主－从遗传算法求解柔性调度问题[J].计算机集成制造系统，2006，12（8）:1241－1245.

ZHANG Wei-cun，ZHENG Pi-e，WU Xiao-dan.Solving flexible job-shop scheduling problems based on master-slave genetic algorithm[J].ComputerIntegrated Manufacturing Systems，2006，12（8）:1241－1245.

[4]Ho N B，Tay J C.LEGA:an architecture for learning and evolving flexible job-shop schedules[C]//The 2005 IEEE Congress on Evolutionary Computation，2005，2（2－5）:1380－1387.

[5]许化强，邱洪泽.用属性导向归纳法发掘job-shop调度中的排序规则[C]//第三届智能CAD与数字娱乐学术会议，济南:山东大学出版社，2006:231－237.

[6]王小平.遗传算法—理论、应用及软件实现[M].西安:西安交通大学出版社，2002.

[7]Kacern I， Hammadi S， Borne P.Pareto-optimality approach for flexible job-shop scheduling problems:Hybridization of evolutionary algorithms and fuzzy logic[J].Mathematics and Computers in Simulation， 2002，60（3－5）:245－276.