调度问题是组合优化问题,属于NP问题,寻找调度问题的最优解是非常困难的,最有工程意义的求解算法是放弃寻找最优解的目标,转而试图在合理、有限的时间内寻找到一个近似的、有用的解。近几年各种智能计算方法逐渐被引入到调度问题中,如遗传算法、模拟退火算法、禁忌搜索算法等。 遗传算法是仿真遗传学和自然选择机理构造的一种搜索算法,因其对优化问题的弱依赖性、求解的非线性和鲁棒性、隐含并行性等特点被广泛应用于当前的各个领域。本文应用遗传算法求解生产调度问题,主要有以下几个方面: 1.基于遗传算法的Job-shop调度问题 Job-shop调度问题是经典强NP-问题,本文针对Job-shop调度问题的特殊性,对遗传算法的编码/解码方式、遗传算子的设计、目标函数及适应值比例变换进行了研究,设计了一种求解Job-shop调度问题的遗传算法,并用著名的Fisher和Thompson的基准测试问题进行仿真,然后进一步设计了求解Job-shop调度问题的改进遗传算法。 2.基于遗传算法的Flow-Shop调度问题 Flow-shop调度问题是一类复杂且极有代表性的流水线调度问题,一般用遗传算法可以成功求解Flow-shop问题。装配生产线平衡问题一直被认为是设施规划问题,用“分级位置权重法”来解决,但本文认为装配线平衡问题更应该是一个动态的生产调度问题,因此,设计了一种混合遗传算法,有效地解决装配生产线平衡问题。 3.并行机调度及其遗传算法 并行机调度是实际生产过程中的一类典型调度问题,所有工件在各机器上的分配问题以及各机器上工件加工顺序,是解决并行机调度问题的两个本质问题。本章首先介绍并行多机提前/拖期调度问题,然后针对一类带工艺约束的并行机调度问题进行遗传算法设计,并以示例进行仿真。 在调度方法方面,遗传算法虽然得到极为广泛的应用,但它的弊端也是显而易见的,进一步提高算法的收敛速度和精度仍是未来很长一段时间内的研究主题。各种各样的改进算法(自适应GA,模拟退火GA,并行GA,正交GA等等)只能在一个方面取得令人满意的效果,如何既能提高进化速度,又可提高抗早熟能力亦是人们一直期待解决的问题。