基于免疫克隆选择算法的作业车间调度问题研究

论文摘要

作业车间调度问题（Job-Shop Scheduling Problem JSSP）是一种典型的组合优化问题,在工程应用中有着十分重要的地位。本文在研究现有JSSP求解方法的基础上,重点关注了基于免疫克隆选择算法的JSSP求解,对编码方式,邻域结构,克隆算子的构造以及免疫克隆选择算法等方面都做出了改进。具体内容如下：系统研究了进化计算求解JSSP时的常用编码方式,提出了一种新的编码方式。传统的基于操作编码的进化算法在求解JSSP时会出现编码冗余的现象,本文在分析冗余性对算法性能影响的基础上,提出一种新编码—调度编码。调度编码无需解码且避免了编码空间与调度空间多对一的映射关系。深入分析了邻域结构对进化算法中邻域搜索性能的影响,并提出改进的邻域结构。在此基础上,以发挥调度编码的优势和提高求解性能为出发点,有效结合邻域搜索和克隆选择算法设计了一种基于邻域搜索的克隆算子,提出了运用此算子的免疫克隆选择算法（ICSANS）来求解JSSP。该算法对当前国际文献中的benchmark问题实例进行了测试,取得了较好的效果。通过仿真实验发现,采用基于邻域搜索的克隆算子,运用免疫克隆选择算法求解JSSP时可能出现在某个解上循环搜索,影响了算法效率。本文结合禁忌搜索中禁忌解的特点提出禁忌策略,提出了加入禁忌策略的免疫克隆选择算法（ICSA NS TS）。在搜索过程中将已经搜索到的解记忆,并在进一步的迭代搜索中“禁止”向这些解的方向移动来避免循环搜索,从而保证对不同的有效搜索途径的探索。最后运用加入禁忌策略的免疫克隆选择算法对大量的标准测试问题进行了测试,证明了算法的有效性。本论文得到了国家教育部博士点基金（No.20060701007）和国家自然科学基金（No.60703107）的资助。

论文目录

• 摘要
• Abstract
• 第一章 绪论
• 1.1 研究背景
• 1.2 车间调度问题的发展及研究现状
• 1.2.1 车间调度问题的发展概况
• 1.2.2 车间调度问题的研究现状
• 1.3 人工免疫系统进展
• 1.3.1 人工免疫系统的发展概况
• 1.3.2 人工免疫系统的研究领域
• 1.4 论文研究的主要内容
• 第二章 作业车间调度问题及其基本理论
• 2.1 问题的描述
• 2.1.1 作业车间调度问题
• 2.1.2 性能指标
• 2.1.3 JSSP的基本数学模型
• 2.2 作业车间调度问题的表示法
• 2.2.1 Gantt图表示法
• 2.2.2 析取图表示法
• 2.3 活动调度
• 2.3.1 基本定义
• 2.3.2 GT算法
• 2.4 关键路径和关键块
• 2.5 计算复杂性
• 2.6 本章小结
• 第三章 作业车间调度问题的编码研究
• 3.1 作业车间调度问题的遗传算法编解码分析
• 3.1.1 编码要考虑的问题
• 3.1.2 编码分类
• 3.2 基于工序编码方式的分析
• 3.2.1 编解码分析
• 3.2.2 编码的冗余性分析
• 3.3 新的编码方式—调度编码
• 3.3.1 调度编码的编码分析
• 3.3.2 调度编码的解码分析
• 3.3.3 调度编码的特性分析
• 3.4 本章小结
• 第四章 基于调度编码的免疫克隆选择的作业车间调度求解
• 4.1 人工免疫系统的基本概念及仿生机理
• 4.1.1 免疫系统的基本概念
• 4.1.2 免疫识别
• 4.1.3 免疫学习和记忆
• 4.1.4 克隆选择
• 4.1.5 抗体多样性
• 4.2 基于邻域搜索的免疫克隆选择求解作业车间调度问题
• 4.2.1 邻域搜索
• 4.2.2 一种改进的邻域结构
• 4.2.3 基于邻域搜索的克隆算子
• 4.2.4 基于邻域搜索的免疫克隆选择算法
• 4.2.5 仿真实验及结果分析
• 4.2.6 小结
• 4.3 加入禁忌策略的免疫克隆选择求解作业车间调度问题
• 4.3.1 循环搜索现象
• 4.3.2 禁忌搜索
• 4.3.3 禁忌策略
• 4.3.4 仿真实验及结果分析
• 4.3.5 小结
• 4.4 本章小结
• 第五章 总结与展望
• 5.1 工作总结
• 5.2 进一步工作展望
• 致谢
• 参考文献
• 攻读硕士期间发表的论文