论文标题
对少数非相同处理器的LPT计划的最坏情况分析
Worst-Case Analysis of LPT Scheduling on Small Number of Non-Identical Processors
论文作者
论文摘要
在几篇论文中研究了最长处理时间（LPT）调度算法的近似值。尽管所有处理器相同的情况都知道紧密的近似值，但是当处理器具有不同的速度时，该比率尚不清楚。在这项工作中，我们给出了处理器数量为3,4和5的情况下的近似值，我们表明，这些情况的比率不超过Gonzalez，Ibarra和Sahni提供的下限（Siam J. Computing 1977）。它们的三个处理器约为1.38，四个处理器为1.43，五个处理器为1.46。
The approximation ratio of the longest processing time (LPT) scheduling algorithm has been studied in several papers. While the tight approximation ratio is known for the case when all processors are identical, the ratio is not yet known when the processors have different speeds. In this work, we give a tight approximation ratio for the case when the number of processors is 3,4, and 5. We show that the ratio for those cases are no more than the lower bound provided by Gonzalez, Ibarra, and Sahni (SIAM J. Computing 1977). They are approximately 1.38 for three processors, 1.43 for four processors, and 1.46 for five processors.
