基于免疫遗传算法的Job Shop调度问题研究

论文摘要

Job Shop调度是计算机集成制造系统（CIMS）工程中的一个重要组成部分,它对企业的生产管理和控制系统有着重要的影响。同时,Job Shop调度问题（Job Shop schedulingproblem,JSP）又是一个典型的NP Hard问题,是组合优化问题中最难求解的问题之一。将优化方法的理论研究引入到Job Shop生产调度领域中,改进算法性能、拓宽算法应用领域,完善算法体系,是一个同时具有理论意义和应用价值的课题。本文分析总结了一些现有的调度算法,针对它们的不足,基于免疫理论和遗传算法,设计了一种新颖的自适应混合免疫遗传算法SIGA（Self-adaptive Hybrid Immune GeneticAlgorithm）。为了更有效地求解JSP,基于SIGA提出了改进的调度算法SIGAⅡ。本文的主要工作如下:1.针对传统免疫遗传算法存在过早收敛及后期搜索效率低的问题,提出一种基于浓度的自适应混合免疫遗传算法（SIGA）,该算法有效融合多种群遗传算法与模拟退火算法的优点,同时在算法中引入生物免疫系统中抗体多样性的维持机制,提出了基于浓度的自适应交叉变异算子和选择策略,通过仿真实验,证明了算法的有效性;2.将该算法应用于求解JSP,给出了一种基于免疫遗传算法的求解方法,以及染色体的编码方法和相应的免疫遗传操作,针对Job Shop调度问题的特殊复杂性,本文将转换瓶颈算法（Shifting Bottleneck）和禁忌算法（Tabu）两者相结合,提出了一种瓶颈禁忌算法（STA）,并将瓶颈禁忌算法引入SIGA中,提出改进的自适应混合免疫遗传算法（SIGAⅡ）,加强算法在求解JSP的局部搜索能力,从而进一步提高算法的性能。3.通过对JSP中的经典Benchmarks算例问题进行仿真实验,系统地分析了一些关键参数和算子对算法性能的影响,结果证明改进的自适应混合免疫遗传算法优于其他四种算法,具有更好的全局收敛性能。最后将SIGAⅡ应用于实际的生产调度,满足企业的生产需求,验证算法的实用性。

论文目录

• 摘要
• ABSTRACT
• 第1章 绪论
• 1.1 研究的背景
• 1.2 研究的意义
• 1.3 国内外的研究现状
• 1.4 本文主要研究内容
• 1.5 论文结构
• 第2章 Job Shop车间调度问题概述
• 2.1 车间调度问题的分类
• 2.2 车间调度问题的特点
• 2.3 Job Shop调度问题
• 2.3.1 Job Shop调度问题的描述
• 2.3.2 Job Shop调度问题的描述方法
• 2.3.3 优化目标
• 2.3.4 调度算法的设计
• 2.3.5 经典的调度算法
• 2.4 本章小结
• 第3章 免疫遗传算法概述
• 3.1 遗传算法
• 3.1.1 遗传算法的基本思想
• 3.1.2 遗传算法的概念
• 3.1.3 遗传操作的基本操作
• 3.1.4 遗传算法的基本流程
• 3.1.5 遗传算法的特点
• 3.1.6 遗传算法存在的不足
• 3.2 免疫算法
• 3.2.1 生物免疫机制
• 3.2.2 免疫算法
• 3.2.3 免疫算法的分类
• 3.3 免疫遗传算法
• 3.3.1 免疫遗传算法的特点
• 3.3.2 研究现状
• 3.3.3 免疫遗传算法的不足
• 3.4 模拟退火算法
• 3.4.1 新解的产生和接受机制
• 3.4.2 模拟退火算法的步骤
• 3.4.3 模拟退火算法的特点
• 3.5 本章小结
• 第4章 自适应混合免疫遗传算法——SIGA
• 4.1 基于浓度的自适应种群更新策略
• 4.1.1 新的浓度定义
• 4.1.2 基于浓度的自适应交叉变异
• 4.1.3 基于浓度的种群更新
• 4.2 免疫操作
• 4.2.1 接种疫苗
• 4.2.2 免疫选择
• 4.2.3 免疫记忆
• 4.3 双种群系统
• 4.4 算法流程
• 4.5 性能分析
• 4.5.1 问题描述
• 4.5.2 实验结果与分析
• 4.6 本章小结
• 第5章 基于SIGA的Job Shop调度
• 5.1 编码设计
• 5.2 初始种群的产生
• 5.3 疫苗接种
• 5.4 适应值函数
• 5.5 遗传算子的设计
• 5.5.1 选择策略
• 5.5.2 交叉策略
• 5.5.3 变异策略
• 5.5.4 模拟退火选择
• 5.6 基于瓶颈禁忌的局部搜索
• 5.6.1 转换瓶颈算法
• 5.6.2 禁忌算法
• 5.6.3 基于瓶颈禁忌的局部搜索
• 5.7 改进的自适应混合免疫遗传算法——SIGA Ⅱ
• 5.8 本章小结
• 第6章 算法的性能分析与应用
• 6.1 实验和性能分析
• 6.1.1 疫苗评估
• 6.1.2 参数评估
• 6.1.3 机制评估
• 6.1.4 算法性能的对比分析
• 6.2 SIGA Ⅱ的实际应用
• 6.2.1 应用实例Ⅰ
• 6.2.2 应用实例Ⅱ
• 6.3 本章总结
• 第7章 总结与展望
• 7.1 结论
• 7.2 展望
• 参考文献
• 致谢
• 攻读学位期间参加的科研项目和成果