基于遗传规划和遗传算法的跨单元调度方法

发布时间：2017-05-31 16:04

  本文关键词：基于遗传规划和遗传算法的跨单元调度方法，由笔耕文化传播整理发布。

【摘要】：单元制造是当代最新、最有效的生产线设置方式之一,为日本以及欧美企业所广泛采用。在单元制造中,相似工艺的工件聚成同一工件族,能够生产同一工件族的机器被放在一起组成同一生产单元。在实际生产中,由于零件在生产单元之间频繁转移导致单元间需协同安排工件的加工路径,在这种情况下产生了跨单元调度问题(inter-cell scheduling)。对于国内装备制造业的调研结果显示,对车辆综合传动装置这样的复杂产品来说,有50%以上的零件需要跨车间协作完成,在延迟零件中有75%以上属于跨车间协作零件。因此,跨单元调度不可避免,有必要对于考虑跨单元运输的调度问题进行研究。本文在分析了国内外相关研究成果及其发展现状的基础上,结合装备制造企业的生产实际,针对跨单元运输当中运输能力受限的实际情况,提出一种考虑运输能力受限的跨单元调度方法。首先,对考虑运输能力受限的跨单元调度问题进行详细描述,并建立数学模型。然后,基于上述模型提出一种基于遗传规划和遗传算法的超启发式算法(A Hyper-Heuristic Approach Based on Genetic Programming and Genetic Algorithm,HHGPA)。该算法首先根据零件或机器的信息,利用遗传规划(Genetic Programming,GP)自动为调度问题生成合适的启发式规则;然后利用遗传算法(Genetic Algorithm,GA)同时为机器和工件搜索合适的规则组合;最后利用这些启发式规则组合求得调度解。与直接搜索调度解的遗传算法相比,该算法能兼顾计算效率和寻优能力。实验结果表明,该算法与传统的启发式规则、业界常用的超启发式算法以及一种适用于大规模调度问题的元启发式算法相比,解性能有显著改善,也适用于求解具有大数据规模的实际调度问题。最后,针对HHGPA存在的过早收敛和局部搜索能力较弱的问题,分别提出了一种灾变操作和一种基于爬山算法的局部搜索算法。实验表明,改进后的HHGPA相比于改进前的HHGPA解性能有显著改善。同时与CPLEX相比,该算法无论是计算效率还是解性能均优于CPLEX。与现有研究相比,本文主要工作有:(1)对考虑运输能力受限的跨单元问题建模;(2)设计了一种高效的基于遗传规划和遗传算法的超启发式算法;(3)提出了一种灾变操作和一种基于爬山算法的局部搜索算法,改进HHGPA,从而解决算法过早收敛和局部搜索能力较弱的问题。
【关键词】：跨单元调度 超启发式 遗传算法 遗传规划
【学位授予单位】：北京理工大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：TP18
【目录】：

• 摘要5-7
• abstract7-11
• 第1章 绪论11-20
• 1.1 研究背景11-12
• 1.2 生产调度基本理论12-13
• 1.2.1 流水车间调度12-13
• 1.2.2 作业车间调度13
• 1.3 国内外研究现状及发展趋势13-18
• 1.3.1 单元制造系统概述13-14
• 1.3.2 跨单元调度问题研究现状14-16
• 1.3.3 超启发式算法研究现状16-18
• 1.4 课题来源及研究内容18
• 1.5 论文结构18-19
• 1.6 本章小结19-20
• 第2章 运输能力受限的跨单元调度问题建模20-26
• 2.1 问题描述20-22
• 2.2 数学模型22-25
• 2.3 本章小结25-26
• 第3章 基于遗传规划和遗传算法的超启发式算法26-64
• 3.1 算法设计背景26-28
• 3.2 解的表示28-33
• 3.2.1 编码方案28-31
• 3.2.2 解码方案31-33
• 3.3 算法框架33-35
• 3.4 基于遗传规划的规则生成35-44
• 3.4.1 遗传规划算法简介35-36
• 3.4.2 实现细节36-41
• 3.4.3 适应度评价41
• 3.4.4 算法流程41-44
• 3.5 基于遗传算法的规则组合选择44-49
• 3.5.1 遗传算法简介44-45
• 3.5.2 实现细节45-48
• 3.5.3 适应度评价48
• 3.5.4 算法流程48-49
• 3.6 仿真实验49-63
• 3.6.1 实验设计49-50
• 3.6.2 参数实验50-52
• 3.6.3 性能比较实验52-63
• 3.7 本章小结63-64
• 第4章 基于灾变操作和爬山算法的改进超启发式算法64-75
• 4.1 算法设计背景64-65
• 4.2 算法框架65-66
• 4.3 实现细节66-68
• 4.3.1 灾变操作67
• 4.3.2 基于爬山算法的局部搜索67-68
• 4.4 仿真实验68-74
• 4.4.1 实验设计69
• 4.4.2 参数实验69
• 4.4.3 性能比较实验69-74
• 4.5 本章小结74-75
• 总结与展望75-78
• 总结75-76
• 展望76-78
• 参考文献78-82
• 攻读学位期间发表的论文与研究成果清单82-84
• 致谢84

【相似文献】

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

