Models and algorithms for energy-efficient scheduling with immediate start of jobs. (English) Zbl 1420.90024
Summary: We study a scheduling model with speed scaling for machines and the immediate start requirement for jobs. Speed scaling improves the system performance, but incurs the energy cost. The immediate start condition implies that each job should be started exactly at its release time. Such a condition is typical for modern Cloud computing systems with abundant resources. We consider two cost functions, one that represents the quality of service and the other that corresponds to the cost of running. We demonstrate that the basic scheduling model to minimize the aggregated cost function with \(n\) jobs is solvable in \(O(n\log n)\) time in the single-machine case and in \(O(n^{2}m)\) time in the case of \(m\) parallel machines. We also address additional features, e.g., the cost of job rejection or the cost of initiating a machine. In the case of a single machine, we present algorithms for minimizing one of the cost functions subject to an upper bound on the value of the other, as well as for finding a Pareto-optimal solution.
MSC:
| 90B35 | Deterministic scheduling theory in operations research |
| 68M20 | Performance evaluation, queueing, and scheduling in the context of computer systems |
References:
| [1] | Aceto, G., Botta, A., de Donato, W., & Pescapè, A. (2013). Cloud monitoring: A survey. Computer Networks, 57, 2093-2115. · doi:10.1016/j.comnet.2013.04.001 |
| [2] | Ahuja, R. K., Magnanti, T. L., & Orlin, J. B. (1993). Network flows: Theory, algorithms and applications. Englewood Cliffs: Prentice Hall. · Zbl 1201.90001 |
| [3] | Albers, S. (2009). Algorithms for energy saving. Lecture Notes in Computer Science, 5760, 173-186. · doi:10.1007/978-3-642-03456-5_12 |
| [4] | Albers, S. (2010a). Energy-efficient algorithms. Communications of the ACM, 53, 86-96. · Zbl 1285.68005 · doi:10.1145/1735223.1735245 |
| [5] | Albers, S. (2010b). Algorithms for energy management. Lecture Notes in Computer Science, 6072, 1-11. · Zbl 1285.68005 |
| [6] | Albers, S., & Fujiwara, H. (2007). Energy-efficient algorithms for flow time minimization. ACM Transactions on Algorithms, 3, 49:1-49:17. · Zbl 1445.68036 · doi:10.1145/1290672.1290686 |
| [7] | Albers, S., Antoniadis, A., & Geiner, G. (2011). On multiprocessor speed scaling with migration. In Proceedings of the symposium on parallelism in algorithms and architectures (SPAA) (pp. 279-288). |
| [8] | Albers, S., Müller, F., & Schmelzer, S. (2014). Speed scaling on parallel processors. Algorithmica, 68, 404-425. · Zbl 1317.68020 · doi:10.1007/s00453-012-9678-7 |
| [9] | Angel, E., Bampis, E., Kacem, F., & Letsios, D. (2012). Speed scaling on parallel processors with migration. Lecture Notes in Computer Science, 7484, 128-140. · Zbl 1312.68029 · doi:10.1007/978-3-642-32820-6_15 |
| [10] | Angel, E., Bampis, E., Chau, V., & Letsios, D. (2013). Throughput maximization for speed-scaling with agreeable deadlines. Lecture Notes in Computer Science, 7876, 10-19. · Zbl 1382.68040 · doi:10.1007/978-3-642-38236-9_2 |
| [11] | Angel, E., Bampis, E., Chau, V., & Thang, N. K. (2016). Throughput maximization in multiprocessor speed-scaling. Theoretical Computer Science, 630, 1-12. · Zbl 1339.68029 · doi:10.1016/j.tcs.2016.03.020 |
| [12] | Antoniadis, A., Barcelo, N., Consuegra, M., Kling, P., Nugen, M., Pruhs, K., & Scquizzatok, M. (2014). Efficient computation of optimal energy and fractional weighted flow trade-off schedules. In Proceedings of the 31st international symposium on theoretical aspects of computer science (STACS ’14) (pp. 63-74). · Zbl 1359.68032 |
| [13] | Armbrust, M., Fox, A., Griffith, R., Joseph, A. D., Katz, R. H., Konwinski, A., et al. (2009). Above the clouds: A Berkeley view of cloud computing (p. 28). UCB/EECS, vol: Technical Report, EECS Department, University of California, Berkeley. |
| [14] | Armbrust, M., Fox, A., Griffith, R., Joseph, A. D., Katz, R. H., Konwinski, A., et al. (2010). A view of cloud computing. Communications of the ACM, 53, 55-58. · doi:10.1145/1721654.1721672 |
| [15] | Bampis, E. (2016). Algorithmic issues in energy-efficient computation. Lecture Notes in Computer Science, 9869, 3-14. · doi:10.1007/978-3-319-44914-2_1 |
| [16] | Bampis, E., Letsios, D., & Lucarelli, G. (2015). Green scheduling, flows and matchings. Theoretical Computer Science, 579, 126-136. · Zbl 1312.68030 · doi:10.1016/j.tcs.2015.02.020 |
| [17] | Bansal, N., Pruhs, K., & Stein, C. (2010). Speed scaling for weighted flow time. SIAM Journal on Computing, 39, 1294-1308. · Zbl 1213.68196 · doi:10.1137/08072125X |
| [18] | Barcelo, N. (2015). The complexity of speed-scaling. Ph.D. thesis, University of Pittsburgh. · Zbl 1465.68030 |
| [19] | Barcelo, N., Cole, D., Letsios, D., Nugent, M., & Pruhs, K. (2013). Optimal energy trade-off schedules. Sustainable Computing: Informatics and Systems, 3, 207-217. |
| [20] | Bekki, Ö. B., & Azizoğlu, M. (2008). Operational fixed interval scheduling problem on uniform parallel machines. International Journal of Production Economics, 112, 756-768. · doi:10.1016/j.ijpe.2007.06.004 |
| [21] | Bouzina, K. I., & Emmons, H. (1996). Interval scheduling on identical machines. Journal of Global Optimization, 9, 379-393. · Zbl 0866.90069 · doi:10.1007/BF00121680 |
| [22] | Brooks, D. M., Bose, P., Schuster, S. E., Jacobson, H., Kudva, P. N., Buyuktosunoglu, A., et al. (2000). Power-aware microarchitecture: Design and modeling challenges for next-generation microprocessors. IEEE Micro, 20, 26-44. · doi:10.1109/40.888701 |
| [23] | Bunde, D. P. (2009). Power-aware scheduling for makespan and flow. Journal of Scheduling, 12, 489-500. · Zbl 1176.90196 · doi:10.1007/s10951-009-0123-y |
| [24] | Carlisle, M. C., & Lloyd, E. L. (1995). On the \[k\] k-coloring of intervals. Discrete Applied Mathematics, 59, 225-235. · Zbl 0826.68092 · doi:10.1016/0166-218X(95)80003-M |
| [25] | Chan, S.-H., Lam, T.-W., & Lee, L.-K. (2013). Scheduling for weighted flow time and energy with rejection penalty. Theoretical Computer Science, 470, 93-104. · Zbl 1266.68068 · doi:10.1016/j.tcs.2012.11.021 |
| [26] | Do Lago, D.G., Madeira, E.R.M., & Bittencourt, L.F. (2011). Power-aware virtual machine scheduling on clouds using active cooling control and DVFS. In Proceedings of the 9th international workshop on middleware for grids, clouds and e-science (MGC ’11) (pp. 1-6). |
| [27] | Garg, S. K., Versteeg, S., & Buyya, R. (2013). A framework for ranking of cloud computing services. Future Generation Computer Systems, 29, 1012-1023. · doi:10.1016/j.future.2012.06.006 |
| [28] | Gerards, M. E. T., Hurink, J. L., & Hölzenspies, P. K. F. (2016). A survey of offline algorithms for energy minimization under deadline constraints. Journal of Scheduling, 19, 3-19. · Zbl 1341.90046 · doi:10.1007/s10951-015-0463-8 |
| [29] | Gupta, U. I., Lee, D. T., & Leung, J. Y.-T. (1979). An optimal solution for the channel-assignment problem. IEEE Transactions on Computers, 28, 807-810. · Zbl 0422.68031 · doi:10.1109/TC.1979.1675260 |
| [30] | Hiraishi, K., Levner, E., & Vlach, M. (2002). Scheduling of parallel identical machines to maximize the weighted number of just-in-time jobs. Computers and Operations Research, 29, 841-848. · Zbl 0999.68029 · doi:10.1016/S0305-0548(00)00086-1 |
| [31] | Iqbal, W., Dailey, M., & Carrera, D. (2009). SLA-driven adaptive resource management for web applications on a heterogeneous compute cloud. Lecture Notes in Computer Science, 5931, 243-253. · doi:10.1007/978-3-642-10665-1_22 |
| [32] | Jennings, B., & Stadler, R. (2015). Resource management in clouds: Survey and research challenges. Journal of Network and Systems Management, 23, 567-619. · doi:10.1007/s10922-014-9307-7 |
| [33] | Jing, S.-Y., Ali, S., She, K., & Zhong, Y. (2013). State-of-the-art research study for green cloud computing. Journal of Supercomputing, 65, 445-468. · doi:10.1007/s11227-011-0722-1 |
| [34] | Kolen, A. W. J., Lenstra, J. K., Papadimitriou, C. H., & Spieksma, F. C. R. (2007). Interval scheduling: A survey. Naval Research Logistics, 54, 530-543. · Zbl 1143.90337 · doi:10.1002/nav.20231 |
| [35] | Kovalyov, M. Y., Ng, C. T., & Cheng, T. C. E. (2007). Fixed interval scheduling: Models, applications, computational complexity and algorithms. European Journal of Operational Research, 178, 331-342. · Zbl 1107.90019 · doi:10.1016/j.ejor.2006.01.049 |
| [36] | Kushida, K. E., Murray, J., & Zysman, J. (2015). Cloud computing: From scarcity to abundance. Journal of Industry, Competition and Trade, 15, 5-19. · doi:10.1007/s10842-014-0188-y |
| [37] | Lam, T.-W., Lee, L.-K., To, I. K. K., & Wong, P. W. H. (2008). Speed scaling functions for flow time scheduling based on active job count. Lecture Notes in Computer Science, 5193, 647-659. · Zbl 1158.68347 · doi:10.1007/978-3-540-87744-8_54 |
| [38] | Lam, T. W., Lee, L. K., To, I. K. K., & Wong, P. W. H. (2012). Improved multi-processor scheduling for flow time and energy. Journal of Scheduling, 15, 105-116. · Zbl 1280.68074 · doi:10.1007/s10951-009-0145-5 |
| [39] | Lann, A., & Mosheiov, G. (2003). A note on the maximum number of on-time jobs on parallel identical machines. Computers and Operations Research, 30, 1745-1749. · Zbl 1039.90016 · doi:10.1016/S0305-0548(02)00084-9 |
| [40] | Leyvand, Y., Shabtay, D., Steiner, G., & Yedidsion, L. (2010). Just-in-time scheduling with controllable processing times on parallel machines. Journal of Combinatorial Optimization, 19, 347-368. · Zbl 1188.90100 · doi:10.1007/s10878-009-9270-5 |
| [41] | Li, M., Yao, A. C., & Yao, F. F. (2006). Discrete and continuous min-energy schedules for variable voltage processors. Proceedings of the National Academy of Sciences of the United States of America, 103, 3983-3987. · doi:10.1073/pnas.0510886103 |
| [42] | Li, M., Yao, F. F., & Yuan, H. (2014). An \[O(n^2)O\](n2) algorithm for computing optimal continuous voltage schedules. arXiv:1408.5995v1. · Zbl 1485.68113 |
| [43] | Moreno, I. S., Garraghan, P., Townend, P., & Xu, J. (2014). Analysis, modeling and simulation of workload patterns in a large-scale utility cloud. IEEE Transactions on Cloud Computing, 2, 208-221. · doi:10.1109/TCC.2014.2314661 |
| [44] | Nakajima, K., Hakimi, S. L., & Lenstra, J. K. (1982). Complexity results for scheduling tasks in fixed intervals on two types of machines. SIAM Journal on Computing, 11, 512-520. · Zbl 0486.68020 · doi:10.1137/0211040 |
| [45] | Patriksson, M. (2008). A survey on the continuous nonlinear resource allocation. European Journal of Operational Research, 185, 1-46. · Zbl 1146.90493 · doi:10.1016/j.ejor.2006.12.006 |
| [46] | Pruhs, K., Uthaisombut, P., & Woeginger, G. (2008). Getting the best response for your erg. ACM Transactions on Algorithms, 4, 38:1-38:17. · Zbl 1445.68041 · doi:10.1145/1367064.1367078 |
| [47] | Rackspace: Our 100 |
| [48] | Shabtay, D., Bensoussan, Y., & Kaspi, M. (2012). A bicriteria approach to maximize the weighted number of just-in-time jobs and to minimize the total resource consumption cost in a two-machine flow-shop scheduling system. International Journal of Production Economics, 136, 67-74. · doi:10.1016/j.ijpe.2011.09.011 |
| [49] | Shabtay, D., & Steiner, G. (2007). A survey of scheduling with controllable processing times. Discrete Applied Mathematics, 155, 1643-1666. · Zbl 1119.90022 · doi:10.1016/j.dam.2007.02.003 |
| [50] | Shioura, A., Shakhlevich, N.V., & Strusevich, V.A. (2015). Energy saving computational models with speed scaling via submodular optimization. In Proceedings of the 3rd international conference on green computing, technology and innovation (ICGCTI2015) |
| [51] | Tian, W., & Zhao, Y. (2015). Optimized cloud resource management and scheduling: Theory and practices. Los Altos: Morgan Kaufmann. |
| [52] | Von Laszewski, G., Wang, L., Younge, A. J., & He, X. (2009). Power-aware scheduling of virtual machines in DVFS-enabled clusters. In IEEE international conference on cluster computing and workshops (CLUSTER ’09) (pp. 1-10). |
| [53] | Wu, C.-M., Chang, R.-S., & Chan, H.-Y. (2014). A green energy-efficient scheduling algorithm using the DVFS technique for cloud datacenters. Future Generation Computer Systems, 37, 141-147. · doi:10.1016/j.future.2013.06.009 |
| [54] | Yao, F. F., Demers, A. J., & Shenker, S. (1995). A scheduling model for reduced CPU energy. In Proceedings of the 36th IEEE symposium on foundations of computer science (FOCS ’95) (pp. 374-382). · Zbl 0938.68533 |
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.
