基于混合遗传算法的订单生产调度在机车车辆行业中的应用

4 仿真实验

本文的仿真试验中，以某机车车辆行业的10个零件、10台机器的调度问题为例。下面给出加工时间阵、机器顺序阵以及GATS算法计算10次所得的最优工件排序阵及其对应的最优加工Gantt图，如图1所示，最优解为87个单位时间。同时，该调度问题的Gantt图也明显地反映了此问题的求解复杂性。通过Gantt图可以清晰地了解到在每台机器上加工的工件及其各工序加工的起始时间和终止时间。如果调度的最佳解不是唯一的，则该调度算法同样也可以将它们全部搜索到，该算例的最佳调度结果就也不是唯一的，图1只是其中的一个最佳调度的Gantt图。

以下是其各个矩阵的表示方法，其中机器顺序阵为Jm；加工时间阵为T；工件排列阵为MJ。
（1）机器顺序阵Jm，Jm（i，j）表示加工i工件的第j个操作的机器号。
（2）加工时间阵T，T（i，j）为j工件在机器上的加工时间。
（3）工件排列阵MJ，MJ（i，j）为i机器上第j次加工的工件号。

实验在仿真环境下分别使用GATS和GA计算了10次，并且记录了每次得到目标函数的最小值，如表1所示。由表1的结果表明，禁忌搜索算法在10次运算中有2次达到最小值，而且最差的值与最优值之间的偏差也只有3，结果波动不大。

为了验证算法的有效性，在交叉算法和变异算法以及一些参数设置相同的情况下，采用传统的遗传算法重复运算10次得到的最优解为95，与最差值之间的偏差为8。同时可以比较出，禁忌搜索混合遗传算法比传统的遗传算法有较好的稳定性。

在充分分析机车车辆行业生产调度特点的基础上，提出的遗传算法和禁忌搜素算法混合的混合遗传算法应用在生产调度中。实验数据表明，改进的混合遗传算法既保存了遗传算法和禁忌搜索算法的各自优点，又针对各自的不足做了改进，使得混合遗传算法既克服了禁忌搜索算法对初始解的依赖性，又克服了遗传算法爬山能力差、易于早熟的缺点。实验证明，本文提出的混合遗传算法可以改善原有算法，是可行的。