考虑维护和可中断工件的混合型平行机调度问题研究

摘要

含有维护的调度已成为组合优化领域里的一个研究热点。本文考虑一个混合型平行机调度问题，其中所有工件加工时长均相等，工件均可中断且工件个数不超过机器台数，部分机器需要周期维护而其余机器无需维护。目标是将所有工件安排在机器上加工，以使得时间表长最小。　　本文对于该调度问题进行了理论分析，首先分析几种特殊情况，对于每一种特殊情况给出一个多项式时间最优算法；接着，对于一般情况，通过建立注水模型给出最优时间表长的一个下界；然后，对一般情况下的两种水位情况，分别给出目标值等于下界的多项式时间算法，从而得到一个求解该调度问题一般情况的一个多项式时间最优算法。同时，为了使读者更好地理解本文所采用的求解思想和所给出的算法，本文提供了丰富的实例分析和验证。

目录

声明

第1章 绪论

1.1 调度的产生及其发展

1.2 调度问题的基本概念

1.3 带有周期维护调度问题的简要回顾

1.4 工件可中断调度问题的简要回顾

1.5 本文的结构安排

第2章 一类含维护的混合型平行机时间表长最小的调度问题的提出

2.1 提出问题

2.2 符号说明

2.3 问题分析

第3章 特殊情况下的混合型平行机调度问题研究

3.1 几种特殊情况的分析

3.2 注记

第4章 一般情况下的混合型平行机调度问题研究

4.1 建立模型求下界

4.2 对应于两种水位的多项式时间算法

4.3 注记

第5章 结论与展望

5.1 总结

5.2 展望

致谢

参考文献