首页> 正文

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

2020-12-01阅读(489)

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

论文摘要

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

论文目录

  • 摘要
  • Abstract
  • 第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 本章小结
  • 结论
  • 参考文献
  • 攻读硕士学位期间发表的学术论文
  • 致谢

    • 相关论文文献

    • [1].考虑倒垛情况的场吊调度问题研究[J]. 交通运输工程与信息学报 2017(02)
    • [2].一种电网经济调度问题的分布式对偶优化解法[J]. 山西建筑 2016(33)
    • [3].云制造调度问题研究综述[J]. 计算机集成制造系统 2017(06)
    • [4].水电混合网络经济调度问题的分布式优化算法设计与分析（英文）[J]. 电子科技大学学报 2020(05)
    • [5].考虑维护且原材料易变质的单机调度问题[J]. 黑龙江工业学院学报(综合版) 2020(07)
    • [6].混合并行机调度问题的多目标优化模型及算法[J]. 控制理论与应用 2014(11)
    • [7].建模分析外卖送餐员的调度问题[J]. 数理天地(初中版) 2020(04)
    • [8].求解调度问题的粒子群算法编码方法研究[J]. 武汉科技大学学报 2010(01)
    • [9].基于“实时智能”方法的港口物流调度问题研究[J]. 物流技术 2009(12)
    • [10].考虑空载能耗的双代理单机调度问题[J]. 电子世界 2020(10)
    • [11].浅谈公共自行车调度问题[J]. 科技风 2015(21)
    • [12].基于二分图匹配的一类多机调度问题研究[J]. 软件导刊 2009(07)
    • [13].航空器着陆调度问题的一种新型元启发式方法（英文）[J]. Transactions of Nanjing University of Aeronautics and Astronautics 2020(02)
    • [14].综合考量借还车需求与调度成本的公共自行车调度优化模型[J]. 中国公路学报 2019(07)
    • [15].考虑行为特征的分布式流水线调度问题研究[J]. 信息通信 2019(06)
    • [16].大数据背景下集群调度结构与研究进展[J]. 计算机研究与发展 2018(01)
    • [17].具有负载依赖型维护时长和弹性维护开始时刻的单机调度问题[J]. 江西科学 2017(01)
    • [18].考虑设备定周期预防性维护的单批处理机调度问题研究[J]. 电子世界 2020(15)
    • [19].带模糊排序的移动瓶颈法求解不确定调度问题[J]. 机械制造 2011(02)
    • [20].空间调度问题的非线性规划分析求解方法[J]. 计算机集成制造系统 2010(06)
    • [21].关于柔性制造系统调度问题的研究[J]. 牡丹江师范学院学报(自然科学版) 2010(02)
    • [22].工件有尺寸的单机批调度问题的在线算法[J]. 山东大学学报(理学版) 2009(12)
    • [23].考虑成本的最大延迟时间同类机调度问题[J]. 运筹与管理 2019(12)
    • [24].微电子生产过程调度问题基于指标快速预报的分解算法[J]. 控制与决策 2020(01)
    • [25].配网调度精细化管理对策[J]. 低碳世界 2018(10)
    • [26].基于优先规则的复杂并行机调度问题研究[J]. 系统工程理论与实践 2016(03)
    • [27].飞机调度系统的数学模型设计[J]. 数码世界 2018(09)
    • [28].带有单服务器的并行机调度问题[J]. 沈阳大学学报(自然科学版) 2012(04)
    • [29].混合离散教与学算法求解复杂并行机调度问题[J]. 自动化学报 2020(04)
    • [30].基于调度池的共享单车调度研究[J]. 交通信息与安全 2019(05)

    标签：;  ;  ;  

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

    猜你喜欢

    © 2024 毕速过 版权所有 鄂ICP备12018319号-5