Lam, Tak-Wah3; Lee, Lap Kei5; To, Isaac K. K.4; Wong, Prudence W. H.4
1 Department of Computer Science, Science and Technology, Aarhus University2 Department of Computer Science - Center for Massive Data Algoritmics, Department of Computer Science, Science and Technology, Aarhus University3 Department of Computer Science, University of Hong Kong4 Department of Computer Science, University of Liverpool5 Department of Computer Science, Science and Technology, Aarhus University
This paper is concerned with online scheduling algorithms that aim at minimizing the total flow time plus energy usage. The results are divided into two parts. First, we consider the well-studied “simple” speed scaling model and show how to analyze a speed scaling algorithm (called AJC) that changes speed discretely. This is in contrast to the previous algorithms which change the speed continuously. More interestingly, AJC admits a better competitive ratio, and without using extra speed. In the second part, we extend the study to a more general speed scaling model where the processor can enter a sleep state to further save energy. A new sleep management algorithm called IdleLonger is presented. This algorithm, when coupled with AJC, gives the first competitive algorithm for minimizing total flow time plus energy in the general model.
Algorithmica, 2013, Vol 65, Issue 3, p. 605-633
Online algorithms; Competitive analysis; Scheduling; Energy efficiency; Dynamic speed scaling; Sleep management; Flow time