基于分枝界限法的开放车间调度问题的研究

论文摘要

车间调度问题作为制造系统优化的核心问题之一,一直受到人们的广泛关注。开放车间调度问题是生产调度问题中一个非常重要的课题,是学术上熟知的困难度极高的组合最优化问题。因而,在应用领域也受到人们的广泛关注。在实际的工业环境中,加工一个工作之前往往要做一些准备。通常,所做准备的时间长短取决于两个连续工作之间的顺序。这种情况下,所做的准备叫做顺序决定的准备。本文是利用分枝界限法以最小化制造期为优化目标,求解顺序决定准备时间的开放车间调度问题。调度问题在求最优解时,往往利用分枝界限法作为求解方法。但是求最优解时,因为求解过程非常复杂而且耗时多,所以在实际中的应用并不十分广泛,特别是当前,各类智能优化算法几乎成为调度算法的主流。然而,由于多数智能优化算法为随机优化算法,不能总是保证算法在每一次运行中解的质量,而且,算法运行过程中对于各类参数的选择、算法结束的条件等问题也难以得到一般化的规律。因此,研究分枝界限法等传统最优化方法依然有其重要的意义和价值。在分枝界限法中,设计良好的上限值和下限值是获得最优解的关键。因为上限值和下限值的品质越好,就可以删除很多无用的分枝节点,进而加快求解的速度。本文提出几个上下限值算法,可得到相当优的解,但尚无一个良好的删除法则,故而仍然要浪费很多时间在无用的分枝节点上。通过实例验证比较了几个上限值算法的优劣,但实际应用中主要依赖于数据。最后,给出了未来的几点研究方向。

论文目录

• 摘要
• Abstract
• 第一章 绪论
• 1.1 研究背景及意义
• 1.2 开放车间调度问题国内外研究现状
• 1.3 最优解方法与近似解方法
• 1.4 本文主要内容
• 第二章 问题描述
• 2.1 开放车间
• 2.1 顺序决定的准备时间
• 2.3 优化目标
• 2.4 派工法则
• 第三章 研究方法与步骤
• 3.1 数学模型
• 3.2 符号定义
• 3.3 下限值算法
• 3.3.1 下限值算法（1）
• 3.3.2 下限值算法（2）
• 3.4 上限值算法
• 3.4.1 上限值算法（1）
• 3.4.2 上限值算法（2）
• 3.4.3 上限值算法（3）
• 3.5 分枝界限法
• 3.5.1 分枝策略
• 3.5.2 搜索策略
• 3.5.3 删除法则
• 第四章 实例验证
• 4.1 两台机器实例验证
• 4.2 多台机器实例验证
• 第五章 总结与展望
• 5.1 本文总结
• 5.2 研究展望
• 参考文献
• 在学研究成果
• 致谢