使用遗传算法解决柔性作业车间调度问题 （pezzella2008genetic)

本博文参考以下论文：

Pezzella F, Morganti G, Ciaschetti G. A genetic algorithm for the flexible job-shop scheduling problem[J]. Computers & Operations Research, 2008, 35(10): 3202-3212.

本博文所有图片均为该论文截图。

在GitHub上查看本文的代码：

https://github.com/mwanggh/FJSSP_GA

编码

使用sequencing list representation方法进行编码，例如下面的调度

被编码为

初始化

初始化需要为每个工序分配一个机器，并且需要确定工序之间的顺序。

分配方法

这里使用了两个分配方法：

• 分配方法1：在加工时间表中寻找全局最小加工时间。
• 分配方法2：随机交换加工时间表中工件和机器的顺序。

我们先来看分配方法1：

1. 在加工时间表中，选取全局最小加工时间（假设为t）对应的工序和机器；
2. 将该机器分配给该工序；
3. 在处理时间表中，为该机器其它工序的加工时间增加t；
4. 重复以上步骤，直至所有工序都已被分配机器。

看看一下面的例子：

我们有4台机器，3个工件，3个工件分别有3个、3个和2个工序。首先我们从中选出全局最小加工时间，它是工件2工序2在机器3上的处理时间，为1；将机器3分配给工件2工序2；在处理时间表中，将机器3其他工序的处理时间增加1. 接着寻找全局最小处理时间……重复此步骤，直至所有工序都被分配机器。

事实上，已经被分配机器的工序不会被再次选中，因此，每为一个工序分配了机器，我们就可以将该工序从加工时间表上删除。

接下来我们看看分配方法2：在加工时间表中，随机交换工件和机器的顺序，按照”从上到下“的规则，为每个工序分配加工时间（假设为t）最少的机器，在每次分配机器后，为该机器其他工序的加工时间增加t。下面是一个例子：

如图所示，随机交换后工件的顺序是3-1-2，机器的顺序是4-1-3-2. 按照“从上到下”的顺序，为每个工序分配加工时间最少的机器，因此为工件3工序1分配机器3（加工时间为3），并为机器3的其他工序加工时间增加3. 接下来为工件3工序2分配机器……

同样的，已经被分配机器的工序不会被再次选中，因此，每为一个工序分配了机器，我们就可以将该工序从加工时间表上删除。

排序方法

这里使用了3个确定工序顺序的方法：

• 随机顺序。
• 最大剩余加工时间顺序。
• 最多剩余工序顺序。

以最大剩余加工时间顺序为例，在按照分配规则1分配机器后（上文 Table 3），工件1、2和3的剩余加工时间分别为13(4+4+5)，7(1+4+2)和6(3+3)，其中具有最大剩余加工时间的工件为工件1，因此，先处理机器1的工序1；之后3个工件的剩余最大加工时间为9(4+5)，7(1+4+2)和6(3+3)，其中具有最大剩余加工时间的工件为工件2，因此，之后处理机器2的工序1……最后，调度为：

适应度值

本文的目标函数值为最大完工时间(makespan)，将其作为适应度值，适应度值越小，个体越优秀。

选择

本文介绍了3中选择方法，但是最终证明Binary Tournament最有效：

• Binary tournament：随机选择两个个体，其中最优的个体被选择进入重生(reproduction)环节。
• n-Size tournament：随机选择n个个体，其中最优的个体被选择进入重生环节。
• Linear ranking：根据个体的适应度值对个体进行排序，排序位次为 r_iri 的个体被选择进入重生环节的概率为：pi=(2ri)/(N(N+1)) .

交叉

对于表示机器分配情况的基因，交叉算子从所有工序中选择一个工序子集，交换两个父代个体中的这两个工序子集中工序的机器分配基因。

对于表示工序排序情况的基因，使用POX交叉：

1. 选择一个工件；
2. 将两个父代p1,p2中该工件的所有工序复制到各自的子代c1,c2个体该工件的所有工序复制到各自的子代 c_1, c_2中，保持这些工序的位置；
3. 将父代个体p_1p1中其他工件的工序复制到子代个体c_2才c2中，将父代个体

p_2p2中其他工件的工序复制到子代个体c_1c1中，保持这些工序的顺序。

变异

对于表示机器分配情况的基因，本文使用了两种变异算子：

• 交换一个个体中两个工序的机器分配情况。
• 选择一个使用具有最大工作量机器的工序，为它分配一个具有最低工作量的机器，如果可以的话。

对于表示工序排序情况的基因，使用PPS变异：

1. 选择一个工序并且将它移动到另一个位置；
2. 注意满足工序之间的顺序约束。

PPS变异只有变异后个体更优的情况下才会执行。

需要注意的是，具有最低工作量的机器不一定能处理具有最高工作量机器能处理的工序；一个工序在移动时需要满足工序之间的顺序约束。