Publications related to Exact quantification of the sub-optimality of uniprocessor fixed-priority pre- emptive scheduling

Zeta: Scheduling Interactive Services with Partial Execution

James Richard Larus, Sameh Mohamed Elnikety, Chenyu Yan

This paper presents a scheduling model for a class of interactive services in which requests are time bounded and lower result quality can be traded for shorter execution time. These applications include web search engines, finance servers, and other inter ...

ACM2012

Partitioned real-time scheduling on heterogeneous shared-memory multiprocessors

Martin Niemeier

We consider several real-time scheduling problems on heterogeneous multiprocessor platforms, in which the different processors share a common memory pool. These include (i)~scheduling a collection of implicit-deadline sporadic tasks with the objective of m ...

2011

Greedy Scheduling for Distributed Computing Clusters

Amin Karbasi, Milan Vojnovic

Allocating tasks to machines in computing clusters is described. In an embodiment a set of tasks associated with a job are received at a scheduler. In an embodiment an index can be computed for each combination of tasks and processors and stored in a looku ...

2011

Scheduling periodic tasks in a hard real-time environment

Friedrich Eisenbrand, Martin Niemeier, Nicolai Hähnle

We give a rigorous account on the complexity landscape of an important real-time scheduling problem that occurs in the design of software-based aircraft control. The goal is to distribute tasks

\tau_i=(c_i,p_i)

on a minimum number of identical machines a ...

Springer-Verlag2010

EDF-schedulability of synchronous periodic task systems is coNP-hard

Friedrich Eisenbrand, Thomas Rothvoss

In the synchronous periodic task model, a set \tau_1,...,\tau_n of tasks is given, each releasing jobs of running time c_i with relative deadline d_i, at each integer multiple of the period p_i. It is a classical result that Earliest Deadline First (EDF) i ...

2010

A Tighter Analysis of Work Stealing

Nicolas Gabriel Gast, Denis Trystram

Classical list scheduling is a very popular and efficient technique for scheduling jobs in parallel platforms. However, with the increasing number of processors, the cost for managing a single centralized list becomes prohibitive. The objective of this wor ...

Springer Berlin Heidelberg2010

On the computational complexity of periodic scheduling

Thomas Rothvoss

In periodic scheduling jobs arrive regularly and have to be executed on one or several machines or processors. An enormous amount of literature has been published on this topic, e.g. the founding work of Liu & Layland [LL73] is among the top cited computer ...

EPFL2009

Multi-Agent Adaptive Mechanism Leading to Optimal Real-Time Load Sharing

Max-Olivier Hongler, Olivier Gallay

We propose a new real-time load sharing policy (LSP), which optimally dispatches the incoming workload according to the current availability of the operators. Optimality means here that the global service permanently requires the engagement of a minimum nu ...

2009

Forward Error Correction for Multipath Media Streaming

Pascal Frossard, Aleksandar Jovanovic, Dan Jurca

We address the problem of joint optimal rate allocation and scheduling between media source rate and error protection rate in scalable streaming applications over lossy multipath networks. Starting from a distortion representation of the received media inf ...

Institute of Electrical and Electronics Engineers2009

A PTAS for Static Priority Real-Time Scheduling with Resource Augmentation

Friedrich Eisenbrand, Thomas Rothvoss

We present a polynomial time approximation scheme for the real-time scheduling problem with fixed priorities when resource augmentation is allowed. For a fixed ε > 0, our algorithmcomputes an assignment using atmost (1+ε)·OPT +1 processors in polynomial ti ...

Springer2008

Exact quantification of the sub-optimality of uniprocessor fixed-priority pre- emptive scheduling

Graph Chatbot

Chat with Graph Search

Zeta: Scheduling Interactive Services with Partial Execution

Partitioned real-time scheduling on heterogeneous shared-memory multiprocessors

Greedy Scheduling for Distributed Computing Clusters

Scheduling periodic tasks in a hard real-time environment

EDF-schedulability of synchronous periodic task systems is coNP-hard

A Tighter Analysis of Work Stealing

On the computational complexity of periodic scheduling

Multi-Agent Adaptive Mechanism Leading to Optimal Real-Time Load Sharing

Forward Error Correction for Multipath Media Streaming

A PTAS for Static Priority Real-Time Scheduling with Resource Augmentation

A Tighter Analysis of Work Stealing

Forward Error Correction for Multipath Media Streaming

Greedy Scheduling for Distributed Computing Clusters

Scheduling periodic tasks in a hard real-time environment

EDF-schedulability of synchronous periodic task systems is coNP-hard

Multi-Agent Adaptive Mechanism Leading to Optimal Real-Time Load Sharing

Partitioned real-time scheduling on heterogeneous shared-memory multiprocessors

On the computational complexity of periodic scheduling

Zeta: Scheduling Interactive Services with Partial Execution

A PTAS for Static Priority Real-Time Scheduling with Resource Augmentation