基于约束满足的改进蚁群算法在车间调度中的应用研究

论文摘要

调度（Scheduling）研究的问题是将有限的资源实行任务的时间分配,以实现某性能指标最优。而现实中的调度问题多为复杂的组合优化问题,如车间调度问题（Job-shop Scheduling Problem, JSP）即为典型的NP难问题,在其复杂多项式时间内难以找到最优解。因车间调度问题的研究具有理论和实践意义,所以一直是调度问题中研究的热点,也是难点,近年来对JSP的研究主要集中于利用现代智能算法以及各种改进的混合算法求近似解。本文利用新兴的蚁群优化算法,结合约束满足技术对车间调度问题进行求解。蚁群优化算法（Ant Colony Optimization Algorithm, ACO）因其鲁棒性、正反馈性、并行性等优点,已经在求解很多组合优化问题方面取得了良好的效果,算法的效率也很高；但是蚁群算法也存在着收敛慢、易停滞的缺点。本文在充分利用蚁群算法优点的前提下,对蚁群算法进行改进,采用全局和局部信息素更新相结合的信息素更新策略以避免算法过早停滞；而对于收敛慢的缺点,采用约束满足技术修剪搜索空间,以加快搜索速度,提高算法效率。另外,蚁群算法中各参数的选取对算法的性能也有较大的影响,本文也给出了详细的分析。约束满足（Constraint Satisfaction）作为求解大规模组合优化问题的方法之一,能对搜索空间进行修剪,从而大大减少搜索的次数和时间。一致性预处理技术和约束传播技术可以在搜索过程中动态地排除不符合约束条件的区域,使搜索过程不必遍历所有的变量和赋值,只须保持局部一致性。混合算法充分利用二者的优点,约束满足技术的使用使得蚁群算法的效率有了更进一步的提高,从而很快地找到可行解和最佳方案。本文通过实验验证了混合算法的可行性,并通过标准的车间调度实例进行仿真实验,实验结果的分析比较（和其他算法进行比较）证明,改进的混合算法不但具有可行性,而且具有高效性。另外,本文还实现了实际生产调度过程中并行机存在时的调度情况,使算法的求解更符合实际生产的要求。最后,本文利用C++Builder和Microsoft SQL Server 2000开发了车问调度系统,实现了车间资源的信息管理；并在系统中集成了混合算法的调度优化。

论文目录

• 中文摘要
• Abstract
• 第1章 绪论
• 1.1 引言
• 1.2 调度问题研究现状
• 1.2.1 国内外文献综述
• 1.2.2 研究存在的问题
• 1.3 课题研究的目的及意义
• 1.3.1 课题研究的目的
• 1.3.2 课题研究的意义
• 1.4 课题来源
• 1.5 课题研究的内容方法和论文结构
• 1.5.1 研究的主要内容与方法
• 1.5.2 论文结构
• 第2章 车间调度问题
• 2.1 车间调度问题
• 2.1.1 车间调度问题的概念及描述
• 2.1.2 车间调度问题的数学模型
• 2.1.3 车间调度问题的约束分析
• 2.1.4 车间调度问题的性能评价标准
• 2.1.5 解的表示方法
• 2.2 车间调度问题的分类及特点
• 2.2.1 车间调度问题的分类
• 2.2.2 车间调度问题的特点
• 2.3 车间调度问题计算复杂性
• 2.4 车间调度问题常用的优化算法
• 第3章 蚁群算法
• 3.1 蚁群算法基本知识
• 3.1.1 蚁群算法产生背景
• 3.1.2 蚁群算法的基本原理
• 3.1.3 蚁群优化算法的发展及应用
• 3.1.4 蚁群优化算法的特点
• 3.2 蚁群算法的模型（以TSP为例）
• 3.2.1 基本的蚁群算法
• 3.2.2 TSP模型
• 3.2.3 参数选取与分析
• 3.2.4 算法实现步骤
• 3.3 改进的蚁群算法
• elite)'>3.3.1 带精英策略的蚂蚁系统(AS_elite)
• 3.3.2 蚁群系统
• rank)'>3.3.3 基于优化排序的蚂蚁系统(AS_rank)
• 3.3.4 最大最小蚂蚁系统
• 3.3.5 其它改进算法和混合算法
• 3.4 蚁群优化算法解决JSP
• 3.4.1 模型及初始化
• 3.4.2 算法流程及步骤
• 第4章 基于约束满足的蚁群算法求解JSP
• 4.1 约束满足技术
• 4.1.1 约束满足技术的数学描述
• 4.1.2 约束满足技术的求解方法
• 4.2 改进的蚁群算法
• 4.2.1 信息素更新策略
• 4.2.2 算法流程
• 4.3 基于约束满足的改进蚁群算法
• 4.3.1 约束满足技术的应用
• 4.3.2 改进算法的流程及步骤
• 4.3.3 改进算法的TSP求解和验证
• 4.3.4 改进算法的JSP求解模型
• 第5章 基于改进蚁群算法的车间管理与调度原型系统
• 5.1 原型系统的设计与开发
• 5.1.1 设计原则
• 5.1.2 系统体系结构与功能设计
• 5.1.3 开发工具与运行环境
• 5.2 原型系统的功能实现
• 5.2.1 系统功能模块
• 5.2.2 模块功能实现
• 5.3 原型系统的运行与分析
• 5.3.1 问题建模
• 5.3.2 仿真与甘特图
• 5.3.3 算法分析与比较
• 5.4 小结
• 第6章 总结与展望
• 6.1 全文总结
• 6.2 展望
• 参考文献
• 致谢
• 攻读学位期间发表的与学位论文相关的论文