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

基于时间D-子集任务排序与调度问题研究

作　者: 杨新玲
导　师: 李彦平
学　校: 沈阳大学
专　业: 管理科学与工程
关键词: 极大代数时间D-子集任务排序函数最优排序与调度启发式动态规划算法
分类号: F224
类　型: 硕士论文
年　份: 2010年
下　载: 17次
引　用: 0次
阅　读: 论文下载

内容摘要

摘要本文以车间调度问题为背景,以Dioid代数理论为基础,研究了单机任务排序与调度问题及多机任务排序与调度问题。两者都是车间调度问题的特例,同时也是复杂车间调度问题的基础。首先通过引入单机与多机任务排序函数及任务开工与完工时间D子集,从机理上建立了单机与多机任务调度的极大代数模型。模型描述了任务的开工时间和完工时间与任务的到达时间和加工时间之间的复杂关系。多机任务排序函数表征了任务在机器上的分配与排序双重问题。在此基础上,给出极大代数意义下的单机与多机任务最优排序与调度问题规划模型。然后,论文分别研究了单机和多机任务最优排序与调度问题的启发式求解算法。在单机任务排序与调度问题中,给出了求解单机任务排序与调度问题的k均加工时间启发式动态规划算法与多规则混合启发式算法。算法从整体机理考虑调度问题,兼顾了常规启发式算法的优点,可以得到单机问题比较满意的调度方案。在多机任务排序与调度问题中,分别给出了在同速并行机与异速并行机下的动态规划启发式算法。最后,通过实例对比分析,证明了论文所提出启发式算法的有效性,同时指出了相应算法的优缺点。

全文目录

摘要  5-6
Abstract  6-9
1 绪论  9-21
  1.1 车间调度概述  9-14
    1.1.1 车间调度描述方法  9-11
    1.1.2 车间调度分类  11-13
    1.1.3 车间调度性能指标  13-14
  1.2 车间调度研究方法  14-16
  1.3 车间调度研究现状  16-17
  1.4 本文研究动机与主要工作  17-21
2 Dioid代数基础  21-33
  2.1 Dioid代数  21-25
  2.2 极大代数  25-27
  2.3 布尔代数  27-29
  2.4 D子集  29-31
  2.5 本章小结  31-33
3 单机任务排序与调度  33-43
  3.1 基本概念与假设  33
  3.2 单机任务排序函数  33-34
  3.3 单机任务调度模型  34-35
  3.4 单机任务最优排序与调度  35-37
  3.5 几种常规启发式算法  37-39
  3.6 启发式动态规划算法  39-40
  3.7 多规则混合启发式算法  40-41
  3.8 本章小结  41-43
4 多机任务排序与调度  43-53
  4.1 基本概念与假设  43
  4.2 多机与单机关系  43-44
  4.3 多机任务排序函数  44-45
  4.4 多机任务调度模型  45-46
  4.5 多机任务最优排序与调度  46-48
  4.6 多机任务排序与调度启发式算法  48-51
    4.6.1 同速并行机启发式算法  48-50
    4.6.2 异速并行机启发式算法  50-51
  4.7 本章小结  51-53
5 实例分析  53-65
  5.1 单机任务排序与调度算法实例分析  53-59
    5.1.1 动态规划启发式算法实例分析  53-56
    5.1.2 多规则混合启发式算法实例分析  56-59
  5.2 多机任务排序与调度实例分析  59-63
  5.3 本章小结  63-65
6 总结与展望  65-67
  6.1 现阶段工作总结  65
  6.2 进一步研究工作  65-67
参考文献  67-73
在学期间研究成果  73-75
致谢  75

基于时间D-子集任务排序与调度问题研究

内容摘要

全文目录

相似论文