Parallel Processor Scheduling with Limited Number of Preemptions, Siam

Abstract. 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 ipreemptive schedule length C ip∗ max versus the optimal preemptive schedule length C p∗ max is bounded fromabove by C ip∗ max ≤ (2 − 2/(m/(i + 1) + 1))C p∗ max. Furthermore, we show that the ratio of the length CLP T max of a nonpreemptive schedule following the longest processing time (LPT) rule versus the optimal preemptive schedule length C p∗ max is bounded fromabove by exactly the same bound when i =0. Key words. parallel processor scheduling, preemptive scheduling, nonpreemptive scheduling, i-preemptive scheduling, longest processing time rule, schedule length, worst-case analysi