AG 1   Info

AG Audience

English

30 Minutes

Saarbrücken

We consider a scheduling problem of periodic tasks. That is, each task is represented by a tuple $(c,p)$ where $c$ determines the execution time and $p$ the period of the task. The tasks appear periodically at each time that is a non-negative integer multiple of the respective period. Each task has to be assigned to exactly one processor such that it will always finish before its period ends and it appears again. Our objective is to minimize the number of necessary processors. Since the Binpacking problem is the special case if all periods are 1, we present approximation algorithms and analyze their worst-case and average-case behavior. [Joint work with Thomas Rothvoss]

Andreas Karrenbauer

--email hidden

passcode not visible

logged in users only

Real-Time Scheduling, Approximation Algorithms