求解流水车间调度问题的分解多目标局部搜索算法

发布时间：2017-05-02 07:08

  本文关键词：求解流水车间调度问题的分解多目标局部搜索算法，由笔耕文化传播整理发布。

【摘要】：多目标流水车间调度问题在现实产生中应用极为广泛,其关注如何合理利用有限的时间和资源,满足多个产生目标的需求,以提高企业的经济效益和运行效率。其已被证明是NP难问题,精确算法很难在有限的时间内求出令人满意的结果,然而基于群体智能的进化算法和一些邻域搜索策略在处理这类问题上表现出极大的优势,引起了国内外学者的广泛关注和研究。本文研究解决两类多目标调度问题,即常规的多目标流水车间调度问题和带顺序相关调整时间的多目标流水车间调度问题,而且均考虑两个生产目标的优化,即最小化最终完工时间和总流程时间。第二类问题是在第一类问题的基础上考虑了顺序相关的调整时间,在现实生产调度中,相邻作业之间会存在着一定的调整时间,比如清洗机器,释放资源等,而这些时间的消耗在设计调度方案的时候是不可忽略的。针对所考虑的问题,本文提出了一种高效的分解多目标局部搜索算法框架(简称MOLSD)。该算法框架利用聚合函数将所求解的多目标问题分解为若干个单目标子问题,然后对这些单目标子问题进行搜索和优化,从而实现多目标问题的优化。首先,本文提出一种基于调度问题的NEH启发式策略来初始化种群,使种群保持较好的多样性和适应性;接着,一种结合重干扰操作的Pareto局部搜索作用于非支配解集,以扩大优良个体的搜索邻域;其次,利用快速非支配排序方法将当前种群分为精英个体和普通个体,这两种个体在后续阶段将会经历不同的进化和搜索操作。在处理种群的每个个体的时候,本文提出了一种基于插入操作的局部搜素算法和迭代局部搜索机制,分别负责种群的开采和挖掘工作,从而平衡了算法的开发和搜索能力,提高了整体算法的全局寻优能力。为了避免算法陷入局部最优,本文提出了双重干扰机制,即轻干扰机制和重干扰机制,分别对没有提高的普通个体和精英个体进行干扰操作。为了提高算法的鲁棒性和健壮性,一种改进的重启机制将作用于那些经历多次迭代进化依然没有得到改善和提高的个体。在实验阶段,本文选取了大量学者广泛使用的基准测试实例来对算法进行性能评价和比较实验。首先,文本分别对MOLSD中的参数进行性能测试和分析,接着对所涉及的一些算法策略和机制进行有效性评估,最后本文将MOLSD与当前若干种优秀的基准算法进行性能比较和分析。最终的实验统计结果表明,在解决这两类多目标流水车间调度问题上,MOLSD的性能要高于其他基准算法。
【关键词】：进化多目标优化 流水车间调度 Pareto局部搜索 局部搜索 分解 非支配排序
【学位授予单位】：东北师范大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：TB497;TP301.6
【目录】：

• 摘要4-5
• Abstract5-9
• 第一章 引言9-14
• 1.1 研究背景和意义9-10
• 1.2 论文研究的问题10
• 1.3 国内外研究现状10-13
• 1.4 本文研究工作和结构安排13-14
• 第二章 进化多目标优化14-21
• 2.1 多目标优化问题的数学描述14-15
• 2.2 进化算法概述15-16
• 2.3 多目标进化优化算法框架16-19
• 2.3.1 问题编码16
• 2.3.2 适应度函数的确定16-17
• 2.3.3 种群的初始化17
• 2.3.4 个体更新17
• 2.3.5 种群更新17-18
• 2.3.6 算法参数的确定18-19
• 2.4 局部搜索算法概述19-21
• 第三章 求解流水车间调度的分解多目标局部搜索算法21-38
• 3.1 多目标流水车间调度问题的数学描述21-22
• 3.1.1 不带调整时间的多目标流水车间调度问题21
• 3.1.2 带有顺序相关调整时间的多目标流水车间调度问题21-22
• 3.1.3 流水车间调度问题的编码表示22
• 3.2 基于权重向量的分解技术22-23
• 3.3 基于调度问题的NEH启发式策略23-25
• 3.4 精英保留机制25
• 3.5 Pareto局部搜索25-28
• 3.6 快速非支配排序28-29
• 3.7 分解多目标局部搜索机制29-34
• 3.7.1 基于插入操作的局部搜索和迭代搜索机制30-32
• 3.7.2 双重干扰机制32-33
• 3.7.3 重启机制33-34
• 3.8 MOLSD的主要程序34-38
• 第四章 实验结果与分析38-54
• 4.1 基准测试实例和基准算法的选取38-39
• 4.2 性能评价指标39-40
• 4.3 实验参数设置40-43
• 4.4 局部搜索算法有效性的讨论43-44
• 4.5 与基准算法的比较实验与分析44-54
• 第五章 总结与展望54-55
• 参考文献55-59
• 致谢59-60
• 在研究生期间公开发表论文情况60

【相似文献】

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

1 潘全科;赵保华;屈玉贵;毕于慧;;一类解决无等待流水车间调度问题的蚁群算法[J];计算机集成制造系统;2007年09期

2 何利;刘永贤;刘笑天;;粒子群优化算法求解车间调度问题[J];机械与电子;2007年08期

3 王秋芬;杨泽平;梁道雷;;一种改进的车间调度问题算法[J];科学技术与工程;2013年11期

4 苏子林;;车间调度问题及其进化算法分析[J];机械工程学报;2008年08期

5 徐建有;董乃群;顾树生;;带有顺序相关调整时间的多目标流水车间调度问题[J];计算机集成制造系统;2013年12期

6 康宁,王凤儒,刘丕娥,常会友;有交货期的单件车间调度问题的逆序算法[J];系统工程理论与实践;1999年12期

7 马邦雄;叶春明;;利用猫群算法求解流水车间调度问题[J];现代制造工程;2014年06期

8 曲媛;杨晓伟;;关于流水车间调度问题的综述[J];中小企业科技;2007年08期

9 王柏琳;李铁克;;等待时间受限的流水车间调度问题的若干性质[J];系统工程理论与实践;2012年06期

10 邵扬;王晓娟;;类电磁机制算法求解模糊流水车间调度问题[J];武汉理工大学学报(交通科学与工程版);2013年02期

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

1 邹逢兴;曾令李;高政;刘烽;;一种求解混合流水车间调度问题的分布式方法[A];2009中国控制与决策会议论文集（2）[C];2009年

2 朱婧;;求解车间调度问题的改进模拟退火算法[A];第五届（2010）中国管理学年会——商务智能分会场论文集[C];2010年

3 洪宗友;庞哈利;;No-wait流水车间调度问题的一种启发式算法[A];2007中国控制与决策学术年会论文集[C];2007年

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

1 陶翼飞;面向分组加工的混合流水车间优化调度问题研究[D];昆明理工大学;2013年

2 何利;即时定制生产模式及其车间调度问题的研究[D];东北大学;2008年

3 黄英杰;基于目标级联法和智能优化算法的车间调度问题研究[D];华南理工大学;2012年

4 刘延风;置换流水车间调度问题的几种智能算法[D];西安电子科技大学;2012年

5 常桂娟;基于微粒群算法的车间调度问题研究[D];青岛大学;2008年

6 崔U，

本文编号：340491