表b的OS String和MS String代表染色体编码。

在这里插入图片描述

OS String中有N个数字（N代表总工序数），每一位数字代表一道工序对应的工件。简单的说，在decode的过程中，优先安排靠左的工件到对应机器上。同一数字出现的次数代表工件的第k道工序，例如第一个“1”代表O11，也就是J1T1。第二个“3”代表O31，J3T1。第三个“1”代表O12，J1T2。

MS String中也有N个数字，代表每个工件选择的机器。MS的顺序按照工件顺序排列，如图，J1、J2、J3都有2道工序，那么第一位数字“2”则代表O11，J1T1，需要安排在第二个可以加工的机器上。注意这里的数字不代表机器序号，代表的是可加工的机器。例如最后一位数字“2”，代表的不是machine2，因为J3T3无法在machine2上加工；它代表的是J3T3第二个可加工的机器，也就是machine3。

表c用甘特图表示了表b中编码解码出的一个可行解。

最基本的思路是按照OS的顺序，在甘特图中一个接一个填入工序。但这样做后你会发现，O22本应该出现在O12后面（在OS中第二个2出现在第二个1后面），但它却跑到了O12前面；但是，图中的解确实可行，而且优于我们之前的做法。这就涉及一个查找的过程，是decode中的一个优化。

这里介绍一下如何优化decode。首先，我们设定 （allowing starting time），代表Oij的在工序约束（必须在同一工件上一道工序结束后才能开始加工）下的最早允许开始时间；代表Oij的结束时间。则我们得到公式。

从第一道工序开始按OS的顺序，安排工序Oij：

计算检查工序所在加工机器中的所有空闲时间区间。例如对O22而言，其所在加工机器M1中的空闲时间区间有一个：。，则设置当前工序Oij的开始时间。其中表示Oij在机器k上加工的时间。否则，检查下一个空闲时间区间。若所有区间都不满足，放置机器最后。设置工序加工结束时间。

编码的过程则比较简单。MS编码自不用说，按顺序把机器需要排列好就行；OS编码论文中没提编码方法，小编觉得可以对所有工序直接按照starting time排序，再按规则填入数字即可。简单试验后发现，对一串染色体进行这样的解码编码后得到的染色体与原本的染色体是相同的。

除了编码解码外，其他交叉、变异、选择部分与一般的GA算法没有太大差别。对一串合法的OS序列，无论进行怎样的交换、插入运算，都可以解码成可行解。对MS序列，在同一工件范围内任意交换顺序，也可以保证得到可行解。所以后续处理相对常规。

下面我们分别介绍相关步骤。

初始解生成

初始解生成采用随机生成的方式。

交叉OS

OS String介绍两种crossover方法，分别为POX（precedence operation crossover ）和JBX（job－basedcrossover ），每次迭代分别以50％的概率选择其中一个实行。

先介绍POX。

记父代为P1，P2，子代为O1，O2。

将工件随机分配成两组，Jobset1和Jobset12；将P1中属于JS1的部分插入O1相同位置处，将P2中属于JS1的部分插入O1相同位置处；将P1中属于JS2的部分按顺序插入O1的空余位置中（如图所示），P2同。