蚁群优化算法在平行机批调度问题中的应用与研究

发布时间：2017-07-15 10:26

  本文关键词：蚁群优化算法在平行机批调度问题中的应用与研究

  更多相关文章： 平行批处理机 差异尺寸工件 动态到达 不同机器容量 机器适应限制 蚁群优化算法

【摘要】：生产调度问题是一类组合优化问题,应用背景十分广泛,其研究成果已经较为丰富,并且已被应用到许多现实的生产实践中。与经典调度问题不同的是,在批处理机调度问题中,多个工件可以同时在一台机器上加工,只有满足容量约束的工件才能在该机器上加工。所以批调度问题更加接近实际,对批处理机调度问题的深入探索和研究具有十分重要的意义。首先,本文简单介绍了生产调度问题的产生背景、与调度问题有关的概念并简单介绍了调度问题的分类：然后简单介绍了批处理机调度问题、差异工件尺寸的批处理机调度问题及动态环境下差异工件尺寸的批处理机调度问题以及这几类问题的研究现状。第二,本文简单介绍了当前用于求解批处理机调度问题的两种主流方法,即确定性方法和近似性方法,然后对这两种主流方法的特点做了简要的分析并且简单介绍了这两种主流方法的代表性算法及其大致框架。第三,在容量差异的平行批处理机环境下,针对工件带有差异尺寸以及机器适用限制的最小化制造跨度的批调度问题,提出一种有效的蚁群优化(ACO1)算法。首先给出了问题假设并且分析了问题的复杂性。为了衡量算法的性能,给出问题的一个有效下界。然后提出基于MultiFit规则的启发式算法以及基于ACO1的元启发式算法分别对问题进行求解。在基于ACO1的算法中,根据解的浪费空间与问题目标的相关性分析,基于浪费空间定义启发式信息来指导蚂蚁的行为。同时,采用候选集策略来构建解,以减小搜索空间。此外引入一种局部优化方法对蚂蚁所构建的解进行优化,以进一步提高解的质量。最后,通过仿真实验比较所提算法与其他已有算法的性能,实验结果表明所提的ACO1算法优于其他算法。第四,在容量不同的平行批处理机环境下,针对工件动态到达且差异工件尺寸以及机器适用限制的最小化制造跨度的批处理机调度问题,提出一种有效的蚁群优化(AC02)算法。除了在静态批调度问题中使用的策略之外,在构建的过程中采用ERT规则对机器集合中每台机器上已有的批序列排序,从而减少工件到达时间对解的影响。此外引入一种局部优化策略对蚂蚁所构建的解进行优化,以进一步提高解的质量。最后,通过仿真实验比较所提算法与其他已有算法的性能,实验结果表明所提的AC02算法优于其他算法。最后,总结了本文所研究的批调度问题以及所提出的解决方法,然后对本文所研究的批调度问题在未来的更进一步的方向做了展望。
【关键词】：平行批处理机 差异尺寸工件 动态到达 不同机器容量 机器适应限制 蚁群优化算法
【学位授予单位】：安徽大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：TP18
【目录】：

• 摘要3-5
• Abstract5-9
• 第一章 引言9-15
• 1.1 调度问题概述9-11
• 1.1.1 研究背景9
• 1.1.2 问题描述及问题分类9-11
• 1.2 批调度问题11-13
• 1.2.1 差异工件尺寸批调度问题12-13
• 1.2.2 动态环境下差异工件尺寸的批调度问题13
• 1.3 论文研究内容及结构安排13-15
• 1.3.1 论文研究内容13-14
• 1.3.2 论文结构安排14-15
• 第二章 批调度问题的研究方法15-21
• 2.1 确定性算法15-16
• 2.2 启发式算法16-17
• 2.3 元启发式算法17-21
• 第三章 差异容量下差异工件尺寸的平行机批调度算法研究21-36
• 3.1 差异容量平行机批调度算法研究21-23
• 3.1.1 问题假设21-22
• 3.1.2 问题下界22-23
• 3.2 基于MultiFit的启发式23-24
• 3.3 基于ACO1的元启发式算法24-28
• 3.3.1 编码机制24
• 3.3.2 信息素定义和更新24-25
• 3.3.3 启发式信息和候选列表25-27
• 3.3.4 解的构建和局部优化策略27-28
• 3.3.5 算法ACO1过程28
• 3.4 实验结果与分析28-35
• 3.4.1 实验参数设置28-29
• 3.4.2 ACO1算法参数设置29-30
• 3.4.3 实验结果与分析30-35
• 3.5 本章小节35-36
• 第四章 动态环境下差异容量平行机批调度算法研究36-52
• 4.1 动态环境下平行机批调度算法研究36-38
• 4.1.1 问题假设36-37
• 4.1.2 问题下界37-38
• 4.2 启发式算法38-39
• 4.3 基于ACO2的元启发式算法39-44
• 4.3.1 编码机制39
• 4.3.2 信息素定义和更新39-40
• 4.3.3 启发式信息和候选列表40-42
• 4.3.4 解的构建和局部优化策略42-43
• 4.3.5 算法ACO2过程43-44
• 4.4 仿真实验44-50
• 4.4.1 实验参数设置44-45
• 4.4.2 蚁群算法参数设置45-46
• 4.4.3 实验结果与分析46-50
• 4.5 本章小结50-52
• 第五章 总结与展望52-54
• 5.1 总结52-53
• 5.2 展望53-54
• 参考文献54-59
• 致谢59-60
• 攻读学位期间发表的学术论文目录60

