作业车间调度JSP与遗传算法GA及其Python/Java/C++实现
- 2020 年 2 月 25 日
- 筆記
最近小编接触了遗传算法（Genetic Algorithm）。关于遗传算法，公众号内已经有多盘技术推文介绍：
【优化算法】遗传算法(Genetic Algorithm) （附代码及注释）
今天小编再为大家带来CSDN上一位大牛@sundial dreams
关于遗传算法在 作业车间调度问题 上的相关内容，希望大家喜欢！
（原文附图）
问题描述
作业车间调度(Job shop scheduling problem, JSP) 是车间调度中最常见的调度类型，是最难的组合优化问题之一，应用领域极其广泛，涉及航母调度，机场飞机调度，港口码头货船调度，汽车加工流水线等，因此对其研究具有重大的现实意义。科学有效的生产调度不但可以提高生产加工过程中工人、设备资源的高效利用，还可缩短生产周期，降低生产成本。
作业车间调度问题描述：
一个加工系统有M台机器，要求加工N个作业，其中，作业i包含工序数为L_i。令，则L为任务集的总工序数。其中，各工序的加工时间已确定，并且每个作业必须按照工序的先后顺序加工。调度的任务是安排所有作业的加工调度排序，约束条件被满足的同时，使性能指标得到优化。作业车间调度需要考虑如下约束:
1.每道工序在指定的机器上加工，且必须在前一道工序加工完成后才能开始加工。
2.某一时刻1台机器只能加工1个作业。
3.每个作业只能在1台机器上加工1次。
4.各作业的工序顺序和加工时间已知，不随加工排序的改变而改变。
问题的数学模型：
令(i,j)表示作业i的第j个工序。S_ij和T_ij分别表示(i,j)的加工起始时刻和加工时间。Z_ijk表示(i,j)是否在第k台机器上加工：如果(i,j)在第k台机器上加工，Z_ijk=1；否则，Z_ijk=0，C_k为第k台机器的完工时间，则问题的数学模型如下：
公式(1)为目标函数，即优化目标，系统中使用总加工时间最短为优化目标。公式(2)表示1个作业只能在加工完成前一道工序后才可以加工后一道工序。公式(3)表示1个作业的第1道工序的起始加工时刻大于或等于0。公式(4)表示在1台机床上不会同时加工1个以上的作业。
遗传算法
随着遗传算法（genetic algorithm (GA)）在组合优化问题的广泛应用，许多人开始对遗传算法进行深度研究。已有研究结果表明，遗传算法对求解作业车间调度问题具有较好的效果，因此系统采用遗传算法来解该问题，遗传算法是计算数学中用于解决最优化的搜索算法，是进化算法的一种。进化算法最初是借鉴了进化生物学中的一些现象而发展起来的，这些现象包括遗传、突变、自然选择以及杂交等。系统通过模拟生物进化，包括遗传、突变、选择等，来不断地产生新个体，并在算法终止时求得最优个体，即最优解。
遗传算法解决作业车间调度问题基本步骤：
1.初始化一定数量的种群（染色体编码）
2.计算个体适应度（染色体解码）
3.采用锦标赛法选择染色体并交叉产生新个体
4.个体（染色体）变异
5.达到遗传代数终止算法并从中选取适应度最优的个体作为作业车间调度问题的解
流程图如下：
遗传算法所需参数：
1.种群规模：种群中个体的数量，用populationNumber表示
2.染色体长度：个体的染色体的长度，用chromosomeSize表示
3.交叉概率：控制交叉算子的使用频率，用crossProbability表示，并且值为0.95
4.变异概率：控制变异算子的使用频率，用mutationProbability表示，并且值为0.05
5.遗传代数：种群的遗传代数，用于控制遗传算法的终止，用times来表示
遗传算法实现基本步骤及伪代码：
1. 编码及初始化种群
采用工序实数编码来表示染色体，即M台机器，N个工件，每个工件的工序数为process_i，则染色体长度为chromosome=process_1+process_2+…，对染色体编码如下：
chromosome=…,w_i,w_j,w_k,…
其中w_i代表第i个工件编号，而出现的次数代表该工件的第几道工序。例如{0, 1, 2, 1, 2, 0, 0, 1, 2}，中0，1，2表示工件的编号，第几次出现就代表第几道工序。然后将每一次随机生成的染色体个体加入到种群集合中。
算法伪代码：
2. 解码及计算适应度
将优化目标定义为总加工时间最短，因此适应度定义为最短加工时间的倒数，设fitness为对应个体的适应度，fulfillTime为最短加工时间，因此
其中fulfillTime的计算方法如下：
首先定义如下变量
然后从左到右遍历个体的染色体序列，其中表示第i个工件的编号，则对应的当前工序为,设为p。当前工件当前工序所使用的机器编号为，设为m。当前工件当前工序对应的加工时间为，设为t。则工件的第p道工序的最晚开始时间为
而第m台机器的加工时间为
工件的第p道工序的结束时间为
最后加工完所有工件的最短加工时间fulfillTime为
从而计算出适应度fitness。
PS.小编觉得解码的过程类似动态规划。
伪代码如下：
3. 个体选择算子
个体的选择使用锦标赛法，其基本策略为从整个种群中随机抽取n个个体让它们竞争，选取其中最优的个体。该算子的选择过程如下
伪代码如下：
4. 染色体交叉算子
使用Order Crossover(OX)交叉算子，该算子的交叉步骤如下：
对于一对染色体g1, g2，首先随机产生一个起始位置start和终止位置end，并由从g1的染色体序列从start到end的序列中产生一个子代原型
将g2中不包含在child prototype的其余编码加入到child prototype两侧
上述步骤将产生一个child，交换g1, g2即可产生另一个child
伪代码如下：
5. 染色体变异算子
变异的作用主要是使算法能跳出局部最优解，因此不同的变异方式对算法能否求得全局最优解有很大的影响。使用位置变异法作为变异算子，即从染色体中随机产生两个位置并交换这两个位置的值
伪代码如下：
6. 算法整体伪代码如下：
代码实现
原作者编写了Java，Python，C++三个版本的代码，小编仔细阅读了Java代码，在其中加入一些注释并略作修改，分享给大家。
说明一下输入部分，输入的算例是写死在代码中的，算例如下：
- Jop0=[(0,3),(1,2),(2,2)]
- Jop1=[(0,2),(2,1),(1,4)]
- Jop2=[(1,4),(2,3)]
在这个例子中，作业jop0有3道工序：它的第1道工序上标注有(0,3)，其表示第1道工序必须在第0台机器上进行加工，且需要3个单位的加工时间；它的第2道工序上标注有(1,2)，其表示第2道工序必须在第1台机器上进行加工，且需要2个单位的加工时间；余下的同理。总的来说，这个实例中共有8道工序。
图中是其中一种可行解。
那么本期内容到这里就差不多结束了。下次再见~
最后祝愿武汉早日度过难关，小编早就想上学了！
武汉加油！
