基于混合蚁群算法的车间作业调度问题求解

论文摘要

随着市场竞争的日益激烈,面向顾客订货的、多品种、小批量生产已经成为21世纪的主导生产模式。相应地,制造企业正向着精益生产和敏捷制造的方向发展。在这种生产环境下,如何安排生产计划、如何进行调度成为企业有效进行生产的关键问题。有效的调度方法与优化技术的研究和应用,对于制造企业提高生产效率、降低生产成本等方面起着重要作用,因而越来越受到学者们的关注。生产与运作管理的核心是车间作业调度问题(JSSP)能否高效的获得优化解,因此,JSSP的调度策略一直是制造业研究的重点之一,对JSSP的研究具有重要的理论意义和现实意义。蚁群优化算法(Ant Colony Algorithms,ACA)是一种近年来才发展起来的新颖的仿生型的智能优化算法,具有正反馈、分布计算和启发性搜索等特点。作为计算智能和群智能的重要分支之一,蚁群优化算法的研究方兴未艾,备受瞩目。蚁群优化算法的思想来源于我们真实世界中的蚂蚁群体的智能特性。本文介绍了JSSP研究的目的、意义及其重要性,分析了国内外对JSSP进行研究的方法与发展现状;研究了JSSP的特点及其分类,探讨了JSSP的调度策略,回顾了求解JSSP的主要历程及其方法;对蚁群优化算法的发展背景、内容、实现方法作了详细介绍,对该算法本身进行了深入研究,提出了自己的改进方案。本文主要有以下几个方面创新:提出一种新的JSSP邻域结构,与传统的邻域结构比较,有效的缩小邻域空间的规模;针对蚁群优化算法中信息素强度在蚁群之间起通讯、协作的关键作用,提出了利用全局和局部最优解来增强优质个体所走路径上的信息素强度的方案;简化了蚁群优化参数设置问题,对部分参数实行动态的调整策略;提出了一种通过分阶段变邻域求解JSSP的新的混合算法。最后通过面向对象技术思想实现了系统核心调度算法功能,给出了一种基于MVC模式进行系统设计方法,为进一步的工作奠定基础。通过对一些代表性的基准问题进行仿真,混合蚁群算法能够更快速的搜索到更优解,加快算法的收敛速度,提高算法的搜索能力,能够有效的解决JSSP问题。本文研究成果对蚁群算法的研究有一定的参考价值,并对建立现代优化调度系统有现实的理论指导意义和应用价值。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 课题研究目的及意义
• 1.2 国内外研究现状
• 1.3 本文研究内容
• 第二章 车间作业调度问题
• 2.1 车间调度问题的分类
• 2.2 车间作业调度问题的描述
• 2.2.1 车间作业调度问题（Job Shop Scheduling Problem）
• 2.2.2 性能评价标准
• 2.2.3 JSSP的基本数学模型
• 2.3 车间作业调度问题的表示方法
• 2.3.1 甘特图（Gantt Chart）表示法
• 2.3.2 析取图（Disjunctive Graph）表示法
• 2.4 JSSP的计算性复杂性
• 2.5 JSSP的求解方法
• 第三章 蚁群算法及其对JSSP的求解
• 3.1 蚂蚁觅食行为及其优化过程
• 3.1.1 蚂蚁觅食行为
• 3.1.2 双桥实验
• 3.2 基本蚁群算法原理及研究
• 3.2.1 旅行商问题（TSP）描述
• 3.2.2 基本蚁群算法的实现
• 3.2.3 蚁群算法流程
• 3.2.4 算法的复杂度分析
• 3.3 基本蚁群算法的特点及研究发展
• 3.4 蚁群算法求解JSSP的研究
• 3.4.1 JSSP的表示方法
• 3.4.2 符合调度约束的工序判断准则
• 3.4.3 规则定义
• 3.4.4 蚁群算法解决JSSP的实现步骤
• 3.4.5 应用基本蚁群算法求解JSSP分析
• 第四章 邻域搜索算法求解JSSP
• 4.1 领域搜索算法的基本概念
• 4.1.1 邻域结构与局部最优
• 4.1.2 邻域搜索算法的描述
• 4.1.3 邻域搜索算法的特性
• 4.1.4 避免局部最优
• 4.2 JSSP的邻域结构及其研究
• 4.2.1 关键路径（critical path）和关键块（critical block）
• 4.2.2 AE领域结构
• 4.2.3 CB领域结构
• 4.2.4 JSSP邻域结构的设计
• 4.2.5 CBI邻域结构下的非法移动判断
• 第五章 混合蚁群算法对JSSP的求解
• 5.1 蚁群系统（ACS）
• 5.2 最大最小蚂蚁系统（MMAS）
• 5.3 混合蚁群算法设计
• 5.3.1 前期全局搜索阶段
• 5.3.2 后期快速收敛阶段
• 5.3.3 q0动态调整策略
• 5.3.4 算法流程图
• 5.3.5 算法伪代码
• 5.3.6 参数的控制设定
• 5.3.7 混合蚁群算法特点分析
• 第六章 算法实现与仿真
• 6.1 算法实现
• 6.1.1 数据结构定义
• 6.1.2 求解Makespan算法
• 6.1.3 基于面向对象技术的系统设计
• 6.1.4 混合蚁群算法的高层视图
• 6.1.5 基于MVC模式的软件系统设计
• 6.2 仿真实验
• 第七章 总结与展望
• 7.1 总结
• 7.2 展望
• 致谢
• 参考文献
• 攻硕期间取得的研究成果