Nikhil Bansal
Abstract
This article initiates a theoretical investigation into online scheduling problems with speed scaling where the allowable speeds may be discrete, and the power function may be arbitrary, and develops algorithmic analysis techniques for this setting. We show that a natural algorithm, which uses Shortest Remaining Processing Time for scheduling and sets the power to be one more than the number of unfinished jobs, is 3-competitive for the objective of total flow time plus energy. We also show that another natural algorithm, which uses Highest Density First for scheduling and sets the power to be the fractional weight of the unfinished jobs, is a 2-competitive algorithm for the objective of fractional weighted flow time plus energy.
- Albers, S. and Fujiwara, H. 2007. Energy-Efficient algorithms for flow time minimization. ACM Trans. Algor. 3, 4, 49. Google Scholar
Digital Library
- Andrew, L. L., Wierman, A., and Tang, A. 2009. Optimal speed scaling under arbitrary power functions. SIGMETRICS Perform. Eval. Rev. 37, 2, 39--41. Google ScholarDigital Library
- Bansal, N. and Chan, H.-L. 2009. Weighted flow time does not admit O(1)-competitive algorithms. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms. 1238--1244. Google ScholarDigital Library
- Bansal, N., Chan, H.-L., Lam, T. W., and Lee, L.-K. 2008. Scheduling for speed bounded processors. In Proceedings of the International Colloquium on Automata, Languages and Programming. 409--420. Google ScholarDigital Library
- Bansal, N., Pruhs, K., and Stein, C. 2007. Speed scaling for weighted flow time. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms. 805--813. Google ScholarDigital Library
- Bower, F. A., Sorin, D. J., and Cox, L. P. 2008. The impact of dynamically heterogeneous multicore processors on thread scheduling. IEEE Micro 28, 3, 17--25. Google ScholarDigital Library
- Gupta, A., Krishnaswamy, R., and Pruhs, K. 2010a. Nonclairvoyantly scheduling power-heterogeneous processors. In Proceedings of the IEEE International Green Computing Conference. Google ScholarDigital Library
- Gupta, A., Krishnaswamy, R., and Pruhs, K. 2010b. Scalably scheduling power-heterogeneous processors. In Proceedings of the International Colloquium on Automata Languages and Programming. 312--323. Google ScholarDigital Library
- Lam, T., Lee, L., To, I., and Wong, P. 2008. Speed scaling functions based for flow time scheduling based on active job count. In Proceedings of the European Symposium on Algorithms. 647--659. Google ScholarDigital Library
- Li, M. and Yao, F. F. 2005. An efficient algorithm for computing optimal discrete voltage schedules. SIAM J. Comput. 35, 658--671. Google ScholarDigital Library
- Pruhs, K. 2007. Competitive online scheduling for server systems. SIGMETRICS Perform. Eval. Rev. 34, 4, 52--58. Google ScholarDigital Library
- Pruhs, K., Uthaisombut, P., and Woeginger, G. J. 2008. Getting the best response for your erg. ACM Trans. Algor. 4, 3. Google ScholarDigital Library
Index Terms
- Speed Scaling with an Arbitrary Power Function
Recommendations
Throughput maximization for speed scaling with agreeable deadlines
We study the following energy-efficient scheduling problem. We are given a set of n jobs which have to be scheduled by a single processor whose speed can be varied dynamically. Each job $$J_j$$Jj is characterized by a processing requirement (work) $$p_j$...
Throughput maximization in multiprocessor speed-scaling
In the classical energy minimization problem, introduced in 24, we are given a set of n jobs each one characterized by its release date, its deadline, its processing volume and we aim to find a feasible schedule of the jobs on a single speed-scalable ...
Speed Scaling for Maximum Lateness
We consider the power-aware problem of scheduling non-preemptively a set of jobs on a single speed-scalable processor so as to minimize the maximum lateness, under a given budget of energy. In the offline setting, our main contribution is a ...
Comments