第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