## April 23, Spring Quarter 2010: Theory Seminar

### 1:00pm in ICS 243

#
Algorithms and Complexity for Periodic Real-Time Scheduling

## Kiran Shivaram, UC Irvine

Presenting a SODA 2010 paper by Vincenzo Bonifaci, Ho-Leung Chan,
Alberto Marchetti-Spaccamela, and Nicole Megow

Abstract:
We investigate the preemptive scheduling of periodic tasks with hard
deadlines. We show that, even in the uniprocessor case, no polynomial
time algorithm can test the feasibility of a task system within a
constant speedup bound, unless P =NP. This result contrasts with
recent results for sporadic task systems. For two special cases,
synchronous task systems and systems with a constant number of
different task types, we provide the first polynomial time
constant-speedup feasibility tests for multiprocessor platforms.
Furthermore, we show that the problem of testing feasibility is
coNP-hard for synchronous multiprocessor task systems. The complexity
of some of these problems has been open for a long time.
We also propose a profit maximization variant of the feasibility
problem, where every task has a non-negative profit, and the goal is
to find a subset of tasks that can be scheduled feasibly with maximum
profit. We give the first constant-speed, constant-approximation
algorithm for the case of synchronous task systems, together with
related hardness results.