求解模糊Job Shop调度的混合算法研究与应用
文献类型：学位论文
| 作者 | 宋晓宇1,2 |
| 答辩日期 | 2007-02-04 |
| 文献子类 | 博士 |
| 授予单位 | 中国科学院沈阳自动化研究所 |
| 授予地点 | 沈阳 |
| 导师 | 朱云龙 |
| 关键词 | 模糊job Shop调度 禁忌搜索算法 并行遗传算法 蚁群算法 混合算法 |
| 学位名称 | 博士 |
| 学位专业 | 机械电子工程 |
| 其他题名 | Research and Application of Hybrid Algorithms for fuzzy Job Shop Scheduling Problem |
| 英文摘要 | 有效的调度方法和优化技术的研究与应用，是实现先进制造和提高生产效益、资源利用率的基础和关键。由于企业生存的内外部环境的剧烈变化，以及由机器故障和操作工人熟练程度造成的实际加工时间和交货期的不确定性，使得确定性生产调度方法已不适应这类实际生产环境的需求。伴随模糊集合理论的长足发展，模糊Job Shop调度问题建模和求解方法已成为当前制造执行系统的关键和运筹学的研究热点之一。本文在考虑模糊加工时间、模糊交货期的情况下，主要进行生产计划中模糊Job shop调度问题混合优化算法的研究。具体研究内容和取得的研究成果如下： 1．Job shop调度问题智能优化算法研究进展分析：首先分析求解Job shop调度问题的近似优化方法中智能优化算法部分研究成果，为求解模糊Job shop调度问题提供研究基础。在评述求解模糊Job shop调度问题智能优化算法的当前研究成果的基础上，分析了当前求解模糊Job shop调度问题研究的热点、难点和不足，指出求解模糊Job Shop调度问题混合优化算法的研究方向。 2．基于关键工序邻域结构的研究：通过对影响邻域搜索算法效率因素的分析，对四种典型邻域结构的邻域大小、交换的有效性进行归纳，找出邻域结构中影响搜索效率的关键工序，提出了基于关键工序的邻域结构。设计了基于关键工序邻域选择方法的禁忌搜索算法（TSCO），通过对13个难解的benchmarks问题实例仿真，验证了基于关键工序的邻域结构的合理性和改进TS算法的有效性。 3．模糊Job Shop调度中混合搜索策略的研究：通过对遗传算法求解Job Shop调度问题的研究，对影响优化Job Shop调度问题的因素进行分析，针对遗传算法求解Job Shop调度问题过程中的问题，提出了求解Job Shop调度问题的混合搜索策略。该混合搜索策略中，采用并行遗传算法进行全局搜索，嵌入局部搜索算法，改善并行遗传算法易于早熟和陷入局部最优的缺点。局部搜索算法设计成基于关键工序邻域选择方法的改进TS算法，利用其局部搜索能力对部分解进行改进，同时提高了并行遗传算法跳出局部最优的能力；为提高搜索效率，两个种群分别采用非延时调度和活动调度生成初始解，当某个种群收敛时，通过迁移操作对其进行扰动，扩大搜索范围。通过对13个难解的benchmarks问题实例仿真实验表明，混合搜索策略的搜索效率较单一优化算法有明显提高，特别是对较复杂的benchmarks问题搜索效率和搜索质量较高。 4．基于蚁群算法的混合搜索策略与算法的研究：在蚁群算法求解模糊Job Shop调度问题中，设计了信息素更新策略；运用信息素分布决定Giffler&Thompson算法中的工序选择，使Giffler&Thompson算法适用于蚁群算法求解模糊Job Shop调度问题；提出了基于蚁群算法的求解模糊Job Shop调度问题混合优化策略并给出了混合优化算法；通过对模糊Job Shop调度问题的实例仿真，验证了混合蚁群优化算法的有效性，为使用蚁群算法求解模糊Job Shop调度问题提供了一种可行、有效的方法。 5．基于ACO与GA的混合优化策略与算法：通过对蚁群算法、遗传算法和TS算法搜索原理的分析，采用并行异构搜索策略将上述三种智能优化方法融合，提出了蚁群算法和遗传算法的混合优化策略并给出了混合优化算法；并将TS局部优化算法嵌入蚁群算法和遗传算法中，进一步提高混合优化算法的搜索能力。通过对模糊Job Shop调度问题的实例仿真实验表明，采用多算法融合策略的混合优化算法的优化结果较单一优化算法有显著改善。 6．模糊Job Shop调度仿真系统研究与开发：研究了仿真系统架构、基于UML的系统设计方案，采用Visual C++ .NET开发了仿真原型系统，为算法的有效性验证提供了基础平台。本文重点研究考虑模糊加工时间、模糊交货期的情况下，生产计划的优化调度方法，主要对模糊Job Shop调度问题邻域结构进行分析和求解模糊Job Shop调度问题的混合搜索策略和混合优化算法进行研究，并取得了具有创新性的研究成果。由于模糊Job Shop调度问题的为NP难题，其求解难度较大，还存在许多问题有待进一步的研究与实践。 |
| 语种 | 中文 |
| 公开日期 | 2010-11-29 |
| 产权排序 | 1 |
| 页码 | 111页 |
| 分类号 | TP315 |
| 源URL | [http://210.72.131.170//handle/173321/87]  |
| 专题 | 沈阳自动化研究所_工业信息学研究室_先进制造技术研究室 |
| 作者单位 | 1.中国科学院研究生院 2.中国科学院沈阳自动化研究所 |
| 推荐引用方式 GB/T 7714 | 宋晓宇. 求解模糊Job Shop调度的混合算法研究与应用[D]. 沈阳. 中国科学院沈阳自动化研究所. 2007. |
入库方式： OAI收割
来源：沈阳自动化研究所
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。