Nonmigratory multiprocessor scheduling for response time and energy
Energy usage has been an important concern in recent research on online job scheduling, where processors are allowed to vary the speed dynamically so as to save energy whenever possible. Providing good quality of service such as response time (flowtime) and conserving energy are conflicting objectives. An interesting problem for scheduling is how to optimize an economic trade-off of flowtime and energy. To this end, the past two years have witnessed significant progress in the single-processor setting, and online algorithms with performance close to optimal have been obtained. In this paper, we extend the study of optimizing the trade-off between flowtime and energy to the multiprocessor setting. We devise and analyze a simple nonmigratory online algorithm that makes use of the classified round-robin (CRR) strategy to dispatch jobs. Even in the worst case, its performance is within O(log P) times of the optimal migratory offline algorithm, where P is the ratio of the maximum job size to the minimum job size. Technically speaking, this online result stems from a nontrivial solution to an offline problem of eliminating migration, which is also interesting by itself.
analysis of algorithms and problem complexity sequencing and scheduling online computation energy-aware systems