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

作     者：崔春红 

作者单位：内蒙古大学 

学位级别：硕士

导师姓名：行飞

授予年度：2006年

学科分类：07[理学] 070104[理学-应用数学] 0701[理学-数学] 

主      题：遗传算法 组合优化 混合流水车间问题 逆序数 启发式规则 

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