带有维护时段的平行机排序问题近似算法研究

This project mainly investigates parallel machine scheduling problems with machine maintenance periods. In contrast with classical scheduling problems, these problems are more practical. Although there have been a lot of researches considering such problems, however, most of them are with respect to problems of minimizing the makespan; only few researches study the objective of total completion time, especially on the design and analysis of approximation algorithms. In this project, we focus on the latter objective. We first consider scheduling problems with periodic maintenance periods, then those problems with arbitrary maintenance periods. For each problem, our main work is analyzing computational complexity and designing approximation algorithms with good performance.

本项目主要考虑机器带有维护时段的平行机排序问题。相比经典排序问题，该排序模型更具实际应用背景。对该模型的研究，已有的文献大多以极小化工件最大完工时间为目标，而对极小化工件总完工时间的目标研究甚少，特别是在近似算法设计与分析方面。本项目重点研究以极小化工件总完工时间为目标的问题，我们将首先考虑维护时段周期性发生的情形，随后讨论维护时段任意分布的情形。针对每一种情形，项目的核心工作是分析问题的计算复杂性以及设计求解问题的高性能近似算法。

近年来，机器带有维护时段的排序问题引起了国内外诸多学者的研究兴趣，对此类问题的深入研究促使了大量排序新模型和新方法不断涌现，对排序理论和实际应用都产生了深远的影响。本项目重点研究以极小化工件总完工时间为目标的机器带有维护时段的排序问题。首先，我们研究了工件可跨越维护时段的单机排序问题，证明了该问题的NP-困难性，并提出了一个近似比为20/17的多项式时间近似算法；再者，我们考虑了带有维护时段的两台机排序问题，在证明此问题不存在近似比严格小于2的多项式时间近似算法的同时，设计了一个近似比恰好为2的多项式时间近似算法，由此得到了该问题理论上的最好结果。上述结果均已得到国内外同行的认可并发表在国际SCI期刊上。