Brief announcement: Approximation algorithms for preemptive resource allocation

Abstract

Cloud services require the allocation of scarce resources to multiple user requests (jobs) in a setting that facilitates preemption and migration, while respecting resource and timing constraints. This gives rise to the following variants of the classical resource allocation problem (RAP). The input is a set J of jobs and a set M of homogeneous hosts, each has 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. We consider two essential 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 address these fundamental problems, which have been studied previously in the non-preemptive model, and develop novel techniques for tackling them. In the full version of the paper, we present an Ω(1)-approximation algorithm for MaxT, assuming there is sufficient slack for each job to be completed in its time window. 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.