一种调问题新的遗传算法的设计与应用

摘要

调度问题在计算机学科、管理学科和控制论学科等很多学科都有重要而广泛的应用，大多数调度问题通常都是非常难解的NP-完全问题，对它们构造有效算法十分困难，对小规模的问题，通常使用启发式方法求出他们的近似最优解，而对比较大规模的问题，还没有十分有效的算法。因此对他们进行研究不仅有重要的科学意义，而且有重要而广泛的应用价值。Flow-shop调度问题是如下的一类调度问题：设有m 台机器，n个零件(也称为任务或工件)，每个工件都要依次经过m台机器进行加工，所有工件在每台机器上均要按照一定的顺序进行加工，本文考虑同顺序的flow-shop调度问题，即所有工件在每一台机器上的加工顺序都相同，则问题为，当给定n个工件在每台机器上的加工时间，如何确定n个工件在每台机器上的加工顺序才能使得加工完所有工件所用的时间最短？当机器的台数多于两台时，在一般条件下，目前还没有有效的求解方法。
　　 本文对这种调度问题进行了研究。主要工作包括：首先，在对问题进行全面分析的基础上，给出了加工完所有工件所用时间的数学表达式，在此基础上，建立了此问题的一个全局最优化模型：加工时间极小化的优化模型，该模型为一个极小极大优化模型；其次，针对问题的特点和结构，给出了适合此问题调度方案的编码方法，并定义了适应度函数；进一步，设计了一个新的杂交算子和变异算子，在此基础上，设计了求解同顺序flow-shop调度问题极小极大优化模型的一个新的遗传算法。最后，对一个企业的实际调度问题建立了同顺序flow-shop调度问题的极小极大优化模型，对此模型用所提算法进行了求解，所得方案将企业每月加班加点每天不停生产也难以完成任务的状况改进到每月只需26.5天的时间便可完成任务，该调度方案极大地改进了企业目前所用的方案，可以满足企业的要求。另外，对5个试验问题也进行了数值模拟，结果表明了算法的可行性和有效性。