AG 1, AG 2, AG 3, AG 4, AG 5, RG1, SWS, MMCI   Info

AG Audience

English

30 Minutes

Saarbrücken

This talk introduces a new resource constrained scheduling model and presents some first results. We consider a number of jobs scheduled on $m$ identical processors sharing a continuously divisible resource. Each job $j$ comes with a resource requirement $r_j\in\{0,1\}$ and can be processed at full speed if granted its full resource requirement. If receiving only an $x$-portion of $r_j$, it is processed at an $x$-fraction of the full speed. Our goal is to find a resource assignment that minimizes the makespan. Variants of such problems, relating the resource assignment of jobs to their processing speeds, have been studied under the term discrete-continuous scheduling. Known results are either very pessimistic or heuristic in nature.

We suggest a slightly simplified model, focusing on the assignment of shared continuous resources to the processors. The job assignment to processors and the ordering of the jobs have already been fixed. Our work shows that finding an optimal solution is NP-hard if the number of processors is a part of the input, even in the case of unit size jobs. On the positive side, we can give an optimal algorithms for two processors and prove that "balanced" schedules yield a $2-1/m$-approximation. Such schedules can be computed by a simple greedy algorithm, for which this bound is tight.

Antonios Antoniadis

--email hidden

passcode not visible

logged in users only