基于学习效应的单机调度总完工时间最小化问题研究

发布时间：2017-05-27 12:23

  本文关键词：基于学习效应的单机调度总完工时间最小化问题研究，由笔耕文化传播整理发布。

【摘要】：在许多现实生产活动中因为有人的参与,人的学习活动会对生产过程产生重要的影响,因而在某些生产调度问题的研究中考虑其生产环境存在学习效应更具合理性。同时作为工件属性之一的释放时间是制定生产调度计划必须考虑的影响因素之一,直接关系到整个生产过程的效率高低。例如,在芯片生产中的批处理环节,同一批次中的工件数量越多代表该批次效率越高。然而由于工件的释放时间不同,如果某批次中的某个工件需要的等待时间过长,不等待反而有利于整个生产过程效率的提高。因此在某些生产调度环境中同时考虑学习效应和工件不同释放时间具有重要的理论和现实意义。 现有的同时考虑学习效应和工件释放时间不同的生产调度问题研究有限且都是基于位置或者正常加工时间之和的学习效应模型,本文对其进行了扩展,考虑更加符合实际的基于实际加工时间之和的学习效应模型,且优化目标为总完工时间最小化的单机调度问题。 针对该问题,本文首先构建了一个非线性整数规划模型,该模型将被用来得到当工件数量规模较小时候的解。接着通过成对交换技术得到加工序列的两个优先规则。在提出的优先规则基础上结合证明的两个下界,提出了分支定界算法来求解小规模工件数量的该问题。因为该问题的NP难特性,本文又提出了一个混合了遗传算法相关操作,模拟退火算法思想和优先规则的混合粒子群优化算法来求解工件数量大规模的情况。 为了检验提出的相关算法的性能。本文根据工件数量规模的大小设计了两个仿真实验来验证提出的分支定界算法和混合粒子群优化算法的可行性和有效性。仿真实验一的结果表明,求解小规模的该问题,分支定界算法比CP方法更有效率,同时该实验也一定程度上验证了混合粒子群优化算法的求解精确性。实验二中通过从解的最优,最劣和平均情况三个方面对各个算法进行比较,结果表明混合粒子群优化算法在三个方面都优于其对比的三个经典的基本算法,而且这种优势随着工件规模的增加越来越明显。
【关键词】：调度 学习效应 不同释放时间 粒子群优化算法 优先规则
【学位授予单位】：中国科学技术大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：TP18;TB497
【目录】：

• 摘要5-6
• ABSTRACT6-8
• 目录8-10
• 第1章 绪论10-18
• 1.1 研究背景及研究意义10-11
• 1.2 国内外研究现状11-15
• 1.2.1 调度问题的研究综述11-12
• 1.2.2 考虑学习效应的调度问题研究12-14
• 1.2.3 同时考虑学习效应和释放时间的研究现状及不足14-15
• 1.3 本文所要研究的内容和创新点15-16
• 1.4 本文的章节安排16-18
• 第2章 SMSPLEUR问题描述及分析18-24
• 2.1 SMSPLEUR问题描述18
• 2.2 SMSPLEUR问题的非线性混合整数规划模型18-19
• 2.3 SMSPLEUR问题的优先规则19-23
• 2.4 本章小结23-24
• 第3章 求解SMSPLEUR问题的相关算法24-38
• 3.1 分支定界算法24-27
• 3.1.1 分支定界算法的两个下界24-26
• 3.1.2 分支定界算法设计26-27
• 3.2 遗传算法27-29
• 3.2.1 遗传算法简介27
• 3.2.2 遗传算法设计27-29
• 3.3 模拟退火算法29-30
• 3.3.1 模拟退火算法简介29-30
• 3.3.2 模拟退火算法设计30
• 3.4 基本粒子群优化算法30-34
• 3.4.1 基本粒子群优化算法介绍30-32
• 3.4.2 基本粒子群优化算法设计32-34
• 3.5 混合粒子群优化算法34-35
• 3.6 本章小结35-38
• 第4章 仿真实验及结果分析38-50
• 4.1 小规模工件实验38-42
• 4.1.1 实验描述38-39
• 4.1.2 实验结果39-41
• 4.1.3 实验结果分析41-42
• 4.2 大规模工件实验42-48
• 4.2.1 实验描述43
• 4.2.2 实验结果43-45
• 4.2.3 实验结果分析45-48
• 4.3 实验小结48
• 4.4 本章小结48-50
• 第5章 总结和展望50-52
• 5.1 研究总结50-51
• 5.2 未来研究展望51-52
• 参考文献52-56
• 致谢56-58
• 在读期间发表的学术论文与取得的研究成果58

【参考文献】

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

1 徐海燕;李小平;;基于学习和恶化效应模型的单机调度[J];东南大学学报(自然科学版);2013年06期

2 王策;王书锋;冯冬青;梁燕;;混合粒子群算法在job-shop动态调度中的应用[J];计算机工程与应用;2010年26期

3 齐学梅;罗永龙;赵诚;;求解流水车间调度问题的混合粒子群算法[J];计算机工程与应用;2012年09期

4 刘敏;严隽薇;;基于自适应退火遗传算法的车间日作业计划调度方法[J];计算机学报;2007年07期

5 高尚,韩斌,吴小俊,杨静宇;求解旅行商问题的混合粒子群优化算法[J];控制与决策;2004年11期

6 李永林;叶春明;刘勤明;;具有工件相关学习效应的一般多机器流水车间调度问题研究[J];计算机应用研究;2014年06期

7 赵静;叶春明;;基于萤火虫算法的学习遗忘效应BFSP问题研究[J];上海理工大学学报;2014年06期

  本文关键词：基于学习效应的单机调度总完工时间最小化问题研究，由笔耕文化传播整理发布。

，

本文编号：399983