Energy-efficient algorithms for flow time minimization

ABSTRACT

We study scheduling problems in battery-operated computing devices, aiming at schedules with low total energy consumption. While most of the previous work has focused on finding feasible schedules in deadline-based settings, in this article we are interested in schedules that guarantee good response times. More specifically, our goal is to schedule a sequence of jobs on a variable-speed processor so as to minimize the total cost consisting of the energy consumption and the total flow time of all jobs.

We first show that when the amount of work, for any job, may take an arbitrary value, then no online algorithm can achieve a constant competitive ratio. Therefore, most of the article is concerned with unit-size jobs. We devise a deterministic constant competitive online algorithm and show that the offline problem can be solved in polynomial time.

REFERENCES

• 1: John Augustine , Sandy Irani , Chaitanya Swamy, Optimal Power-Down Strategies, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, p.530-539, October 17-19, 2004 [doi>10.1109/FOCS.2004.50]
• 2: Nikhil Bansal , Tracy Kimbrel , Kirk Pruhs, Dynamic Speed Scaling to Manage Energy and Temperature, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, p.520-529, October 17-19, 2004 [doi>10.1109/FOCS.2004.24]
• 3: Bansal, N., and Pruhs, K. 2005. Speed scaling to manage temperature. In Proceedings of the 22nd Annual Symposium on Theoretical Aspects of Computer Science (STACS). Lecture Notes in Computer Science, vol. 3404, Springer, 460--471.
• 4: Nikhil Bansal , Kirk Pruhs , Cliff Stein, Speed scaling for weighted flow time, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.805-813, January 07-09, 2007, New Orleans, Louisiana
• 5: David P. Bunde, Power-aware scheduling for makespan and flow, Proceedings of the eighteenth annual ACM symposium on Parallelism in algorithms and architectures, July 30-August 02, 2006, Cambridge, Massachusetts, USA [doi>10.1145/1148109.1148140]
• 6: Cornuéjols, G., Nemhauser, G., and Wolsey, L. 1990. The uncapacitated facility location problem. In Discrete Location Theory, P. Mirchandani and R. Francis (eds.), John Wiley and Sons, New York, 119--171.
• 7: Daniel R. Dooly , Sally A. Goldman , Stephen D. Scott, On-line analysis of the TCP acknowledgment delay problem, Journal of the ACM (JACM), v.48 n.2, p.243-273, March 2001 [doi>10.1145/375827.375843]
• 8: Alex Fabrikant , Ankur Luthra , Elitza Maneva , Christos H. Papadimitriou , Scott Shenker, On a network creation game, Proceedings of the twenty-second annual symposium on Principles of distributed computing, p.347-351, July 13-16, 2003, Boston, Massachusetts [doi>10.1145/872035.872088]
• 9: Sandy Irani , Kirk R. Pruhs, Algorithmic problems in power management, ACM SIGACT News, v.36 n.2, June 2005 [doi>10.1145/1067309.1067324]
• 10: Sandy Irani , Sandeep Shukla , Rajesh Gupta, Algorithms for power savings, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 11: Karlin, A., Kenyon, C., and Randall, D. 2003. Dynamic TCP acknowledgement and other stories about e/(e−1). Algorithmica 36, 209--224.
• 12: Mirchandani, P., and Francis, R. 1990. Discrete Location Theory. John Wiley and Sons, New York.
• 13: Pruhs, K., Uthaisombut, P., and Woeginger, G. 2004. Getting the best response for your ERG. In Proceedings of the 9th Scandinavian Workshop on Algorithm Theory (SWAT). Lecture Notes in Computer Science, vol. 3111, Springer, 15--25.
• 14: David B. Shmoys , Joel Wein , David P. Williamson, Scheduling Parallel Machines On-line, SIAM Journal on Computing, v.24 n.6, p.1313-1331, Dec. 1995 [doi>10.1137/S0097539793248317]
• 15: Daniel D. Sleator , Robert E. Tarjan, Amortized efficiency of list update and paging rules, Communications of the ACM, v.28 n.2, p.202-208, Feb. 1985 [doi>10.1145/2786.2793]
• 16: F. Yao , A. Demers , S. Shenker, A scheduling model for reduced CPU energy, Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS'95), p.374, October 23-25, 1995

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sequencing and scheduling

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Combinatorial algorithms

General Terms:
Algorithms, Theory

Keywords:
Variable-speed processor, competitive analysis, dynamic programming, flow time, offline algorithms, online algorithms