GA求解JOB SHOP调度问题

应用背景 车间调度问题是对n个工作在m个台机器上加工的问题。已知每个工作中工序加工顺序、各工序的加工时间以及每个工件所包含的工序，在满足约束条件的前提下，目的是确定机器上各工件顺序，以保证某项性能指标最优。 其中，车间调度问题的约束条件包括以下几个方面： （1） 在任一时刻一台机器最多只能加工一个工件； （2） 在任一时刻一个工件最多只能在一台机器上加工； （3） 一个工件一旦开始加工不允许中断； （4） 在零时刻，所有工件都可被加工； （5）任一工序只能在其指定的机器上加工，同一工件的所有工序必须满足预先给定的加工顺序。 程序功能说明：共4个工件，每个工件3个工序，6台机器，给出了每个工件的各工序能使用的机器序号矩阵Jm，求解最优调度方案的加工时间 关键技术 遗传操作包括以下三个基本遗传算子：选择、交叉、变异。 选择 ：从群体中选择优胜的个体，淘汰劣质个体的操作叫选择。选择的目的是把优化的个体(或解)直接遗传到下一代或通过配对交叉产生新的个体再遗传到下一代。选择操作是建立在群体中个体的适应度评估基础上的，轮盘赌选择法是最简单也是最常用的选择方法。 交叉 ：在自然界生物进化过程中起核心作用的是生物遗传基因的重组(加上变异)。同样，遗传算法中起核心作用的是遗传操作的交叉算子。所谓交叉是指把两个父代个体的部分结构加以替换重组而生成新个体的操作。通过交叉，遗传算法的搜索能力得以飞跃提高。交叉算子根据交叉率将种群中的两个个体随机地交换某些基因，能够产生新的基因组合，期望将有益基因组合在一起。 变异：变异算子的基本内容是对群体中的个体串的某些基因座上的基因值作变动。一般来说，变异算子操作的基本步骤如下： a)对群中所有个体以事先设定的编译概率判断是否进行变异 b)对进行变异的个体随机选择变异位进行变异。 遗传算法引入变异的目的有两个:一是使遗传算法具有局部的随机搜索能力。当遗传算法通过交叉算子已接近最优解邻域时，利用变异算子的这种局部随机搜索能力可以加速向最优解收敛。显然，此种情况下的变异概率应取较小值，否则接近最优解的积木块会因变异而遭到破坏。二是使遗传算法可维持群体多样性，以防止出现未成熟收敛现象。此时收敛概率应取较大值。