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 paper 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 power consumption and the total flow time of all the 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 paper 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.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Augustine, J., Irani, S., Swamy, C.: Optimal power-down strategies. In: Proc. 45th Annual IEEE Symposium on Foundations of Computer Science, pp. 530–539 (2004)
Bansal, N., Kimbrel, T., Pruhs, K.: Dynamic speed scaling to manage energy and temperature. In: Proc. 45th Annual IEEE Symposium on Foundations of Computer Science, pp. 520–529 (2004)
Bansal, N., Pruhs, K.: Speed scaling to manage temperature. In: Diekert, V., Durand, B. (eds.) STACS 2005. LNCS, vol. 3404, pp. 460–471. Springer, Heidelberg (2005)
Cornuéjols, G., Nemhauser, G.L., Wolsey, L.A.: The uncapacitated facility location problem. In: Mirchandani, P., Francis, R. (eds.) Discrete Location Theory, pp. 119–171. John Wiley & Sons, Chichester (1990)
Dooly, D.R., Goldman, S.A., Scott, S.D.: On-line analyis of the TCP acknowledgment delay problem. Journal of the ACM 48, 243–273 (2001)
Fabrikant, A., Luthra, A., Maneva, E., Papadimitriou, C.H., Shenker, S.: On a network creation game. In: Proc. 22nd Annual ACM Symposium on Principles of Distributed Computing, pp. 347–351 (2003)
Irani, S., Shukla, S., Gupta, R.: Algorithms for power savings. In: Proc. 14th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 37–46 (2003)
Karlin, A.R., Kenyon, C., Randall, D.: Dynamic TCP acknowledgement and other stories about e/(e − 1). In: Proc. 33rd ACM Symposium on Theory of Computing, pp. 502–509 (2001)
Mirchandani, P., Francis, R. (eds.): Discrete Location Theory. John Wiley & Sons, Chichester (1990)
Pruhs, K., Uthaisombut, P., Woeginger, G.: Getting the best response for your erg. In: Hagerup, T., Katajainen, J. (eds.) SWAT 2004. LNCS, vol. 3111, pp. 15–25. Springer, Heidelberg (2004)
Sleator, D.D., Tarjan, R.E.: Amortized efficiency of list update and paging rules. Communications of the ACM 28, 202–208 (1985)
Shmoys, D., Wein, J., Williamson, D.P.: Scheduling parallel machines on-line. SIAM Journal on Computing 24, 1313–1331 (1995)
Yao, F., Demers, A., Shenker, S.: A scheduling model for reduced CPU energy. In: Proc. 36th Annual Symposium on Foundations of Computer Science, pp. 374–382 (1995)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Albers, S., Fujiwara, H. (2006). Energy-Efficient Algorithms for Flow Time Minimization. In: Durand, B., Thomas, W. (eds) STACS 2006. STACS 2006. Lecture Notes in Computer Science, vol 3884. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11672142_51
Download citation
DOI: https://doi.org/10.1007/11672142_51
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-32301-3
Online ISBN: 978-3-540-32288-7
eBook Packages: Computer ScienceComputer Science (R0)