基于混合蚁群算法Job-Shop调度问题的研究与实现

摘要

Job-Shop调度问题是许多实际车间调度问题的简化模型，是一个典型的NP-Hard问题，已被证明在多项式时间内得不到最优值。蚁群算法是近年来兴起的一种优化算法，特别在解决组合优化问题中被越来越多的人所采用。为了更好的解决Job-Shop调度问题，通常将一些解决某类问题的较好算法组合起来。 本文采用邻域搜索混合蚁群算法和自适应遗传蚁群混合算法来求解Job-Shop调度问题。针对蚁群算法的早熟收敛及收敛速度慢等问题，设计了一种基于邻域搜索的混合蚁群算法。运用具有可变邻域搜索的变异算子对搜索结果进行优化，该算子除了具有通常的变异作用外，还具备步长为2和3的局部搜索功能。最后针对经典Job-Shop调度问题中的LA类部分问题进行了仿真实验，实验结果对比表明，该算法求解Job-Shop调度问题具有较快的寻优速度和更好的全局搜索能力，同时增加了解的多样性，减小了陷入局部极值的几率。在充分分析自适应遗传算法和蚁群算法的基础之上，并根据两种算法的特点，将自适应遗传算法与蚁群算法动态融合来求解Job-Shop调度问题。首先，利用自适应遗传算法全局、随机、快速搜索特性生成部分优秀染色体，将其转化为蚁群算法所需的初始信息素分布，然后利用蚁群算法的正反馈、高效性求取Job-Shop调度问题的最优解；其次，确定自适应遗传算法与蚁群算法的最佳融合时机，避免自适应遗传算法过早或过晚结束而影响整体算法的性能。最后，本文针对Job-Shop调度问题中的11个经典问题进行了仿真实验。结果证明了自适应遗传蚁群算法具有更好的全局收敛性能，即克服了自适应遗传算法搜索到一定阶段时最优解搜索效率降低又避免了蚁群算法初始信息素匮乏的不足之处。尤其是问题规模越大，算法优势越明显。

目录

文摘

英文文摘

声明

第1章绪论

1.1课题研究背景

1.2 Job-Shop调度问题概述

1.2.1 Job-Shop调度问题的描述

1.2.2 Job-Shop调度问题的数学模型

1.2.3 Job-Shop调度问题的析取图模型

1.3车间作业调度问题的研究方法

1.4车间作业调度问题存在的问题及发展趋势

1.4.1车间作业调度问题存在的问题

1.4.2车间作业调度问题的发展趋势

1.5论文结构及主要内容安排

第2章基础理论

2.1蚁群算法

2.1.1蚁群算法基本思想

2.1.2基本蚁群算法

2.1.3蚁群算法总结

2.2遗传算法

2.2.1遗传算法基本思想

2.2.2标准遗传算法

2.2.3遗传算法总结

2.3本章小结

第3章求解Job-Shop调度问题的邻域搜索蚁群算法

3.1基于蚁群算法的Job-Shop调度问题

3.1.1解构造过程

3.1.2信息素更新

3.2改进蚁群算法

3.2.1基本蚁群算法缺点

3.2.2算法改进策略

3.2.3改进算法流程

3.3面向Job-Shop调度问题的邻域搜索蚁群算法

3.4模拟实验及结果分析

3.5本章小结

第4章求解Job-Shop调度问题自适应遗传蚁群算法

4.1自适应遗传蚁群混合算法

4.1.1算法的背景

4.1.2算法融合的基本思想

4.1.3自适应遗传算法策略

4.1.4混合算法动态临界点的确定

4.2面向Job-Shop调度问题的AGA-ACA

4.2.1自适应遗传算法规则

4.2.2蚁群算法规则

4.2.3衔接策略

4.2.4 Job-Shop调度算法流程

4.2.5算法复杂性分析

4.3模拟实验及结果分析

4.4本章小结

结论

参考文献

攻读硕士学位期间发表的学术论文

致谢