基于遗传算法的流动车间作业调度

刘明，索良泽

（贵州大学电气工程学院，贵州 贵阳 550025）

0 引言

一直以来，调度问题都是一个极其重要的课题。在各种工业活动中，制订一个高效的调度计划是不可或缺的组成部分。这就要求计划制订者要做出满足任务要求的调度安排，并根据任务确定最晚完工时间。此问题最具挑战性的地方在于如何找到理想的调度计划，既满足任务要求又是问题的最优解[1-3]。在数学上，通常将此类问题归结为组合优化问题，同时也属于NP完全问题，其特点是还没有找到一种算法可以在多项式时间内求出其最优解。由于启发式算法对解决此类问题有着很明显的优点，如算法简单易于设计，计算效率高等，所以一直以来人们使用启发式算法来对调度问题进行求解。在本文中，研究调度问题中的一种典型问题，车间调度问题[4-8]。

车间作业调度问题是生产管理中必须要面临的问题。调度计划的好坏对生产成本和生产时间有直接的影响。通过科学的调度方法，车间内的资源可以得到更合理高效的利用，同时还能以最快的速度将要加工的零件送入车间，加工完成的零件运到下一车间[9]。车间调度涉及到每一批加工的零件在时间、空间及设备等各种资源上的协调和分配，这属于运筹学中的动态调度问题。

我们常常需要考虑实际的约束条件，根据现有的资源去完成各种加工任务，给出不同工件在相关机器上的加工时间和顺序，使得相关的性能指标达到最优，这不仅能有效的提高企业的作业效率，还能为企业带来巨大的经济效益。……