Resource cost aware scheduling. (English) Zbl 1388.90051
Summary: We are interested in the scheduling problem where there are several different resources that determine the speed at which a job runs and we pay depending on the amount of each resource that we use. This work is an extension of the resource dependent job processing time problem and the energy aware scheduling problems. We develop a new constant factor approximation algorithm for resource cost aware scheduling problems: the objective is to minimize the sum of the total cost of resources and the total weighted completion time in the one machine non-preemptive setting, allowing for arbitrary precedence constraints and release dates. Our algorithm handles general job-dependent resource cost functions. We also analyze the practical performance of our algorithms, showing that it is significantly superior to the theoretical bounds and in fact, it is very close to optimal. The analysis is done using simulations and real instances, which are left publicly available for future benchmarks. We also present additional heuristic improvements and study their performance in other settings.
MSC:
| 90B35 | Deterministic scheduling theory in operations research |
References:
| [1] | Albers, S., Algorithms for energy saving, (Albers, S.; Alt, H.; Näher, S., Efficient algorithms. Efficient algorithms, Lecture notes in computer science, vol. 5760 (2009), Springer: Springer Berlin, Heidelberg), 173-186 |
| [2] | Albers, S., Energy-efficient algorithms, Communications of the ACM, 53, 5, 86 (2010) |
| [3] | Albers, S.; Fujiwara, H., Energy-efficient algorithms for flow time minimization, ACM Transactions on Algorithms, 3, 4, 49-es (2007) · Zbl 1445.68036 |
| [4] | Andrew, L. L.; Lin, M.; Wierman, A., Optimality, fairness, and robustness in speed scaling designs, SIGMETRICS Performance Evaluation Review, 38, 1, 37-48 (2010) |
| [5] | Andrew, L. L.; Wierman, A.; Tang, A., Optimal speed scaling under arbitrary power functions, ACM SIGMETRICS Performance Evaluation Review, 37, 2, 39 (2009) |
| [6] | Atkins, L.; Aupy, G.; Cole, D.; Pruhs, K. R., Speed scaling to manage temperature, Lecture notes in computer science, 6595, 9-20 (2011) · Zbl 1325.68036 |
| [7] | Bansal, N.; Bunde, D.; Chan, H. L.; Pruhs, K. R., Average rate speed scaling, Proceedings of the eight Latin American conference on theoretical informatics, 240-251 (2008), Springer-Verlag · Zbl 1136.68348 |
| [8] | Bansal, N.; Chan, H. L.; Lam, T.; Lee, L., Scheduling for speed bounded processors, Proceedings of the International Colloquium on Automata, Languages, and Programming, 409-420 (2010) · Zbl 1153.68334 |
| [9] | Bansal, N.; Chan, H. L.; Pruhs, K. R., Speed scaling with an arbitrary power function, Proceedings of the nineteenth annual ACM-SIAM symposium on discrete algorithms, 693-701 (2009), Society for Industrial and Applied Mathematics · Zbl 1422.68017 |
| [10] | Bansal, N.; Kimbrel, T.; Pruhs, K. R., Dynamic speed scaling to manage energy and temperature, 45th Annual IEEE Symposium on Foundations of Computer Science, 520-529 (2004) |
| [11] | Bansal, N.; Kimbrel, T.; Pruhs, K. R., Speed scaling to manage energy and temperature, Journal of the ACM (JACM), 54, 1, 3 (2007) · Zbl 1326.68043 |
| [12] | Bansal, N.; Pruhs, K. R., Speed scaling to manage temperature, Lecture notes in computer science, 3404, 460-471 (2005) · Zbl 1118.68769 |
| [13] | Bansal, N.; Pruhs, K. R.; Stein, C., Speed scaling for weighted flow time, Proceedings of the eighteenth annual ACM-SIAM symposium on discrete algorithms, 813 (2007), Society for Industrial and Applied Mathematics · Zbl 1302.68036 |
| [14] | Carrasco, R. (2018). Server scheduling benchmark instances v.1. Mendeley Data, (10.17632/ph95d337dj.1).; Carrasco, R. (2018). Server scheduling benchmark instances v.1. Mendeley Data, (10.17632/ph95d337dj.1). |
| [15] | Carrasco, R. A.; Iyengar, G. N.; Stein, C., Energy aware scheduling for weighted completion time and weighted tardiness, Technical Report (2011), Columbia University |
| [16] | Chang, H.; Kodialam, M.; Kompella, R. R.; Lakshman, T. V.; Lee, M.; Mukherjee, S., Scheduling in MapReduce-like systems for fast completion time, Proceedings of the IEEE INFOCOM, 3074-3082 (2011) |
| [17] | Chekuri, C.; Khanna, S., Approximation algorithms for minimizing average weighted completion time, Handbook of scheduling: Algorithms, models, and performance analysis, 1-30 (2004) |
| [18] | Chekuri, C.; Motwani, R.; Natarajan, B.; Stein, C., Approximation techniques for average completion time scheduling, SIAM Journal on Computing, 31, 1, 146 (2001) · Zbl 0992.68066 |
| [19] | Chen, J.; Kuo, T.; Lu, H., Power-saving scheduling for weakly dynamic voltage scaling devices, Algorithms and Data Structures, 338-349 (2005) · Zbl 1161.90390 |
| [20] | Cheng, T.; Janiak, A.; Kovalyov, M. Y., Single machine batch scheduling with resource dependent setup and processing times, European Journal of Operational Research, 135, 1, 177-183 (2001) · Zbl 1077.90525 |
| [21] | Cheng, T. C.E.; Janiak, A.; Kovalyov, M. Y., Bicriterion single machine scheduling with resource dependent processing times, SIAM Journal on Optimization, 8, 2, 617-630 (1998) · Zbl 0907.68113 |
| [22] | Comscore (2016). Comscore February 2016 ranking. http://goo.gl/yC55zw; Comscore (2016). Comscore February 2016 ranking. http://goo.gl/yC55zw |
| [23] | Daniels, R. L., A multi-objective approach to resource allocation in single machine scheduling, European Journal of Operational Research, 48, 2, 226-241 (1990) · Zbl 0825.90535 |
| [24] | Daniels, R. L.; Sarin, R. K., Single machine scheduling with controllable processing times and number of jobs tardy, Operations Research, 37, 6, 981-984 (1989) · Zbl 0686.90023 |
| [25] | DOE (2011). Department of Energy website. http://goo.gl/DWojgg; DOE (2011). Department of Energy website. http://goo.gl/DWojgg |
| [26] | Duffuaa, S.; Duffuaa, S. O.; Raouf, A.; Campbell, J. D., Planning and control of maintenance systems: Modeling and analysis (1999), John Wiley & Sons Inc |
| [27] | Foundation, P. S. (2016). Python language reference, version 3.5. http://www.python.org; Foundation, P. S. (2016). Python language reference, version 3.5. http://www.python.org |
| [28] | Goemans, M. X., Improved approximation algorthims for scheduling with release dates, Proceedings of the ACM-SIAM Symposium on Discrete algorithms, 591-598 (1997) · Zbl 1321.68502 |
| [29] | Goemans, M. X.; Queyranne, M.; Schulz, A. S.; Skutella, M.; Wang, Y., Single machine scheduling with release dates, SIAM Journal on Discrete Mathematics, 15, 2, 165 (2002) · Zbl 1009.90096 |
| [30] | Google (2009). Google datacentre webpage. http://goo.gl/44nDs; Google (2009). Google datacentre webpage. http://goo.gl/44nDs |
| [31] | Graham, R.; Lawler, E. L.; Lenstra, J. K.; Rinnooy Kan, A. H.G., Optimization and approximation in deterministic sequencing and scheduling: A survey, Discrete optimization, 5, 287-326 (1979) · Zbl 0411.90044 |
| [32] | Gurobi Optimization, I. (2016). Gurobi optimizer reference manual. http://www.gurobi.com; Gurobi Optimization, I. (2016). Gurobi optimizer reference manual. http://www.gurobi.com |
| [33] | Hall, L. A.; Schulz, A. S.; Shmoys, D. B.; Wein, J., Scheduling to minimize average completion time: off-line and on-line approximation algorithms, Mathematics of Operations Research, 22, 3, 513-544 (1997) · Zbl 0883.90064 |
| [34] | Hall, L. A.; Shmoys, D. B.; Wein, J., Scheduling to minimize average completion time: off-line and on-line algorithms, Proceedings of the seventh annual ACM-SIAM symposium on discrete algorithms, SODA ’96, 142-151 (1996), Society for Industrial and Applied Mathematics: Society for Industrial and Applied Mathematics Philadelphia, PA, USA · Zbl 0845.90071 |
| [35] | Herroelen, W.; Leus, R., Project scheduling under uncertainty: Survey and research potentials, European journal of operational research, 165, 289-306 (2005) · Zbl 1066.90050 |
| [36] | Irani, S.; Shukla, S.; Gupta, R., Algorithms for power savings, ACM Transactions on Algorithms, 3, 4, 41 (2007) · Zbl 1422.68018 |
| [37] | Janiak, A., One-machine scheduling with allocation of continuously-divisible resource and with no precedence constraints, Kybernetika, 23, 4 (1987) · Zbl 0635.90048 |
| [38] | Janiak, A., Single machine scheduling problem with a common deadline and resource dependent release dates, European Journal of Operational Research, 53, 317-325 (1991) · Zbl 0743.90066 |
| [39] | Janiak, A.; Kovalyov, M. Y., Single machine scheduling subject to deadlines and resource dependent processing times, European Journal of Operational Research, 2217, 96 (1996) · Zbl 0947.90584 |
| [40] | Jawor, W., Three dozen papers on online algorithms, ACM SIGACT News, 36, 1, 71-85 (2005) |
| [41] | Kaspi, M.; Shabtay, D., A bicriterion approach to time/cost trade-offs in scheduling with convex resource-dependent job processing times and release dates, Computers & Operations Research, 33, 10, 3015-3033 (2006) · Zbl 1086.90024 |
| [42] | Kwon, W.-C.; Kim, T., Optimal voltage allocation techniques for dynamically variable voltage processors, ACM Transactions on Embedded Computing, 4, 1, 211-230 (2005) |
| [43] | Lagos, C.d. P.; Stevens, A. R.H.; Bower, R. G.; Davis, T. A.; Contreras, S.; Padilla, N. D., Quantifying the impact of mergers on the angular momentum of simulated galaxies, Monthly Notices of the Royal Astronomical Society, 473, 4, 4956-4974 (2018) |
| [44] | Monma, C. L.; Schrijver, A.; Todd, M. J.; Wei, V. K., Convex resource allocation problems on directed acyclic graphs: duality, complexity, special cases, and extensions, Mathematics of Operations, 15, 4, 736-748 (1990) · Zbl 0717.90080 |
| [45] | Muñoz Arancibia, A. M.; Navarrete, F. P.; Padilla, N. D.; Cora, S. A.; Gawiser, E.; Kurczynski, P.; Ruiz, A. N., Properties of submillimetre galaxies in a semi-analytic model using the Count Matching’ approach: application to the ECDF-S, Monthly Notices of the Royal Astronomical Society, 446, 3, 2291-2311 (2015) |
| [46] | Muñoz, G.; Espinoza, D.; Goycoolea, M.; Moreno, E.; Queyranne, M.; Letelier, O. R., A study of the Bienstock-Zuckerberg algorithm: Applications in mining and resource constrained project scheduling (2017), Springer US: Springer US US |
| [47] | Phillips, C. A.; Stein, C.; Wein, J., Minimizing average completion time in the presence of release dates, Mathematical Programming, 82, 1-2, 199-223 (1998) · Zbl 0920.90074 |
| [48] | Pinedo, M., Scheduling: theory, algorithms, and systems (2008), Springer: Springer New York, NY · Zbl 1155.90008 |
| [49] | Pruhs, K. R.; Stee, R.; Uthaisombut, P., Speed scaling of tasks with precedence constraints, Theory of Computing Systems, 43, 1, 67-80 (2007) · Zbl 1140.68010 |
| [50] | Pruhs, K. R.; Uthaisombut, P.; Woeginger, G. J., Getting the best response for your erg, ACM Transactions on Algorithms, 4, 3, 1-17 (2008) · Zbl 1445.68041 |
| [51] | Shabtay, D.; Kaspi, M., Minimizing the total weighted flow time in a single machine with controllable processing times, Computers & Operations Research, 31, 13, 2279-2289 (2004) · Zbl 1073.90017 |
| [52] | Shabtay, D.; Steiner, G., A survey of scheduling with controllable processing times, Discrete Applied Mathematics, 155, 13, 1643-1666 (2007) · Zbl 1119.90022 |
| [53] | Shabtay, D.; Steiner, G., A bicriteria approach to minimize the total weighted number of tardy jobs with convex controllable processing times and assignable due dates, Journal of Scheduling, 14, 5, 455-469 (2011) · Zbl 1280.90071 |
| [54] | Skutella, M., List scheduling in order of \(α\)-points on a single machine, (Bampis, E.; Jansen, K.; Kenyon, C., Efficient approximation and online algorithms. Efficient approximation and online algorithms, Lecture notes in computer science, vol. 3484 (2006), Springer: Springer Berlin, Heidelberg), 250-291 · Zbl 1132.90333 |
| [55] | Stevens, A. R.H.; del P. Lagos, C.; Contreras, S.; Croton, D. J.; Padilla, N. D.; Schaller, M., How to get cool in the heat: comparing analytic models of hot, cold, and cooling gas in haloes and galaxies with EAGLE, Monthly Notices of the Royal Astronomical Society, 467, 2, stx243 (2017) |
| [56] | Van Wassenhove, L. N.; Baker, K. R., A bicriterion approach to time/cost trade-offs in sequencing, European Journal of Operational Research, 11, 1, 48-54 (1982) · Zbl 0482.90043 |
| [57] | Vickson, R. G., Choosing the job sequence and processing times to minimize total processing plus flow cost on a single machine, Operations Research, 28, 5 (1980) · Zbl 0449.90054 |
| [58] | Wang, J.-B.; Wang, M.-Z., Single-machine scheduling to minimize total convex resource consumption with a constraint on total weighted flow time, Computers & Operations Research, 39, 3, 492-497 (2011) · Zbl 1251.90197 |
| [59] | Williams, T. J., Analysis and design of hierarchical control systems: with special reference to steel plant operations, vol. 3 (1985), Elsevier |
| [60] | Xu, K.; Feng, Z.; Ke, L., Single machine scheduling with total tardiness criterion and convex controllable processing times, Annals of Operations Research, 186, 1, 383-391 (2011) · Zbl 1225.90058 |
| [61] | Yao, F.; Demers, A.; Shenker, S., A scheduling model for reduced CPU energy, Proceedings of ieee thirty-sixth annual foundations of computer science, 374-382 (1995), IEEE Computer Society Press · Zbl 0938.68533 |
| [62] | Yun, H.; Kim, J., On energy-optimal voltage scheduling for fixed-priority hard real-time systems, ACM Transactions on Embedded Computing Systems (TECS), 2, 3, 393-430 (2003) |
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.
