目录

第1章 绪论
1．1 传统的机器调度问题
1．1．1 发展简史
1．1．2 分类与符号表示
1．1．3 常见的求解方法
1．2 考虑维护时间的机器调度问题
1．2．1 研究背景和研究意义
1．2．2 分类与符号表示
1．3 研究内容及结构安排
1．3．1 研究内容
1．3．2 结构安排

第2章 文献综述
2．1 维护时段固定的调度问题
2．1．1 单机调度问题
2．1．2 平行机调度问题
2．1．3 流水作业调度问题
2．1．4 自由作业调度问题
2．1．5 异序作业调度问题
2．2 维护时段可调的调度问题
2．2．1 一般情形：维护时段对应时间窗情形
2．2．2 特殊情形：机器连续工作时间受限情形
2．3 研究现状分析
2．4 本章小结

第3章 维护时段固定且加工时间恒定的单机调度问题
3．1 引言
3．2 最大完工时间最小化问题
3．2．1 LPT规则的相对误差界
3．2．2 启发式算法LPT-PI
3．2．3 启发式算法MLPT及其相对误差界
3．2．4 实验结果及分析
3．2．5 三种启发式算法的比较
3．3 加权完工时间和最小化问题
3．3．1 最优解的性质
3．3．2 动态规划算法
3．3．3 分枝定界算法
3．3．4 实验结果及分析
3．4 本章小结

第4章 维护时段固定且加工时间可变的单机调度问题
4．1 引言
4．2 可续加工情形
4．2．1 加工时间线性增加时的调度问题
4．2．2 加工时间线性减少时的调度问题
4．3 不可续加工情形
4．3．1 动态规划算法
4．3．2 SNPT规则的相对误差界
4．3．3 启发式算法
4．3．4 实验结果及分析
4．3．5 其他不可续情形
4．4 本章小结

第5章 维护时段可调的单机调度问题
5．1 引言
5．2 加工时间恒定的可续加工情形
5．2．1 最优解的性质
5．2．2 SPT算法及其最优性证明
5．3 加工时间恒定的不可续加工情形
5．3．1 最优解的性质
5．3．2 SPT算法及其性能分析
5．3．3 动态规划算法
5．3．4 分枝定界算法
5．3．5 实验结果及分析
5．4 加工时间可变的调度问题
5．5 本章小结

第6章 带维护时段的多机调度问题
6．1 引言
6．2 最大完工时间最小化问题
6．2．1 整数规划模型
6．2．2 启发式算法
6．2．3 算例
6．2．4 实验结果及分析
6．3 加权完工时间和最小化问题
6．3．1 最优解的性质
6．3．2 动态规划算法
6．3．3 启发式算法
6．3．4 实验结果及分析
6．4 其他多机调度问题的研究思路
6．5 本章小结

第7章 总结与展望
7．1 总结
7．2 展望
附录A 定理5-4的证明
参考文献
致谢

内容摘要

　　《考虑维护时间的机器调度问题研究》首先较为详尽的研究了考虑维护时间的单机调度问题，包括维护时段固定且加工时间恒定、维护时段固定且加工时间可变、维护时段可调且加工时间恒定以及维护时段可调且加工时间可变等四类问题。由于不同问题的复杂性不同，《考虑维护时间的机器调度问题研究》给出了不同的求解方法：对于NP—难问题，一方面致力于设计能求解尽可能大规模问题的算法；另一方面，鉴于算法在时间和空间性能上的不足，《考虑维护时间的机器调度问题研究》也致力于构造高效的启发式算法，从而能够在合理的时间内求得大规模问题高质量的满意解。另外，在某些特殊情形下，有些问题是多项式可解的。对于这些问题，通过证明某种多项式时间算法能够为其提供*优解来说明其多项式可解性。