The preemptive resource allocation problem

Kanthi Sarpatwar (), Baruch Schieber () and Hadas Shachnai ()
Additional contact information
Kanthi Sarpatwar: IBM T. J. Watson Research Center
Baruch Schieber: New Jersey Institute of Technology
Hadas Shachnai: Technion

Journal of Scheduling, 2024, vol. 27, issue 1, No 6, 103-118

Abstract: 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. Assuming that time is slotted, 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)$$ Ω ( 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)$$ O ( log d ) -approximation for any fixed $$d \ge 1$$ 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)$$ O ( log d log ∗ T ) , where T is the maximum due date of any job.

Keywords: Machine scheduling; Resource allocation; Vector packing; Approximation algorithms (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10951-023-00786-6 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jsched:v:27:y:2024:i:1:d:10.1007_s10951-023-00786-6

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10951

DOI: 10.1007/s10951-023-00786-6

Access Statistics for this article

Journal of Scheduling is currently edited by Edmund Burke and Michael Pinedo

More articles in Journal of Scheduling from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().