面向蚁群算法的车间调度问题研究

论文题目: 面向蚁群算法的车间调度问题研究

论文类型: 硕士论文

论文专业: 计算机应用技术

作者: 周品

导师: 李小平

关键词: 车间调度,蚁群算法,启发式算法

文献来源: 哈尔滨理工大学

发表年度: 2005

论文摘要: 车间调度是一个典型的NP 难问题,理论上已经证明想在多项式时间内对这一类问题找到全局最优解是不可能的。蚁群算法是近年来兴起的一种寻优算法,特别在解决组合优化问题中被越来越多的人所采用。本文应用蚁群算法求解两个车间调度问题,提出建立蚂蚁初始点的概率优先权分布方法,利用蚁群算法的正反馈和并行搜索特点提高解的质量和稳定性。1. 通过对基本蚁群算法的实现过程和Job-shop 调度问题的分析和研究,给出了求解Job-shop 调度问题的析取图模型,并给出了详细的ACA 蚁群算法求解Job-shop 调度问题的算法描述,然后通过对28 个Benchmark 实例进行模拟。试验结果表明:蚁群算法可以有效地求解车间调度问题;对于个别实例可以达到最优解;蚁群算法的平均性能优于遗传算法。2. 通过对基本蚁群算法的实现过程和流水调度问题进行研究,给出了求解流水调度问题的解构造图,提出了两种蚁群算法来求解以总流程时间最小为目标的流水调度问题-FACA 蚁群算法和PACA 蚁群算法,分别给出了FACA 蚁群算法和PACA 蚁群算法的参数初始化方式、相对应的信息素更新方法和概率分布规则,并提出了局部搜索模式,最后进行模拟试验,对这两种算法进行比较,试验结果表明:对于较大规模的问题,PACA 蚁群算法要优于FACA 蚁群算法,而对于较小规模的问题,FACA 蚁群算法优于PACA蚁群算法。平均来说,PACA 蚁群算法的性能优于FACA 蚁群算法。

论文目录:

摘要

Abstract

第1章 绪论

1.1 车间调度问题及其传统研究方法

1.1.1 车间调度问题

1.1.2 车间调度问题的分类

1.1.3 车间调度问题的研究状况

1.2 蚁群算法及其研究状况

1.2.1 蚁群算法

1.2.2 蚁群算法的研究现状

1.2.3 蚁群算法的发展方向

1.3 课题来源及论文主要研究内容

1.3.1 课题来源

1.3.2 主要研究内容

1.4 论文结构

第2章 蚁群算法参数初始化

2.1 引言

2.2 蚁群算法的原理

2.2.1 蚁群算法的物理学背景

2.2.2 蚁群算法的原理

2.3 蚁群算法的实现

2.3.1 蚁群算法的参数设定

2.3.2 蚁群算法的步骤

2.4 蚁群算法的特点

2.5 蚁群算法在组合优化中的应用

2.5.1 蚁群算法在静态组合优化中的应用

2.5.2 蚁群算法在动态组合优化中的应用

2.6 本章小结

第3章 Job-shop调度问题的蚁群算法求解

3.1 引言

3.2 Job-shop调度问题描述

3.3 Job-shop调度问题的析取图模型

3.4 面向Job-shop调度问题的ACA蚁群算法

3.4.1 ACA蚁群算法的参数初始化

3.4.2 面向Job-shop调度问题的ACA蚁群算法描述

3.4.3 实例说明ACA蚁群算法求解过程

3.4.4 模拟试验结果与分析

3.5 本章小结

第4章 流水调度的蚁群算法求解

4.1 引言

4.2 流水调度问题描述

4.3 流水调度的模型

4.4 面向流水调度问题的FACA 蚁群算法

4.4.1 FACA蚁群算法的参数初始化

4.4.2 FACA蚁群算法的描述

4.4.3 构造蚂蚁序列及局部搜索模式

4.4.4 信息素更新

4.5 面向流水调度问题的PACA蚁群算法

4.5.1 PACA蚁群算法的参数初始化

4.5.2 构造蚂蚁序列

4.5.3 信息素更新

4.6 模拟试验结果与分析

4.7 本章小结

结论

参考文献

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

致谢

发布时间: 2005-11-18

参考文献

• [1].置换流水车间调度问题上的蚁群算法研究[D]. 杨文进.湖南大学2010
• [2].基于约束满足的改进蚁群算法在车间调度中的应用研究[D]. 禹晓蕾.武汉理工大学2010
• [3].基于新的动态邻域算法的车间调度问题的研究[D]. 卫鑫.西安电子科技大学2009
• [4].基于蜂群繁殖算法的流水车间调度问题研究[D]. 郭鹏.华中科技大学2012
• [5].类电磁机制算法的改进与应用[D]. 王双记.西安电子科技大学2012
• [6].竞选算法及其应用研究[D]. 李劲.广东工业大学2008
• [7].利用混合多目标智能算法求解柔性流水车间调度问题[D]. 刘晓娟.长安大学2014
• [8].类电磁机制算法及其若干应用研究[D]. 王晓娟.华中科技大学2006
• [9].相关工件车间调度问题模型与算法研究[D]. 腾方媛.哈尔滨理工大学2018
• [10].求解流水车间调度问题的分解多目标局部搜索算法[D]. 李明杰.东北师范大学2016

相关论文

• [1].蚁群算法求解生产调度问题研究[D]. 薛拾贝.上海交通大学2008
• [2].基于改进蚁群算法的车间调度方法及实现[D]. 熊婧.浙江工业大学2007
• [3].蚁群算法在组合优化中的应用[D]. 曾艳.西安电子科技大学2006
• [4].作业车间调度的建模及优化方法研究[D]. 陆韡.上海交通大学2007
• [5].基于蚁群算法的车辆优化调度系统[D]. 周涛.电子科技大学2007
• [6].蚁群算法研究及其应用[D]. 黄瑞平.西北大学2007
• [7].遗传蚁群混合算法及其在车间调度问题中的应用[D]. 姜欢容.武汉理工大学2007
• [8].改进蚁群算法研究及其在车辆调度中的应用[D]. 兰世海.东华大学2007
• [9].基于蚁群算法的车辆调度问题研究[D]. 滕玮.华中师范大学2006
• [10].蚁群算法的改进与应用[D]. 秦玲.扬州大学2004

标签：车间调度论文;  蚁群算法论文;  启发式算法论文;