Scheduling Algorithms for new Emerging Applications

May, 29th - June, 2nd 2006, CIRM, Marseille, France

Scheduling with reservations

SpeakerLionel Eyraud-Dubois

Co-authorsGrégory Mounié and Denis Trystram

In this work, we target on scheduling a set of independent jobs on a parallel platform composed of identical processors. This general problem has been widely studied on both theoretical side (complexity analysis, approximability of some families of scheduling algorithms) and practical side (dedicated softwares that are utilized under production). It is frequent that some processors of a cluster become not available for a certain amount of time (it corresponds to reservations where, for instance, a specific application will have to start its execution at a determined moment on a given number of processors).

We propose here to investigate the scheduling problem where there are restricted resource avalabilities (temporary deconnection of a sub-set of machines). Our main result is to provide a deep analysis for this problem (complexity, lower bounds, upper bounds) for several variants of list scheduling algorithms. More precisely, we show that the problem of scheduling with any reservations can not be approximated. This leads to study restricted versions of this problem where the amount of reservation is limited.

Our analysis is based on an old bound of Graham for list resource constraint scheduling for which we propose a new simpler proof by considering the continuous version of this problem.