Improved multi‐processor scheduling for flow time and energy

Improved multi‐processor scheduling for flow time and energy

0.00 Avg rating0 Votes
Article ID: iaor2012923
Volume: 15
Issue: 1
Start Page Number: 105
End Page Number: 116
Publication Date: Feb 2012
Journal: Journal of Scheduling
Authors: , , ,
Keywords: scheduling, networks: flow, combinatorial optimization
Abstract:

Energy usage has been an important concern in recent research on online scheduling. In this paper, we study the tradeoff between flow time and energy (Albers and Fujiwara 2007; Bansal et al. 2007b, Bansal et al. 2008; Lam et al. 2008b) in the multi‐processor setting. Our main result is an enhanced analysis of a simple non‐migratory online algorithm called CRR (classified round robin) on m≥2 processors, showing that its flow time plus energy is within O(1) times of the optimal non‐migratory offline algorithm, when the maximum allowable speed is slightly relaxed. The result still holds even if the comparison is made against the optimal migratory offline algorithm. This improves previous analysis that CRR is O(log P)‐competitive where P is the ratio of the maximum job size to the minimum job size.

Reviews

Required fields are marked *. Your email address will not be published.