基于小生境蚁群算法的JSSP研究

VIP免费
3.0 牛悦 2024-11-19 6 4 1.19MB 59 页 15积分
侵权投诉
摘 要
蚁群算法是一种并行的模拟进化算法，具有较强的解空间搜索能力、适应性
和鲁棒性等优点，但是搜索时间长，容易陷入局部最优解。
本文在寻求有效的车间调度算法时，结合蚁群算法，分析并研究了小生境蚁
群算法在求解 JSSP 中的应用，主要开展了以下的工作。
(1) 提出小生境蚁群优化调度规则，通过蚁群中的并行、多样化寻优活动，从
信息素分布的多样性，蚂蚁更新信息素策略和信息交流多样性方面改进了基本蚁
群算法。
(2) 在求解目标函数为最小加工完成时间的 JSSP 问题时，小生境蚁群优化调
度规则在启发函数、更新路径等环节加入等待时间要素，进一步优化解的性能。
通过与基本蚁群算法，蚁群基本调度规则的比较，证明蚁群优化调度优化能获得
相当的优化结果和寻优性能。
(3) 为了寻求蚁群算法各参数的配置关系，获得良好的寻优性能，较快的收
敛速度。本文采用了正交试验优化配置小生境蚁群优化算法的参数α0、
β0、
kα、
kβ，
分析了α0和β0，kα和kβ，α0和kα以及β0和kβ之间的交互作用对算法的影响，提高
了算法的寻优性能。对不同规模的 TSP 和JSSP 基准算例进行了求解，证明了本
文采用的算法以及优化配置的参数能获得较优求解精度和收敛速度。
(4) 构建了一种不同于传统调度模式的新型的基于小生境蚁群算法的网络化
JSSP 资源调度模式，将小生境蚁群调度规则应用到网络化的资源调度中，结合实
例分析并仿真验证了该调度模式和调度规则的有效性。
关键词：小生境蚁群算法 小生境调度规则 TSP JSSP 正交试验 参数
配置
ABSTRACT
Ant colony algorithm is a parallel simulated evolutionary algorithm, with strong
solution space search ability, adaptability and robustness etc., but the search for a long
time, easy to fall into local optimal solution.
Combined with the ant colony algorithm, Microhabitat Ant Colony Optimization is
analyzed and studied into solving the JSSP while seeking for an effective workshop
scheduling algorithm. Mainly job hve done as follow.
(1) Simulating the parallel and multiform optimized actions of ant colony, basic
scheduling rules of ants (BSRA) were built up. To improve the optimized performance,
Microhabitat Ant Colony Optimization Strategy (MACOS) was built up to improve
basic ant colony optimization (ACO) by pheromone time-varying distribution,
pheromone updating tactic and information exchanging mutation.
(2) Microhabitat Ant colony optimization scheduling rules (MACO SR) were built
up based on MACO to solve JSSP. Waiting time was integrated into the heuristic
function and path updating of MACO SR. MACO SR can achieve more satisfactory
results than basic ACO and BSRA for JSSP with the objects function of minimum
makespan. And MACO SR also shows significant optimization performance.
(3)To find the parameters’ configuration relationship of the Ant Colony Algorithm,
to avoid the running time of the algorithm be so long, run into the local optimal and
achieve stagnation. The parameters,α0、β0、kαand kβof MACO were configured by the
orthogonal experiment to enhance the performance of the algorithm, in which the
interaction of α0and β0,kαand kβ,α0and kα,β0and kβare also analyzed. Some
benchmarks of TSP and JSSP were solved by MACO which shows significant
optimize performance with configured parameters.
(4) Along with the development of computer technology and network technology
a new JSSP network resource scheduling mode is constructed, which is different from
the traditional scheduling mode, and Microhabitat Ant colony optimization rules is
used to slove it. A new JSSP resource scheduling model with examples is discussed,
analysised and simulated in this paper.
Keywords: MACO MACO-SR TSP JSSP Orthogonal Experiment
Parameters’ Configuration
目 录
中文摘要
ABSTRACT
第一章 绪论 .....................................................................................................................1
§1.1 课题背景 ..........................................................................................................1
§1.2 国内外研究现状 ...............................................................................................2
§1.2.1 车间调度问题研究现状 .......................................................................2
§1.2.2 蚁群算法研究现状 ...............................................................................3
§1.3 论文目的以及研究内容 ..................................................................................4
§1.3.1 主要目的以及意义 ................................................................................4
§1.3.2 主要研究内容 ........................................................................................5
第二章 车间调度问题 ...................................................................................................7
§2.1 JSSP 描述 ......................................................................................................... 7
§2.1.1 JSSP 描述 .............................................................................................. 7
§2.1.2 JSSP 的特点和分类 .............................................................................. 8
§2.2 JSSP 模型描述 ................................................................................................. 9
§2.2.1 JSSP 的模型描述 .................................................................................. 9
§2.2.2 JSSP 问题建模 .................................................................................... 10
§2.2.3 JSSP 问题析取图模型 .........................................................................11
§2.3 JSSP 求解算法与策略 ....................................................................................11
§2.3.1 JSSP 求解算法 .....................................................................................11
§2.3.2 JSSP 调度策略 .................................................................................... 12
§2.4 本章小结 ........................................................................................................13
第三章 蚁群优化求解 JSSP ........................................................................................14
§3.1 基本蚁群算法 ................................................................................................14
§3.1.1 基本蚁群算法的原理 .........................................................................14
§3.1.2 基本蚁群算法模型 .............................................................................16
§3.1.3 基本蚁群算法的实现 .........................................................................18
§3.2 小生境蚁群优化 ............................................................................................20
§3.2.1 信息素分布多样性 .............................................................................21
§3.2.2 更新信息素策略 .................................................................................22
§3.2.3 信息交流突变性 .................................................................................23
§3.3 蚁群优化求解 JSSP ...................................................................................... 23
§3.3.1 基本蚁群调度规则 .............................................................................23
§3.3.2 小生境蚁群优化调度规则 .................................................................26
§3.4 仿真和分析 ....................................................................................................27
§3.4.1 算法对比 .............................................................................................27
§3.4.2 算法改进 .............................................................................................28
§3.5 本章小结 ........................................................................................................30
第四章 MACO 的参数配置研究 .............................................................................. 31
§4.1 基本参数 ........................................................................................................31
§4.2 正交试验设计简介 ........................................................................................32
§4.3 基于正交试验的 JSSP 参数配置研究 ......................................................... 33
§4.3.1 正交试验的因素与水平 .....................................................................33
§4.3.2 试验结果 .............................................................................................34
§4.3.3 TSP、JSSP 的结果分析 ......................................................................38
§ 4.4 本章小结 .......................................................................................................41
第五章 网络化 JSSP 的制造资源调度应用 .................................................................42
§5.1 网络化制造资源调度概述 ............................................................................42
§5.2 网络化制造资源调度建模 ............................................................................43
§5.2.1 网络化制造资源描述指标 .................................................................43
§5.2.2 网络化制造资源模型 .........................................................................44
§5.3 调度实例的 MACO 实现 ..............................................................................46
§5.3.1 算法设计 .............................................................................................46
§5.3.2 应用实例 .............................................................................................47
§5.4 本章小结 ........................................................................................................49
第六章 结论与展望 .....................................................................................................50
§6.1 结论 ................................................................................................................50
§6.2 展望 ................................................................................................................51
参考文献 .........................................................................................................................52
在读期间公开发表的论文和承担科研项目及取得成果 .............................................56
致 谢 .............................................................................................................................57
第一章 绪论
1
第一章 绪论
§1.1 课题背景
本论文的研究工作受到国家自然科学基金资助的研究项目（50505030），《基
于蚁群生态模型的区域性网络化制造动态联盟研究》，上海市曙光计划研究项目
（07SG51）《基于仿生优化的制造网格系统资源配置研究与应用》的资助。
自21 世纪以来，随着科学技术的迅猛发展，生产规模越来越大，复杂性越来
越高，市场竞争也越来越激烈，因此对企业的管理和市场的监控都提出了更高的
要求。很多的企业为了赢得市场、赢得用户而全面减小成本、缩短交货期、提高
企业的服务质量。而近几十年来，各类生产过程都发生了显著的变化，其主要特
征是生产规模的大型化和生产过程的连续化。在激烈的市场竞争中，为了保证生
产的高效稳定有序运行，以获得最大的经济效益，原来简单的、局部的、常规的
控制和仅凭经验的管理已经不能满足现代生产的要求了。许多企业都采用 MRP/
ERP 系统来加强管理，然而生产计划管理跟市场的关系越来越紧密而且极易受市
场影响。面对客户对交货期的提出的苛刻要求、对更多产品改型、订单的调整，
企业的决策者认识到，计划的制订要依赖于市场和实际的作业执行状态，而不能
完全依靠物料和库存来指导生产。因此如何在现有有限的资源上尽可能的满足被
加工任务所需的各种约束条件，使所有的订单任务能尽量按时完成并获得最佳的
经济效益，就成为一个亟待解决的现实问题[1]。
理论上已经证明了车间调度问题属于典型的 NP-hard 问题[2]，即算法不可能
在多项式复杂度的时间内找到问题的最优解。随着现代制造业的发展提高了车间
调度问题[3]的复杂性和重要性，迫切的需要一种求解车间调度问题行之有效的方
法。如何利用计算机模拟车间调度过程，提供最简洁、高效的调度方案成为越来
越多的研究人员研究的内容，随着对调度问题的深入研究和各种交叉学科的蓬勃
发展，新的车间调度理论和新的调度算法不断的涌现在车间调度问题的研究上取
得良好的效果。
基于小生境蚁群算法的 JSSP 研究
2
§1.2 国内外研究现状
§1.2.1 车间调度问题研究现状
自20 世纪 50 年代以来，国内外大量学者对车间调度问题做了大量的研究；
其中 50 年代早期的 S M Johnson 提出解决 N/2/F/Cmax 问题的求解时经典调度理
论诞生的重要标志[4]。从 20 世纪 60 年代开始对车间问题的研究从求解一些特殊
的小规模流水车间调度问题到利用整数规划、动态规划、分枝界定来求解车间调
度问题，这一时期 Story[5]提出使用数学规划模型和算法求解车间调度问题，同时
Gavet[6]开始尝试用启发式算法研究车间作业调度问题。20 世纪 60 年代后期初步
形成经典调度理论。20 世纪 70 年代，人们开始了算法复杂性的研究，多数调度
问题被证明属于 NP-hard 问题[2]，难以找到多项式算法，因此开始关注启发式算
法。Panwalkar[7]总结和归纳出了 113 条调度规则，并对其进行了分类。70 年代后
期，经典调度理论趋向成熟。1975 年，越民义、韩继业发表的论文[8]首次推动了
车间调度问题在我国的研究。20 世纪 90 年代，随着计算机应用技术的发展，各
种方法在车间调度问题的研究中得到了充分的发挥，同时新的研究手段层出不穷。
其中智能调度已成为车间调度问题研究的主流，其中蚁群算法等智能优化技术在
调度问题研究中的应用成为该领域的又一个新的发展方向。这时采用的方法有:
智能规划方法[9]、仿真调度方法[10]、Genetic Algorithm(GA[11])、Artificial Neural
Network(ANN) [12]、Tabu Search(TS)、Simulated Annealing (SA)，蚁群算法(ACO）
等。实验证明，利用这些智能搜索算法，在类似与解决车间调度存在“组合爆炸”
问题的组合优化问题方面，可以在一定的时间内求得问题的近似最优解。
近几年来，随着软件技术及其它相关技术的发展和计算机硬件性能的提高，
开发智能化生产计划与控制系统的时机己经成熟。目前，国外许多科研机构和软
件公司都研究和开发了针对各种生产实际的生产作业计划和调度系统，国内许多
高校和科研机构如清华大学、东北大学等单位参与了该领域的工作，有些成果得
到了一定程度的应用。华东理工大学的顾幸生、陈知美等[13]对蚁群算法进行了改
进并利用到 JOB-SHOP 调度问题中取得了很好的研究成果。陈义宝[14]、赵虎[15]、
孙新宇[16]等也对蚁群算法做出了一定的改进取得了相关成果。以上这些关于车间
调度问题的蚁群算法在解决小型的调度优化方面有很好的效果，但是用于大型的
调度系统时候有的不收敛，有的早熟得不到最优解，有的求解时间很长。
摘要：

摘要蚁群算法是一种并行的模拟进化算法，具有较强的解空间搜索能力、适应性和鲁棒性等优点，但是搜索时间长，容易陷入局部最优解。本文在寻求有效的车间调度算法时，结合蚁群算法，分析并研究了小生境蚁群算法在求解JSSP中的应用，主要开展了以下的工作。(1)提出小生境蚁群优化调度规则，通过蚁群中的并行、多样化寻优活动，从信息素分布的多样性，蚂蚁更新信息素策略和信息交流多样性方面改进了基本蚁群算法。(2)在求解目标函数为最小加工完成时间的JSSP问题时，小生境蚁群优化调度规则在启发函数、更新路径等环节加入等待时间要素，进一步优化解的性能。通过与基本蚁群算法，蚁群基本调度规则的比较，证明蚁群优化调度优化能获得...

展开>> 收起<<
基于小生境蚁群算法的JSSP研究.pdf

共59页,预览6页

还剩页未读， 继续阅读

相关推荐

更多
立即下载
作者：牛悦 分类：高等教育资料 价格：15积分 属性：59 页 大小：1.19MB 格式：PDF 时间：2024-11-19

开通VIP享超值会员特权

  • 多端同步记录
  • 高速下载文档
  • 免费文档工具
  • 分享文档赚钱
  • 每日登录抽奖
  • 优质衍生服务

作者详情

相关内容

更多

推荐作者

热门标签

/ 59
评分 收藏
分享
立即下载 VIP免费下载
客服
关注