期刊
SIAM JOURNAL ON COMPUTING
卷 32, 期 3, 页码 671-680出版社
SIAM PUBLICATIONS
DOI: 10.1137/S0097539702410697
关键词
parallel processor scheduling; preemptive scheduling; nonpreemptive scheduling; i-preemptive scheduling; longest processing time rule; schedule length; worst-case analysis
In this paper, we compare the makespan of preemptive and i-preemptive schedules where only a limited number i of preemptions is allowed. The problem is to schedule n independent jobs on m identical processors that operate in parallel. The objective is to minimize the makespan, i. e., the completion time of the last job that finishes. We show that the ratio of the optimal i-preemptive schedule length C-max(ip)* versus the optimal preemptive schedule length C-max(p)* is bounded from above by C-max(ip)* less than or equal to ( 2 - 2/(m/(i + 1) + 1)) C-max(p)*. Furthermore, we show that the ratio of the length C-max(LPT) of a nonpreemptive schedule following the longest processing time (LPT) rule versus the optimal preemptive schedule length C-max(p)* is bounded from above by exactly the same bound when i = 0.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据