Volume

Dagstuhl Seminar Proceedings, Volume 10071

Publication Details

  • published at: 2010-05-03
  • Publisher: Schloss Dagstuhl – Leibniz-Zentrum für Informatik

Access Numbers

Documents

No documents found matching your filter selection.
Document
DOI: 10.4230/DagSemProc.10071.1
10071 Abstracts Collection – Scheduling

Authors: Susanne Albers, Sanjoy K. Baruah, Rolf H. Möhring, and Kirk Pruhs

Abstract
From 14.02. to 19.02.2010, the Dagstuhl Seminar 10071 ``Scheduling '' was held in Schloss Dagstuhl-Leibniz Center for Informatics. During the seminar, several participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in this paper. The first section describes the seminar topics and goals in general. Links to extended abstracts or full papers are provided, if available.
Cite as

Susanne Albers, Sanjoy K. Baruah, Rolf H. Möhring, and Kirk Pruhs. 10071 Abstracts Collection – Scheduling. In Scheduling. Dagstuhl Seminar Proceedings, Volume 10071, pp. 1-12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{albers_et_al:DagSemProc.10071.1,
  author =	{Albers, Susanne and Baruah, Sanjoy K. and M\"{o}hring, Rolf  H. and Pruhs, Kirk},
  title =	{{10071 Abstracts Collection – Scheduling}},
  booktitle =	{Scheduling},
  pages =	{1--12},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{10071},
  editor =	{Susanne Albers and Sanjoy K. Baruah and Rolf H. M\"{o}hring and Kirk Pruhs},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.10071.1},
  URN =		{urn:nbn:de:0030-drops-25479},
  doi =		{10.4230/DagSemProc.10071.1},
  annote =	{Keywords: Scheduling, real-time, complexity, approximation algorithms}
}
Document
DOI: 10.4230/DagSemProc.10071.2
10071 Executive Summary – Scheduling

Authors: Susanne Albers, Sanjoy K. Baruah, Rolf H. Möhring, and Kirk Pruhs

Abstract
The primary objectives of this seminar were to bring together leading researchers working on scheduling problems in three different research communities – operations research, theoretical computer science, and real-time systems – to expose each community to the important problems addressed by the other communities; to enable and encourage cooperation among the researchers; and to facilitate a transfer of solution techniques from each community to the others.
Cite as

Susanne Albers, Sanjoy K. Baruah, Rolf H. Möhring, and Kirk Pruhs. 10071 Executive Summary – Scheduling. In Scheduling. Dagstuhl Seminar Proceedings, Volume 10071, pp. 1-2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{albers_et_al:DagSemProc.10071.2,
  author =	{Albers, Susanne and Baruah, Sanjoy K. and M\"{o}hring, Rolf  H. and Pruhs, Kirk},
  title =	{{10071 Executive Summary – Scheduling}},
  booktitle =	{Scheduling},
  pages =	{1--2},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{10071},
  editor =	{Susanne Albers and Sanjoy K. Baruah and Rolf H. M\"{o}hring and Kirk Pruhs},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.10071.2},
  URN =		{urn:nbn:de:0030-drops-25417},
  doi =		{10.4230/DagSemProc.10071.2},
  annote =	{Keywords: Scheduling, real-time, complexity, approximation algorithms}
}
Document
DOI: 10.4230/DagSemProc.10071.3
10071 Open Problems – Scheduling

Authors: Jim Anderson, Björn Andersson, Yossi Azar, Nikhil Bansal, Enrico Bini, Marek Chrobak, José Correa, Liliana Cucu-Grosjean, Rob Davis, Arvind Easwaran, Jeff Edmonds, Shelby Funk, Sathish Gopalakrishnan, Han Hoogeveen, Claire Mathieu, Nicole Megow, Seffi Naor, Kirk Pruhs, Maurice Queyranne, Adi Rosén, Nicolas Schabanel, Jiří Sgall, René Sitters, Sebastian Stiller, Marc Uetz, Tjark Vredeveld, and Gerhard J. Woeginger

Abstract
Collection of the open problems presented at the scheduling seminar.
Cite as

Jim Anderson, Björn Andersson, Yossi Azar, Nikhil Bansal, Enrico Bini, Marek Chrobak, José Correa, Liliana Cucu-Grosjean, Rob Davis, Arvind Easwaran, Jeff Edmonds, Shelby Funk, Sathish Gopalakrishnan, Han Hoogeveen, Claire Mathieu, Nicole Megow, Seffi Naor, Kirk Pruhs, Maurice Queyranne, Adi Rosén, Nicolas Schabanel, Jiří Sgall, René Sitters, Sebastian Stiller, Marc Uetz, Tjark Vredeveld, and Gerhard J. Woeginger. 10071 Open Problems – Scheduling. In Scheduling. Dagstuhl Seminar Proceedings, Volume 10071, pp. 1-24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{anderson_et_al:DagSemProc.10071.3,
  author =	{Anderson, Jim and Andersson, Bj\"{o}rn and Azar, Yossi and Bansal, Nikhil and Bini, Enrico and Chrobak, Marek and Correa, Jos\'{e} and Cucu-Grosjean, Liliana and Davis, Rob and Easwaran, Arvind and Edmonds, Jeff and Funk, Shelby and Gopalakrishnan, Sathish and Hoogeveen, Han and Mathieu, Claire and Megow, Nicole and Naor, Seffi and Pruhs, Kirk and Queyranne, Maurice and Ros\'{e}n, Adi and Schabanel, Nicolas and Sgall, Ji\v{r}{\'\i} and Sitters, Ren\'{e} and Stiller, Sebastian and Uetz, Marc and Vredeveld, Tjark and Woeginger, Gerhard J.},
  title =	{{10071 Open Problems – Scheduling}},
  booktitle =	{Scheduling},
  pages =	{1--24},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{10071},
  editor =	{Susanne Albers and Sanjoy K. Baruah and Rolf H. M\"{o}hring and Kirk Pruhs},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.10071.3},
  URN =		{urn:nbn:de:0030-drops-25367},
  doi =		{10.4230/DagSemProc.10071.3},
  annote =	{Keywords: Open problems, scheduling}
}
Document
DOI: 10.4230/DagSemProc.10071.4
A Stochastic Framework for Multiprocessor Soft Real-Time Scheduling

Authors: James Anderson and Alex Mills

Abstract
Prior work has shown that the global earliest-deadline-first (GEDF) scheduling algorithm ensures bounded deadline tardiness on multiprocessors with no utilization loss; therefore, GEDF may be a good candidate scheduling algorithm for soft real-time workloads. However, such workloads are often implemented assuming an average-case provisioning, and in prior tardiness-bound derivations for GEDF, worst-case execution costs are assumed. As worst-case costs can be orders of magnitude higher than average-case costs, using a worst-case provisioning may result in significant wasted processing capacity. In this paper, prior tardiness-bound derivations for GEDF are generalized so that execution times are probabilistic, and a bound on expected (mean) tardiness is derived. It is shown that, as long as the total expected utilization is strictly less than the number of available processors, the expected tardiness of every task is bounded under GEDF. The result also implies that any quantile of the tardiness distribution is also bounded. The uploaded paper is from the upcoming RTAS. I would like to hear suggestions about how to ease the assumption of independent execution times in this analysis.
Cite as

James Anderson and Alex Mills. A Stochastic Framework for Multiprocessor Soft Real-Time Scheduling. In Scheduling. Dagstuhl Seminar Proceedings, Volume 10071, pp. 1-10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{anderson_et_al:DagSemProc.10071.4,
  author =	{Anderson, James and Mills, Alex},
  title =	{{A Stochastic Framework for Multiprocessor Soft Real-Time Scheduling}},
  booktitle =	{Scheduling},
  pages =	{1--10},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{10071},
  editor =	{Susanne Albers and Sanjoy K. Baruah and Rolf H. M\"{o}hring and Kirk Pruhs},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.10071.4},
  URN =		{urn:nbn:de:0030-drops-25374},
  doi =		{10.4230/DagSemProc.10071.4},
  annote =	{Keywords: GEDF, multiprocessor, tardiness}
}
Document
DOI: 10.4230/DagSemProc.10071.5
Energy Efficient Scheduling via Partial Shutdown

Authors: Samir Khuller, Jian Li, and Barna Saha

Abstract
We define a collection of new problems referred to as ``machine activation'' problems. The central framework we introduce considers a collection of M machines (unrelated or related), with machine $i$ having an activation cost of $a_i$. There is also a collection of N jobs that need to be performed, and $p_{ij}$ is the processing time of job $j$ on machine $i$. Standard scheduling models assume that the set of machines is fixed and all machines are available. We assume that there is an activation cost budget of $A$ -- we would like to select a subset S of the machines to activate with total cost $a(S)le A$ and find a schedule for the jobs on the machines in $S$ minimizing the makespan. In this work we develop bi-criteria approximation algorithms for this problem based on both LP rounding and a greedy approach.
Cite as

Samir Khuller, Jian Li, and Barna Saha. Energy Efficient Scheduling via Partial Shutdown. In Scheduling. Dagstuhl Seminar Proceedings, Volume 10071, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{khuller_et_al:DagSemProc.10071.5,
  author =	{Khuller, Samir and Li, Jian and Saha, Barna},
  title =	{{Energy Efficient Scheduling via Partial Shutdown}},
  booktitle =	{Scheduling},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{10071},
  editor =	{Susanne Albers and Sanjoy K. Baruah and Rolf H. M\"{o}hring and Kirk Pruhs},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.10071.5},
  URN =		{urn:nbn:de:0030-drops-25435},
  doi =		{10.4230/DagSemProc.10071.5},
  annote =	{Keywords: Unrelated parallel machine scheduling, approximation algorithms}
}
Document
DOI: 10.4230/DagSemProc.10071.6
Every Deterministic Nonclairvoyant Scheduler has a Suboptimal Load Threshold

Authors: Jeff Edmonds

Abstract
The goal is to prove a surprising lower bound for resource augmented nonclairvoyant algorithms for scheduling jobs with sublinear nondecreasing speed-up curves on multiple processors with the objective of average response time. Edmonds and Pruhs in SODA09 prove that for every $\e > 0$, there is an algorithm $\alg_{\e}$ that is $(1\!+\!\epsilon)$-speed $O({1 \over \e2})$-competitive. A problem, however, is that this algorithm $\alg_{\e}$ depends on $\e$. The goal is to prove that every fixed deterministic nonclairvoyant algorithm has a suboptimal speed threshold, namely for every (graceful) algorithm $\alg$, there is a threshold $1\!+\!\beta_{\alg}$ that is $\beta_{\alg} > 0$ away from being optimal such that the algorithm is $\Omega({1 \over \e \beta_{\alg}})$ competitive with speed $(1 \!+\! \beta_{\alg}) \!+\! \e$ and is $\omega(1)$ competitive with speed $1 \!+\! \beta_{\alg}$. I have worked very hard on it and have felt that I was close. The proof technique is to use Brouwer's fixed point theorem to break the cycle of needing to know which input will be given before one can know what the algorithm will do and needing to know what the algorithm will do before one can know which input to give. Every thing I have can be found at
Cite as

Jeff Edmonds. Every Deterministic Nonclairvoyant Scheduler has a Suboptimal Load Threshold. In Scheduling. Dagstuhl Seminar Proceedings, Volume 10071, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{edmonds:DagSemProc.10071.6,
  author =	{Edmonds, Jeff},
  title =	{{Every Deterministic Nonclairvoyant Scheduler has a Suboptimal Load Threshold}},
  booktitle =	{Scheduling},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{10071},
  editor =	{Susanne Albers and Sanjoy K. Baruah and Rolf H. M\"{o}hring and Kirk Pruhs},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.10071.6},
  URN =		{urn:nbn:de:0030-drops-25447},
  doi =		{10.4230/DagSemProc.10071.6},
  annote =	{Keywords: Scheduling}
}
Document
DOI: 10.4230/DagSemProc.10071.7
Optimal Mechanisms for Scheduling

Authors: Birgit Heydenreich, Debasis Mishra, Rudolf Müller, and Marc Uetz

Abstract
We study the design of optimal mechanisms in a setting where a service provider needs to schedule a set of non-preemptive jobs, one job at a time. Jobs need to be compensated for waiting, and waiting cost is private information. In this setting, an optimal mechanism is one that induces jobs to report truthfully their waiting cost, while minimizing the total expected compensation cost of the service provider. Here, truthful refers to Bayes-Nash implementability, and assumes that private information is independently drawn from known distributions. We derive closed formulae for the optimal mechanism, and show that it is a modification of Smith’s ratio rule. We also show that it can be implemented in dominant strategies. Our analysis relies on a graph-theoretic interpretation of the incentive compatibility constraints. It parallels the analysis known for auctions with single parameter agents, yet it exhibits some subtle differences. We also consider the multi-dimensional case where also the service times of jobs are private information. We show that for this problem the optimal mechanism generally does not satisfy an independence condition known as IIA, and thus known approaches are doomed to fail.
Cite as

Birgit Heydenreich, Debasis Mishra, Rudolf Müller, and Marc Uetz. Optimal Mechanisms for Scheduling. In Scheduling. Dagstuhl Seminar Proceedings, Volume 10071, pp. 1-22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{heydenreich_et_al:DagSemProc.10071.7,
  author =	{Heydenreich, Birgit and Mishra, Debasis and M\"{u}ller, Rudolf and Uetz, Marc},
  title =	{{Optimal Mechanisms for Scheduling}},
  booktitle =	{Scheduling},
  pages =	{1--22},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{10071},
  editor =	{Susanne Albers and Sanjoy K. Baruah and Rolf H. M\"{o}hring and Kirk Pruhs},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.10071.7},
  URN =		{urn:nbn:de:0030-drops-25401},
  doi =		{10.4230/DagSemProc.10071.7},
  annote =	{Keywords: Optimal Mechanism Design, Scheduling, Job Agents, Smith's Rule}
}
Document
DOI: 10.4230/DagSemProc.10071.8
Polynomial Time Algorithms for Minimum Energy Scheduling

Authors: Marek Chrobak, Philippe Baptiste, and Christoph Dürr

Abstract
The aim of power management policies is to reduce the amount of energy consumed by computer systems while maintaining satisfactory level of performance. One common method for saving energy is to simply suspend the system during the idle times. No energy is consumed in the suspend mode. However, the process of waking up the system itself requires a certain fixed amount of energy, and thus suspending the system is beneficial only if the idle time is long enough to compensate for this additional energy expenditure. In the specific problem studied in the paper, we have a set of jobs with release times and deadlines that need to be executed on a single processor. Preemptions are allowed. The processor requires energy L to be woken up and, when it is on, it uses the energy at a rate of R units per unit of time. It has been an open problem whether a schedule minimizing the overall energy consumption can be computed in polynomial time. We solve this problem in positive, by providing an O(n5)-time algorithm. In addition we provide an O(n4)-time algorithm for computing the minimum energy schedule when all jobs have unit length.
Cite as

Marek Chrobak, Philippe Baptiste, and Christoph Dürr. Polynomial Time Algorithms for Minimum Energy Scheduling. In Scheduling. Dagstuhl Seminar Proceedings, Volume 10071, pp. 1-12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{chrobak_et_al:DagSemProc.10071.8,
  author =	{Chrobak, Marek and Baptiste, Philippe and D\"{u}rr, Christoph},
  title =	{{Polynomial Time Algorithms for Minimum Energy Scheduling}},
  booktitle =	{Scheduling},
  pages =	{1--12},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{10071},
  editor =	{Susanne Albers and Sanjoy K. Baruah and Rolf H. M\"{o}hring and Kirk Pruhs},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.10071.8},
  URN =		{urn:nbn:de:0030-drops-25351},
  doi =		{10.4230/DagSemProc.10071.8},
  annote =	{Keywords: Scheduling, algorithm, dynamic programming, energy}
}
Document
DOI: 10.4230/DagSemProc.10071.9
Power-Aware Real-Time Scheduling: Models, Open Problems, and Practical Considerations

Authors: Nathan Fisher

Abstract
Power-related issues have received considerable research attention from the real-time community in the past decade. In our talk, we introduce a recent model and set of assumptions made in the recent real-time literature on energy and thermal issues; suggest two high-level open problems for power-aware real-time scheduling: {em peak-temperature minimization} and {em energy-minimization with temperature as a constraint}; and discuss practical considerations that should be considered in proposed solutions.
Cite as

Nathan Fisher. Power-Aware Real-Time Scheduling: Models, Open Problems, and Practical Considerations. In Scheduling. Dagstuhl Seminar Proceedings, Volume 10071, pp. 1-4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{fisher:DagSemProc.10071.9,
  author =	{Fisher, Nathan},
  title =	{{Power-Aware Real-Time Scheduling: Models, Open Problems, and Practical Considerations}},
  booktitle =	{Scheduling},
  pages =	{1--4},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{10071},
  editor =	{Susanne Albers and Sanjoy K. Baruah and Rolf H. M\"{o}hring and Kirk Pruhs},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.10071.9},
  URN =		{urn:nbn:de:0030-drops-25395},
  doi =		{10.4230/DagSemProc.10071.9},
  annote =	{Keywords: Real-time scheduling, power-aware scheduling, sporadic tasks}
}
Document
DOI: 10.4230/DagSemProc.10071.10
Recent Hardness Results for Periodic Uni-processor Scheduling

Authors: Friedrich Eisenbrand and Thomas Rothvoss

Abstract
Consider a set of $n$ periodic tasks $ au_1,ldots, au_n$ where $ au_i$ is described by an execution time $c_i$, a (relative) deadline $d_i$ and a period $p_i$. We assume that jobs are released synchronously (i.e. at each multiple of $p_i$) and consider pre-emptive, uni-processor schedules. We show that computing the response time of a task $ au_n$ in a Rate-monotonic schedule i.e. computing [ minleft{ r geq mid c_n + sum_{i=1}^{n-1} leftlceil frac{r}{p_i} ight ceil c_i leq r ight} ] is (weakly) $mathbf{NP}$-hard (where $ au_n$ has the lowest priority and the deadlines are implicit, i.e. $d_i = p_i$). Furthermore we obtain that verifying EDF-schedulability, i.e. [ forall Q geq 0: sum_{i=1}^n left( leftlfloor frac{Q-d_i}{p_i} ight floor +1 ight)cdot c_i leq Q ] for constrained-deadline tasks ($d_i leq p_i$) is weakly $mathbf{coNP}$-hard.
Cite as

Friedrich Eisenbrand and Thomas Rothvoss. Recent Hardness Results for Periodic Uni-processor Scheduling. In Scheduling. Dagstuhl Seminar Proceedings, Volume 10071, pp. 1-7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{eisenbrand_et_al:DagSemProc.10071.10,
  author =	{Eisenbrand, Friedrich and Rothvoss, Thomas},
  title =	{{Recent Hardness Results for Periodic Uni-processor Scheduling}},
  booktitle =	{Scheduling},
  pages =	{1--7},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{10071},
  editor =	{Susanne Albers and Sanjoy K. Baruah and Rolf H. M\"{o}hring and Kirk Pruhs},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.10071.10},
  URN =		{urn:nbn:de:0030-drops-25458},
  doi =		{10.4230/DagSemProc.10071.10},
  annote =	{Keywords: Hardness, periodic scheduling, uni-processor scheduling}
}
Document
DOI: 10.4230/DagSemProc.10071.11
Resource Sharing in Global Fixed-Priority Preemptive Multiprocessor Scheduling

Authors: Arvind Easwaran and Björn Andersson

Abstract
In this paper we consider global fixed-priority preemptive multiprocessor scheduling of constrained-deadline sporadic tasks that share resources in a non-nested manner. We develop a novel resource-sharing protocol and a corresponding schedulability test for this system. We also develop the first schedulability analysis of priority inheritence protocol for the aforementioned system. Finally, we show that these protocols are efficient (based on the developed schedulability tests) for a class of priority-assignments called emph{reasonable} priority-assignments.
Cite as

Arvind Easwaran and Björn Andersson. Resource Sharing in Global Fixed-Priority Preemptive Multiprocessor Scheduling. In Scheduling. Dagstuhl Seminar Proceedings, Volume 10071, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{easwaran_et_al:DagSemProc.10071.11,
  author =	{Easwaran, Arvind and Andersson, Bj\"{o}rn},
  title =	{{Resource Sharing in Global Fixed-Priority Preemptive Multiprocessor Scheduling}},
  booktitle =	{Scheduling},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{10071},
  editor =	{Susanne Albers and Sanjoy K. Baruah and Rolf H. M\"{o}hring and Kirk Pruhs},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.10071.11},
  URN =		{urn:nbn:de:0030-drops-25385},
  doi =		{10.4230/DagSemProc.10071.11},
  annote =	{Keywords: Scheduling}
}
Document
DOI: 10.4230/DagSemProc.10071.12
Scalably Scheduling Processes with Arbitrary Speedup Curves

Authors: Jeff Edmonds and Kirk Pruhs

Abstract
We give a scalable ((1+\epsilon)-speed O(1)-competitive) nonclairvoyant algorithm for scheduling jobs with sublinear nondecreasing speed-up curves on multiple processors with the objective of average response time.
Cite as

Jeff Edmonds and Kirk Pruhs. Scalably Scheduling Processes with Arbitrary Speedup Curves. In Scheduling. Dagstuhl Seminar Proceedings, Volume 10071, pp. 1-9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{edmonds_et_al:DagSemProc.10071.12,
  author =	{Edmonds, Jeff and Pruhs, Kirk},
  title =	{{Scalably Scheduling Processes with Arbitrary Speedup Curves}},
  booktitle =	{Scheduling},
  pages =	{1--9},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{10071},
  editor =	{Susanne Albers and Sanjoy K. Baruah and Rolf H. M\"{o}hring and Kirk Pruhs},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.10071.12},
  URN =		{urn:nbn:de:0030-drops-25463},
  doi =		{10.4230/DagSemProc.10071.12},
  annote =	{Keywords: Scheduling}
}
Document
DOI: 10.4230/DagSemProc.10071.13
Scheduling periodic tasks in a hard real-time environment

Authors: Friedrich Eisenbrand, Nicolai Hähnle, Martin Niemeier, Martin Skutella, Jose Verschae, and Andreas Wiese

Abstract
We consider a real-time scheduling problem that occurs in the design of software-based aircraft control. The goal is to distribute tasks $ au_i=(c_i,p_i)$ on a minimum number of identical machines and to compute offsets $a_i$ for the tasks such that no collision occurs. A task $ au_i$ releases a job of running time $c_i$ at each time $a_i + kcdot p_i, , k in mathbb{N}_0$ and a collision occurs if two jobs are simultaneously active on the same machine. We shed some light on the complexity and approximability landscape of this problem. Although the problem cannot be approximated within a factor of $n^{1-varepsilon}$ for any $varepsilon>0$, an interesting restriction is much more tractable: If the periods are dividing (for each $i,j$ one has $p_i | p_j$ or $p_j | p_i$), the problem allows for a better structured representation of solutions, which leads to a 2-approximation. This result is tight, even asymptotically.
Cite as

Friedrich Eisenbrand, Nicolai Hähnle, Martin Niemeier, Martin Skutella, Jose Verschae, and Andreas Wiese. Scheduling periodic tasks in a hard real-time environment. In Scheduling. Dagstuhl Seminar Proceedings, Volume 10071, pp. 1-3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{eisenbrand_et_al:DagSemProc.10071.13,
  author =	{Eisenbrand, Friedrich and H\"{a}hnle, Nicolai and Niemeier, Martin and Skutella, Martin and Verschae, Jose and Wiese, Andreas},
  title =	{{Scheduling periodic tasks in a hard real-time environment}},
  booktitle =	{Scheduling},
  pages =	{1--3},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{10071},
  editor =	{Susanne Albers and Sanjoy K. Baruah and Rolf H. M\"{o}hring and Kirk Pruhs},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.10071.13},
  URN =		{urn:nbn:de:0030-drops-25348},
  doi =		{10.4230/DagSemProc.10071.13},
  annote =	{Keywords: Real-Time Scheduling, Periodic scheduling problem, Periodic maintenance problem, Approximation hardness, Approximation algorithm}
}
Document
DOI: 10.4230/DagSemProc.10071.14
The Parallel Supply Function Abstraction for a Virtual Multiprocessor

Authors: Enrico Bini, Bertogna Marko, and Sanjoy K. Baruah

Abstract
A new abstraction --- the Parallel Supply Function (PSF) --- is proposed for representing the computing capabilities offered by virtual platforms implemented atop identical multiprocessors. It is shown that this abstraction is strictly more powerful than previously-proposed ones, from the perspective of more accurately representing the inherent parallelism of the provided computing capabilities. Sufficient tests are derived for determining whether a given real-time task system, represented as a collection of sporadic tasks, is guaranteed to always meet all deadlines when scheduled upon a specified virtual platform using the global EDF scheduling algorithm.
Cite as

Enrico Bini, Bertogna Marko, and Sanjoy K. Baruah. The Parallel Supply Function Abstraction for a Virtual Multiprocessor. In Scheduling. Dagstuhl Seminar Proceedings, Volume 10071, pp. 1-14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{bini_et_al:DagSemProc.10071.14,
  author =	{Bini, Enrico and Marko, Bertogna and Baruah, Sanjoy K.},
  title =	{{The Parallel Supply Function Abstraction for a Virtual Multiprocessor}},
  booktitle =	{Scheduling},
  pages =	{1--14},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{10071},
  editor =	{Susanne Albers and Sanjoy K. Baruah and Rolf H. M\"{o}hring and Kirk Pruhs},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.10071.14},
  URN =		{urn:nbn:de:0030-drops-25423},
  doi =		{10.4230/DagSemProc.10071.14},
  annote =	{Keywords: Virtual multiprocessor}
}

Filters

  • Authors
  • A
  • Albers, Susanne
  • Anderson, James
  • Anderson, Jim
  • Andersson, Björn
  • Azar, Yossi
  • B
  • Bansal, Nikhil
  • Baptiste, Philippe
  • Baruah, Sanjoy K.
  • Bini, Enrico
  • C
  • Chrobak, Marek
  • Correa, José
  • Cucu-Grosjean, Liliana
  • D
  • Davis, Rob
  • Dürr, Christoph
  • E
  • Easwaran, Arvind
  • Edmonds, Jeff
  • Eisenbrand, Friedrich
  • F
  • Fisher, Nathan
  • Funk, Shelby
  • G
  • Gopalakrishnan, Sathish
  • H
  • Hähnle, Nicolai
  • Heydenreich, Birgit
  • Hoogeveen, Han
  • K
  • Khuller, Samir
  • L
  • Li, Jian
  • M
  • Marko, Bertogna
  • Mathieu, Claire
  • Megow, Nicole
  • Mills, Alex
  • Mishra, Debasis
  • Möhring, Rolf H.
  • Müller, Rudolf
  • N
  • Naor, Seffi
  • Niemeier, Martin
  • P
  • Pruhs, Kirk
  • Q
  • Queyranne, Maurice
  • R
  • Rosén, Adi
  • Rothvoss, Thomas
  • S
  • Saha, Barna
  • Schabanel, Nicolas
  • Sgall, Jiří
  • Sitters, René
  • Skutella, Martin
  • Stiller, Sebastian
  • U
  • Uetz, Marc
  • V
  • Verschae, Jose
  • Vredeveld, Tjark
  • W
  • Wiese, Andreas
  • Woeginger, Gerhard J.

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 Imprint Privacy Contact