Brief Announcement
| Autor: | Hadas Shachnai, Baruch Schieber, Kanthi K. Sarpatwar |
|---|---|
| Rok vydání: | 2018 |
| Předmět: |
Mathematical optimization
Schedule Computer science business.industry Preemption Approximation algorithm Cloud computing 0102 computer and information sciences 02 engineering and technology Throughput maximization 01 natural sciences Set (abstract data type) Resource (project management) 010201 computation theory & mathematics 020204 information systems 0202 electrical engineering electronic engineering information engineering Resource allocation business |
| Zdroj: | SPAA |
| Popis: | 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 \em 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: \em throughput maximization (MaxT), which seeks a maximum weight subset of the jobs that can be feasibly scheduled on the hosts in M , and \em resource minimization (MinM), 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 \em non-preemptive model, and develop novel techniques for tackling them. In the full version of the paper, we present an $Omega(1)$-approximation algorithm for MaxT, assuming there is sufficient slack for each job to be completed in its time window. For MinM, we study a more general setting with d resources and derive an $O(log d)$-approximation for any fixed $d \geq 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 dlog^* T)$, where T is the maximum due date of any job. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|