作业车间调度与遗传算法PythonJava实现及应⽤：BitMES，
基于Electron的。。。
作业车间调度问题描述
作业车间调度(Job shop scheduling problem, JSP) 是车间调度中最常见的调度类型，是最难的组合优化问题之⼀，应⽤领域极其⼴泛，涉及航母调度，机场飞机调度，港⼝码头货船调度，汽车加⼯流⽔线等，因此对其研究具有重⼤的现实意义。科学有效的⽣产调度不但可以提⾼⽣产加⼯过程中⼯⼈、设备资源的⾼效利⽤，还可缩短⽣产周期，降低⽣产成本。
作业车间调度问题描述：
⼀个加⼯系统有M台机器，要求加⼯N个作业，其中，作业i包含⼯序数为。令，则L为任务集的总⼯序数。其中，各⼯序的加⼯时间已确定，并且每个作业必须按照⼯序的先后顺序加⼯。调度的任务是安排所有作业的加⼯调度排序，约束条件被满⾜的同时，使性能指标得到优化。作业车间调度需要考虑如下约束:
1. 每道⼯序在指定的机器上加⼯，且必须在前⼀道⼯序加⼯完成后才能开始加⼯。
2. 某⼀时刻1台机器只能加⼯1个作业。
3. 每个作业只能在1台机器上加⼯1次。
4. 各作业的⼯序顺序和加⼯时间已知，不随加⼯排序的改变⽽改变。
问题的数学模型：
令(i,j)表⽰作业i的第j个⼯序。和分别表⽰(i,j)的加⼯起始时刻和加⼯时间。表⽰(i,j)是否在第k台机器上加⼯：如果(i,j)在第k台机器上加⼯，；否则，，为第k台机器的完⼯时间，则问题的数学模型如下：
python转java代码公式(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个⼯件，每个⼯件的⼯序数为，则染⾊体长度为
，对染⾊体编码如下：。其中代表第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。
伪代码如下：
3. 个体选择算⼦
个体的选择使⽤锦标赛法，其基本策略为从整个种中随机抽取n个个体让它们竞争，选取其中最优的个体。该算⼦的选择过程如下
伪代码如下：
4. 染⾊体交叉算⼦
使⽤Order Crossover(OX)交叉算⼦，该算⼦的交叉步骤如下：
对于⼀对染⾊体g1, g2，⾸先随机产⽣⼀个起始位置start和终⽌位置end，并由从g1的染⾊体序列从start到end的序列中产⽣⼀个⼦代原型
将g2中不包含在child prototype的其余编码加⼊到child prototype两侧
上述步骤将产⽣⼀个child，交换g1, g2即可产⽣另⼀个child
伪代码如下：
5. 染⾊体变异算⼦
变异的作⽤主要是使算法能跳出局部最优解，因此不同的变异⽅式对算法能否求得全局最优解有很⼤的影响。使⽤位置变异法作为变异算⼦，即从染⾊体中随机产⽣两个位置并交换这两个位置的值
伪代码如下：

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。