遗传算法解决FJSSP

问题建模

图3

编码和解码

本文采用分段编码法来对染色体进行编码，染色体由机器选择部分(MS)和工序选择部分(OS)两部分组成，长度分别为N，N表示所有工件的所有工序的数量之和，MS和OS均采用间接编码的方式来实现，如图2所示。假设用i表示某个工件的序号，则i在OS中第几次出现就代表是该工件i的第几道工序。在MS中的数值表示某工件的某道工序所对应的在可选机器集中的第几台机器，就像问题建模中所描述的，MS中的数值表示的是按先后顺序从第一个工件的第一道工序开始至最后一个工件的最后一个工件结束所选择的在可选机器集中的第几台机器。所以OS和MS就这样对应起来了，具体实现时考虑到效率问题会将OS中某个元素所对应的某一个工件的某一道工序在MS中的位置和在proDesMatrix[][]中的位置用一个hashMap一一对应起来。使用hashMap关联某工件的某工序在MS和proDesMatrix[][]中的位置可大幅降低查找时间，这对最终大幅降低获得最优解所花费的时间具有极大的帮助作用。
对染色体的解码过程是这样的：从左到至右遍历OS序列，由OS序列确定其工件号和工序号，然后由其工件号和工序号经由hashMap确定其在MS和proDesMatrix[][]中的位置，由MS中的值确定其在proDesMatrix[][]中的加工机器号和加工时间。

图4
初始化种群

首先随机产生一个100个个体大小的种群，每一个个体用一条染色体来表示。对于每一条染色体，在保证所有工件的所有工序数量都满足的情况下随机产生一个OS序列，在保证某工件工序所对应机器存在的情况下随机产生一个MS序列。本算法对传统的用单一方法生成初始种群的方法进行改进，以局部搜索、全局搜索和随机搜索相结合的方式来产生初始种群，从而保证了初始解的质量和种群的基因多样性，从而大幅降低了获得可行解所需要的时间。

适应度值计算

本文的适应度值的取值为各个工件完成所有加工操作的最大完工时间Cmax。
求解柔性车间调度的最短的总调度时间的难点有以下三点：各个工件不同的工序之间有严格的先后顺序，这个问题可以在OS编码时被解决，因为染色体序列中各个工件出现的顺序就代表着各个工件的工序序列；每道工序有多台加工机器可供选择，这在MS编码时被考虑，编码、交叉和变异的过程就是对机器进行选择的过程；同一台机器某个时刻只可以加工一种工件，这个问题可以通过维护一个机器数目大小的一维数组来实现，数组存储的值是该机器处理完当前工件后的空闲时间点。
车间调度执行的顺序是按OS的编码从左向右执行，如图2所示，由调度问题的执行位置和OS在该位置的值可知要加工工件的工件号i，然后通过工件号在OS的出现次数获得该工件所在的工序号j，然后由其工件号和工序号经由hashMap确定其在MS和proDesMatrix[][]中的位置，由MS中的值确定其在proDesMatrix[][]中相应位置上的加工机器号和加工时间，然后更新第i个工件第j道工序的开始时间为第i个工件第(j-1)道工序的结束时间或该工序将要使用机器的最近空闲时间点的之中的较大者，更新第i个工件第j道工序的结束时间为该工序的完工时间，即开始时间与加工时间之和，更新该工序所使用机器的最近空闲时间点为第i个工件第j道工序的加工完成时间。如果该工序的完工时间大于当前的最大完工时间，更新最大完工时间的值，直至OS中的所有工序被加工完毕，最终可以获得完成车间调度所需的最大完工时间。最大完工时间越长说明越不符合我们的预期，因此，适应度的值反比于最大完工时间。
选择

本文将轮盘赌策略和精英策略相结合的方式来选择下一代个体，适应度越大的个体被选中的可能性越大。精英策略保证了种群朝着更高的质量进行进化，而轮盘赌策略有效地防止了求解陷入了局部最优化的陷阱，两者相辅相成，加速了种群的迭代和有效解的获得。

交叉和变异

由于FJSSP编码的特殊性，其遗传算子的设计跟JSSP有显著的不同。本文在大量实验的基础上选择了以下算子：对MS采用的分别为两点交叉和单点变异算子，对OS则采用了顺序交叉和逆转变异算子。下面就分别简要介绍下本文所用到的交叉和变异算子。

1)、变异算子

对OS采用的逆转变异算子非常简单，就是互换OS中不同位置的值。
对MS采用的单点变异要稍复杂些，具体过程是将MS指定位置中的值更新为某工件工序所对应的可选机器集中加工时间最短的那台机器的代号。以图2中工序O12 为例，其对应基因值为1，表示可选机器集中的第一台机器M2。而该位置对应的可选加工机器包括M2和M4，如图1所示，M2和M4的加工时间分别为5和3，由于M2的加工时间大于M4的加工时间，所以该位置基因变异为第二台可选机器M4的代码2，否则，则保持1不变。这种变异方法可加速产生最优解的速度，降低获得最有解所耗费的总的运行时间。

2)、交叉算子

MS的交叉操作采用两点交叉法，具体过程是互换两条染色体的MS部分的某一位置区间的所有基因值。由于MS的特殊设计，从第一个工件的第一道工序到最后一个工件的最后一道工序所选择的机器保证了染色体交叉后仍然是有效的机器选择序列，这大大地降低了单个工序在多个机器中选择一个进行处理的难度。
OS的交叉操作采用顺序交叉法，首先产生范围在[N,2*N]的两个随机数，而这两个随机数需满足第一个随机数小于第二个随机数的条件，产生的两个随机数代表父代染色体要遗传给子代染色体的染色体序列的起始和结束位置，以图2中的OS序列为例，在本例中的两个随机数分别为2和3。父代染色体的部分编码序列被子代继承：Father1的编码序列(2 1)被Child1继承，Father2的编码序列(1 2)被Child2继承。Child1:[,2,1,,]，即：继承的工序分别为工件2的第二个工序和工件1的第一个工序。为了获得Child1染色体的其它工序项：
首先，我们以Father2为模板从第二个随机数3所在的位置后面开始循环构造一个新的染色体序列：(2///1 2 1 2)。然后，我们将已经从Father1中继承的工件序列从新产生的染色体序列中移除(即：工件2的第二个工序和工件1的第一个工序)：由(2 X X 1 2)获得(2 1 2)。最后，填充Child1剩余部分 ：首先从第二个随机数所代表的位置后面开始填充得到[ , 2, 1, 2, 1]，然后循环填充得到最终序列[2,2,1,2,1]。同理可求得Child 2的其它工序项。顺序交叉的大致步骤如图3所示。由于这种特殊的设计，OS序列交叉后所获得的序列仍然是有效的，这极大地扩大了遗传算法在可行解中的搜索范围，提高了遗传算法的搜索能力，对最终获得最优解提供了有力的保证。

图

停止条件

遗传算法运行到总调度时间达到给定下限或者迭代次数达到200次。

实验结果

考虑到图片中文字的可读性，本文以规格为10*6的经典FJSSP测试用例mk01为例将一个最佳调度以甘特图的形式展示出来。具体调度信息如图4所示，其中，图中p(i,j)表示工件j在机器i上的加工时间，i表示机器i，j表示工件j。

图