一种求解资源受限项目调度问题的混合遗传算法

摘要

资源受限的项目调度问题广泛存在于建筑工程、软件开发、飞机及轮船制造等单件或小批量生产方式的企业中。在理论上，该问题属于NP-hard问题，一直吸引着国内外众多学者的研究和关注，提出了许多求解该问题的优化算法，概括起来可分为精确算法和启发式算法。由于精确算法的求解时间呈指数增长，无法处理大规模问题。相反，启发式算法在计算大规模的问题时能在合适的时间里得出令人满意的计算结果，尤其是启发式算法中的遗传算法，作为一种全局优化搜索算法，因其简单易用，对很多优化问题能够得到令人满意的解，已在科学研亢和工程最优化领域中得到广泛应用。
　　 本文提出一种新的遗传算法，该算法的编码方式为工序优先权数的拓扑排序，解码方式采用了串行调度产生方案。算法的进化过程如下：
　　 ⑴采用新的选择策略，使得每代中的优良个体的基因编码不会因为交叉操作和变异操作所破坏。
　　 ⑵本文采用了峰交叉算子[40]，使得算法在搜索迭代过程中对个体的优良“基因片段”进行保护，不会因为交叉和变异操作算子所破坏。
　　 ⑶在变异操作中，采用把少量随机产生的新个体直接加入种群中，代替个体中单个基因发生变异，保持种群个体的多样性。
　　 ⑷在每代种群的开始，采用向前向后排序搜索算法对种群个体进行局部搜索，极大的提高了算法的搜索质量。选用标准数据库PSPLIB中的1560个例子对该算法进行测试，数值试验结果表明该算法是有效的。

目录

文摘

英文文摘

声明

第一章 绪论

1.1遗传算法简介

1.2资源受限的项目调度问题

1.3本文所做的工作及安排

第二章 遗传算法的基本原理

2.1遗传算法的基本术语

2.2遗传算法的基本操作

2.2.1参数编码

2.2.2初始化群体

2.2.3适应值函数

2.2.4遗传算子

2.2.5控制参数和选择

2.2.6终止循环的条件

2.3遗传算法的收敛性

2.4遗传算法的基本特性

2.5遗传算法的应用

第三章 资源受限的项目调度问题(RCPSP)

3.1 RCPSP问题的描述

3.2 RCPSP的研究现状

3.2.1精确算法

3.2.2启发式算法

第四章 求解RCPSP问题的遗传算法

4.1算法描述

4.1.1解的编码表示与解码

4.1.2向前向后排序局部搜索

4.1.3初始种群的产生

4.1.4进化策略

4.2数值实验

4.2.1参数设置

4.2.2与文献中的计算结果的比较

第五章 总结和展望

5.1总结

5.2展望

参考文献

致谢