求解同顺序加工调度问题的一种改进遗传算法

摘要：

同顺序加工调度问题是一类典型的NP-hard问题,具有广泛的工程背景,该问题的研究具有重要的理论意义和工程价值,同时开发有效的优化算法一直是该领域的热门课题.结合启发式和随机方法产生初始解,对种群进行分解并用多种交叉操作进行进化,在整体替换后用模拟退火的Metropolis抽样过程代替变异操作,本文提出了一种改进的遗传算法,算法保证了初始种群一定的质量和多样性,多种交叉操作有利于丰富搜索行为,在温度控制下的抽样过程成为概率可控的变异操作且搜索行为一定程度上可控.基于典型算例的仿真研究验证了改进遗传算法的有效性和较好的初值鲁棒性,其优化质量大大优于传统遗传算法和著名的NEH启发式方法.

关键词：遗传算法、调度、模拟退火、启发式方法

所属期刊栏目：22

分类号：TP301;TP391(计算技术、计算机技术)

资助基金：国家自然科学基金60074012;国家重点基础研究发展计划973计划G1998020310

在线出版日期：2004-01-08（万方平台首次上网日期，不代表论文的发表时间）

页数：共6页

页码：74-79