1 吴瑞镛,徐大纹;具有年龄结构的遗传算法[J];桂林电子工业学院学报;2001年04期

2 杨艳丽,史维祥;一种新的优化算法—遗传算法的设计[J];液压气动与密封;2001年02期

3 杨宜康,李雪,彭勤科,黄永宣;具有年龄结构的遗传算法[J];计算机工程与应用;2002年11期

4 谷峰,吴勇,唐俊;遗传算法的改进[J];微机发展;2003年06期

5 ;遗传算法[J];计算机教育;2004年10期

6 赵义红,李正文,何其四;生物信息处理系统遗传算法探讨[J];成都理工大学学报(自然科学版);2004年05期

7 刘坤,刘伟波,吴忠强;基于模糊遗传算法的电液位置伺服系统控制[J];黑龙江科技学院学报;2005年04期

8 张英俐,刘弘 ,马金刚;遗传算法作曲系统研究[J];信息技术与信息化;2005年05期

9 丁发智;;浅谈遗传算法[J];乌鲁木齐成人教育学院学报;2005年04期

10 李冰洁;;遗传算法及其应用实例[J];吉林工程技术师范学院学报;2005年12期

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

1 陈家照;廖海涛;张中位;罗寅生;;一种改进的遗传算法及其在路径规划中的应用[A];2009系统仿真技术及其应用学术会议论文集[C];2009年

2 李国云;刘颖;薛梅;邬志敏;;遗传算法在高温空冷冷凝器优化设计中的应用[A];第五届全国制冷空调新技术研讨会论文集[C];2008年

3 王志军;李守春;张爽;;改进的遗传算法在反演问题中的应用[A];新世纪 新机遇 新挑战——知识创新和高新技术产业发展（上册）[C];2001年

4 任燕翔;姜立;刘连民;从滋庆;;改进遗传算法在三维日照方案优化中的应用[A];工程三维模型与虚拟现实表现——第二届工程建设计算机应用创新论坛论文集[C];2009年

5 韩娟;;遗传算法概述[A];第三届河南省汽车工程科技学术研讨会论文集[C];2006年

6 庞国仲;王元西;;基于遗传算法控制步长的定性仿真方法[A];'2000系统仿真技术及其应用学术交流会论文集[C];2000年

7 张忠华;杨淑莹;;基于遗传算法的聚类设计[A];全国第二届信号处理与应用学术会议专刊[C];2008年

8 何翠红;区益善;;遗传算法及其在计算机编程中的应用[A];1995年中国智能自动化学术会议暨智能自动化专业委员会成立大会论文集（下册）[C];1995年

9 靳开岩;张乃尧;;几种实用遗传算法及其比较[A];1996年中国智能自动化学术会议论文集（下册）[C];1996年

10 王宏刚;曾建潮;李志宏;;摄动遗传算法[A];1996年中国智能自动化学术会议论文集（下册）[C];1996年

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

1 林京;《神经网络和遗传算法在水科学领域的应用》将面市[N];中国水利报;2002年

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

1 蔡美菊;交互式遗传算法及其在隐性目标决策问题中的应用研究[D];合肥工业大学;2015年

2 张士伟;三维声学快速多极基本解法在机械噪声预测中的应用研究[D];沈阳工业大学;2016年

3 高军;无铅焊料本构模型及其参数识别方法研究[D];南京航空航天大学;2015年

4 Amjad Mahmood;半监督进化集成及其在网络视频分类中的应用[D];西南交通大学;2015年

5 周辉仁;递阶遗传算法理论及其应用研究[D];天津大学;2008年

6 郝国生;交互式遗传算法中用户的认知规律及其应用[D];中国矿业大学;2009年

7 侯格贤;遗传算法及其在跟踪系统中的应用研究[D];西安电子科技大学;1998年

8 马国田;遗传算法及其在电磁工程中的应用[D];西安电子科技大学;1998年

9 唐文艳;结构优化中的遗传算法研究和应用[D];大连理工大学;2002年

10 周激流;遗传算法理论及其在水问题中应用的研究[D];四川大学;2000年

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

1 张英俐;基于遗传算法的作曲系统研究[D];山东师范大学;2006年

2 钟海萍;原对偶遗传算法与蚁群算法的一种融合算法[D];暨南大学;2013年

3 李志添;模糊遗传算法与资源优化配置的预测控制[D];华南理工大学;2015年

4 王琳琳;新型双层液压轿运车车厢的设计研究[D];上海工程技术大学;2015年

5 李海全;基于遗传算法的建筑体形系数及迎风面积比优化方法研究[D];华南理工大学;2015年

6 彭骞;基于遗传算法的山区高等级公路纵断面智能优化方法研究[D];昆明理工大学;2015年

7 周玉林;基于小波分析和遗传算法的配电网故障检测[D];昆明理工大学;2015年

8 郭颂;基于粗糙集和遗传算法的数字管道生产管理系统研究[D];昆明理工大学;2015年

9 吴南;数值逼近遗传算法的研究应用[D];华南理工大学;2015年

10 于光帅;一类优化算法的改进研究与应用[D];渤海大学;2015年

  本文关键词：基于遗传规划和遗传算法的跨单元调度方法，由笔耕文化传播整理发布。

，

本文编号：409939