×

Continuous speed scaling with variability: a simple and direct approach. (English) Zbl 1370.68036

Summary: We consider an extension of the dynamic speed scaling scheduling model introduced by F. Yao et al. [in: Proccedings of the 36th annual IEEE symposium on foundations of computer science, FOCS’95. Los Alamitos, CA: IEEE Computer Society Press. 374–382 (1995; Zbl 0938.68533)]: A set of jobs, each with a release time, deadline, and workload, has to be scheduled on a single, speed-scalable processor. Both the maximum allowed speed of the processor and the energy costs may vary continuously over time. The objective is to find a feasible schedule that minimizes the total energy costs.
Theoretical algorithm design for speed scaling problems often tends to discretize problems, as our tools in the discrete realm are often better developed or understood. Using the above speed scaling variant with variable, continuous maximal processor speeds and energy prices as an example, we demonstrate that a more direct approach via tools from variational calculus can not only lead to a very concise and elegant formulation and analysis, but also avoids the “explosion of variables/constraints” that often comes with discretizing [A. Antoniadis et al., LIPICS – Leibniz Int. Proc. Inform. 25, 63–74 (2014; Zbl 1359.68032)]. Using well-known tools from calculus of variations, we derive combinatorial optimality characteristics for our continuous problem and provide a quite concise and simple correctness proof.

MSC:

68M20 Performance evaluation, queueing, and scheduling in the context of computer systems
49N90 Applications of optimal control and differential games
90B35 Deterministic scheduling theory in operations research
90C25 Convex programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Yao, F. F.; Demers, A. J.; Shenker, S., A scheduling model for reduced CPU energy, (Proc. FOCS (1995)), 374-382 · Zbl 0938.68533
[2] Antoniadis, A.; Barcelo, N.; Consuegra, M. E.; Kling, P.; Nugent, M.; Pruhs, K.; Scquizzato, M., Efficient computation of optimal energy and fractional weighted flow trade-off schedules, (Proc. STACS (2014)), 63-74 · Zbl 1359.68032
[3] Barroso, L. A.; Hölzle, U., The case for energy-proportional computing, Computer, 40, 12, 33-37 (2007)
[4] Albers, S., Energy-efficient algorithms, Commun. ACM, 53, 5, 86-96 (2010)
[5] Albers, S., Algorithms for dynamic speed scaling, (Proc. STACS (2011)), 1-11 · Zbl 1230.68097
[6] Brooks, D. M.; Bose, P.; Schuster, S. E.; Jacobson, H.; Kudva, P. N.; Buyuktosunoglu, A.; Wellman, J.-D.; Zyuban, V.; Gupta, M.; Cook, P. W., Power-aware microarchitecture: design and modeling challenges for next-generation microprocessors, IEEE MICRO, 20, 6, 26-44 (2000)
[7] ITWatchDogs, Are heat and humidity hurting your equipment?, Processor, 36, 20, 1 (2014)
[8] Bansal, N.; Kimbrel, T.; Pruhs, K., Speed scaling to manage energy and temperature, J. ACM, 54, 1, 3:1-3:39 (2007) · Zbl 1326.68043
[9] Thang, N. K., Lagrangian duality in online scheduling with resource augmentation and speed scaling, (Proc. ESA (2013)), 755-766 · Zbl 1395.90150
[10] Barcelo, N.; Cole, D.; Letsios, D.; Nugent, M.; Pruhs, K., Optimal energy trade-off schedules, Sustain. Comput., Inform. Syst., 3, 207-217 (2013)
[11] Chan, H.; Chan, J. W.; Lam, T. W.; Lee, L.; Mak, K.; Wong, P. W.H., Optimizing throughput and energy in online deadline scheduling, ACM Trans. Algorithms, 6, 1, Article 10 pp. (2009) · Zbl 1300.90013
[12] Li, M., Approximation algorithms for variable voltage processors: min energy, max throughput and online heuristics, Theoret. Comput. Sci., 412, 32, 4074-4080 (2011) · Zbl 1217.68247
[13] Fang, K.; Uhan, N. A.; Zhao, F.; Sutherland, J. W., Scheduling on a single machine under time-of-use electricity tariffs, Ann. Oper. Res., 1-29 (2015)
[14] Koutsopoulos, I.; Tassiulas, L., Control and optimization meet the smart power grid: scheduling of power demands for optimal energy management, (Proc. e-Energy (2011)), 41-50
[15] Bansal, N.; Chan, H.-L.; Pruhs, K., Speed scaling with a solar cell, Theoret. Comput. Sci., 410, 45, 4580-4587 (2009) · Zbl 1187.68105
[16] Irani, S.; Pruhs, K., Algorithmic problems in power management, SIGACT News, 36, 2, 63-76 (2005)
[17] Albers, S.; Fujiwara, H., Energy-efficient algorithms for flow time minimization, ACM Trans. Algorithms, 3, 4, Article 49 pp. (2007) · Zbl 1445.68036
[18] Bansal, N.; Chan, H.-L.; Pruhs, K., Speed scaling with an arbitrary power function, ACM Trans. Algorithms, 9, 2, 18 (2013) · Zbl 1301.90026
[20] Jain, K.; Vazirani, V. V., Approximation algorithms for metric facility location and k-median problems using the primal-dual schema and Lagrangian relaxation, J. ACM, 48, 2, 274-296 (2001) · Zbl 1138.90417
[21] Boyd, S. P.; Vandenberghe, L., Convex Optimization (2004), Cambridge University Press · Zbl 1058.90049
[22] Smith, D. R., Variational Methods in Optimization (1998), Dover Publications · Zbl 0918.49001
[23] Luenberger, D. G., Optimization by Vector Space Methods (1997), John Wiley & Sons, Inc. · Zbl 0176.12701
[24] Li, M.; Yao, A. C.; Yao, F. F., Discrete and continuous min-energy schedules for variable voltage processors, Proc. Natl. Acad. Sci. USA, 103, 11, 3983-3987 (2006)
[25] Li, M.; Yao, F. F.; Yuan, H., An \(O(n^2)\) algorithm for computing optimal continuous voltage schedules, CoRR · Zbl 1485.68113
[26] Kosmol, P.; Müller-Wichards, D., Optimization in Function Spaces: With Stability Considerations in Orlicz Spaces (2011), De Gruyter · Zbl 1226.90006
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.