用混合遗传算法解决单机调度问题

1、毕业设计（论文）开题报告用混合遗传算法解决单机 论文题目：调度问题姓 名：学 号：学 院：专 业：年 级： 指导教师:毕业论文开题报告1.本课题的研究意义在生产调度研究领域，单机调度问题(Single Machine Scheduling, SMS) 一直是研究热点。单机调度问题是一类重要的生产调度问题，在理论上，单机调 度可看作是其它调度问题的特殊形式，是复杂的多机调度系统的一个子系统。深 入研究单机调度问题可以更好地理解复杂调度系统的结构。在生产实践中，复杂 调度问题往往可以分解为多个单机问题来解决。对单机调度问题求解算法的研究 可以为求解复杂调度问题提供算法基础，因此，设计一种简单高效的

2、求解算法是 单机调度问题研究的重要方向。因传统的解决生产调度的算法如遗传算法(GA)、模拟退火算法(SA),对解 决生产调度问题有一定的局限性。遗传算法作为一种全局优化搜索算法,存在着 运算速度慢、易过早收敛、局部搜索能力弱、优化效率较低等缺点。而模拟退火 算法虽然有较好的局部搜索能力，但是对全局解的搜索性能较差。而且，解决 生产调度问题的经济性要求也不允许用这类方法来求解。为了适应实际生产调度的经济性，增强解决优化问题全局和局部意义下的 搜索能力和效率。本课题将采用混合遗传算法(GASA)对单机调度进行求解。以 期通过两者算法的优越性进行互补，弥补各自的缺点。得到一种优化能力、效率 和可靠性

3、较高的优化方法，对单机调度问题进行优化求解，为解复杂的多机调度 问题提供理论依据。.本课题的基本内容本课题通过对调度问题中最基本的单机调度问题进行深度研究，采用混合遗 传算法对该模型进行求解。希望通过对基本的单机调度问题的求解，给生产过程 中复杂的调度问题提供算法依据。调度问题学习：通过阅读前人的书籍以及文献资料，对调度问题进行深 入了解，侧重生产调度问题。对生产调度的产生、目前的研究进展、在实际工业 生产中运用进行学习和理解。单机调度1|r. | w.c.分析：选定特定的单机调度模型，通过对该问题学习 理解，对模型进行公式化表示，并选取具体的状态利用算法进行求解。构造混合遗传算法：对混合遗传

4、算法的主要思想和基本原理进行阐述。通 过对该模型的分析，归纳适合该模型的混合遗传算法。同时选定编码及初始种群 的生成方式，适应度函数计算，算子设计，收敛条件等。描绘基于单机调度的混 合算法流程图。实验程序编写：将混合遗传算法的具体流程通过c语言表达出来，并进行 模拟实验，将获得的最优解与实际模型分析以及遗传算法和模拟退火算法进行比 较，不断改进遗传算法的参数，最终获得预期的最优解。.本课题的重点和难点单机调度模型分析选取基于调度问题对于现实工业操作的重要性和实际工业生产的指导作用，如何 选定有意义的单机调度模型，使得其具有很好的现实意义，同时能够确保在毕业 设计时间段能够完成对其的研究。是本课

5、题的一大难点。混合遗传算法的设计深入学习了车间调度问题的特点及分类、遗传算法和模拟退火算法的理论原 理、特点及操作流程，在分析遗传算法和模拟退火算法特点的基础上，学习了解基 于遗传算法和模拟退火算法相结合的混合遗传算法。应用混合遗传算法求解典型 的单机调度问题,算法在设计时，确定生成初始种群、交叉变异算子、产生随机数、 收敛条件等的方式。确定混合算法流程图，并通过c语言表示出来。最后，将混 合遗传算法应用在单机调度模型中，获得最优解，并在算法参数相同的情形下，和 标准遗传算法及模拟退火算法进行实验结果对比。通过对比实验,证实混合遗传 算法具有更优良的寻优性能。C语言编写混合遗传算法对于复杂算法

6、、原始数据众多、进行大规模数据操作的算法的编写。不管是 对计算机性能以及对编写者本人都是不小的挑战。全局变量的设计、产生随机数 的方式、全局空间的分配和释放、具体函数的时间复杂度和空间复杂度等等都是 要考虑的问题。.论文提纲绪论（一）研究的背景与意义（二）求解单机问题的研究现状（三）研究的主要内容和论文章节安排混合遗传算法（一）遗传算法（二）模拟退火算法（三）混合遗传算法单机调度的混合遗传算法操作模型（一）单机调度问题描述及数学模型（二）单机调度问题的染色体编码（三）适应度评价函数（四）交叉与变异算子（五）混合遗传算法流程四基于混合遗传算法的单机调度算法设计（一）编码、解码（二）交叉操作算子（三）变异操作算子（四）收敛条件（五）算法参数设定及实现方法五基于混合遗传算法的单机调度实现及仿真（一）环境选择（二）GASA算法设计实现（三）GASA与GA、SA结果分析比对（四）总体实验结果分析六总结与