点击次数：

论文类型：期刊论文

发表时间：2010-09-06

发表刊物：THEORETICAL COMPUTER SCIENCE

收录刊物：SCIE、EI、Scopus

卷号：411

期号：40-42

页面范围：3587-3600

ISSN号：0304-3975

关键字：Online algorithms; Competitive analysis; Deadline scheduling; Speed scaling; Sleep management; Energy saving

摘要：In this paper we consider online deadline scheduling on a processor that can manage its energy usage by scaling the speed dynamically or entering a sleep state. A new online scheduling algorithm called SOA is presented. Assuming speed can be scaled arbitrarily high (the infinite speed model), SOA can complete all jobs with reduced energy usage, improving the competitive ratio for energy from 2(2 alpha-2)alpha(alpha) + 2(alpha-1) + 2 (Irani et al. (2007) [17]) to alpha(alpha) + 2, where alpha is the constant involved in the speed-to-power function, commonly believed to be 2 or 3. More importantly, SOA is the first algorithm that works well even if the processor has a fixed maximum speed and the system is overloaded. In this case, SOA is 4-competitive for throughput and (alpha(alpha) + alpha(2)4(alpha) + 2)-competitive for energy. Note that the throughput ratio cannot be better than 4 even if energy is not a concern. (C) 2010 Elsevier B.V. All rights reserved.