改进的混合遗传算法求解混合流水车间调度问题

摘要

混合流水车间调度问题(简称HFSP)是一个典型的NP-Hard组合优化问题。一般很难精确地求出其最优解，人们都在寻找快速、有效的近似求解算法。混合流水车间调度问题是一般流水车间调度(FSP)问题和并行机调度问题的扩展，在流程制造业中比较常见。其研究具有重要的理论和实际意义。遗传算法是一种生物自然选择与遗传机理的随机搜索与优化方法，广泛应用于很多领域。 本文首先从图论的角度阐述了几种车间调度之间的关系，描述混合流水车间调度问题。针对混合流水车间调度问题的特点，设计了一种新的编码方案，使搜索空间包含混合流水车间调度问题的所有半活动调度。在初始种群的产生中使用启发式规则加入了一些优良个体，加快了遗传算法的搜索速度。在单点交叉过程中引入了逆序数向量进行交叉，简化了自然数序列的交叉过程。在变异算法后增加用贪心算法进行局部搜索。经实例测试表明，改进后的遗传算法在解决HFSP的有效性和优越性。

目录

文摘

英文文摘

引言

第一章 遗传算法

第二章 关于混合流水车间调度问题的描述

第三章用改进的混合遗传算法求解混合Flow shop调度问题

第四章软件实现

结论

参考文献

致谢