max planck institut
informatik

# MPI-INF or MPI-SWS or Local Campus Event Calendar

 << Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
Title: Scheduling Shared Continuous Resources on Many-Cores Peter Kling University of Paderborn AG1 Mittagsseminar (own work) D1, D2, D3, D4, D5, RG1, SWS, MMCIWe use this to send out email in the morning. AG Audience English
Date: Tuesday, 22 April 2014 13:00 30 Minutes Saarbrücken E1 4 024
 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.