Document Open Access Logo

The Preemptive Resource Allocation Problem

Authors Kanthi Sarpatwar , Baruch Schieber, Hadas Shachnai

PDF
Thumbnail PDF

File

LIPIcs.FSTTCS.2019.26.pdf
  • Filesize: 0.5 MB
  • 15 pages

Document Identifiers

Author Details

Kanthi Sarpatwar
  • IBM T. J. Watson Research Center, Yorktown Heights, NY, United States of America
Baruch Schieber
  • Computer Science Department, New Jersey Institute of Technology, Newark, NJ, United States of America
Hadas Shachnai
  • Computer Science Department, Technion, Haifa, Israel

Cite As Get BibTex

Kanthi Sarpatwar, Baruch Schieber, and Hadas Shachnai. The Preemptive Resource Allocation Problem. In 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 150, pp. 26:1-26:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.FSTTCS.2019.26

Abstract

We revisit a classical scheduling model to incorporate modern trends in data center networks and cloud services. Addressing some key challenges in the allocation of shared resources to user requests (jobs) in such settings, we consider the following variants of the classic resource allocation problem (RAP). The input to our problems is a set J of jobs and a set M of homogeneous hosts, each has an available amount of some resource. A job is associated with a release time, a due date, a weight and a given length, as well as its resource requirement. A feasible schedule is an allocation of the resource to a subset of the jobs, satisfying the job release times/due dates as well as the resource constraints. A crucial distinction between classic RAP and our problems is that we allow preemption and migration of jobs, motivated by virtualization techniques. 
We consider two natural objectives: throughput maximization (MaxT), which seeks a maximum weight subset of the jobs that can be feasibly scheduled on the hosts in M, and resource minimization (MinR), that is finding the minimum number of (homogeneous) hosts needed to feasibly schedule all jobs. Both problems are known to be NP-hard. We first present an Omega(1)-approximation algorithm for MaxT instances where time-windows form a laminar family of intervals. We then extend the algorithm to handle instances with arbitrary time-windows, assuming there is sufficient slack for each job to be completed. For MinR we study a more general setting with d resources and derive an O(log d)-approximation for any fixed d >= 1, under the assumption that time-windows are not too small. This assumption can be removed leading to a slightly worse ratio of O(log d log^* T), where T is the maximum due date of any job.

Subject Classification

ACM Subject Classification
  • Theory of computation → Design and analysis of algorithms
  • Theory of computation → Packing and covering problems
  • Theory of computation → Scheduling algorithms
