Real-Time k-bounded Preemptive Scheduling
| Autor: | Sivan Albagli-Kim, Tami Tamir, Baruch Schieber, Hadas Shachnai |
|---|---|
| Rok vydání: | 2015 |
| Předmět: |
Rate-monotonic scheduling
Earliest deadline first scheduling Schedule Mathematical optimization Job shop scheduling Computer science 020208 electrical & electronic engineering 010103 numerical & computational mathematics 02 engineering and technology Dynamic priority scheduling 01 natural sciences Deadline-monotonic scheduling Linear programming relaxation Fixed-priority pre-emptive scheduling 0202 electrical engineering electronic engineering information engineering 0101 mathematics Computer Science::Operating Systems |
| Zdroj: | ALENEX |
| DOI: | 10.1137/1.9781611974317.11 |
| Popis: | We consider a variant of the classic real-time scheduling problem, which has natural applications in cloud computing. The input consists of a set of jobs, and an integer parameter k ≥ 1. Each job is associated with a processing time, a release time, a due-date and a positive weight. The goal is to feasibly schedule a subset of the jobs of maximum total weight on a single machine, such that each of the jobs is preempted at most k times. Our theoretical results for the real-time k-bounded preemptive scheduling problem include hardness proofs, as well as algorithms for subclasses of instances, for which we derive constant-ratio performance guarantees. We bridge the gap between theory and practice through a comprehensive experimental study, in which we also test the performance of several heuristics for general instances on multiple parallel machines. We use in the experiments a linear programming relaxation to upper bound the optimal solution for a given instance. Our results show that while k-bounded preemptive scheduling is hard to solve already on highly restricted instances, simple priority-based heuristics yield almost optimal schedules for realistic inputs and arbitrary values of k. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|