【相似文献】

中国期刊全文数据库 前10条

1 刘文涛,张群,孙肃清;关于炼钢厂重调度问题的研究[J];冶金自动化;2004年06期

2 张居阳 ,礼欣 ,孙吉贵;基于约束的调度研究和实现[J];计算机工程与应用;2004年33期

3 刘琳;谷寒雨;席裕庚;;工件到达时间未知的动态车间滚动重调度[J];机械工程学报;2008年05期

4 黄峰;丁亚武;;人机协同模式下的手工调度技术研究[J];黑龙江科技信息;2011年35期

5 郭艳东;黄敏;王庆;;锁定初始调度的紧急工作单机重调度问题[J];东北大学学报(自然科学版);2013年05期

6 姜洋;孙伟;丁秋雷;张旭;;考虑行为主体的单机调度干扰管理模型[J];机械工程学报;2013年14期

7 李向军,王书振;网络化集成制造模式下调度问题的混合遗传算法[J];西安联合大学学报;2002年04期

8 王中杰,吴启迪,有杰;基于多目标的半导体生产线满意调度[J];控制与决策;2002年06期

9 李云峰;凌晓冬;武小悦;;调度问题中的冲突研究[J];兵工自动化;2007年06期

10 徐群岭;;基于免疫优化的公交驾驶员调度问题[J];计算机工程;2010年24期

中国重要会议论文全文数据库 前10条

1 李建更;涂凍生;马海涛;;单机拖后时间总和问题交付期扰动时最优调度不变范围的一种求法[A];第十九届中国控制会议论文集（一）[C];2000年

2 刘海龙;黄小原;;总的未完工费用最小的多机调度问题[A];1995中国控制与决策学术年会论文集[C];1995年

3 沈吟东;曾西洋;;公共交通驾驶员调度的复杂性及解决方法[A];’2004计算机应用技术交流会议论文集[C];2004年

4 李兵;蒋慰孙;;Job shop问题的建模及调度[A];1996中国控制与决策学术年会论文集[C];1996年

5 王海星;申金升;;智能蚁群算法解决公交区域调度问题研究[A];2006年首届ICT大会信息、知识、智能及其转换理论第一次高峰论坛会议论文集[C];2006年

6 王成尧;汪定伟;;模糊加工时间的单机调度问题[A];1996中国控制与决策学术年会论文集[C];1996年

7 齐向彤;涂奉生;;双交付期E／T调度问题[A];1997年中国控制会议论文集[C];1997年

8 吴斌;方叶祥;崔志勇;;基于人工蜂群算法的越库调度问题研究[A];第25届中国控制与决策会议论文集[C];2013年

9 方涛;吴受章;;FMS的自适应调度:结构与算法研究[A];1992年中国控制与决策学术年会论文集[C];1992年

10 刘兴初;赵千川;郑大钟;;具有不同准备时间和交付期的单机E／T调度问题研究[A];1998年中国控制会议论文集[C];1998年

中国重要报纸全文数据库 前2条

1 本报记者 贾科华;火电机组叫苦调度不合理[N];中国能源报;2012年

2 本报记者 高芳;牵住“牛鼻子” 巧解“推进难”[N];湖南经济报;2008年

中国博士学位论文全文数据库 前10条

1 郭鹏;具有分段恶化效应生产过程的智能优化调度研究[D];西南交通大学;2014年

2 元野;基于图着色模型的零担物流调度优化问题研究[D];哈尔滨工业大学;2015年

3 李雪松;模糊环境下若干单机批加工调度问题的模型及其算法研究[D];哈尔滨工业大学;2015年

4 汤雅连;关联物流运输调度问题研究[D];广东工业大学;2015年

5 周理;高效可重构阵列计算：体系结构，设计方法与程序映射技术研究[D];国防科学技术大学;2014年

6 冯大光;一类批处理机调度的理论和方法研究[D];东北大学;2011年

7 孟盈;钢铁企业并行批生产决策与调度问题研究[D];东北大学;2011年

8 杨磊;内容网络中内容调度技术研究[D];重庆大学;2015年

9 李亚志;流水制造单元调度智能优化方法[D];东南大学;2015年

10 丁宁;若干调度问题的算法研究[D];大连理工大学;2016年

中国硕士学位论文全文数据库 前10条

1 张亮;云计算环境下的资源调度技术的研究[D];江南大学;2015年

2 冯卓鹏;重载运输卸车组织优化研究[D];西南交通大学;2015年

3 崔雪源;基于遗传模拟退火算法的航班着陆调度问题[D];华中师范大学;2015年

4 王翠;基于超图模型和相继干扰消除的链路调度问题的研究[D];曲阜师范大学;2015年

5 张勇;带拒绝和释放时间的单机批调度问题[D];山东大学;2015年

6 吴凡;基于粒子群优化算法的风电-火电机组组合调度研究[D];华北电力大学;2015年

7 赵虎;MTO模式下的制造企业稳健型调度问题研究[D];重庆理工大学;2015年

8 吉佳红;基于细菌觅食算法的改进及应用研究[D];江苏科技大学;2015年

9 周超;柔性作业车间批量问题研究[D];宁波大学;2014年

10 赵兴野;工序顺序柔性作业车间描述与调度研究[D];大连理工大学;2015年

，

本文编号：543492