Keywords
  • Machine Scheduling
  • Resource Allocation
  • Vector Packing
  • Approximation Algorithms

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Micah Adler, Phillip B Gibbons, and Yossi Matias. Scheduling space-sharing for internet advertising. Journal of Scheduling, 5(2):103-119, 2002. Google Scholar
  2. Alexander A. Ageev and Maxim Sviridenko. Pipage Rounding: A New Method of Constructing Algorithms with Proven Performance Guarantee. J. Comb. Optim., 8(3):307-328, 2004. Google Scholar
  3. Nikhil Bansal, Alberto Caprara, and Maxim Sviridenko. A New Approximation Method for Set Covering Problems, with Applications to Multidimensional Bin Packing. SIAM J. Comput., 39(4):1256-1278, 2009. Google Scholar
  4. Nikhil Bansal, Marek Eliáš, and Arindam Khan. Improved approximation for vector bin packing. In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1561-1579, 2016. Google Scholar
  5. Nikhil Bansal, Zachary Friggstad, Rohit Khandekar, and Mohammad R Salavatipour. A logarithmic approximation for unsplittable flow on line graphs. ACM Transactions on Algorithms, 10(1):1, 2014. Google Scholar
  6. Amotz Bar-Noy, Reuven Bar-Yehuda, Ari Freund, Joseph Naor, and Baruch Schieber. A unified approach to approximating resource allocation and scheduling. J. ACM, 48(5):1069-1090, 2001. Google Scholar
  7. Amotz Bar-Noy, Sudipto Guha, Joseph Naor, and Baruch Schieber. Approximating the Throughput of Multiple Machines in Real-Time Scheduling. SIAM J. Comput., 31(2):331-352, 2001. Google Scholar
  8. Gruia Călinescu, Amit Chakrabarti, Howard J. Karloff, and Yuval Rabani. An improved approximation algorithm for resource allocation. ACM Trans. Algorithms, 7(4):48:1-48:7, 2011. Google Scholar
  9. Venkatesan T Chakaravarthy, Anamitra R Choudhury, Shalmoli Gupta, Sambuddha Roy, and Yogish Sabharwal. Improved algorithms for resource allocation under varying capacity. In European Symposium on Algorithms, pages 222-234. Springer, 2014. Google Scholar
  10. Chandra Chekuri and Sanjeev Khanna. On multidimensional packing problems. SIAM journal on computing, 33(4):837-851, 2004. Google Scholar
  11. Bo Chen, Refael Hassin, and Michal Tzur. Allocation of bandwidth and storage. IIE Transactions, 34(5):501-507, 2002. Google Scholar
  12. Julia Chuzhoy and Paolo Codenotti. Resource minimization job scheduling. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, pages 70-83. Springer, 2009. Google Scholar
  13. Julia Chuzhoy, Sudipto Guha, Sanjeev Khanna, and Joseph Naor. Machine minimization for scheduling jobs with interval constraints. In Foundations of Computer Science, 2004. Proceedings. 45th Annual IEEE Symposium on, pages 81-90, 2004. Google Scholar
  14. Milind Dawande, Subodha Kumar, and Chelliah Sriskandarajah. Performance bounds of algorithms for scheduling advertisements on a web page. Journal of Scheduling, 6(4):373-394, 2003. Google Scholar
  15. Milind Dawande, Subodha Kumar, and Chelliah Sriskandarajah. Scheduling web advertisements: a note on the minspace problem. Journal of Scheduling, 8(1):97-106, 2005. Google Scholar
  16. L. Fleischer, M. X. Goemans, V. S. Mirrokni, and M. Sviridenko. Tight Approximation Algorithms for Maximum Separable Assignment Problems. Math. Oper. Res., 36(3):416-431, 2011. Google Scholar
  17. Kyle Fox and Madhukar Korupolu. Weighted flowtime on capacitated machines. In Proceedings of the twenty-fourth annual ACM-SIAM symposium on Discrete algorithms, pages 129-143. SIAM, 2013. Google Scholar
  18. Ari Freund and Joseph Naor. Approximating the advertisement placement problem. Journal of Scheduling, 7(5):365-374, 2004. Google Scholar
  19. Navendu Jain, Ishai Menache, Joseph Naor, and Jonathan Yaniv. Near-optimal scheduling mechanisms for deadline-sensitive jobs in large computing clusters. ACM Transactions on Parallel Computing, 2(1):3, 2015. Google Scholar
  20. Klaus Jansen and Lorant Porkolab. On preemptive resource constrained scheduling: polynomial-time approximation schemes. Integer Programming and Combinatorial Optimization, pages 329-349, 2002. Google Scholar
  21. Bala Kalyanasundaram and Kirk Pruhs. Eliminating Migration in Multi-processor Scheduling. J. Algorithms, 38(1):2-24, 2001. Google Scholar
  22. Arshia Kaul, Sugandha Aggarwal, Anshu Gupta, Niraj Dayama, Mohan Krishnamoorthy, and PC Jha. Optimal advertising on a two-dimensional web banner. International Journal of System Assurance Engineering and Management, pages 1-6, 2017. Google Scholar
  23. Subodha Kumar, Milind Dawande, and Vijay Mookerjee. Optimal scheduling and placement of internet banner advertisements. IEEE Transactions on Knowledge and Data Engineering, 19(11), 2007. Google Scholar
  24. Eugene L Lawler. A dynamic programming algorithm for preemptive scheduling of a single machine to minimize the number of late jobs. Annals of Operations Research, 26(1):125-133, 1990. Google Scholar
  25. Shinjini Pandey, Goutam Dutta, and Harit Joshi. Survey on Revenue Management in Media and Broadcasting. Interfaces, 47(3):195-213, 2017. Google Scholar
  26. Cynthia A. Phillips, R. N. Uma, and Joel Wein. Off-line admission control for general scheduling problems. In Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, pages 879-888, 2000. Google Scholar
  27. Kanthi K. Sarpatwar, Baruch Schieber, and Hadas Shachnai. The Preemptive Resource Allocation Problem. CoRR, abs/1811.07413, 2018. URL: http://arxiv.org/abs/1811.07413.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact