当前位置:首页 > 工业技术
考虑维护时间的机器调度问题研究
考虑维护时间的机器调度问题研究

考虑维护时间的机器调度问题研究PDF电子书下载

工业技术

  • 电子书积分:9 积分如何计算积分?
  • 作 者:权怡
  • 出 版 社:合肥:合肥工业大学出版社
  • 出版年份:2016
  • ISBN:9787565028403
  • 页数:187 页
图书介绍:本书首先较为详尽的研究了考虑维护时间的单机调度问题,包括维护时段固定且加工时间恒定、维护时段固定且加工时间可变、维护时段可调且加工时间恒定以及维护时段可调且加工时间可变等四类问题。由于不同问题的复杂性不同,本书给出了不同的求解方法:对于NP—难问题,一方面致力于设计能求解尽可能大规模问题的精确算法;另一方面,鉴于精确算法在时间和空间性能上的不足,本书也致力于构造高效的启发式算法,从而能够在合理的时间内求得大规模问题高质量的满意解。另外,在某些特殊情形下,有些问题是多项式可解的。对于这些问题,通过证明某种多项式时间算法能够为其提供最优解来说明其多项式可解性。
《考虑维护时间的机器调度问题研究》目录

第1章 绪论 1

1.1 传统的机器调度问题 1

1.1.1 发展简史 2

1.1.2 分类与符号表示 3

1.1.3 常见的求解方法 6

1.2 考虑维护时间的机器调度问题 10

1.2.1 研究背景和研究意义 10

1.2.2 分类与符号表示 12

1.3 研究内容及结构安排 15

1.3.1 研究内容 15

1.3.2 结构安排 16

第2章 文献综述 18

2.1 维护时段固定的调度问题 18

2.1.1 单机调度问题 19

2.1.2 平行机调度问题 22

2.1.3 流水作业调度问题 26

2.1.4 自由作业调度问题 32

2.1.5 异序作业调度问题 33

2.2 维护时段可调的调度问题 34

2.2.1 一般情形:维护时段对应时间窗情形 34

2.2.2 特殊情形:机器连续工作时间受限情形 35

2.3 研究现状分析 50

2.4 本章小结 52

第3章 维护时段固定且加工时间恒定的单机调度问题 53

3.1 引言 53

3.2 最大完工时间最小化问题 55

3.2.1 LPT规则的相对误差界 55

3.2.2 启发式算法LPT-PI 56

3.2.3 启发式算法MLPT及其相对误差界 58

3.2.4 实验结果及分析 62

3.2.5 三种启发式算法的比较 67

3.3 加权完工时间和最小化问题 68

3.3.1 最优解的性质 68

3.3.2 动态规划算法 69

3.3.3 分枝定界算法 71

3.3.4 实验结果及分析 74

3.4 本章小结 80

第4章 维护时段固定且加工时间可变的单机调度问题 81

4.1 引言 81

4.2 可续加工情形 83

4.2.1 加工时间线性增加时的调度问题 83

4.2.2 加工时间线性减少时的调度问题 87

4.3 不可续加工情形 89

4.3.1 动态规划算法 89

4.3.2 SNPT规则的相对误差界 91

4.3.3 启发式算法 93

4.3.4 实验结果及分析 94

4.3.5 其他不可续情形 103

4.4 本章小结 104

第5章 维护时段可调的单机调度问题 105

5.1 引言 105

5.2 加工时间恒定的可续加工情形 106

5.2.1 最优解的性质 106

5.2.2 SPT算法及其最优性证明 108

5.3 加工时间恒定的不可续加工情形 109

5.3.1 最优解的性质 109

5.3.2 SPT算法及其性能分析 109

5.3.3 动态规划算法 111

5.3.4 分枝定界算法 112

5.3.5 实验结果及分析 123

5.4 加工时间可变的调度问题 133

5.5 本章小结 135

第6章 带维护时段的多机调度问题 136

6.1 引言 136

6.2 最大完工时间最小化问题 138

6.2.1 整数规划模型 138

6.2.2 启发式算法 139

6.2.3 算例 145

6.2.4 实验结果及分析 147

6.3 加权完工时间和最小化问题 149

6.3.1 最优解的性质 149

6.3.2 动态规划算法 151

6.3.3 启发式算法 152

6.3.4 实验结果及分析 154

6.4 其他多机调度问题的研究思路 163

6.5 本章小结 165

第7章 总结与展望 166

7.1 总结 166

7.2 展望 168

附录A 定理5-4的证明 170

参考文献 172

致谢 187

返回顶部