基于GA与EDA的智能算法求解复杂车间调度问题

发布时间：2017-10-18 19:24

  本文关键词：基于GA与EDA的智能算法求解复杂车间调度问题

  更多相关文章： 分布估计算法 遗传算法 零等待作业车间 可重入作业车间 最大完工时间

【摘要】：生产制造系统作为一类复杂的人造系统,具有NP难、多局部最优、不确定性、多目标、多约束、非线性等特点。生产调度是制造系统的一个研究热点,也是理论研究中最为困难的问题之一。根据生产目标和各种约束条件,为每个加工对象确定具体的加工路径、时间、机器和操作等是调度的主要任务。鉴于复杂生产调度问题重要的应用价值和理论意义,基于该问题的智能优化算法研究已受到工业界和理论界的广泛关注。遗传算法(Genetic Algorithm,GA)作为一种经典的群体智能优化算法,已在各个领域得到广泛应用,而分布估计算法(Estimation of Distribution Algorithm,EDA)作为一种基于优势个体概率分布模型的新兴智能优化算法,近年已在多个工业领域得到了成功应用。因此,本文对三类重要的车间调度问题进行基于GA或EDA的求解算法研究。主要工作如下：(1)针对最大完工时间(makespan)指标下的流水线车间调度问题,设计了一种带有Insert邻域局部搜索机制的遗传算法,利用GA对问题解空间进行搜索并发现优质解区域,同时采用局部搜索对优质解区域进行较细致的搜索。通过在不同规模测试问题上的仿真实验验证了所提算法的有效性和鲁棒性。(2)针对最大完工时间(makespan)指标下的零等待作业车间调度问题,通过分析问题的结构特性,设计了一种增强型的分布估计算法(Enhanced Estimation of Distribution Algorithm,EEDA)。该算法采用移位时间表方法对问题解进行解码,从而可直接提高基于工件排序编码的解的质量,同时利用2维概率矩阵作为EDA概率模型积累优质解信息并引导全局搜索,进而加入了基于首次改进跳出策略和Interchange邻域的局部搜索。通过若干典型问题(benchmarks)进行仿真实验并与其它有效算法进行比较,验证了所提EEDA的有效性和鲁棒性。(3)针对最大完工时间(makespan)指标下带序相关设置时间的可重作业车间调度问题,设计了一种基于贝叶斯统计推理的EDA算法(Bayesian Statistical Inference-Based EDA,BEDA)进行求解。在该算法中,根据问题性质,采用活动化解码来提高基于工序排列编码的解的质量,利用简单贝叶斯网络模型作为EDA概率模型描述问题变量间的关联关系,同时学习和积累优质解信息,并引导算法搜索。通过仿真实验和算法比较验证了所提BEDA算法的有效性和鲁棒性。
【关键词】：分布估计算法 遗传算法 零等待作业车间 可重入作业车间 最大完工时间
【学位授予单位】：昆明理工大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：TP18;TB497
【目录】：

• 摘要5-7
• Abstract7-12
• 第一章 绪论12-24
• 1.1 研究意义12
• 1.2 置换流水线调度问题研究12-13
• 1.2.1 置换流水线调度问题描述12-13
• 1.2.2 置换流水线调度问题研究概述13
• 1.3 零等待作业车间调度问题研究13-15
• 1.3.1 零等待作业车间调度问题描述13-14
• 1.3.2 零等待作业车间调度问题研究概述14-15
• 1.4 可重入作业车间调度问题研究15-17
• 1.4.1 可重入作业车间调度问题的数学模型描述15-16
• 1.4.2 可重入作业车间调度问题研究概述16-17
• 1.5 遗传算法及其在智能调度领域的应用17-19
• 1.5.1 遗传算法17-18
• 1.5.2 遗传算法在智能调度领域的应用18-19
• 1.6 分布估计算法及其在智能调度领域的应用19-21
• 1.6.1 分布估计算法19-21
• 1.6.2 分布估计算法在智能调度领域的应用21
• 1.7 主要研究工作21-24
• 第二章 求解流水线调度问题的改进遗传算法24-30
• 2.1 引言24
• 2.2 以最小化最大完工时间为目标的置换流水线调度问题描述24-25
• 2.3 改进遗传算法25-27
• 2.3.1 解的表达25
• 2.3.2 种群初始化25
• 2.3.3 基于Insert邻域的局部搜索25-26
• 2.3.4 选择操作26
• 2.3.5 交叉操作26
• 2.3.6 变异操作26-27
• 2.3.7 改进遗传算法步骤27
• 2.4 仿真实验与分析27-29
• 2.4.1 实验设置27-28
• 2.4.2 性能比较28-29
• 2.4.3 仿真结果和对比29
• 2.5 小结29-30
• 第三章 求解零等待车间调度问题的增强型EDA算法30-42
• 3.1 引言30-31
• 3.2 零等待作业车间调度问题描述31-35
• 3.2.1 问题模型31-32
• 3.2.2 时间表确定问题32-35
• 3.3 增强型分布估计算法35-39
• 3.3.1 解的表达35
• 3.3.2 种群初始化35
• 3.3.3 新种群的生成35-36
• 3.3.4 基于Insert的变异策略36-37
• 3.3.5 基于首次改进原则的邻域搜索策略37
• 3.3.6 增强型分布估计算法步骤37-39
• 3.4 仿真实验与分析39-40
• 3.4.1 实验设置39
• 3.4.2 性能比较39-40
• 3.4.3 仿真结果和对比40
• 3.5 小结40-42
• 第四章 求解带序设置时间的可重入车间调度问题的贝叶斯分布估计算法42-52
• 4.1 引言42-43
• 4.2 带序设置时间的可重入作业车间调度问题描述43-45
• 4.3 基于贝叶斯网络的分布式估计算法45-50
• 4.3.1 解的表达45
• 4.3.2 种群初始化策略45
• 4.3.3 解码方案45
• 4.3.4 概率模型及其更新策略45-48
• 4.3.4.1 概率模型45-46
• 4.3.4.2 概率模型更新策略46-48
• 4.3.5 新种群的生成48-49
• 4.3.6 基于Insert的邻域结构49
• 4.3.7 基于贝叶斯网络的分布式估计算法步骤49-50
• 4.4 仿真实验与分析50-51
• 4.4.1 实验设置50
• 4.4.2 性能比较50
• 4.4.3 仿真结果和对比50-51
• 4.5 小结51-52
• 第五章 结论与展望52-54
• 5.1 论文总结52-53
• 5.2 研究展望53-54
• 致谢54-56
• 参考文献56-62
• 附录A (攻读硕士学位期间的科研成果)62

【相似文献】

中国期刊全文数据库 前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，

本文编号：1056700