Job Shop

Job Shop问题（1）

flow shop：

如果每个作业需要在每个处理机上加工，而且每个作业的工序也相同，即在处理机上加工的顺序相同，则这种多类机的环境称为同顺序作业或流水作业。

job shop：

如果每个作业需要在每个处理机上加工，每个作业有自己的加工顺序，称之为异顺序作业。

open shop:

如果每个作业需要在每个处理机上加工，每个作业有自己的加工顺序，称之为异顺序作业。

遗传算法与JobShop

遗传算法是一种随机搜索算法，它主要分为六大功能模块：编码、交叉、变异、解码、评价、选择。整个算法的流程如下:

1.编码：

我们利用工件号的排列来表示工序的先后顺序，例如：1212这个排列中第一个1代表第一个工件的第一道工序，第二个1代表第一个工件的第二道工序，第一个2代表第二个工件的第一道工序，第二个2代表第2个工件的第二道工序。

2.交叉

交叉是遗传算法中的一个重要操作，它的目的是从两条染色体中各自取出一部分来组合成一条新的染色体这里，在车间调度中一种常见的交叉方法叫Generalized Order Crossover方法(GOX)，假设有三个工件A,B,C, 每个工件下面包含三道工序，根据这一信息我们可以利用上一节介绍的编码技术随机生成两条染色体如下：

3.变异

变异操作通常发生在交叉操作之后，它的操作对象是交叉得到的新染色体。在本文中我们通过随机交换染色体的两个位置上的值来得到变异后的染色体