Abstract
While previous work on energy-efficient algorithms focused on assumption that tasks can be assigned to any processor, we initially study the problem of task scheduling on restricted parallel processors. The objective is to minimize the overall energy consumption while speed scaling (SS) method is used to reduce energy consumption under the execution time constraint (Makespan C max ). In this work, we discuss the speed setting in the continuous model that processors can run at arbitrary speed in [s min ,s max ]. The energy-efficient scheduling problem, involving task assignment and speed scaling, is inherently complicated as it is proved to be NP-Complete. We formulate the problem as an Integer Programming (IP) problem. Specifically, we devise a polynomial time optimal scheduling algorithm for the case tasks have an uniform size. Our algorithm runs in O(mn 3 logn) time, where m is the number of processors and n is the number of tasks. We then present a polynomial time algorithm that achieves an approximation factor of \(2^{\alpha-1}(2-\frac{1}{m^{\alpha}})\) (α is the power parameter) when the tasks have arbitrary size work.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Mudge, T.: Power: A first-class architecture design constraint. Journal of Computer 34(4), 52–58 (2001)
Aupy, G., Benoit, A., Dufossé, F., Robert, Y.: Reclaiming the energy of a schedule: Models and algorithms. INRIA Research report RR-7598 (April 2011); Short version appeared in SPAA 2011
Yao, F., Demers, A., Shenker, S.: A scheduling model for reduced CPU energy. In: Proceedings of the IEEE Symposium on Foundation of Computer Science (FOCS 1995), pp. 374–382 (1995)
Ishihara, T., Yasuura, H.: Voltage scheduling problem for dynamically variable voltage processors. In: Proceeding of the International Symposium on Low Power Electronics and Design (ISLPED 1998), pp. 197–202 (1998)
Irani, S., Shukla, S., Gupta, R.: Algorithms for power savings. In: ACM-SIAM Symposium on Discrete Algorithms (SODA 2003), pp. 37–46 (2003)
Chen, J., Kuo, W.: Multiprocessor energy-efficient scheduling for real-time jobs with different power characteristics. In: International Conference on Parallel Processing (ICPP 2005), pp. 13–20 (2005)
Albers, S., Müller, F., Schmelzer, S.: Speed scaling on parallel processors. In: Proceedings of the 19th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA 2007), pp. 289–298 (2007)
Pruhs, K., van Stee, R., Uthaisombut, P.: Speed scaling of tasks with precedence constraints. Theory of Computing System 43(1), 67–80 (2008)
Greiner, G., Nonner, T., Souza, A.: The bell is ringing in speed-scaled multiprocessor scheduling. In: Proceedings of the 21st Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA 2009), pp. 11–18 (2009)
Angel, E., Bampis, E., Kacem, F., Letsios, D.: Speed scaling on parallel processors with migration. In: Kaklamanis, C., Papatheodorou, T., Spirakis, P.G. (eds.) Euro-Par 2012. LNCS, vol. 7484, pp. 128–140. Springer, Heidelberg (2012)
Srikantaiah, S., Kansal, A., Zhao, F.: Energy aware consolidation for cloud computing. In: Proceedings of the Conference on Power Aware Computing and Systems (Hotpower 2008) (2008)
Gupta, A., Im, S., Krishnaswamy, R., Moseley, B., Pruhs, K.: Scheduling heterogeneous processors isn’t as easy as you think. In: ACM-SIAM Symposium on Discrete Algorithms (SODA 2012), pp. 1242–1253 (2012)
Leung, J., Li, L.: Scheduling with processing set restrictions: A survey. International Journal of Production Economics 116(2), 251–262 (2008)
Boyd, S., Vandenberghe, L.: Convex Optimization. Cambridge University Press (2004)
Jin, X., Zhang, F., Song, Y., Fan, L., Liu, Z.: Energy-efficient Scheduling with Time and Processors Eligibility Restrictions. CoRR-abs/1301.4131 (2013), http://arxiv.org/abs/1301.4131
Lin, Y., Li, W.: Parallel machine scheduling of machine-dependent jobs with unit-length. European Journal of Operational Research 156(1), 261–266 (2004)
Alon, N., Azar, Y., Woeginger, G., Yadid, T.: Approximation schemes for scheduling. In: ACM-SIAM Symposium on Discrete Algorithms (SODA 1997), pp. 493–500 (1997)
Azar, Y., Epstein, L., Richter, Y., Woeginger, G.: All-norm approximation algorithms. Journal of Algorithms 52(2), 120–133 (2004)
Nesterov, Y., Nemirovskii, A.: Interior-point polynomial algorithms in convex programming. SIAM Studies in Applied Mathematics. SIAM (1994)
Gandhi, R., Khuller, S., Parthasarathy, S., Srinivasan, A.: Dependent rounding in bipartite graphs. In: Proceedings of the IEEE Symposium on Foundation of Computer Science (FOCS 2002), pp. 323–332 (2002)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Jin, X., Zhang, F., Song, Y., Fan, L., Liu, Z. (2013). Energy-Efficient Scheduling with Time and Processors Eligibility Restrictions. In: Wolf, F., Mohr, B., an Mey, D. (eds) Euro-Par 2013 Parallel Processing. Euro-Par 2013. Lecture Notes in Computer Science, vol 8097. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-40047-6_10
Download citation
DOI: https://doi.org/10.1007/978-3-642-40047-6_10
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-40046-9
Online ISBN: 978-3-642-40047-6
eBook Packages: Computer ScienceComputer Science (R0)