学位论文 > 优秀研究生学位论文题录展示

基于网络流的开放式车间调度问题研究

作　者: 孟令玉
导　师: 邱长华
学　校: 哈尔滨工程大学
专　业: 机械制造及其自动化
关键词: 开放式车间调度问题网络最大流含参最大流减量集合
分类号: TH186
类　型: 硕士论文
年　份: 2010年
下　载: 56次
引　用: 2次
阅　读: 论文下载

内容摘要

开放式车间调度问题(Open-Shop Scheduling Problem)也称为自由作业调度问题,是作业车间调度问题的一种特殊形式。开放式车间调度问题因应用领域广泛受到人们的重视,本文研究一类带有并行机的开放式车间调度问题,其中工件具有时间窗约束,加工过程允许中断,但不允许延期,分别求出问题的可行调度结果以及以最小制造期为目标的最优调度结果。本文将开放式车间调度问题的求解过程分解为资源分配和排序两个阶段。在资源分配阶段,首先建立了开放式车间的线性规划模型,然后将线性规划模型转化为网络模型,在网络模型中机器和工件用节点表示,车间的各种约束条件用弧的容量约束表示,最后,通过网络最大流算法求得了开放式车间的可行调度结果,并在此基础上通过含参最大流网络对分配结果进行优化,得到了以最小制造期为目标的开放式车间的调度结果。在排序阶段,首先制定规则将分配到并行机组的加工时间分配到每台并行机,然后分别建立每个时间段内的加工时间矩阵,通过在各矩阵中选择减量集合得到最终调度结果。最后,通过算例分析初步验证了算法的正确性,并在VC++6.0环境中以SQL Server 2000作为后台数据库开发了开放式车间调度系统原型。该系统具有友好的交互界面,并能够以甘特图的形式直观的给出调度结果。

全文目录

摘要  5-6
ABSTRACT  6-10
第1章绪论  10-18
  1.1 研究的目的意义  10-11
  1.2 开放式车间调度简介  11-12
  1.3 开放式车间调度问题的研究现状  12-15
  1.4 主要工作  15-16
  1.5 论文结构  16-18
第2章网络最大流算法的选择  18-27
  2.1 概述  18-19
  2.2 最大流问题的基本算法  19-26
    2.2.1 增广路算法  20-21
    2.2.2 预流-推进算法  21
    2.2.3 两类算法的比较  21-22
    2.2.4 算法复杂度分析与实验性能测试  22-26
  2.3 本章小结  26-27
第3章开放式车间调度问题及求解分析  27-36
  3.1 开放式车间调度问题描述  27-30
    3.1.1 开放车间调度问题的数学模型  28-29
    3.1.2 网络流模型  29-30
  3.2 应用网络流算法求解调度问题的基本思路  30-35
    3.2.1 资源分配阶段的求解分析  31-33
    3.2.2 资源分配阶段的核心算法—Dinic阻塞流算法  33-35
  3.3 本章小结  35-36
第4章开放式车间的可行性调度  36-49
  4.1 调度可行性条件的等价转换  36-37
  4.2 可行性调度的总体方案设计  37-38
  4.3 数据预处理  38-39
  4.4 分配问题求解  39-44
    4.4.1 初步分配过程  40-41
    4.4.2 最终分配过程  41-44
  4.5 分配结果排序  44-48
    4.5.1 并行机组的负载平衡规则  44-45
    4.5.2 排序过程  45-46
    4.5.3 排序实例  46-48
  4.6 本章小结  48-49
第5章最小制造期调度及实例  49-66
  5.1 优化的必要性分析  49
  5.2 最小制造期调度总体方案  49-51
  5.3 最小制造期调度求解  51-54
  5.4 计算实例  54-65
  5.5 本章小结  65-66
第6章开放式车间调度系统开发  66-71
  6.1 数据库设计  66-68
  6.2 系统交互界面开发  68-69
  6.3 调度系统应用  69-70
  6.4 本章小结  70-71
结论  71-73
参考文献  73-79
攻读硕士学位期间发表的论文和取得的科研成果  79-80
致谢  80-81
附录A 网络流理论的基本概念  81-84
附录B 数据库连接源代码  84

基于网络流的开放式车间调度问题研究

内容摘要

全文目录

相似论文