| 【中文题名】 | 基于分解策略处理Job shop调度问题的两种方法 |
| 【英文题名】 | Two Procedures for Solving Job Shop Scheduling Problem Based on Decomposition Strategy |
| 【学科专业】 | 控制理论与控制工程 |
| 【论文级别】 | 硕士论文 |
| 【投稿时间】 | 2007-7-19 |
| 【中关键词】 | 车间调度,分解,滚动时域,禁忌搜索,, |
| 【英关键词】 | Job shop,decomposition,rolling horizon procedure,tabu search, |
| 【分类导航】 | 工业技术>自动化技术、计算机技术>自动化基础理论>自动控制理论>> |
| 【论文摘要】 |
作业车间调度问题(Job Shop Scheduling Problem，JSSP)被认为是一种困难的组合最优化问题之一，它的复杂性主要体现在其计算的难处理性和动态不确定性，由于人们找不到处理这类复杂问题的精确优化算法，因此用启发式算法求解成为当今研究这类问题的重点。
分解策略作为一种启发式方法，能够有效的降低问题的复杂性。将调度问题分为两层，上层考虑各子问题之间的约束关系，下层考虑各子问题内的约束关系，实际的调度发生在下层，再考虑上层中的约束关系，使得到的调度解可行。
本文给出了处理一类典型Job shop调度问题的基于分解策略的两种方法：一种是滚动时域方法并给出其改进，另一种是基于移动瓶颈的禁忌搜索方法。归纳起来，本文主要做了以下几方面的工作：
简单介绍了车间调度问题的分类和特点、研究现状及方法以及研究方法存在的缺陷和解决思路；
对于一种滚动时域方法，给出了它的改进算法，分别给出这两种算法的仿真结果，并对这两种算法做出比较。由于调度问题本身的复杂性，仿真过程中的参数很多，我们首先做出每个参数变化对调度结果的影响，再取其折中值，最后用该值对改进前后的算法做出详细比较... |
| 【论文题纲】 |
|
中文摘要 |
8-9 |
|
Abstract |
9-11 |
|
第一章 绪论 |
11-21 |
|
1.1 引言 |
11 |
|
1.2 车间调度问题 |
11-13 |
|
1.2.1 调度问题表述 |
11 |
|
1.2.2 车间调度问题的分类和特点 |
11-13 |
|
1.3 Job shop调度问题的求解方法 |
13-17 |
|
1.4 Job shop调度问题的求解策略 |
17-18 |
|
1.4.1 并行与分解策略 |
17 |
|
1.4.2 实时动态重调度策略 |
17 |
|
1.4.3 多目标权衡策略 |
17 |
|
1.4.4 生产计划与调度集成策略 |
17-18 |
|
1.5 车间调度研究存在问题及其解决思路 |
18 |
|
1.6 处理Job shop调度问题的分解方法 |
18-19 |
|
1.7 论文主要内容及章节安排 |
19-21 |
|
1.7.1 论文主要研究内容 |
19 |
|
1.7.2 论文的章节安排 |
19-21 |
|
第二章 处理Job shop调度问题的滚动时域方法 |
21-35 |
|
2.1 引言 |
21 |
|
2.2 一类Job shop调度问题描述 |
21-23 |
|
2.3 移动瓶颈方法 |
23-25 |
|
2.4 滚动时域方法(RHP)算法流程 |
25-27 |
|
2.4.1 预测窗口的确定 |
26 |
|
2.4.2 滚动窗口的确定 |
26 |
|
2.4.3 操作的参数更新 |
26-27 |
|
2.5 滚动时域方法的改进(IRHP) |
27-28 |
|
2.6 仿真实验与分析 |
28-34 |
|
2.6.1 滚动窗口大小变化对算法的影响 |
28-30 |
|
2.6.2 参数ρ变化对算法的影响 |
30-33 |
|
2.6.3 IRHP与RHP的比较 |
33-34 |
|
2.7 本章小结 |
34-35 |
|
第三章 基于移动瓶颈的禁忌搜索方法 |
35-45 |
|
3.1 引言 |
35 |
|
3.2 问题模型 |
35-37 |
|
3.3 禁忌搜索方法 |
37-39 |
|
3.4 倒转技术 |
39-40 |
|
3.5 TS-SB算法 |
40-44 |
|
3.5.1 初始解的获得 |
41 |
|
3.5.2 禁忌搜索过程 |
41-42 |
|
3.5.3 局部再优化过程 |
42-43 |
|
3.5.4 算法流程 |
43-44 |
|
3.6 本章小结 |
44-45 |
|
第四章 总结与展望 |
45-47 |
|
参考文献 |
47-51 |
|
致谢 |
51-52 |
|
学位论文评阅及答辩情况表 |
52 |
|
| 【DOI】 | LunWen.ID:2.2008.388688 |
