基于分解策略处理Job shop调度问题的两种方法

论文摘要

作业车间调度问题(Job Shop Scheduling Problem，JSSP)被认为是一种困难的组合最优化问题之一，它的复杂性主要体现在其计算的难处理性和动态不确定性，由于人们找不到处理这类复杂问题的精确优化算法，因此用启发式算法求解成为当今研究这类问题的重点。分解策略作为一种启发式方法，能够有效的降低问题的复杂性。将调度问题分为两层，上层考虑各子问题之间的约束关系，下层考虑各子问题内的约束关系，实际的调度发生在下层，再考虑上层中的约束关系，使得到的调度解可行。本文给出了处理一类典型Job shop调度问题的基于分解策略的两种方法：一种是滚动时域方法并给出其改进，另一种是基于移动瓶颈的禁忌搜索方法。归纳起来，本文主要做了以下几方面的工作：简单介绍了车间调度问题的分类和特点、研究现状及方法以及研究方法存在的缺陷和解决思路；对于一种滚动时域方法，给出了它的改进算法，分别给出这两种算法的仿真结果，并对这两种算法做出比较。由于调度问题本身的复杂性，仿真过程中的参数很多，我们首先做出每个参数变化对调度结果的影响，再取其折中值，最后用该值对改进前后的算法做出详细比较；提出了一种基于移动瓶颈的禁忌搜索方法，用移动瓶颈方法给出初始值，然后用局部搜索不断改进得到的调度解，每当搜索到一个更好的解，再用移动瓶颈方法再优化，最终达到求解的目的。

论文目录

• 中文摘要
• Abstract
• 第一章 绪论
• 1.1 引言
• 1.2 车间调度问题
• 1.2.1 调度问题表述
• 1.2.2 车间调度问题的分类和特点
• 1.3 Job shop调度问题的求解方法
• 1.4 Job shop调度问题的求解策略
• 1.4.1 并行与分解策略
• 1.4.2 实时动态重调度策略
• 1.4.3 多目标权衡策略
• 1.4.4 生产计划与调度集成策略
• 1.5 车间调度研究存在问题及其解决思路
• 1.6 处理Job shop调度问题的分解方法
• 1.7 论文主要内容及章节安排
• 1.7.1 论文主要研究内容
• 1.7.2 论文的章节安排
• 第二章 处理Job shop调度问题的滚动时域方法
• 2.1 引言
• 2.2 一类Job shop调度问题描述
• 2.3 移动瓶颈方法
• 2.4 滚动时域方法（RHP）算法流程
• 2.4.1 预测窗口的确定
• 2.4.2 滚动窗口的确定
• 2.4.3 操作的参数更新
• 2.5 滚动时域方法的改进（IRHP）
• 2.6 仿真实验与分析
• 2.6.1 滚动窗口大小变化对算法的影响
• 2.6.2 参数ρ变化对算法的影响
• 2.6.3 IRHP与RHP的比较
• 2.7 本章小结
• 第三章 基于移动瓶颈的禁忌搜索方法
• 3.1 引言
• 3.2 问题模型
• 3.3 禁忌搜索方法
• 3.4 倒转技术
• 3.5 TS-SB算法
• 3.5.1 初始解的获得
• 3.5.2 禁忌搜索过程
• 3.5.3 局部再优化过程
• 3.5.4 算法流程
• 3.6 本章小结
• 第四章 总结与展望
• 参考文献
• 致谢
• 学位论文评阅及答辩情况表