摘要:通过查阅大量的相关参考文献，全面考虑目前单机动态调度的发展现状，从理论上讲，有大量的调度问题都是NP难的问题，当前仍旧没有高效率的多项式方法进行求解，因此从理论上研究调度问题，寻找有效的求解策略并探求其理论基础，仍具有重大的意义。从实践角度看，目前的调度理论和方法研究与实际要求还存在着较大差距，理论成果不能很好地应用到实践，因此研究缩小理论成果与实际问题之间的差距，使丰富的理论成果应用到实际调度问题，将会产生巨大的经济效益。

本文以单机调度问题为研究对象，探讨了该问题的分支定界算法并进行了改进设计，同时，本文还研究了该问题的滚动调度算法，提出了滚动调度框架并进行了仿真分析。

关键词：单机动态调度；分支定界算法；滚动调度

目录

摘要

Abstract

1 绪论-1

1.1 研究背景和意义-1

1.2 单机动态调度问题的发展过程及研究现状-3

1.2.1 关于单机调度问题-3

1.2.2 常见的单机调度问题-4

1.3 本文的工作内容-4

2 单机动态调度问题的数学描述及建模-6

2.1 调度问题的数学描述-6

2.2 单机动态调度问题模型建立-6

2.3本章小结-7

3 单机调度分支定界法及其算法改进-8

3.1 优化问题的分支定界算法-8

3.1.1 分支定界的算法特征-8

3.1.2 分支定界算法的基本实现技术-9

3.2 单机调度的线性规划松弛方法-10

3.3 基于线性规划松弛的单机调度分支定界改进算法-12

3.4 仿真实验分析-12

3.5 本章小结-13

4 滚动调度方法及其仿真分析-14

4.1 滚动调度的研究背景-14

4.2 滚动调度策略-14

4.2.1 有终端约束的单机滚动调度算法-15

4.2.2 无终端约束的单机滚动调度算法-16

4.3 滚动调度参数仿真分析-17

4.4 本章小结-19

结    论-20

参 考 文 献-21

致    谢-22