基于改进和声搜索算法的车间作业调度问题研究

发布时间：2017-06-24 09:22

  本文关键词：基于改进和声搜索算法的车间作业调度问题研究，由笔耕文化传播整理发布。

【摘要】：车间作业调度问题(Job Shop Scheduling Problem, JSSP)是现代生产制造系统中一个广受关注的典型生产线调度问题。由于车间作业调度具有工艺路径约束和资源(机器)独占性约束,使其成为了一个NP难问题。本文研究了基于改进和声搜索算法和模拟退火算法的混合算法(IHSSA)及其在解决车间作业调度问题中的应用。首先,提出了基于改进和声搜索算法和模拟退火算法的混合算法IHSSA。改进和声搜索算法(IHS)解决了基本和声搜索算法的音调微调概率(PAR)和波动范围(BW)取值固定所引发的问题,不仅保证了算法早期搜索时和声解的多样性,而且加快了搜索后期的算法收敛速度。然而改进和声搜索算法对初始解的依赖性仍未降低,为了解决这个问题,在和声搜索算法生成初始解的过程中引入模拟退火过程,以提高和声记忆库中初始解的适应度。同时使用模拟退火算法对和声搜索算法生成的新和声解进行搜索,用最终搜索结果取代新和声解,提高了算法搜索到全局最优解的可能性,也加快了算法的收敛速度。然后使用基于工序的编码方式对车间作业调度问题进行编码。基于工序的编码方式保证了生成解的合法性,但是作为一种离散的编码方式,不能被适用于连续问题的和声搜索算法直接使用。本文使用最大位置排序(LPV)规则实现离散问题的连续编码。针对和声搜索算法会产生非法解的问题,提出了基于工件号的排序规则(ROJ),以保证生成新和声解的合法性。最后,使用本文提出的IHSSA算法对单机器加工和复杂作业的调度系统进行仿真实验,通过和已有算法运行结果的比较,证明了该算法在解决车间作业调度问题上的正确性和有效性。
【关键词】：车间作业调度 和声搜索算法 模拟退火算法 混合策略 仿真系统
【学位授予单位】：南京理工大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：TB497
【目录】：

• 摘要3-4
• Abstract4-8
• 1 绪论8-13
• 1.1 研究的背景与意义8-9
• 1.2 课题来源9
• 1.3 国内外研究现状9-11
• 1.3.1 车间作业调度问题的研究现状9-10
• 1.3.2 和声搜索算法的研究现状10-11
• 1.4 本文所做的工作11-12
• 1.5 本文的论文结构12-13
• 2 基础理论综述13-25
• 2.1 车间作业调度系统综述13-18
• 2.1.1 车间作业调度系统的基本概念13
• 2.1.2 车间作业调度系统的研究方法13-16
• 2.1.3 车间作业调度系统的编码方式16-18
• 2.2 和声搜索算法综述18-24
• 2.2.1 和声搜索算法的原理18-19
• 2.2.2 和声搜索算法的主要概念19-20
• 2.2.3 和声搜索算法的运算过程20-23
• 2.2.4 和声搜索算法的基本特征23
• 2.2.5 和声搜索算法的应用23-24
• 2.3 本章小结24-25
• 3 和声搜索算法的改进25-32
• 3.1 现有改进方法25-27
• 3.1.1 改进和声搜索算法25-26
• 3.1.2 全局和声搜索算法26-27
• 3.2 改进和声搜索和模拟退火算法的混合算法(IHSSA)27-31
• 3.2.1 混合策略27
• 3.2.2 IHSSA算法流程27-28
• 3.2.3 IHSSA算法测试与分析28-31
• 3.3 本章小结31-32
• 4 IHSSA算法在JSSP问题中的应用32-49
• 4.1 输入文件格式32-34
• 4.2 和声解34-39
• 4.2.1 编码方式34-35
• 4.2.2 LPV规则35-36
• 4.2.3 和声解结构36
• 4.2.4 计算和声解的适应度36-39
• 4.2.5 解码方式39
• 4.3 初始化和声记忆库39-43
• 4.3.1 随机解的生成过程39-41
• 4.3.2 对随机解进行模拟退火41-43
• 4.4 产生新和声43-47
• 4.4.1 基于工件号的排序43-44
• 4.4.2 学习和声记忆库44
• 4.4.3 变量微调44-45
• 4.4.4 随机生成新的决策变量取值45
• 4.4.5 新和声的产生过程45-47
• 4.5 更新和声记忆库47
• 4.6 算法结束47
• 4.7 编码实现47-48
• 4.8 本章小结48-49
• 5 仿真实验与分析49-55
• 5.1 单机器加工的作业调度实验49-50
• 5.2 复杂作业系统的调度实验50-52
• 5.3 多批量作业调度实验52-54
• 5.4 本章小结54-55
• 6 总结与展望55-57
• 6.1 全文总结55
• 6.2 研究展望55-57
• 致谢57-58
• 参考文献58-63
• 附录63

【参考文献】

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

1 武磊;潘全科;潘玉霞;桑红燕;;求解零空闲流水线调度问题的和声退火算法[J];计算机工程与应用;2010年30期

2 韩红燕;潘全科;;求解批量流水线调度问题的改进和声搜索算法[J];计算机工程;2011年06期

3 柳青红;袁逸萍;李晓娟;;基于改进遗传算法的作业车间调度[J];机械工程与自动化;2014年06期

  本文关键词：基于改进和声搜索算法的车间作业调度问题研究，由笔耕文化传播整理发布。

，

本文编号：477759