论文部分内容阅读
作业车间调度问题(JSSP)是一个非常复杂的组合优化问题,它在工程应用中有着十分重要的意义。本文在深入对问题进行剖析的基础上,结合已有研究成果,借鉴自然进化思想和生物免疫系统的内在机理,对JSSP的求解问题进行探索性研究。旨在为求解JSSP问题提供新的解决思路,也为人工免疫系统开辟新的应用领域。本文主要的研究重点放在遗传算法、邻域搜索算法和克隆选择算法上。 本文在对现有的JSSP求解方法和相关基本理论进行研究的基础之上,对当前组合优化应用中最多的遗传算法在JSSP应用中的编解码问题及JSSP的遗传算子设计问题进行了深入的分析,对基于作业号的编码方案提出了一种新的解码方案并设计出一种新的部分调度交叉算子。 在对邻域搜索算法的深入总结之后,对于以最小生产周期为目标函数的JSSP提出了其调度解的一种Gantt图的扩展表示法,并由此给出一种找出全部关键块的方法。对影响邻域搜索算法的几种邻域结构进行了深入的剖析,并给出两个判断准则。在此基础上给出了一种基于关键块邻域搜索的克隆算子。并对应用此算子的克隆选择算法进行了讨论。 最后给出了一种适用于求解大规模JSSP的超变异抗体克隆选择算法,并对大量的标准测试问题进行了测试,测试结果表明其性能明显优于遗传算法。