UNIVERSIT dVRY-VAL dESSONNE

cole Doctorale S&I (Sciences et Ingnierie)

THSE
prsente par :

Fadi Kacem
pour obtenir : - Spcialit : Informatique

Algorithmes Exacts et Approchs pour des problmes dOrdonnancement et de Placement

Thse soutenue le 27 juin 2012 devant le jury compos de :

Rapporteurs : Examinateurs : Directeur de thse : Co-encadrant :

M. Denis Mme. Johanne M. Christoph M. Jean-Marc M. Evripidis M. Eric

Professeur lENSIMAG, Grenoble Charge de Recherche CNRS au PRiSM, Versailles Directeur de Recherche CNRS au LIP6, Paris Professeur lUEVE, Evry Professeur lUPMC, Paris Professeur lUEVE, Evry

Thse prpare au sein de lquipe OPAL du Laboratoire IBISC EA 4526 - Universit dvry-Val dEssonne

Table des matires

Liste des tableaux Table des gures Introduction 1 Ordonnancer pour conomiser lnergie : cas de plusieurs machines identiques 1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.1.1 1.2 1.3 Contribution et organisation du chapitre . . . . . . . . . . . . . . . . . .

vi viii 1 9 9 13 13 14 14 16 23 23 25 32 40 43 43 44

Dnition du problme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Critres doptimalit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3.1 1.3.2 Un programme convexe . . . . . . . . . . . . . . . . . . . . . . . . . . Les conditions KKT . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1.4

Un algorithme combinatoire bas sur le calcul de ots . . . . . . . . . . . . . . . 1.4.1 1.4.2 1.4.3 Le problme de ot-max/coupe-min . . . . . . . . . . . . . . . . . . . . Le problme daectation vitesse constante "AVC" . . . . . . . . . . . Lalgorithme SSM . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1.5

Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2 Ordonnancer pour conomiser lnergie : cas dune seule machine 2.1 2.2 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Dnition du problme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

ii

2.3 2.4 2.5 2.6 2.7 2.8

Travaux connexes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Structure de lordonnancement optimal . . . . . . . . . . . . . . . . . . . . . . . Suxes et Prxes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Le programme dynamique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Analyse de la complexit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

48 49 52 56 58 62 63 63 64 67 70 77 82 85

3 Ordonnancer pour conomiser lnergie : cas de plusieurs machines htrognes 3.1 3.2 3.3 3.4 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Travaux connexes et contributions . . . . . . . . . . . . . . . . . . . . . . . . . Relaxation linaire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Algorithme randomis pour le problme RS | ri j |E + 3.4.1 3.5 3.6 w jC j . . . . . . . . . . .

Drandomisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . w jC j . . . . . . . . . . . . . . . . . . . . . .

Extension au problme RS |ri j , E|

Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4 Ordonnancement avec des contraintes de prcdence et des temps de communication 87 4.1 4.2 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Dnitions et Notations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2.1 4.2.2 4.2.3 4.3 4.4 4.5 Formulation du modle . . . . . . . . . . . . . . . . . . . . . . . . . . . Temps de communication monotones . . . . . . . . . . . . . . . . . . . Algorithmes de liste . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87 90 90 91 92 93 95 97 98 100 104 106

Travaux connexes et contributions . . . . . . . . . . . . . . . . . . . . . . . . . Complexit du problme gnral . . . . . . . . . . . . . . . . . . . . . . . . . . Extension de lalgorithme LPP sur des machines ddies . . . . . . . . . . . . . 4.5.1 4.5.2 4.5.3 Une borne suprieure sur les temps de compltude des tches . . . . . . Modication des dates dchance . . . . . . . . . . . . . . . . . . . . . Optimalit de lextension de lalgorithme LPP . . . . . . . . . . . . . .

4.6

Non optimalit des algorithmes de liste pour des machines identiques . . . . . . iii

4.7

Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

107 111 111 112 113 114 114 116 120 121 125 127 131

5 Algorithmes optimaux pour le problme de placement de donnes 5.1 5.2 5.3 5.4 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Dnition du problme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Travaux connexes et contributions . . . . . . . . . . . . . . . . . . . . . . . . . Algorithme de programmation dynamique . . . . . . . . . . . . . . . . . . . . . 5.4.1 5.4.2 5.4.3 5.5 5.6 Placement de donnes sur une chane . . . . . . . . . . . . . . . . . . . Placement de donnes sur un anneau . . . . . . . . . . . . . . . . . . . . Placement de donnes sur un graphe en toile gnralise . . . . . . . . .

Placement de donnes sur un graphe quelconque . . . . . . . . . . . . . . . . . . Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Conclusion Bibliographie

iv

Liste des tableaux

3.1 4.1 4.2 4.3 4.4 4.5 Exemple dapplication de lalgorithme . . . . . . . . . . . . . . . . Temps de communication monotones pour le graphe dordre dintervalles . . . . Dates darrive et dchance et types des tches pour la gure 4.4 . . . . . . . . Dates darrive, dates dchance et dates de dbut dexcution dune solution . . Dates darrive r amliores et une nouvelle numrotation des tches . . . . . .
Dates dchance amliores dk (i), (i, k) {1, . . . , 8}2 . . . . . . . . . . . . . . . .

71 92 99 99 101 102

vi

vii

Table des gures

1.1 1.2 1.3 1.4 1.5 2.1 2.2 2.3 2.4 3.1 3.2 3.3 3.4 4.1 4.2 4.3 4.4 4.5 4.6 Inuence du choix des vitesses sur lnergie consomme. . . . . . . . . . . . . . 11

Exemple dordonnancement sans premption durant un intervalle I j sur 3 machines. 19 Rduction de linstance (J, I, v) du problme AVC en un problme de ot max . Exemple dinstance du problme de minimisation dnrgie avec migration. . . . Exemple dapplication de lalgorithme SSM. . . . . . . . . . . . . . . . . . . . 26 34 36 46 47 54 61 71 72 72 79 88 88 89 90

Ordonnancement dune instance compose de 5 tches . . . . . . . . . . . . . . Exemple dordonnancement sans augmentation dnergie . . . . . . . . . . . . . Structure dun ordonnancement optimal pour une instance compose de 11 tches Les dirents vnements durant la procdure de compression . . . . . . . . . . Lensemble des intervalles gomtriques dduits de linstance du problme . . . Solution optimale du programme linaire appliqu sur linstance du problme . . Solution retourne suite lexcution de lalgorithme sur linstance . Solution retourne suite lexcution de lalgorithme modi . . . . Ordonnancement dun graphe de prcdence avec 4 tches unitaires . . . . . . . Ordonnancement dun graphe de prcdence avec des temps de communication . Ordonnancement dun graphe de prcdence avec 3 tches unitaires types . . . . Un graphe dordre dintervalles et les intervalles correspondants . . . . . . . . .

Transformation dune instance du problme SCL en une instance du problme SBC 97 Extension du LPP pour lexemple de la gure 4.4 avec des chances modies . 104

viii

4.7 4.8 5.1 5.2 5.3

Les algorithmes de liste ne sont pas optimaux pour 2 machines identiques . . . . Lalgorithme LPP risque de retourner un ordonnancement non ralisable . . . . . Problme de placement de donnes sur une chane. . . . . . . . . . . . . . . . . Problme de placement de donnes sur une topologie danneau. . . . . . . . . .

107 108 115 118 120

Problme de placement de donnes sur une topologie en toile gnralise . . . .

ix

Introduction
Loptimisation combinatoire est une branche de linformatique dans laquelle on cherche obtenir des solutions ecaces pour des problmes discrets. Ces problmes sont, gnralement, caractriss par un ensemble de contraintes que doit satisfaire toute solution ralisable et une fonction, dite fonction objectif, qui dnit la notion de meilleure solution. En eet, pour chaque solution ralisable, la fonction objectif renvoie un entier ou un rel et la meilleure solution (ou solution optimale) est celle qui minimise ou maximise la fonction objectif. Il est, toutefois, possible quun problme doptimisation combinatoire admette plusieurs solutions optimales. Par ailleurs, un algorithme est dit ecace si son temps dexcution est polynomial en la taille de linstance, i.e. le nombre doprations lmentaires requises par lalgorithme est polynomial. Il est ainsi possible de classier les dirents problmes doptimisation en problmes simples et diciles selon lexistence ou non dalgorithmes polynomiaux pouvant les rsoudre. Stephen Cook [36] a formalis cette classication en introduisant les classes de complexit P et NP, et la notion de NP-dicult. La classe de complexit P contient tous les problmes pour lesquels il existe des algorithmes polynomiaux pouvant les rsoudre. Par ailleurs, un problme appartient la classe de complexit NP sil existe un algorithme polynomial capable de valider toute solution du problme de dcision correspondant. Il est clair que tous les problmes dans P sont aussi dans NP, et on a donc linclusion suivante : P NP. Maintenant, un problme doptimisation est quali de NP-dicile sil est au moins aussi dicile que tous les problmes de la classe NP1 . Dans ce cas o on ne peut pas esprer trouver un
1

On utilise la notion de la Rduction polynomiale pour montrer quun problme est au moins aussi dicile que

tous les problmes dune classe de complexit (la classe NP par exemple).

algorithme polynomial pour le rsoudre, sauf si P=NP. Cook [36] et Karp [53] ont prouv quun large ventail de problmes doptimisation naturels sont NP-dicile et depuis, la complexit de la plupart des problmes doptimisation combinatoire a t dtermine, i.e. soit dans P, ou NP-dicile. Cependant, il est noter que la plupart des problmes pratiques sont NP-diciles. Dans limpossibilit dune rsolution optimale dun problme en temps polynomial, on a souvent recours des solutions approches qui sont fournies par des algorithmes dapproximation. Une stratgie classique pour obtenir de tels algorithmes consiste relacher quelques contraintes du problme de faon obtenir une relaxation du problme dorigine pour laquelle on est capable de construire une solution optimale en un temps polynomial en la taille de linstance. Il faut donc ensuite tranformer la solution obtenue de la relaxation en une solution ralisable du problme original. La solution optimale du problme original ntant pas connue, toute la dicult rside dans lanalyse visant garantir que la solution obtenue partir de lapproximation ne sloigne pas trop de loptimum original. Dans ce contexte, nous nous intressons la rsolution de quelques problmes doptimisation combinatoires que nous avons choisi de traiter en deux volets. Dans un premier temps, nous tudions des problmes doptimisation issus de lordonnancement dun ensemble de tches sur des machines de calcul et o on cherche minimiser lnergie totale consomme par ces machines tout en prservant une qualit de service acceptable. Dans un deuxime temps, nous traitons deux problmes doptimisation classiques savoir un problme dordonnancement dans une architecture de machines parallles avec des temps de communication, et un problme de placement de donnes dans des graphes modlisant des rseaux pair--pair et visant minimiser le cot total daccs aux donnes.

Ordonnancement avec minimisation de lnergie Bien que linformatique occupe aujourdhui une place prpondrante dans notre vie dans le sens o elle facilite la gestion de nombreuses activits quotidiennes, il nest cependant plus possible de ngliger les consquences indsirables qui en rsultent. La consommation dnergie

par les appareils informatiques fait partie des plus importants des eets secondaires. En eet, selon une tude mene en 2007 par lagence de protection de lenvironnement des tats-Unis "EPA", on a prdit quen 2010, environ 2% de lnergie produite dans le monde sera consomme par les centres de donnes contre 1% en 2005 et 0.5% en 2000. Une grande partie de cette nergie est consomme alors que les serveurs sont inactifs et attendent sans rien faire. Si des grands eorts, aussi bien du point de vue matriel que logiciel, ont t eectus dans la conception des appareils portatifs (tlphones, ordinateurs portables, etc.) pour orir une grande autonomie nergtique et donc un gaspillage dnergie aussi faible que possible, peu de choses ont t faites pour la minimisation de lnergie consomme par les serveurs informatiques et encore moins pour les centres de donnes. Dans ce contexte, on peut citer les propos dEric Schmidt, directeur excutif de Google, qui dit : " What matters most to the computer designers at Google is not speed but power - low power, because data centers can consume as much as a city ". Nanmoins, tant donn limpact nfaste sur lenvironnement ainsi que le cot important de lnergie, de plus en plus dacteurs prennent conscience du problme. Dans un rapport qui date dAot 2011, Jonathan G. Koomey [56] a montr que contrairement aux prdictions de lEPA, la consommation mondiale en nergie dans les centres de donnes na pas doubl en 2010 par rapport 2005 mais elle a plutt ach un taux denviron 1.3% de la consommation mondiale. Ce ralentissement dans le rythme de croissance de la consommation dnergie est d, en grande partie des politiques et mcanismes de matrise de lnergie dans les centres de donnes. Dun point de vue algorithmique, ceci inclut ltude de problmes dordonnancement ayant comme objectif la minimisation de lnergie consomme par les processeurs. Cette consommation dnergie est cause principalement par lexcution des direntes tches qui sont soumises aux machines. Cependant, une partie non ngligeable de la dpense nergtique provient aussi de linactivit des machines puisque mme en labsence de programmes ou requtes excuter, une machine dpense une quantit constante dnergie que nous appelons nergie statique (ou nergie de base). Nous considrons, donc, deux modles pour caractriser cette consommation dnergie.

Le premier modle connu sous le nom dAdaptation des vitesses (Speed Scaling en anglais) considre des machines capables de modier leurs vitesses dexcution des tches dune faon dynamique et tout moment. Lide consiste adapter la vitesse de chaque machine suivant le prol des tches qui lui sont soumises de faon prserver une certaine qualit de service requise. Cette adaptation des vitesses inue considrablement sur les niveaux de consommation dnergie tant donne que, dans le cas gnral, moins la vitesse dune machine est importante moins dnergie sera consomme. Le deuxime modle que nous considrons est connu sous le nom de Gestion des tats de veille (Power Down Management en anglais). Dans ce modle, les machines tournent des vitesses constantes et donc les dures des tches sont leur tour constantes. Cependant, chaque machine est caractrise par un ou plusieurs tats de veille dans lesquels elle peut transiter dans le cas o lensemble des tches excuter devient vide. Durant ces tats de veille, les machines passent des niveaux de consommation dnergie bas, voire nuls. Par contre, une quantit dnergie xe est ncessaire si une machine passe dans un tat actif pour reprendre lexcution des tches. Dans ce cas, la question est de dterminer quels moments il serait intressant de changer les tats des machines et comment ordonnancer les tches pour proter au mieux de ces tats de basse consommation. Une ide intuitive consiste minimiser le nombre de passages entre tats actifs et tats de veille et maximiser la dure des intervalles o le systme est au repos. Il sagit donc de concevoir des algorithmes qui orent des compromis entre la qualit de services demande par les utilisateurs et lnergie consomme par les machines.

Des problmes doptimisation classiques Comme nous lavons mentionn prcdemment, nous nous intressons deux problmes classiques doptimisation combinatoire. Le premier problme est un problme dordonnancement de tches sur des machines parallles non identiques, et en prsence de contraintes de prcdence et de temps de communication. En eet, ltude de ce type de problmes prsente un intret dans la mesure o les architectures avec

plusieurs machines ou entits de calcul ne cessent de se dvelopper. Au cours de lexcution dun programme sur une telle architecture, dite parallle, il est ncessaire de prvoir des dlais supplmentaires entre les tches dpendantes qui sexcutent sur des machines direntes. Ces dlais de communication sont ncessaires pour transfrer les rsultats fournis par une tche une autre tche dpendante an que cette dernire puisse commencer son excution sur une machine dirente. Lexcution de ces tches sur la mme machine implique labsence des temps de communication du fait que ceux-ci deviennent ngligeable compars aux dures dexcution des tches. Notons, par ailleurs, que dans les calculs parallles, une grande partie de la complexit est due la communication entre les machines. Il sagit, donc, de traiter un problme dordonnancement avec des contraintes classiques de dpendance entre tches, auxquelles sajoutent des dlais supplmentaires appel communment temps de communication. Dans le monde informatique, ce type de problme est souvent rencontr lorsquil est question de modliser lexcution dapplications sur un rseau de processeurs tel que les grilles de calcul. Le deuxime problme est connu sous le nom du problme de placement de donnes et consiste rpliquer un ensemble de chiers sur des machines connectes par un rseau de faon minimiser le cot daccs des dirents utilisateurs aux direntes donnes demandes. Ce type de problme est pos essentiellement dans le contexte des rseaux de partage distribus grande chelle tels que les rseaux pair--pair. Lintrt majeur de la rplication des donnes dans ce type de rseau rside dans lamlioration de la qualit de service caractrise par un accs rapide aux donnes en plus de la abilit et de la tolrance aux fautes du service. Par consquent, la consommation de la bande passante au niveau des serveurs contenant les donnes originales diminue dune faon considrable.

Organisation de la thse Cette thse est divise en deux parties indpendantes. La premire partie stend sur les trois premiers chapitres et traite des problmes dordonnancement avec minimisation de lnergie

consomme. La deuxime partie considre des problmes doptimisation classiques : un problme dordonnancement sur des machines non identiques avec des contraintes de prcdence et des temps de communication, et un problme de placement de donnes dans un rseau pair--pair.

Dans le chapitre 1, nous considrons le modle dadaptation des vitesses (Speed Scaling) et nous traitons le problme dordonnancement dun ensemble de tches sur des machines parallles et identiques. Nous supposons que la premption et la migration des tches sont autorises, cest dire que lexcution dune tche peut tre interrompue et continue plus tard sur la mme ou une autre machine. Nous supposons aussi que chaque tche possde une date darrive et une date dchance. Lobjectif consiste donc minimiser lnergie totale consomme par toutes les machines tout en respectant les contraintes dchances des tches. Nous proposons un algorithme polynomial capable de rsoudre ce problme dune faon optimale. Notre approche consiste dduire la structure de toute solution optimale laide dune formulation convexe du problme, et de le rduire en un problme de recherche de ots maximums dans un graphe construit partir dune instance du problme original. Notons que dune manire indpendante Albers et al. [5] ont galement propos un algorithme optimal pour ce problme.

Dans le chapitre 2, nous tudions un cas plus labor o le modle dadaptation des vitesses (Speed Scaling) et le modle de gestion des tats de veille (Power Down Management) sont considrs la fois. Dans ce chapitre, nous considrons une seule machine pouvant changer dynamiquement sa vitesse dexcution et pouvant aussi passer dans un tat de veille o lnergie consomme est nulle. Le problme consiste ordonnancer un ensemble de tches avec des dates darrive et dchance agrables2 dans le but de minimiser lnergie consomme par la machine en question. Nous proposons ainsi une solution optimale base sur la programmation dynamique. Notons que Albers et al. [4] ont prouv rcemment que le problme gnral est NP-dicile.
2

Dans un problme dordonnancement, une instance est dite agrable si pour chaque paire de tches (i, j) avec des r j si et seulement si di dj.

dates darrive (resp. dchance) ri et r j (resp. di et d j ), ri

Dans le chapitre 3, le problme tudi consiste ordonnancer un ensemble de tches sur des machines parallles non uniformes sans premption ni migration. Dans le modle que lon considre, chaque machine peut modier sa vitesse qui sera slectionne parmi un ensemble ni de vitesses possibles et chaque tche est caractrise par une pondration qui indique son importance, une date darrive qui dpend de la machine laquelle elle est aecte et une dure dexcution et une quantit dnergie qui sont fonctions la fois de la machine daectation et de la vitesse dexcution de la tche. Par ailleurs, nous supposons que chaque tche est excute une vitesse constante. Le but est, donc, la minimisation de la somme des temps de compltude pondrs plus lnergie totale consomme par les machines. Ce problme tant NP-dicile, nous prsentons une extension dun algorithme dapproximation propos par Andreas Schulz et Martin Skutella pour rsoudre le problme R|r j | w jC j [75]. La technique utilise repose sur

larrondi alatoire dune solution optimale dune relaxation linaire du problme et elle permet de construire une solution approche. De plus, nous utilisons la mme technique pour approcher le problme de minimisation de la somme des temps de compltude pondrs avec un budget dnergie xe ne pas dpasser.

Dans le chapitre 4, nous tudions un problme classique qui consiste construire un ordonnancement ralisable sur un ensemble de machines ddies. Les tches considres sont de dures unitaires et elles sont relies par un graphe de prcdence ayant la structure dun ordre dintervalles. Nous supposons que chaque tche possde une date darrive et une date dchance, et nous considrons des dlais de communication entre les tches relies par des contraintes de prcdence et sexcutant sur des machines direntes. De plus, nous considrons des tches types dans le sens o chaque tche ne peut tre excute que par un sous ensemble de machines spcialises. Notons par ailleurs quune machine est dite ddie lorsquelle est la seule tre spcialise dans lexcution dun type donn de tches. Nous montrons, tout dabord, que le problme est NP-complet dans le cas o les dlais de

communication sont quelconques. Ensuite, nous faisons lhypothse que ces dlais de communication sont monotones et nous construisons une extension dun algorithme de liste prsent par Leung et al. [62]. Nous prouvons que, sous cette hypothse, lextension de lalgorithme de Leung et al. rsout notre problme de dcision en un temps polynomial. Finalement, nous montrons par un simple contre exemple que dans le cas de grands temps de communication, il nest pas possible de construire un algorithme de liste pour rsoudre la variante du problme o il existe plusieurs machines identiques spcialises pour lexcution dun type donn de tches. Nanmoins, la question reste ouverte lorsque les temps de communication sont unitaires.

Dans le chapitre 5, nous nous consacrons ltude du problme de placement de donnes dans un rseau de partage de type pair--pair. Ce problme consiste rpliquer au niveau de chaque noeud du rseau un ensemble de chiers de faon minimiser le cot daccs total de tous les noeuds lensemble des donnes requises par chacun des noeuds. Par ailleurs, nous supposons que la capacit de stockage de chaque noeud du rseau est limite. Dans sa forme la plus gnrale, Baev et al. ont montr dans [17] quil nexiste pas de schma dapproximation polynomial pour ce problme moins que que P = NP. Nous nous limitons alors des topologies particulires du rseau (les chanes, les anneaux et les toiles gnralises) pour lesquelles nous dcrivons des algorithmes optimaux bass sur la programmation dynamique. Nous montrons ensuite quil nest pas possible dtendre cette approche dans le cas dune topologie quelconque avec un nombre constant de noeuds de degr suprieur ou gal 3.

Enn dans la conclusion, nous rsumons lensemble des travaux eectus et nous prsentons quelques perspectives qui nous semblent intressantes.

O :

1.1

I
Lecacit nergtique des systmes informatiques est devenue un axe de recherche

important durant ces dernires annes. Des mcanismes prometteurs ont t mis en place dans le but de rduire ecacement lnergie consomme par les units de calcul allant des petits appareils portatifs jusquaux grands centres de donnes. Dun point de vue algorithmique, de nouveaux problmes doptimisation apparaissent o la consommation dnergie est prise en compte en tant que contrainte du problme ou en tant que fonction objectif [3]. Cette dernire approche a t adopte par Yao et al. dans un papier prcurseur [83] o il sagit dordonnancer un ensemble de tches indpendantes caractrises par leurs dates darrive et leurs dates dchance sur une machine unique qui peut faire varier sa vitesse de manire dynamique dans le but de minimiser lnergie totale consomme. Ce modle est connu sous le nom de Speed Scaling ou adaptation de la vitesse. Dans ce modle, si la machine fonctionne une petite vitesse alors lnergie consomme est faible, mais la qualit de lordonnancement retourn risque dtre mauvaise. Il sagit donc dadapter dune faon dynamique la vitesse an de trouver un compromis permettant de rduire lnergie dpense tout en prservant une bonne qualit de lordonnancement.

Le modle de calcul de lnergie le plus tudi dans la littrature est dni comme suit : si la vitesse dune machine est gale une valeur v pendant une dure donne , alors la puissance de consommation dnergie est donne par v pour une constante > 1, et lnergie totale consomme est v [39]. Si nous supposons, maintenant, que la vitesse de la machine est donne par une fonction du temps, v(t), alors lnergie totale consomme pendant la dure est calcule par intgration de la puissance sur la dure :

v(t) dt. Il faut noter que la forme de la

fonction de la puissance de consommation dnergie implique quune petite augmentation de la vitesse peut causer une croissance importante dans la dpense de lnergie par le systme. Dans un problme dordonnancement, chaque tche est caractrise par une quantit de travail qui modlise le nombre de cycles processeur requis pour lexcuter en entier. La dure totale de cette tche dpend, donc, de la vitesse du systme. Soit une tche i et notons par wi sa quantit de travail. Si cette tche est excute sur une machine qui tourne une vitesse v, alors elle aura besoin de wi /v units de temps pour nir et lnergie consomme par la machine est Ei = v . wi . La gure 1.1 montre linuence du choix de la vitesse sur lnergie consomme. v Dans cet exemple nous considrons deux tches i et j avec des quantits de travail wi = 6 et w j = 24, des dates darrive ri = 0 et r j = 5, et des dates dchance di = 4 et d j = 13. Nous considrons aussi une fonction de puissance P(v) = v3 . Par ailleurs, nous supposons que chaque tche est excute une vitesse constante et nous prsentons deux ordonnancements ralisables dans lesquels nous modions les vitesses dexcution des tches et nous montrons que le systme conomise davantage dnergie en diminuant les vitesses dexcution. Notons que dans cet exemple, la quantit de travail de chaque tche est gale la surface du rectangle correspondant.

Cas dune seule machine. Dans [83], Yao et al. ont propos un algorithme fondamental connu sous le nom de "YDS" selon les initiales des auteurs. Cet algorithme rsout en un temps polynomial et dune faon optimale le problme o-line de minimisation dnergie sur une seule machine avec premption, i.e. lexcution dune tche quelconque peut tre interrompue et reprise plus tard. Ils ont galement considr dans le mme papier le cas on-line pour lequel ils ont propos

10

vitesse 4 2

wi = 6, ri = 0, di = 4 w j = 24, r j = 5, d j = 13 P(v) = v3 j
temps

i
0
vitesse 3 5

Ordonnancement 1 vi = 2 et v j = 4 nergie = 24 + 384 = 408

11

3
3 2

j i
0 4
5 13 temps

Ordonnancement 2 3 vi = 2 et v j = 3 nergie = 13.5 + 216 = 229.5

F. 1.1 Inuence du choix des vitesses sur lnergie consomme. deux algorithmes : le premier not "AVR" (Average Rate) est 21 -comptitif par rapport lnergie, et le deuxime, not "OA" (Optimal Available). Dans [18], Bansal et al. ont prouv laide dune fonction de potentiel que lalgorithme OA est -comptitif, et ils ont dcrit un
nouvel algorithme on-line "BKP" avec un rapport de comptitivit gal 2( 1 ) e et amliorant

ainsi la qualit de OA pour des grandes valeurs de .

Cas de plusieurs machines. Dans ce cas, il est possible de distinguer deux variantes direntes du modle dadaptation de la vitesse (Speed Scaling). La premire variante note variante sans migration, autorise la premption des tches mais nautorise pas la migration. Ceci implique que lexcution de toute tche peut tre interrompue et reprise plus tard sur la mme machine et il nest pas autoris que cette reprise ait lieu sur une autre machine. Dans la seconde variante avec migration, la premption et la migration des tches sont toutes les deux autorises. Il faut noter cependant que, dans tous les cas, lexcution parallle des tches nest permise, i.e. chaque instant aucune tche ne peut tre excute simultanment sur deux machines direntes. Dans [7], Albers et al. ont considr la variante sans migration du problme de minimisation de lnergie. Dans le cas o les tches possdent des quantits de travail unitaires et des

11

dates darrive et dchance agrables, les auteurs ont propos un algorithme polynomial bas sur la politique Round Robin pour laectation des tches aux machines. Par ailleurs, si les dates darrive et dchance sont quelconques, alors le problme devient NP-dicile mme pour des quantits de travail unitaires. Dans ce dernier cas, Albers et al. ont dcrit lalgorithme approch "CRR" (Classied Round Robin) qui a un rapport dapproximation gal 24 . Dans le cas o toutes les tches partagent la mme date darrive ou dchance, les auteurs ont propos un autre algorithme dapproximation "EDL" (Earliest Deadline and List scheduling) pour des quantits de travail quelconques o le rapport dapproximation est 2(2
1 m) ,

m tant le nombre de machines

de linstance. Dans [43], Greiner et al. prsentent une rduction gnrique transformant tout algorithme -approch pour le problme sur une seule machine en un algorithme B-approch pour le problme sur plusieurs machines sans migration, o B est le me nombre de Bell1 . Ils ont montr galement quune -approximation pour le problme plusieurs machines avec migration conduit une B-approximation pour le problme plusieurs machines sans migration. Maintenant, dans le contexte de plusieurs machines avec migration, Chen et al. [34] ont initi ltude du problme de minimisation de lnergie consomme et ils ont dcrit un algorithmme optimal simple dans le cas o toutes les tches sont disponibles au mme instant et partagent la mme date dchance. Dans [21], Bingham et al. ont montr que la version o-line du problme peut tre rsolu dune faon polynomiale. Cependant, lalgorithme quils ont propos est bas sur la programmation linaire et selon les auteurs sa complexit peut tre assez leve. Au moment de lachvement de cette tude, un papier de Albers et al. [5] est apparu o les auteurs ont considr le mme problme savoir lordonnancement de tches avec des dates darrives et des dates dchances quelconques sur un ensemble de machines identiques avec migration et dans le but de minimiser lnergie totale consomme. Albers et al. ont utilis une approche combinatoire similaire la notre base sur le calcul de ots maximums et ils ont propos un algorithme polynomial dont la complexit est en O(n2 C(n, n2 )), avec C(x, y) est la complexit ncessaire pour calculer un
1

Si on considre un ensemble E de cardinal n, alors le nme nombre de Bell, not Bn, est le nombre de partitions de
n k k=0 C n Bk .

E. Les nombres de Bell satisfont la formule de rcurrence : Bn+1 = lensemble vide et il est gal B0 = 1.

Le premier nombre de Bell correspond

12

ot maximum dans un graphe en couche avec n sommets et y arcs. Par ailleurs, les auteurs ont tendu lanalyse des algorithmes on-line sur une seule machine AVR et OA [83] dans le cas de plusieurs machines avec migration.

1.1.1 Contribution et organisation du chapitre

Dans ce chapitre, nous considrons le modle dadaptation de la vitesse (speed scaling) et nous tudions le problme dordonnancement sur plusieurs machines identiques avec comme objectif la minimisation dnergie lorsque la migration des tches est autorise. Dans la section 1.3, nous formulons le problme en programme convexe et nous appliquons, ensuite, les conditions de Karush-Kuhn-Tucker (conditions KKT) [54, 57] an dobtenir des proprits ncessaires loptimalit de toute solution du problme. Ensuite, nous dcrivons dans la section 1.4 un algorithme combinatoire optimal bas sur le calcul de ots maximums et nous dtaillons sa complxit.

1.2

D `
Nous considrons lensemble des tches J= {J1 , . . . , Jn }, tel que chaque tche Ji

soit caractrise par une quantit de travail wi , une date darrive ri et une date dchance di . Notons que toutes ces valeurs sont positives et non nulles. Ainsi, une tche Ji est dite disponible linstant t si t [ri , di ) et nous dnissons sa densit i =
wi di ri .

Nous considrons, aussi, m

machines homognes telles que chaque machine soit capable de varier dynamiquement sa vitesse dexcution. Nous supposons que sur chaque machine le spectre des vitesses autorises est continu et non born et que la consommation dnergie est donne par une fonction de puissance convexe P(v) = v , v tant la vitesse dexcution et une constante strictement suprieure 1. Plus prcisment, si une tche Ji J est excute sur une machine qui tourne une vitesse constante vi durant un intervalle de temps de longueur , alors la quantit de travail ectue est vi . et P(s). units dnergie sont consommes. Dune faon plus gnrale, il est clair que lnergie est la puissance intgre sur le temps. Ainsi si nous considrons qu chaque instant t correspond une vitesse v(t) sur une machine quelconque k, alors le travail total eectu est gal et lnergie totale consomme est
|| ||

v(t)dt

v(t) dt, o || reprsente la dure dun ordonnancement 13

quelconque sur la machine k.

Dans notre modle, nous supposons que la premption et la migration sont autorises, i.e. lexcution dune tche peut tre suspendue et reprise ultrieurement sur la mme machine ou sur une autre machine. Cependant, lexcution parralle nest pas autorise dans le sens o aucune tche ne peut tre excute simultanment sur deux ou plusieurs machines direntes. Notre objectif est de construire un ordonnancement ralisable qui minimise lnergie totale consomme par toutes les machines.

Nous dnissons R= {t0 , . . . , tL } comme tant lensemble des dates darrive et dchance des tches dans J considres dans lordre croissant et sans doublons. Il est clair que t0 = minJi J {ri } et que tL = maxJi J {di }. Pour tout 1 j L, nous considrons lintervalle I j = [t j1 , t j ), et soit

lensemble I= {I1 , . . . , IL }. Nous notons par |I j | la longueur de lintervalle I j . Dautre part, pour tout 1 j L, soit D j lensemble de toutes les tches disponibles durant lintervalle I j , i.e. toutes

les tches i telles que I j [ri , di ), et soit |D j | sa cardinalit. tant donn un ordonnancement , on dnit ti, j () la dure totale dexcution de la tche Ji durant lintervalle I j dans lordonnancement .

1.3

C`
Le but de cette partie est de dduire les proprits dun ordonnancement optimal

pour le problme de minimisation de lnergie sur des machines parallles avec migration.

1.3.1 Un programme convexe

Nous formulons notre problme par un programme convexe ce qui nous permettra, ensuite, dappliquer les conditions de KarushKuhnTucker (KKT) an dobtenir des conditions ncessaires doptimalit. Nous montrons, par la suite, que ces conditions sont susantes pour quun ordonnancement ralisable soit optimal. 14

Pour chaque tche Ji J et pour chaque intervalle I j tel que Ji D j nous introduisons les variables vi et ti, j et qui dnissent respectivement la vitesse de la tche Ji et la dure dexcution totale de la tche Ji pendant lintervalle I j . Le programme convexe est dcrit comme suit :

min
Ji J

wi v1 i

(1.1)

wi ti, j vi I : J D
j i j

0 0 1

Ji J j L

(1.2) (1.3)

ti, j m |I j |
Ji D j

ti, j |D j | |I j |
Ji D j

0 0 0 0 1 1

1 j j

(1.4) (1.5) (1.6) (1.7)

ti, j |I j | ti, j vi

L, Ji D j L, Ji D j Ji J

Il faut noter que le temps dexcution total et la consommation de lnergie totale de chaque tche Ji est donn, respectivement par
wi vi

et wi v1 . Il sagit donc de minimiser la fonction i

objectif : lnergie totale consomme par toutes les tches, et qui est exprime dans la ligne 1.1 du programme convexe. Les contraintes 1.2 expriment le fait que chaque tche doit tre excute entirement, i.e. une quantit de travail wi doit tre excute pour chaque tche Ji J une vitesse constante vi . Les contraintes 1.3 et 1.4 garantissent que durant chaque intervalle I j I au plus min{m, |D j |} machines peuvent tre utilises. Dautre part, lensemble des contraintes 1.5 empchent toute tche Ji dtre excute pendant plus que |I j | units de temps durant tous les intervalles I j [ri , di ) an dviter le risque dexcution parallle. Finalement, les contraintes 1.6 et 1.7 impliquent que les variables du programme convexe sont positives.

15

Prcisons quil sagit bien dun programme convexe tant donne que la fonction objectif dans la ligne 1.1, ainsi que le premier ensemble de contraintes dans la ligne 1.2 sont convexes. Toutes les autres contraintes sont linaires. De ce fait, il est possible de rsoudre ce programme convexe en utilisant la mthode de lEllipsode [68]. Cependant, nous nous proposons de construire un algorithme combinatoire plus simple et surtout plus ecace.

1.3.2 Les conditions KKT

Nous appliquons les conditions KKT au programme convexe dcrit ci-dessus an dobtenir des conditions ncessaires doptimalit de toute solution ralisable. Nous montrons, par la suite, que ces conditions susent pour quun ordonnancement donn soit optimal. Nous donnons, tout dabord, une dnition concise des conditions KKT.

La formulation gnrale dun programme convexe est donne par :

min f (x) gi (x) 0 1 1 i j q r

h j (x) = 0 x Rn

Supposons que ce programme soit strictement ralisable dans le sens o il existe une solution x Rn telle que gi (x ) < 0 et h j (x ) = 0 pour tout 1 i q et 1 j r, o gi et h j sont

direntiables en x . Soit i et j les variables duales associes, respectivement, aux contraintes gi (x) par : 0 et h j (x) = 0. Dans ce cas, les conditions de Karush KuhnTucker (KKT) sont donnes

16

gi (x)

1 1 1 1

i j i i

q r q q

(1.8) (1.9) (1.10) (1.11) (1.12)

h j (x) = 0 i 0

i gi (x) = 0
q m

f (x) +
i=1

i gi (x) +
j=1

j h j (x) = 0

Ces conditions sont ncessaires et susantes pour que des solutions x Rn , = ( , , . . . , ) Rq et = ( , , . . . , ) Rr soient primales et duales optimales. Les condir q 1 2 1 2 tions 1.8 et 1.9 garantissent ladmissibilit de la solution du problme primal et lensemble des conditions 1.10 garantissent ladmissibilit de la solution du problme dual. Les conditions 1.11 sont dites conditions de complmentarit et les conditions 1.12 reprsentent les conditions stationnaires. Le lemme suivant rsulte de lapplication des conditions KKT la formulation convexe de notre problme. Lemme 1 Chaque ordonnancement optimal du problme de minimisation dnergie sur des machines parallles avec migration satisfait les proprits suivantes : 1. Chaque tche Ji est excute une vitesse constante vi . 2. Pour tout intervalle I j , on a 3. Si |D j |
Ji D j ti, j

= min{|D j |, m}.|I j |.

m durant un intervalle I j , alors ti, j = |I j |, pour chaque tche Ji telle que I j [ri , di ).

4. Si |D j | > m alors i Toutes les tches Ji disponibles durant I j , avec 0 < ti, j < |I j |, sont excutes la mme vitesse. ii Si une tche Ji nest pas excute durant un intervalle I j [ri , di ), i.e. ti, j = 0, alors vi vk pour chaque tche Jk telle que I j [rk , dk ) et tk, j > 0. vk pour chaque

iii Si une tche Ji vrie ti, j = |I j | pour un intervalle I j donn, alors vi tche Jk disponible durant I j avec tk, j < |I j |. 17

Preuve Soit une instance du problme avec migration et supposons, par contradiction, quil existe un ordonnancemment optimal tel que au moins une tche est excute avec plusieurs vitesses direntes. Soit Jk une telle tche et supposons quil existe un ensemble de vitesses { 1 , . . . , un ensemble de dures {1 , . . . , L } tel que la tche Jk soit excute la vitesse de temps pour tout 1 donne par E (Jk ) = i
i L}

et

pendant i units

L. Ainsi, lnergie totale dpense par lexcution de la tche Jk est

L i=1 i .i .

Soit un ordonnancement identique avec la seule dirence que la tche Jk est excute la vitesse constante vk =
L i=1 i .i L i=1 i

pendant les mmes intervalles de temps. Il est clair que reste

L i=1 i .i

un ordonnancement ralisable tant donn que

constitue la quantit de travail de la tche

L i=1 i .

Jk . Par ailleurs, la nouvelle nergie consomme par Jk est donne par E (Jk ) = v . k

tant donne que la fonction de puissance P(v) = v , pour > 1, est strictement convexe, il en dcoule que pour toute ensemble {1 , . . . , L }, tel que i [0, 1]1 i L et
L i=1 i

= 1, on a :

P(1 v1 + . . . + L vL ) < 1 P(v1 ) + . . . + L P(vL ) Ceci implique que :

P(

1 L j=1

v1 + . . . +

L vL ) L j=1 j

<

1 P(v1 ) L j=1 j

+ ... +

L P(vL ) L j=1 j

j P(vk ) < 1 P(v1 ) + . . . + L P(vL )

j=1

E (Jk ) < E (Jk ) Do une contradiction vis vis de loptimalit de , et la premire proprit est donc vrie.

Considrons, maintenant un intervalle quelconque I j I. tant donn que pour toute tche Ji D j , ti, j |I j |, il est clair que
Ji D j ti, j

min{|D j |, m}.|I j |.
Ji D j ti, j

Supposons par contradiction quil existe un ordonnancement optimal tel que

<

min{|D j |, m}.|I j |. Il est possible de transformer la partie de lordonnancement qui est rstreinte lintervalle I j de faon ce que toutes les tches soient excutes dans un ordre quelconque sans 18

premption et sans priode dinactivit entre la n dune tche et le dbut de la tche suivantes. Au niveau de chaque machine, sil existe des tches excuter, alors lexcution commence toujours au dbut de lintervalle I j et on a recours la migration des tches chaque fois que cest necssaire, i.e. chaque fois que la taille de la partie encore disponible de lintervalle I j sur une machine donne m p ne permet pas dexcuter une tche Jk en sa totalit. Dans ce cas, Jk dbute sur la machine m p et se termine sur la machine m p+1 . La forme de cet ordonnancement est schmatise dans lexemple de la gure 1.2.

J1 J4 J6

J2

J3 J5 J7 Ij J6

J4

m1 m2 m3

F. 1.2 Exemple dordonnancement sans premption durant un intervalle I j sur 3 machines. tant donn que
Ji D j ti, j

< min{|D j |, m}.|I j |, alors il existe au moins une tche Jk dans

lordonnancement obtenu qui commence son excution au dbut de lintervalle I j et telle que tk, j < |I j |. Pour le mme argument, il existe aussi au moins une machine o aucune tche nest excute durant un intervalle = [t j , t j ) pour une valeur > 0 arbitrairement petite (t j est la borne suprieure de I j ). Il est donc possible de rduire la vitesse de la tche Jk en faisant tendre son excution sur lintervalle pour une valeur adquate de . On obtient ainsi un nouvel ordonnancement avec une consommation dnergie moins importante. Do une contradiction de loptimalit de lordonnancement et ceci valide la deuxime proprit.

La troisime proprit est une consquence de la deuxime proprit. En eet, si |D j | alors

Ji D j ti, j

m,

= |D j ||I j |. Supposons donc par contradiction quil existe une tche Jk D j telle
Ji D j ti, j

que tk, j < |I j |. Dans ce cas, on a

< |D j ||I j |, ce qui contredit la deuxime proprit.

Nous nous proposons maintenant dappliquer les conditions KKT au programme convexe d-

19

ni prcdemment pour prouver les proprits 4(i), 4(ii) et 4(iii). Ainsi, nous associons les variables duales i , j , j , i, j , i, j et i respectivement aux ensembles des contraintes allant de 1.2 1.7. Par les conditions stationnaires 1.12 on a :

Ji J L

wi v1 + i
Ji J L

wi ti, j vi I : J D
j i j

+
j=1 L

j
Ji D j

ti, j m |I j | +
j=1 L

j
Ji D j

ti, j |D j | |I j |

+
j=1 Ji D j

i j (ti, j |I j |) +
j=1 Ji D j

i j (ti, j ) +
Ji J

i (vi ) = 0

Cette equation peut tre reformule comme suit :

i + j + j + i, j i, j ti, j
j=1 Ji D j

+
Ji J

( 1)wi s2 i

i wi i si = 0 v2 i

(1.13)

De plus, les conditions de complmentarit 1.11 impliquent que :

i j

wi ti, j = 0 vi I : J D
j i j

Ji J 1 1 1 1 j j j j L L

(1.14) (1.15) (1.16) (1.17) (1.18) (1.19)

ti, j m |I j | = 0
Ji D j

j
Ji D j

ti, j |D j | |I j | = 0 i j (ti, j |I j |) = 0 i j (ti, j ) = 0 i (vi ) = 0

L, Ji D j L, Ji D j Ji J

Il est possible de supposer quil nexiste aucune tche avec une quantit de travail nulle. Ainsi, pour toute tche Ji , il est vrai que vi > 0 et que implique que i = 0, 1 i
I j [ri ,di ) ti, j

> 0. De ce fait, lquation 1.19

n. En annulant les drivs partielles vi et ti, j dans 1.13, nous

20

obtenons i = ( 1)v pour chaque tche Ji J et i ( 1)v = j + j + i, j i, j i (1.20)

pour chaque tche Ji J et I j [ri , di ). Pour chaque intervalle I j , D j > m. A partir de lquation 1.16 et de la deuxime proprit, on dduit que j = 0. Considrons maintenant les cas suivants obtenus en fonction de la dure dexcution de chaque tche Ji D j : 1. Cas 1 : 0 < ti, j < |I j | Les conditions complmentaires 1.17 et 1.18 impliquent que i, j = i, j = 0. Ainsi, 1.20 devient : ( 1)v = j i La variable j est specique pour chaque intervalle I j et donc, toutes les tches dans ce cas possdent la mme vitesse durant tout lordonnancement et la proprit 4(i) est vrie. Nous allons not cette vitesse par v(I j ) pour chaque intervalle I j . 2. Cas 2 : ti, j = 0 Ceci implique, par 1.17, que i, j = 0 et 1.20 peut tre exprime par : ( 1)v = j i, j i de ce fait, comme i, j 0, nous avons vi v(I j ) pour toute tche Ji de ce type. Do la

proprit 4(ii) est vrie. 3. Cas 3 : ti, j = |I j | Dans ce cas, par 1.18, nous obtenons i, j = 0. Ainsi, 1.20 devient : ( 1)v = j + i, j i cause des conditions dadmissibilit duales 1.10, i, j type ont des vitesses vriant vi 0. Do, toutes les tches de ce

v(I j ), et la proprit 4(iii) est donc valide.

21

Lemme 2 Les proprits numres dans le lemme 1 sont susantes pour loptimalit dune solution du problme. Preuve Supposons, par contradiction, quil existe un ordonnancement A non optimal et qui satisfait les proprits du lemme 1 et considrons, aussi, un autre ordonnancement optimal B satisx faisant les mmes proprits. Notons par E x , vix et ti, j , respectivement, lnergie consomme, la

vitesse de la tche Ji et le temps dexcution total de Ji durant lintervalle I j dans un ordonnancement donn X. Ainsi, on a E A > E B . Soit S lensemble de toutes les tches Ji telles que viA > viB .
A B Il est clair quil existe au moins une tche Jk telle que vk > vk car sinon lordonnancement A ne

consommerait pas plus dnergie que lordonnancement B. Ainsi, S nous avons :

et par dnition de S

A ti, j < Ji S I j :Ji D j Ji S I j :Ji D j

B ti, j

Il existe, donc, au moins un intervalle I p tel que :

A ti,p < Ji S Ji S

B ti,p

Ceci implique que

A tk,p

<

B tk,p

B A pour Jk S . Ainsi, tk,p < |I p | et tk,p > 0. Soit un intervalle

quelconque I j , la somme des temps dexcution de toutes les tches dans I j est constante pour tout ordonnancement vriant les proprits du lemme 1. Ainsi, il existe forcment une tche J S

A B A B telle que t,p > t,p . Donc, t,p > 0 et t,p < |I p |. Par la proprit 4(iii) du lemme 1, nous concluons A que v B A vk > vk B v , or ceci contredit le fait que J

S.

Il reste remarquer que les proprits des solutions optimaux cites dans le lemme 1 ne permettent pas daboutir directement la solution optimale mais peuvent, en revanche, nous guider pour construire un ordonnancement optimal. Il sagit, en eet, dattribuer chaque tche une vitesse constante et de spcier lensemble des tches qui seront excutes dans chaque intervalle de temps et sur chaque machine.

22

1.4

Dans cette partie, nous proposons un algorihme combinatoire pour rsoudre le problme de minimisation dnergie sur des machines identiques avec migration. Cet algorithme construit toujours un ordonnancement qui satisfait les proprits du lemme 1 pour toute instance du problme. Comme nous lavons dj mentionn prcdement, ces proprits sont ncessaires et susantes pour loptimalit, ce qui impliquerait que notre algorithme retourne toujours une solution optimale.

Cet algorithme, bas sur la notion de "tches critiques" que nous allons dnir par la suite, procde par tapes. Il sagit, chacune des tapes, de diminuer la taille de lensemble des tches ordonnancer en dtectant un sous ensemble de tches critiques auxquelles nous attribuons une unique vitesse constante dite "vitesse critique". Au terme de cette boucle, une vitesse constante si est attribue chaque tche Ji . La recherche des vitesses (et des tches) critiques repose sur le calcul de ot maximum dans un graphe orient correspondant linstance en cours de rsolution. Cette procdure correspond la rsolution dune instance du problme not "AVC" et qui sera dcrit en dtail dans cette partie. ce stade de lalgorithme, la dure dexcution de chaque tche Ji est donne par wi /si et nalement nous obtenons une instance du problme dordonnancement classique P|ri , di , pmtn| dans lequel on doit dcider sil existe un ordonnancement ralisable avec premption et migration dun ensemble de tches caractrises par leurs dures, leurs dates darrive et leurs dates dchance sur un ensemble de m machines identiques. Ce problme peut tre rsolu en temps polynomial en le reformulant comme un problme de ot maximum [69].

1.4.1 Le problme de ot-max/coupe-min

Dans ce qui suit, nous prsentons, brivement, quelques notations et dnitions concernant les problmes de ot maximum et de coupe minimale. Soit un graphe G = (V, A) orient dans lequel chaque arc (u, v) A possde une capacit c(u, v), et soit deux noeuds s, p V. Une (s, p)-coupe

23

de G est une partition des noeuds du graphe en 2 sous-ensembles disjoints X et Y tels que s X et p Y et tels que la suppression de tous les arcs (u, v) avec u X et v Y entrane la suppression de tous les chemins entre les noeuds s et p. Une (s, p)-coupe (X, Y) est dite minimale si la somme des capacits de tous les arcs (u, v) avec u X et v Y est minimale. Dans la suite, si nous parlons dune coupe alors il sera fait rfrence lensemble des arcs qui la forme.

Un (s, p)-ot F dans le graphe G est tout simplement une quantit de mme unit que la capacit des arcs faire passer du noeud s au noeud p travers le graphe G. Nous notons |F | le cot du ot F et qui nest autre que le ot sortant de s (gal au ot entrant en p). Nous utilisons, aussi, le terme f (u, v) pour reprsenter la quantit du ot passant par larc (u, v) A. Par ailleurs, chaque ot F doit satisfaire les proprits suivantes :

i f (u, v)

c(u, v), pour tout arc (u, v) A,

ii f (u, v) = f (v, u), pour tout arc (u, v) A,

iii
vV (u,v)A

f (u, v) =
wV (w,u)A

f (w, u), pour tout noeud u V,

iv
vV (s,v)A

f (s, v) =
wV (w,p)A

f (w, p) = |F |.

Etant donn un graphe G et un ot F , nous dnissons galement, le graphe rsiduel correspondant G f comme suit :

i G f possde le mme ensemble de noeuds que le graphe G,

ii pour chaque arc (u, v) A, tel que f (u, v) < c(u, v), on rajoute G f larc (u, v) avec une capacit gale c(u, v) f (u, v),

24

iii Pour chaque arc (u, v) avec f (u, v) > 0, nous incluons G f larc (v, u) auquel on attribue la capacit f (u, v).

Soit un ot F . On dit que ce ot sature un arc (u, v) si f (u, v) = c(u, v). De plus, on considre quun chemin est satur par F sil existe au moins un arc (u, v) dans qui soit satur.

1.4.2 Le problme daectation vitesse constante "AVC"

Nous prsentons dans ce paragraphe le problme daectation vitesse constante "AVC", ainsi que la notion de tches crititques et dinstance critique.

Le problme AVC peut tre vu comme une variante du problme P|ri , di , pmtn| et il peut tre dcrit comme suit : soit une instance du problme initial caractrise par lensemble des tches J, lensemble de m machines et lensemble dintervalles I. Nous rappelons que chaque tche Ji J peut tre disponible dans un ou plusieurs intervalles de I, et nous supposons que durant chaque intervalle I j I, m j m machines peuvent tre utilises. Par ailleurs, soit une constante v > 0.

Le problme AVC consiste donc rpondre la question suivante : existe-il un ordonnancement ralisable qui excute toutes les tches dans J la vitesse v ? Rappelons quun ordonnancement est dit ralisable si et seulement si chaque tche est excute durant ses intervalles de disponibilit et par au plus une machine chaque instant t. Nous prcisons, galement, que la premption et la migration des tches sont autorises. Notons que le problme AVC est similaire au problme de dcision P|ri , di , pmtn| avec la seule dirence que, dans le problme AVC, le nombre de machines m j pouvant tre utilises durant chaque intervalle I j I nest pas constant.

Rduction de AVC en un problme de ot.

Chaque instance du problme AVC peut tre

rduite en une instance du problme de ot maximum comme suit : soit une instance J, I, v du problme AVC. Nous dnissons le graphe correspondant G = (V, E) qui contient un noeud (xi )

25

associ chaque tche Ji J, un noeud (y j ) pour chaque intervalle I j I, un noeud source (s) et un noeud puits (p). Ces noeuds sont relis comme suit :

- Un arc (s, xi ) de capacit wi /v relie la source (s) chaque noeud (xi ), 1

|J|.

- Un arc (xi , y j ) de capacit |I j | relie le noeud (xi ) au noeud (y j ) si la tche Ji est disponible durant lintervalle I j , i.e. Ji D j .

- Un arc (y j , p) de capacit m j |I j | relie chaque noeud (y j ) au noeud puits (p). Ce graphe est schmatis dans la gure 1.3.

y1 |I1 | x1
w1 v

|I2 | |I1 | |I2 | |I3 |

m1 |I1 | y2 m2 |I2 | y3 m3 |I3 | p mL1 |IL1 | |IL1 | yL-1 mL |IL |

w2 v

x2

wn v

xn |IL | yL

F. 1.3 Rduction de linstance (J, I, v) du problme AVC en un problme de ot maximum. Dans cet exemple, les ensembles J = {J1 , . . . , Jn } et I = {I1 , . . . , IL } reprsentent les ensembles de tches et dintervalles correspondant au problme original de minimisation dnergie avec migration. Initialement, toutes les machines sont disponible durant chaque intervalle I j , i.e. m1 = . . . = mL = m.

Nous dnissons, ce stade, les notions de tches critiques et dinstance critique.

26

Dnition 1 Soit J, I, v une instance ralisable du problme AVC. Une tche Jc J est dite critique, si et seulement si, pour chaque solution ralisable et pour chaque intervalle I j [rc , dc ), on a soit tc, j () = |I j |, soit
Ji D j ti, j ()

= m j |I j |.

Dnition 2 Une instance J, I, v du problme AVC est critique, si et seulement si, v est la vitesse minimale qui garantit que cette instance est ralisable. Dans ce cas, la vitesse v est appele vitesse critique pour linstance en question. Dans la suite, nous allons prsenter une suite de proprits relatives au problme AVC, et le but nal sera de trouver les conditions dexistence de tches critiques pour une instance quelconque de AVC, et de concevoir un moyen ecace pour les reprer.

Thorme 1 [69] Soit une instance J, I, v du problme AVC. Il existe un ordonnancement ralisable de J, I, v , si et seulement si, il existe un (s, p)ot maximum dans le graphe correspondant de valeur gale
|J| wi i=1 v .

En se basant sur le thorme 1, il est possible dnoncer le corollaire suivant, Corollaire 1 Soit J, I, v une instance ralisable du problme AVC et soit G = (V, E) le graphe correspondant. Une tche Jc est critique, si et seulement si, sur chaque chemin = (xc , y j , p) avec I j I, un des deux arcs (xc , y j ) ou (y j , p) est satur dans tout ot maximum dans G. Les lemmes suivants impliquent les notions de tche et dinstance critique et ils sont trs utiles dans la recherche dun outil pratique de dtection des tches critiques. Lemme 3 Si J, I, v est une instance critique du problme AVC, alors il existe au moins une tche critique Ji J. Preuve Soit G = (V, E) le graphe correspondant linstance J, I, v . tant donn quil sagit dune instance critique, il existe une (s, p)-coupe minimale C du graphe G qui contient soit un arc (xi , y j ) ou un arc (y j , p), pour une certaine tche Ji J et un certain intervalle I j I. En eet, 27

dans le cas contraire la seule (s, p)-coupe minimale serait celle constitue de tous les arcs de type (s, xi ), et toutes les (s, p)-coupes contenant des arcs de type (xi , y j ) ou de type (y j , p) auront des capacits strictement suprieures la coupe minimale, i.e. strictement suprieures
wi Ji J v .

Or,

ceci implique la possibilit de rduire la vitesse v une vitesse v , pour une certaine valeur > 0 bien choisie, et telle que le graphe correspondant linstance J, I, v admet un (s, p)ot maximum gal
wi Ji J v ,

ce qui contredit le fait que linstance J, I, v est critique.

Considrons maintenant la coupe C dnie prcdemment. Cette coupe contient au moins un arc de type (xi , y j ) ou de type (y j , p) et elle ne peut donc pas contenir tous les arcs de type (s, xi ) car dans ce cas elle aura une capacit strictement suprieure la (s, p)-coupe qui contient uniquement les arcs (s, xi ) ce qui contredit la minimalit de C. Il existe donc au moins un arc (s, xc ) ne faisant pas partie de la coupe C. En se basant donc sur la dnition dune (s, p)-coupe, on conclut que la coupe C contient un arc appartenant chaque chemin de type (xc , y j , p), pour I j I. Ainsi, puisque tout (s, p)-ot maximum sature la coupe C et par dnition, la tche Jc reprsente par le noeud xc est critique.

Remarquons que si J, I, v est une instance critique, alors tout instance J, I, v pour > 0 quelconque nest pas ralisable dans le sens o la vitesse v nest pas susante pour excuter toutes les tches entirement. Bien que les tches critiques ont t dnies dans le cas dinstances ralisables, nous nous proposons dtendre cette notion dans le cas dinstances non ralisables et pour lesquelles nous dnissons les tches critiques exactement de la mme manire que pour les instances ralisables.

Soit une instance critique J, I, v du problme AVC et soit G le graphe correspondant. Nous allons proposer, par la suite, un moyen simple et ecace pour identier les tches critiques de cette instance en utilisant le graphe G qui correspond linstance J, I, v pour une valeur > 0 bien choisie. En eet, cette valeur est dnie de faon ce que les deux instances J, I, v et J, I, v possdent exactement les mmes tches critiques. Dans le lemme suivant, nous

28

prouvons lexistence dune telle valeur. Lemme 4 Soit une instance critique J, I, v du problme AVC. Il existe une constante > 0 telle que linstance non ralisable J, I, v et linstance critique J, I, v possdent exactement les mmes tches critiques. Preuve Dans le but de prouver ce lemme, nous allons construire un ensemble de valeurs possibles de tel quune tche Ji soit critique dans linstance J, I, v si et seulement si elle est critique dans linstance J, I, v .

Linstance J, I, v tant critique, daprs le lemme 3, elle contient au moins une tche critique. Dans le cas o toutes les tches sont critiques, il existe dans le graphe G correspondant linstance J, I, v une (s, p)-coupe minimale C contenant exactement un arc pour chaque chemin de type (xi , y j , p). Pour tout > 0, la coupe C est aussi minimale dans le graphe G qui correspond linstance J, I, v . En eet, la seule dirence entre les graphes G et G rside dans laugmentation des capacits des arcs de type (s, xi ) dans le graphe G , i.e. la capacit passe de wi /v wi /v pour chaque tche Ji J. Ainsi, toutes les tches dans J sont aussi critiques dans linstance J, I, v , et le lemme est prouv dans ce premier cas.

Supposons maintenant quil existe au moins une tche non critique Ji dans linstance J, I, v . Ainsi, il existe au moins un (s, p)-ot maximum dans le graphe G correspondant la tche Ji et que lon note par Fi tel quil existe au moins un chemin = (xi , y j , p) non satur par Fi pour un intervalle I j [ri , di ) (dans le cas contraire tout (s, p)-ot maximum sature tous les chemins de type (xi , y j , p), ce qui implique que la tche Ji est critique). Pour chaque tche non critique Jk , nous allons considrer un (s, p)-ot maximum correspondant Fk tel quil existe au moins un chemin non satur (xk , y j , p) que lon appelle k -chemin. Il faut remarquer que pour deux tches non critiques Jk et Jk il est parfois possible que les ots correspondants Fk et Fk soient identiques. Ensuite, nous dnissons k = min{c(xk , y j ) fk (xk , y j ), c(y j , p) fk (y j , p)} pour chaque tche non critique Jk , o fk (e) est la quantit de ot qui passe par larc e dans Fk . En eet, k est la quantit 29

supplmentaire qui peut saturer le k -chemin. Considrons, maintenant, linstance J, I, v o la valeur de > 0 vrie
wi Ji J v wi Ji J v

wi Ji J v(v)

< mink {k }, et soit G le graphe correspondant.

Nous allons, tout dabord, montrer que le passage de linstance J, I, v linstance J, I, v conserve lensemble des tches non critiques. Pour toute tche Jk non critique dans linstance J, I, v , nous dnissons le (s, p)-ot Fk dans le graphe G tel que fk (s, xi ) =
wi v

pour chaque
wi v

tche Ji dont tous les chemins de type (xi , y j , p) sont saturs dans le ot Fk , et fk (s, xi ) =

pour

les tches restantes, o fk (e) est la quantit de ot traversant larc e dans Fk . Remarquons que la seule dirence entre les ots Fk et Fk consiste dans le fait que pour chaque i -chemin= (xi , y j , p) non satur dans le ot Fk on a : fk (xi , y j ) = fk (xi , y j ) +
wi v(v)

et fk (y j , p) = fk (y j , p) +

wi v(v) .

Il est clair que le ot Fk est ralisable et maximum. Pour la tche non critique Jk et le k chemin= (xk , y j , p), et par dnition de la valeur , on a fk (xk , y j ) < c(xk , y j ) et fk (y j , p) < c(y j , p). Donc pour chaque tche non critique Ji , le i -chemin reste non satur dans le ot Fk dans G . Rappelons que pour prouver quune tche Ji est non critique, il sut de trouver un ot maximum qui ne sature pas un chemin de type (xi , y j , p). Do le fait que le passage de linstance J, I, v linstance J, I, v conserve les tches non critiques. Considrons, maintenant, une tche critique Ji dans linstance J, I, v et montrons que cette tche est galement critique dans linstance J, I, v . Par dnition dune tche critique, il existe une (s, p)-coupe minimale C dans le graphe G contenant soit un arc (xi , y j ), soit un arc (y j , p) pour tout chemin (xi , y j , p). Dautre part, puisque linstance J, I, v est ralisable, il existe une (s, p)-coupe minimale C dans le graphe G constitue de tous les arcs (s, xi ). Notons que les coupes C et C ont la mme valeur. tant donn que le graphe G correspondant linstance J, I, v dire du graphe G uniquement par des capacits plus grandes sur les arcs de type (s, xi ), il est possible de conclure que la coupe C reste une (s, p)-coupe minimale pour le graphe G mais pas la coupe C . Ainsi, pour chaque tche Ji critique dans G, chaque chemin (xi , y j , p) est satur par tout (s, p)-ot dans le graphe G . Finalement, si une tche est critique dans linstance J, I, v alors elle reste critique dans linstance J, I, v .

30

Lemme 5 Soit J, I, v une instance critique du problme AVC et soit G le graphe correspondant linstance J, I, v , pour une valeur > 0 susamment petite (conformment au lemme 4). Dans ce cas, toute (s, p)-coupe minimale C dans le graphe G est compose de : (i) un arc de chaque chemin (xi , y j , p) pour chaque tche critique Ji J, (ii) larc (s, xi ) pour chaque tche non critique Ji . Preuve Rappelons tout dabord que daprs le lemme 4 les instances J, I, v et J, I, v possdent le mme ensemble de tches critiques. Considrons une tche critique Ji . Chaque chemin (xi , y j , p) est satur par tout (s, p)ot maximum dans le graphe G ou G . Soit donc F un (s, p)-ot maximum dans le graphe G . Pour la tche critique Ji , le ot F ne sature pas larc (s, xi ) car sinon il existe au moins un chemin (xi , y j , p) qui nest pas satur par au moins un ot maximum dans le graphe G. Ainsi, larc (s, xi ) nappartient aucune (s, p)-coupe minimale dans G et donc chaque coupe minimale contient exactement un seul arc sur chaque chemin (xi , y j , p). Soit maintenant une tche Ji non critique dans les deux instances du problme AVC. Il existe donc un (s, p)-ot maximum F dans le graphe G et un chemin (xi , y j , p), I j [ri , di ), qui nest pas satur par F . Ainsi, les arcs (xi , y j ) et (y j , p) nappartiennent aucune (s, p)-coupe minimale dans G et cest donc larc (s, xi ) qui appartient toute coupe minimale dans G . partir du lemme 5, il est possible de dduire dans le corollaire suivant un moyen simple pour dterminer lensemble des tches critiques tant donne une instance critique du problme AVC. Corollaire 2 Soit une instance critique J, I, v du problme AVC. Lensemble des tches critiques est entirement dni en suivant les deux tapes suivantes :

i Calculer une (s, p)-coupe minimale C dans le graphe correspondant linstance J, I, v pour une valeur > 0 inniment petite. ii Retourner lensemble des tches Ji tel que la coupe C contienne un arc sur chaque chemin partant du noeud xi correspondant Ji jusquau noeud puits p.

31

1.4.3 Lalgorithme SSM

Nous nous proposons prsent de donner une description de lalgorithme combinatoire quon note "SSM" (Speed Scaling avec Migration) pour rsoudre dune faon optimale le problme de minimisation de lnergie consomme sur des machines identiques avec migration.

Initialement, nous dnissons la vitesse vu telle quil existe un ordonnancement ralisable o toutes les tches dune instance du problme initial sexcutent cette vitesse. Lide consiste dcrotre cette vitesse jusqu ne plus tre capable de concevoir un ordonnancement ralisable o toutes les tches sont excutes une vitesse commune. Rappelons que pour une vitesse donne, un ordonnancement ralisable est retourn en calculant un ot maximum pour linstance du problme AVC correspondante. La dernire vitesse garantissant un ordonnancement ralisable est une vitesse critique et il existe au moins une tche critique qui ne peut tre excute qu une vitesse au moins gale cette vitesse critique dans tout ordonnancement ralisable. chaque tape de lalgorithme SSM, lensemble des tches critiques est dtct en utilisant le corollaire 2. Ensuite, lalgorithme attribue la vitesse critique ces tches et met jour le nombre de machines disponibles pour chaque intervalle I j I. Cette mise jour est ralise laide la coupe minimale dcrite dans le corollaire 2 : si cette coupe contient un arc (xi , y j ) alors nous considrons quune machine est utilise pendant lintervalle I j pour lexcution de la tche critique correspondante Ji . Par contre, si la coupe minimale contient un arc (y j , p) alors, durant lintervalle I j , toutes les machines disponibles seront rsrves lexcution des tches critiques. Finalement en supprimant les tches critiques de lensemble initial de tches, nous obtenons un sous-problme et nous dnissons pour chaque vitesse linstance du problme AVC correspondante.

Le pseudo-code de lalgorithme SSM peut tre dcrit comme suit,

32

Algorithme 1: SSM Donnes : Une instance du problme de minimisation dnergie sur des machines identiques avec migration. Rsultat : Un ordonnancement optimal.

dbut v = max Ji J {i }, vu = maxI j I {

Ji D j

wi

|I j |

};

tant que J faire Rechercher par dichotomie sur lintervalle [v , vu ] la vitesse minimale v telle que linstance J, I, v du problme AVC soit ralisable. Calculer un ot maximum dans le graphe correspondant pour vrier la faisabilit de linstance ; Dterminer lensemble de tches critiques J en utilisant linstance J, I, v pour un rel > 0 inniment petit (corollaire 2) ; vi := v pour toute tche critique Ji J ; Mettre jour lensemble des tches : J = J\J ;

Mettre jour le nombre m j de machines disponibles pour chaque intervalle I j laide de la coupe minimale dans le graphe de linstance J, I, v ; vu = v , v = maxJi J {i } ; n

Rsoudre dune faon optimale linstance obtenue du problme P|ri , di , pmtn| avec une dure dexcution gale n
wi vi

pour toute tche Ji J ;

chaque itration de lalgorithme SSM, la vitesse critique et lensemble des tches cri-

33

tiques sont reprsentes, respectivement, par les variables v et J . An de dterminer la vitesse critique chaque itration, lalgorithme eectue une recherche binaire en supposant que toutes les tches non encore traites seront excutes la mme vitesse. Il est possible de dterminer les bornes infrieure et suprieure de lintervalle de recherche dune faon simple. En eet, la vitesse qui sera attribue chaque tche ne peut pas tre infrieure sa densit si elle doit tre excute en sa totalit. Ainsi, tant donn un ensemble de tches J il nexiste aucun ordonnancement ralisable pouvant excuter toutes les tches une vitesse v < max Ji J {i }. Dautre part, observons que pour le mme ensemble J, il est toujours possible de construire un ordonnancement ralisable qui excute toutes les tches une vitesse unique gale v = maxI j I {
Ji D j

wi

|I j |

} et qui constitue donc une borne suprieure dans lintervalle de

recherche. Dans ltape suivante de lalgorithme SSM, ces bornes seront mis jour et la valeur de la borne suprieure de lintervalle sera substitue par la vitesse critique calcule ltape courante.

Soit lexemple suivant : nous considrons lensemble de tches J = {J1 , J2 , J3 , J4 , J5 , J6 } et lensemble dintervalles I = {I1 , I2 , I3 }. La gure 1.4 dtaille les paramtres de cette instance (dates darrive, dates dchance et quantits de travail). Aussi nous supposons que deux machines M1 et M2 sont disposition pour lexcution des tches.
J3 (w3 = 6) J6 (w6 = 4) J2 (w2 = 3) J5 (w5 = 4)

J1 (w1 = 8) J4 (w4 = 6)

I1

I2

I3

temps

F. 1.4 Exemple dinstance du problme de minimisation dnrgie avec migration.

34

En appliquant lalgorithme SSM, celui-ci rsout le problme en trois itrations et nous obtenons lensemble de vitesses critiques suivantes {v1 = 4, v2 = 3, v3 = 2}, o chaque valeur vi reprsente la vitesse critique retourne lissue de la ime itration. Dans la gure 1.5, nous rsumons le droulement de lalgorithme sur linstance en question : la gure 1.5(a) modlise linstance (J, I, v) du problme AVC en terme de ots pour v > 0. Les gures 1.5(b), 1.5(c) et 1.5(d) prsentent les direntes itrations de lalgorithme. Dans chacun des ots, lensemble des arcs colors en rouge reprsentent la coupe minimale dans le graphe correspondant linstance (J, I, v ) pour > 0 inniment petit, et lensemble des noeuds xi colors en bleu reprsentent lensemble des tches Ji critiques trouves la n de litration courante. Il faut noter aussi que suite la mise jour du nombre de machines disponibles durant chaque intervalle lorsquon passe dune itration la suivante, la capacit des arcs de type (y j , p) est susceptible de changer. Par exemple lors du passage de la premire itration (gure 1.5(b)) la deuxime itration (gure 1.5(c)), la machine M1 ou M2 est utilise durant lintervalle I1 par la tche critique dvoile J1 , et ainsi une seule machine est dsormais disponible pendant I1 , ce qui fait passer la capacit de larc (y1 , p) de la valeur 4 la valeur 2. la n, lalgorithme attribue la vitesse v1 la tche J1 , la vitesse v2 aux tches J2 et J3 et la vitesse v3 aux tches J4 , J5 et J6 . Ensuite, il sut de rsoudre linstance du problme P|ri , di , pmtn| correspondante. Dans le thorme suivant, nous allons prouver que lalgorithme SSM retourne un ordonnancement vriant les proprits numres dans le lemme 1 et il est donc optimal daprs le lemme 2.

Thorme 2 Lalgorithme SSM retourne un ordonnancement optimal pour toute instance du problme. Preuve Tout dabord, il est clair que lalgorithme SSM attribue une vitesse constante chaque tche en une seule itration avant que celle-ci soit supprime de linstance. Ainsi, la premire proprit du lemme 1 est vri. chaque itration de lalgorithme, une vitesse constante est attribue un sous ensemble 35

x1 2
8 v 3 v 6 v

2 y1 2/2 4 0.75/0.75 1 1 y2 2 p s 1.5/1.5 1.5/1.5 6 3 1/1 y3 1/1 3

x1

2/2 0.75/2 y1 3.75/4 y2

x2 2 x3

x2 1/2 0.5/1 1/1 x4 0/1 0.5/3 x5 1/3 1/3 x6 y3 2.5/6

x3

1.5/2 p

6 v 4 v

x4

4 v

x5

x6

(a)
1/2 x2 1/2 1/1 s 2/2 2/2 x4 1.33/1.33 x5 1.33/1.33 x6 1.33/3 0/1 1.5/3 1.33/3 y3 4.16/6 2/2 x3 1/1 0.5/1 3/3 y2 1.5/2 p s y1

(b)

2/2 y2 0.5/1 0.5/1 x4 2.5/3 1.5/3 x5 2/2 x6 2/3 y3 6/6 1/1 p

(c)

(d)

F. 1.5 Exemple dapplication de lalgorithme SSM.

36

de tches. En plus, durant un certain nombre dintervalles, le nombre de machines disponibles sera rduit puisquelles seront consacres lexcution de ces tches. Soit la kme itration de lalgorithme, nous allons noter par J (k) et I(k) respectivement lensemble des tches auquelles lalgorithme na pas encore attribu de vitesse, et lensemble des intervalles pendant lesquels au moins une machine est encore disponible, i.e. non utilise par dautres tches critiques pendant les itrations prcdentes. On note, galement, par s(k) et s(k) les bornes infrieure et suprieure de u l lintervalle de recherche de la vitesse critique au cours de la kme itration. Par ailleurs, pour une
(k) vitesse donne v [s(k) , su ], on note par G(k) le graphe correspondant linstance J (k) , I(k) , v l

du problme AVC. Considrons maintenant la proprit 4(i) du lemme 1. Soit un ordonnancement retourn par lalgorithme SSM et supposons quil existe deux tches Ji et J disponibles durant un intervalle I j et telles que 0 < ti, j < |I j | et 0 < t, j < |I j |. Il sagit donc de prouver que ces deux tches sont excutes la mme vitesse ce qui revient prouver que cette vitesse leur a t attribue la n dune unique itration. Supposons donc que la tche Ji devient critique la n de litration k, ce qui implique quil existe une (s, p)-coupe C dans le graphe G(k) contenant larc (xi , y j ) ou larc (y j , p). Du fait que 0 < ti, j < |I j |, il existe un (s, p)-ot maximum dans le graphe G(k) tel que 0 < f (xi , y j ) < |I j |. Larc (xi , y j ) nest donc pas satur, et on dduit que larc (y j , p) fait partie de la coupe C. Ainsi, tout ot maximum sature larc (y j , p), ce qui implique qu la n de litration k, aucune machine ne sera disponible durant lintervalle I j au cours des itrations suivantes, i.e. k + 1, k + 2, etc. Puisque 0 < t, j < |I j |, lattribution dune vitesse la tche J ne peut pas avoir lieu pendant une itration postrieure litration k. De la mme faon, nous montrons que lattribution dune vitesse la tche Ji ne peut pas se faire une itration postrieure litration k, ce qui fait que lalgorithme attribue la mme vitesse aux tches Ji et J la n de litration k. Considrons maintenant la proprit 4(ii) du lemme 1 et soit une tche Ji et un intervalle I j [ri , di ) tels que ti, j = 0. Supposons que la tche Ji devient critique durant la kme itration dans lalgorithme SSM. Dans le graphe G(k) correspondant, il y a deux cas possibles : soit que le noeud y j ne fait pas partie des noeuds du graphe, ce qui implique quaucune machine nest dispo-

37

nibles durant lintervalle I j au dbut de litration k (la totalit des machines utilises pendant les itrations prcdentes), ou alors que larc (y j , p) appartient une (s, p)-coupe minimale dans G(k) . Dans lhypothse quaucun de ces deux cas ntait vrai, larc (y j , p) aurait fait partie de lensemble des arcs du graphe G(k) sans quil appartienne une (s, p)-coupe minimale. Dans ce cas, tous les arcs (x , y j ) tels que I j [ri , d j ) feront partie dune (s, p)-coupe minimale, et en particulier larc (xi , y j ) sera satur par tout (s, p)-ot maximum. Or ceci est une contradiction tant donn quil existe au moins un (s, p)-ot maximum tel que f (xi , y j ) = 0 puisque ti, j = 0. Ainsi, dans les deux cas (y j nappartient pas G(k) ou (y j , p) appartient une coupe minimale), aucune machine ne sera diponible durant lintervalle I j aprs la kme itration de lalgorithme, ce qui fait que toutes les tches J avec t, j > 0 possdent des vitesses dexcution suprieures ou gales la vitesse de la tche Ji . Nous considrons prsent la proprit 4(iii) du lemme 1 et soit une tche Ji telle que ti, j = |I j | et telle que lalgorithme lui attribue une vitesse la kme itration. Il est clair que daprs la proprit 4(i), litration k ne peut pas avoir lieu aprs une itration k la suite de laquelle lalgorithme attribue une vitesse une tche J qui vrie 0 < t, j < |I j |. En eet, il a t dmontr qu la n dune telle itration k , aucune machine nest encore disponible durant lintervalle I j . Ainsi la vitesse si attribue la tche Ji est au moins gale la vitesse s attribue toute tche J vriant 0 < t, j < |I j |. Dans le cas o t, j = 0, daprs la proprit 4(ii), lalgorithme nattribue pas une vitesse la tche Ji aprs avoir traiter la tche J . Donc, la vitesse si est aussi dans ce cas suprieure ou gale s . An de montrer maintenant que toute solution retourne par lalgorithme SSM vrie la 3me proprit du lemme 1, nous considrons une instance telle quil existe un intervalle I j vriant |D j | m et soit une tche quelconque telle que I j [ri , di ) et telle que la tche devient critique

la kme itration de lalgorithme. Montrer que ti, j = |I j | dans la solution retourne revient montrer que dans le graphe G(k) , tout (s, p)-ot maximum sature larc (xi , y j ). Supposons, par contradiction quil existe un (s, p)-ot maximum F dans G(k) tel que f (xi , y j ) < |I j | et tel que f (x , y j ) pour tout J D j \{Ji }. Dans ce cas, on a f (y j , p) =
J D j

|I j |

f (x , y j ) < |D j ||I j |

m|I j |, et donc le

38

ot F ne sature ni larc (y j , p) ni larc (xi , y j ), ce qui contredit le fait que la tche Ji est critique. On conclut que le temps dexcution de toute tche disponible pendant lintervalle I j est gal |I j |. Nous prouvons nalement que lalgorithme SSM retourne des solutions qui vrient la deuxime proprit du lemme 1. Tout dabord, tant donn un intervalle quelconque I j tel que |D j | m, daprs la 3me proprit il est clair que
Ji D j ti, j

= |D j ||I j | et la proprit est prouve

dans ce cas. Ensuite, supposons que min{|D j |, m} = m. Dans ce cas il nest pas possible davoir
Ji D j ti, j

> m|I j | puisque lalgorithme SSM est bas sur le calcul de ots dans des graphes o

la capacit de chaque arc de type (y j , p) ne peut pas dpasser m|I j |. Maintenant, supposons par contradiction que
Ji D j ti, j

< m|I j |. Il existe donc au moins une tche J D j telle que t, j < |I j |.

Il existe aussi au moins une machine qui nest pas utilise dans la solution au cours de lintervalle I j , ainsi larc (y j , p) est prsent dans tout graphe G(k) pour toute itration k de lalgorithme. Soit litration h pendant laquelle la tche J devient critique. tant donn que t, j < |I j | et quil existe au moins une machine non utilise durant I j alors aucun ot maximum dans G(h) ne peut saturer le chemin (x , y j , p) ce qui contredit le fait que la tche J est critique. Finalement, lalgorithme identie correctement les tches critiques chaque itration cause du lemme 5.

Complexit de SSM. Nous analysons maintenant la complexit de lalgorithme SSM. chaque itration, lalgorithme attribue la vitesse critique trouve par recherche binaire au moins une tche. Ceci est garanti par le lemme 3 qui stipule que pour chaque instance critique, il existe au moins une tche critique. Ainsi, lalgorithme SSM eectue au plus n itrations pour une instance J du problme, o |J| = n. Il sagit de raliser dans chacune des itrations une recherche binaire pour trouver la vitesse critique courante. Cette recherche est base sur le calcul de O(log(P)) ots maximums, o P reprsente le nombre de vitesses candidates. En eet, la valeur P peut tre calcule en divisant la taille de lintervalle de recherche [v , vu ] par la prcision dsire. Il est clair que cette valeur est majore par Pmax qui correspond la valeur calcule de la mme manire sur lintervalle [max Ji J {i }, maxI j I {
Ji D j

wi

|I j |

}]. 39

Par ailleurs, notons par C(x, y) le temps ncessaire pour calculer un ot maximum dans un graphe en couche contenant x sommets et y arcs. Ainsi, la complexit totale de lalgorithme SSM est en O(nC(n, n2 )log(Pmax )) tant donn que dans les graphes correspondants aux direntes instances du problme AVC, le nombre de sommets est en O(n) et le nombre darcs est en O(n2 ).

1.5

C
Ce chapitre a t ddi ltude du problme dordonnancement sur des machines

parallles avec premption et migration des tches dans le but de minimiser la consommation de lnergie dans le modle dadaptation de la vitesse (Speed Scaling). Tout dabord, il tait question de trouver la structure de toute solution optimale du problme. Nous avons donc dduit des conditions ncessaires doptimalit en formulant le problme en terme de progarmme convexe et en appliquant les conditions de Karush-Kuhn-Tucker (conditions KKT). Ensuite, nous avons montr que ces critres taient susantes pour loptimalit. Guids par cette structure optimale, nous avons dni les notions dinstance et de tche critiques et nous avons fait usage dune rduction du problme en un problme de ot maximum pour construire un algorithme combinatoire quon a not SSM et qui retourne une solution optimale toute instance du problme en un temps polynomial.

Dans le chapitre 3, nous allons tudi un problme doptimisation avec un double objectif savoir la minimisation de lnergie et du temps de compltude moyen des tches. Dans ce contexte, il semble que lalgorithme SSM peut tre exploit pour rsoudre ecacement quelques problmes dordonnancement multi-critres dont lun des objectifs est la minimisation de lnergie consomme. Nous citons par exemple le problme qui consiste ordonnancer sous le modle dadaptation de la vitesse (Speed Scaling) un ensemble de tches avec des dates darrives ri et des quantits de travail positifs wi sur m machines identiques dans le but de minimiser le temps dexcution total (makespan) sans que lenrgie consomme ne dpasse un seuil E x lavance. Si la migration et la premption sont autorises, alors il est possible de rsoudre ce problme comme suit : supposons que C et Cu reprsentent respectivement une borne infrieure et une 40

borne suprieure sur le temps dexcution total. En xant une valeur quelconque C [C , Cu ], il est possible de savoir sil existe un ordonnancement ralisable dont le temps dexcution total soit gal C et tel que lnergie consomme ne dpasse pas la borne E. Il sut, en eet, dattribuer toutes les tches une date dchance ctive commune gale C et de lancer lalgorithme SSM sur linstance obtenue. Si lordonnancement construit dpense une nergie ES S M E alors il

constitue une solution ralisable du problme. Il sagit donc de raliser une recherche binaire dans lintervalle [C , Cu ] pour trouver la plus petite valeur du makespan telle quil existe une solution ralisable du problme. Pour une instance donne, une borne infrieure sur le makespan peut tre dnie par C =
1 1 W 1 m( E )

o W =

Ji

wi . Cette borne est obtenue en xant la vitesse

dexcution de toutes les tches

W m.x

et en utilisant chaque machine pendant une dure gale x.

Par ailleurs, la borne suprieure sur le temps dexcution total peut tre dnie simplement par Cu = max Ji {ri } + ( W ) 1 . E Dautre part, il est possible dutiliser la mme technique pour rsoudre le problme de minimisation du retard maximum avec un budget E dnergie. Dans ce problme, on attribue chaque tche Ji une date de livraison qi 0 et tant donn un ordonnancement quelconque le retard
1

de Ji est donn par Li = Ci + qi o Ci est le temps de n dexcution de la tche Ji . Pour une valeur quelconque L > 0, il est possible dutiliser lalgorithme SSM en attribuant chaque tche Ji une date dchance di = L qi pour savoir sil existe ou non un ordonnancement ralisable dont lnergie consomme ne dpasse pas le seuil E. En eet, dans lordonnancement retourn par lalgorithme SSM, le retard relatif chaque tche Ji vrie Li = Ci + qi di + qi = L. Il

sut donc de dnir un intervalle de recherche [L , Lu ] et deectuer une recherche binaire pour trouver la plus petite valeur possible L telle quil existe un ordonnancement rlaisable respectant le budget dnergie. Les bornes de lintervalle de recherche peuvent tre dnies par L = 0 et Lu = max Ji {ri } + ( W ) 1 + max Ji {qi }. E
1

Une perspective intressante de ce travail serait daugmenter le modle dadaptation de la vitesse (Speed Scaling) par lintroduction dun ou plusieurs tats de veille (voir chapitre 2) o le

41

systme pourrait passer en un mode de basse consommation dnergie, voire un mode dhibernation o la consommation est nulle. Finalement, il serait intressant de savoir si la formulation en terme de ots pourrait conduire rsoudre cacement dautres problmes faisant intervenir lnergie consomme.

42

O : `

2.1

I
Comme nous lavons vu dans le chapitre prcdent, le mcanisme dadaptation dyna-

mique de la vitesse dune machine ("Speed Scaling") permet de conserver lnergie consomme qui dpend de la vitesse dexcution : plus la vitesse est grande plus lnergie consomme est importante. Il est ainsi possible dimaginer des modles dordonnancement visant minimiser lnergie tout en garantissant une certaine qualit de service.

Dans le modle tudi dans le chapitre prcdent, nous avons suppos que si la vitesse dune machine est nulle pendant une priode donne, alors lnergie dpense par cette machine pendant cette priode est aussi nulle. Cependant, dans un modle plus raliste, il existe toujours une consommation dnergie au niveau de la machine mme dans le cas o la vitesse est nulle. Il sagit dune puissance statique dissipe, constamment prsente et ce en prsence ou en absence de tches en excution. Par ailleurs, un ou plusieurs tats de veille o le systme dexploitation peut choisir de suspendre lactivit de la machine sont aussi disponibles. Le passage un tat de veille a lieu si la machine reste inactif, i.e. nexcute pas des tches, pendant une certaine priode

43

seuil que le systme peut modier et xer lavance. Pendant ces tats de veille, le taux de consommation de lnergie statique est minimal, voire nul mais le retour un tat actif ncessite une quantit xe dnergie.

Dans le but de minimiser lnergie consomme, une approche algorithmique consiste utiliser le mcanisme de passage dans un tat de veille en essayant dy rester le plus longtemps possible et de minimiser le nombre de passage dans ltat actif [20]. Une autre approche combine ce mcanisme avec la technique dadaptation de la vitesse de la machine ("Speed Scaling"). Dans cette approche, il est parfois plus utile dacclrer lexcution des tches an de basculer plus rapidement dans un tat de veille et dpenser ainsi une nergie minimale ou nulle.

2.2

D `
Une instance du problme de minimisation dnergie sur une seule machine avec un

tat de veille consiste en un ensemble de tches J= {J1 , . . . , Jn }, tel que chaque tche Ji , 1 i n soit caractrise par une quantit de travail wi , une date darrive ri et une date dchance di , et tel que la tche Ji ne puisse tre ordonnance que dans lintervalle [ri , di ). Une instance de ce problme est dite agrable sil est possible de rnumroter les tches de telle sorte ce que les dates darrive et les dates dchance soient donnes dans un ordre croissant, i.e. tant donnes deux tches Jk et Jk , k < k implique que rk rk et dk dk . Nous introduisons, dans ce cas un ordre total " " tel que pour tout couple de tches (Jk , Jk ), Jk Jk si et seulement si k k .

Un ordonnancement est dni par 3 fonctions :

mode : R {On, O} vitesse : R R+ tche : R {vide, J1 , . . . , Jn }, o les fonctions mode, vitesse et tche dterminent respectivement ltat du systme, la vitesse 44

de la machine et la tche en cours dexcution chaque instant de lordonnancement. Ces trois fonctions vrient les proprits suivantes :

1. t : vitesse(t) > 0 mode(t) = On. 2. t : vitesse(t) = 0 tche(t) = vide. 3. t : tche(t) = Ji , Ji 4. Ji vide : vide t [ri , di ).

vitesse(t)dt = wi o lintgrale est applique sur tous les instants t tels que

tche(t) = Ji . 5. pour tout instant t, il existe un intervalle de longueur non nulle I tel que t I et durant lequel lordonnancement est constant, i.e. la vitesse reste constante. De plus I est de la forme (, u), [t , u) ou [t , +) pour des instants donns t et u.

La dernire proprit est une hypothse simplicatrice qui permet dviter quun ordonnancement ne dgnre. Un exemple dun tel ordonnancement peut tre dcrit comme suit : 0 si t [0, 1) vitesse(t) = 1 si t [0, 1) R\Q 2 si t [0, 1) Q. Les dirents tats du systme peuvent tre rsums comme suit : si un instant donn t on a tche(t) = vide, alors on dit que la machine est au repos. Dans ce cas, la machine peut tre soit en tat de marche et dans ce cas mode(t) = On, soit teinte et dans ce cas mode(t) = O. Dans le cas o tche(t) vide, alors la machine, dite dans ce cas active, excute la tche tche(t) et elle est,

ainsi, en tat de marche, i.e. mode(t) = On. Le cot de lnergie consomme dun ordonnancement quelconque est caractris par trois paramtres : un exposant > 1, un cot de mise en marche de la machine L > 0 et un cot de dissipation dnergie statique ou de fonctionnement reprsent par un taux de consommation

45

g > 0. Par ailleurs, ce cot dnergie possde deux composantes :

(i) Le cot dexcution, savoir lnergie consomme pendant tous les instants t tel que tche(t) = Ji vide, i.e. machine active. Ce cot est dni par cvitesse = vitesse(t) dt, o

lintgrale est applique sur toute la dure de lordonnancement.

(ii) Le cot du mode du systme, il sagit du cot de lnergie statique dpense lorsque le systme est en tat de marche, i.e. pour tout instant t tel que mode = On, plus le cot de lnergie ncessaire pour la mise en marche de la machine chaque fois que le systme passe dun mode O un mode On. Un ordonnancement avec la proprit (5) partitionne laxe du temps en une squence S dintervalles disjoints et maximaux au sens de linclusion, tel que mode(t) = On si et seulement si t S = Ik S Ik . La squence S est dite le support de lordonnancement, et la consommation dnergie gnre par ce support constitue le cot du mode du systme dni par cmode = L (|S | + 1) + g | S |. Il est noter que dans ce calcul, nous comptons le cot de mise en marche L pour les deux intervalles semi-innis qui bornent le support S . Dans lexemple de la gure 2.1 nous prsentons un ordonnancement de 5 tches sur une machine ainsi que le cot correspondant en terme dnergie consomme.

Off

J1
t1 t2 t3

J2
t4

Off

J3 J4
t5 t6 t7

J5
t8

Off

temps

F. 2.1 Ordonnancement dune instance compose de 5 tches. Nous supposons que chaque tche Ji est excute une vitesse xe vi . La machine est en mode On durant les intervalles [t1 , t4 ) et [t5 , t8 ), et elle est en mode O ailleurs. Ainsi lnergie totale consomme dans cet ordonnancement se dcompose en : cvitesse = v .(t2 t1 ) + v .(t4 t3 ) + v .(t6 t5 ) + v .(t7 t6 ) + v .(t8 t7 ) et 4 3 2 1 5 cmode = 3.L + g. (t4 t1 ) + (t8 t5 ) .

Ainsi, le cot total de lnergie consomme est donn par cvitesse + cmode et le problme

46

tudi consiste trouver un ordonnancement ralisable qui minimise le cot dnergie pour une instance agrable. Notons que pour minimiser lnergie dans ce modle, il nest pas toujours optimal de minimiser les vitesses dexcution des tches le plus possible mais il sagit plutt de trouver un compromis entre le cot dexcution cvitesse et le cot relatif au mode du systme cmode . Cette situation est illustre dans la gure 2.2 o le modle de cot de lnergie consomme est caractris par les paramtres suivants : = 3, L = 50 et g = 16. Nous considrons par ailleurs une instance avec 2 tches : la tche J1 avec w1 = 4, r1 = 0 et d1 = 4, et la tche J2 avec w2 = 4, r2 = 7 et d2 = 9, et nous montrons deux ordonnancements dirents tels que le deuxime soit meilleur que le premier en terme dnergie dpense.

v2 = 2 v1 = 1 J1 (w1 = 4) On temps J2 (w2 = 4)

Ordonnancement 1 cot = 164

v1 = 2 J1 (w1 = 4) Off

v2 = 2 J2 (w2 = 4)

Ordonnancement 2 cot = 146

temps

F. 2.2 Exemple dordonnancement o laugmentation de la vitesse dexcution nentrane pas une augmentation dans la consommation dnergie. Nous supposons que toutes les tches sont excutes des vitesses constantes. Dans le premier ordonnancement la dpense dnergie dans lintervalle [4, 7) est gale 3.g < L, donc le systme reste en mode On, alors que dans le deuxime ordonnancement cette dpense devient 5.g mique. L, do le passage en mode O serait plus cono-

47

2.3

T
Notre problme dordonnancement pour des instances gnrales (non agrables) a

t tudi dans [48], o les auteurs ont fait rfrence deux sous problmes tudis et rsolus indpendamment. Le premier sous problme ne considre pas le mcanisme dadaptation de la vitesse en se limitant des vitesses nulles ou unitaires en fonction du mode dans lequel se trouve le systme. Dans ce cas, il est clair que le but essentiel est de minimiser cmode uniquement. Ce premier sous problme a t rsolu en O(n5 ) en utilisant la programmation dynamique dans [20]. Pour les instances agrables la complexit t amliore en O(n2 ) [9]. Le second sous problme, en revanche, ne considre quun seul tat du systme, savoir ltat On, et restreint le cot de dissipation dnergie statique de fonctionnement g = 0. Lobjectif ici tant de minimiser uniquement cvitesse . Ce sous problme correspond au problme rsolu par le clbre algorithme glouton de Yao, Demers et Shenker [83] en O(n3 ). La complexit de cet algorithme que nous notons par Y DS a pass O(n2 logn) dans [63] avant dtre amliore en O(n2 ) pour des instances agrables [81].

An dtre exhaustif, nous rsumons ici lalgorithme YDS [83] . chaque tape de lalgorithme, on slctionne lintervalle I de densit maximale parmi les O(n2 ) intervalles de la forme [ri , d j ]. La densit dun intervalle est dnie par le ratio v = W/(d j ri ), o W est la quantit de travail totale de toutes les tches Jk telles que [rk , dk ] [ri , d j ]. Ensuite, toutes ces tches sont ordonnances dans I la vitesse v en donnant la priorit la tche ayant la plus courte date dchance. Il faut prciser quaucune tche ne rate sa date dchance tant donn que la densit v est maximale. Dans la suite de lalgorithme, lintervalle I est supprim de laxe du temps, ce qui revient exclure cet intervalle lors du calcul de la densit maximale litration suivante. Cet intervalle est aussi exclut lors de lordonnancement des tches restantes. Lalgorithme YDS prend n lorsque toutes les tches auraient t ordonnances.

La question dexistence dun algorithme polynomial pour le problme dordonnancement

48

avec un tat de veille et vitesse variable a t pose par Irani et Pruhs dans [48] o les auteurs ont voqu une dicult particulire pour dterminer la complexit du problme baptis "Speed Scaling with Sleep State". Dans [49], Irani et al. ont initi ltude de ce problme en prsentant un algorithme polynomial 2-approch. Cet algorithme est bas sur la partition des tches en deux sous ensembles : les tches rapides et les tches lentes. Une tche Ji est dite rapide si sa vitesse critique dnie par wi /(di ri ) dpasse une vitesse bien dnie vcrit et lensemble de ces tches sont ordonnances en utilisant lalgorithme YDS. Toutes les tches restantes sont dites lentes et sont ordonnances la vitesse vcrit .

Rcemment, et pendant la rdaction de ce travail, Albers et al. [4] ont russi prouver que le problme gnral est NP-dicile laide dune rduction partir du problme de 2-partition. Ce rsultat est valable mme pour des instances ayant une structure darbre, i.e. pour 2 tches ji et j j quelconques, on a soit [ri , di ) [r j , d j ) ou [r j , d j ) [ri , di ) ou [ri , di ) [r j , d j ) = . Ils ont, par ailleurs, prsent un algorithme gnrique pouvant induire des rapports dapproximation intressants dans le cas de fonctions de puissance convexes gnrales et aussi dans le cas de fonctions de puissance de la forme P(v) = v + g, o v est la vitesse dexcution, et pour > 1, et ,g > 0.

2.4

Nous nous proposons dans cette partie de dduire quelques proprits doptimalit du problme dcrit ci-dessus. Nous rappelons, tout dabord, que si une tche Ji est excute une vitesse constante v alors wi /v units de temps seraient ncessaires an dachever la tche Ji . Lnergie consomme dans ce cas est gale (v + g)wi /v et cette quantit dnergie est minimise lorsque la vitesse prend une valeur particulire v = (g/( 1))1/ que nous appelons la vitesse critique. Cette vitesse est obtenue en annulant la drive de (v + g)wi /v et ne dpend pas de la tche en question puisquelle est indpendante de la quantit de travail wi . La densit dun intervalle I tant dnie par wi /|I| sur toutes les tches Ji avec [ri , di ) I, 49

un intervalle est dit dense si sa densit est au moins gale v . Il est dit pars dans le cas contraire.

Dans la suite, nous supposons que toute instance du problme est agrable et que les tches sont numrotes en respectant lordre total " " prcdemment dni. Le lemme suivant montre lexistence dun ordonnancement optimal avec quelques proprits intressantes permettant de dduire la structure de lordonnancement optimal. Lemme 6 [49] Soit une instance du problme de minimisation dnergie avec un tat de veille. Il existe un ordonnancement optimal (mode, vitesse, tche) vriant les proprits suivantes. Job Span : pour chaque instant t, si tche(t) = Ji mode(u) = On, on a vitesse(u) vitesse(t). vide, alors vide alors pour tout instant u [ri , di ) avec

Earliest Deadline First : pour tout couple dinstants t < u si tche(t), tche(u) tche(t) tche(u).

Intervalles Denses : tout intervalle dense I est ordonnanc selon lalgorithme YDS. En particulier, la premire proprit implique que chaque tche est excute une vitesse constante. Les deux autres proprits impliquent que les intervalles divisent le problme en des sous problmes indpendants, comme il sera dcrit dans la suite. Dnition 3 Une sous-instance de notre problme est spcie par une paire dentier (i, j) avec i {1, . . . , n} et j {i 1, . . . , n}. Pour plus de clart, nous notons d0 = r1 L/g et rn+1 = dn + L/g. Il sagit, donc, dun intervalle I = [di1 , r j+1 ) et dun ensemble de tches J. Si i = j+1, alors J = , sinon J = {Ji , . . . , J j }. Les intervalles constitus par les dates darrive et les dates dchance de ces tches sont restreints par intersection avec I. Notons que dans le cas o di1 r j+1 ou di1 = di ou r j = r j+1 , la sous-instance (i, j) nest pas ralisable puisque lintervalle de disponibilit dau moins une des tches Ji , . . . , J j sera restreint lintervalle vide.

50

Par ailleurs, nous tendons la dnition de la fonction de cot an denglober les sous-instances dnies ci-dessus. Lordonnancement dune sous-instance (i, j), com-

pose dun ensemble de tches J et dun intervalle I, est dnie par les fonctions vitesse : I R+ , mode : I {On, O} et tche : I {vide} J. Ainsi, le cot dexcution est donn par cvitesse = vitesse(t) dt o lintegrale est calcule sur lintervalle I. Pour le cot du mode du systme, on note par S := {t I : mode(t) = On} le support de lordonnancement, et k le nombre dintervalles dans I\ S . Dans ce cas, cmode := kL + g| S | et si le systme est en mode On immdiatement avant et aprs lintervalle I, alors linterprtation consiste comptabiliser le cot de mise en marche L pour les intervalles O sur les extrmits de I sil en existe dans un ordonnancement optimal.

Nous xons la valeur d0 une distance susante de r1 telle que, sans perte de gnralit, lordonnancement optimal de toute sous-instance de la forme (1, k) dbute par un intervalle O. La proprit symtrique concernant la date rn+1 est aussi valable pour toute sous-instance de la forme (k, n). De ce fait, le cot de la sous-instance (1, n) est cohrent avec la dnition de la fonction du cot pour linstance entire. Notons, par ailleurs, que le cot dune solution optimale dune sous-instance de la forme (i, i 1) est gal min{L, g(ri di1 )}.

Considrons maintenant tous les intervalles denses et maximaux au sens de linclusion. Ces intervalles partitionnent laxe du temps en une squence dintervalles alternant entre des intervalles denses et des intervalles pars. Le lemme suivant est une consquence directe de la dnition des sous-instances. Nous insistons ici sur le fait que lhypothse des dates dchance agrables impliquent lindpendance des sousinstances. Comme il a t prcis dans le lemme 6, il existe un ordonnancement optimal obissant la discipline EDF (earliest deadline rst), ce qui veut dire que si une tche J j est ordonnance, alors toutes les tches Ji J j ont dj termin leurs excutions. Ainsi, lhypothse des instances

51

agrables est assez forte et donne une dcomposition du problme qui permet de suivre une approche de programmation dynamique. Cependant, le problme ne devient pas trivial tant donn quil reste dcider des modes du systme, i.e. quand est ce quon teint la machine et quand est ce quon la rveille. Lemme 7 Les intervalles pars I sont associs des paires (i, j), telles que la partie dun ordonnancement optimal pour linstance originale quon restreint lintervalle I soit aussi un ordonnancement optimal pour la sous-instance (i, j). De plus, aucune de ces sous-instances ne contient des intervalles denses.

2.5

S P

Dans cette partie du chapitre, nous considrons un ordonnancement optimal pour une sousinstance arbitraire compose par un ensemble de tches J et un intervalle I tel que tout sous intervalle de I soit pars. Tout au long de cette section, chaque fois que nous faisons rfrence des dates darrive/dchance rk , d , ceux-ci sont restreintes lintervalle I. Lemme 8 Pour chaque instant t I, vitesse(t) v .

Preuve Soit t un instant dans lintervalle I qui maximise vitesse(t), et supposons, par contradiction, que vitesse(t) > v . Considrons un intervalle maximal au sens de linclusion A t pendant lequel la vitesse est constamment gale vitesse(t). Soit Ji , . . . , Jk , Ji cet intervalle. Si A = [ri , dk ), alors A est un intervalle dense et ceci contredit le Lemme 7. Ainsi, linclusion A [ri , dk ) est stricte. Supposons que dk > u avec u = max A (lautre cas est symtrique). Par la proprit Job Span voque dans le Lemme 6, nous avons mode(u) = O, et il existe un instant t tel que la tche Jk soit ordonnance pendant [t , u). Ainsi, pour une valeur 1 susamment petite, il est possible tche(t) Jk , les tches ordonnances dans

dtirer lexcution de la tche Jk lintervalle [t , u ) pour u = t + (u t ) et diminuer sa vitesse 52

dexcution jusqu vitesse(t)/. Ceci donne une solution avec un cot total strictement infrieur, ce qui contredit loptimalit de lordonnancement. Le support de lordonnancement est compos de blocs spars par des intervalles darrt, i.e. systme en tat O. Nous nous proposons, maintenant, de montrer que les bords de ces blocs ont une structure particulire (Figure 2.3). Dnition 4 Un suxe est une paire de tches (Ja , Jb ) telle que Ja Jb et telle que toutes les

tches Ja , . . . , Jb soient excutes la vitesse critique v entre les dates ra et u avec u = ra + (wa + . . . + wb )/v , et mode(u) = O. La dnition dun prxe est symtrique, i.e. il sagit dune paire de tches (Ja , Jb ) telle que Ja Jb et o les tches Ja , . . . , Jb sont excutes la vitesse critique

v entre les dates s et db avec s = db (wa + . . . + wb )/v , et le systme passe de ltat O ltat On linstant s (mode(s ) = O pour une valeur > 0 susament petite).

Lemme 9 Soit [t, u) un intervalle darrt maximal au sens de linclusion dans I, cest dire mode(t ) = O pour tout t [t, u). Si t ne reprsente pas la borne infrieure de lintervalle I, alors il existe un suxe (a, b) se terminant linstant t = ra + (wa + . . . + wb )/v . Si u ne reprsente pas la borne suprieure de lintervalle I, alors il existe un prxe (b + 1, c) qui dbute linstant u = dc (wb+1 +. . .+wc )/v . De plus, si ces deux conditions sont vries, i.e. inf I < t < u < sup I, alors, sans perte de gnralit, on a rb+1 > t. Preuve Supposons, par contradiction, quil existe un intervalle [t0 , t) o le systme est en tat de marche et tel quune tche Jb = tche(t0 ) soit ordonnance la vitesse vitesse(t0 ) < v . Pour une valeur susamment petite > 0, soit t := t0 + (t t0 )/(1 + ). Considrons, maintenant, un nouvel ordonnancement o lintervalle [t0 , t) est compress lintervalle [t0 , t ) et o la vitesse de la machine est augmente par un facteur de 1 +. Dans ce cas lintervalle darrt [t, u) sera tendu [t , u) et il est clair que le cot total induit par ce nouvel ordonnancement est strictement infrieur, ce qui contredit loptimalit de la solution initiale. Ceci montre que si t nest pas la date de dbut de lintervalle I, alors il existe une tche Jb sexcutant juste avant linstant t, cest--dire dans lintervalle [t0 , t), la vitesse critique v . Nous allons, 53

1
w1 = 1

10

11

w2 = 1 w3 = 1 w4 = 2 w5 = 2 w6 = 3 w7 = 3 w8 = 2 w9 = 3 w10 = 3 w11 = 3

F. 2.3 Structure dun ordonnancement optimal pour une instance compose de 11 tches (les segments dintervalles reprsentent les disponibilits des tches et indiquent leurs dates darrive et dchance ainsi que leurs quantits de travail). Lordonnancement optimal rsultant est compos de 2 blocs spars par un intervalle darrt o le systme est en mode O (limit par la n de la tche 6 et le dbut de la tche 7). Les tches 5 et 6 forment le suxe du premier bloc. Les tches 1,5,6,7 et 11 sont excutes la vitesse critique v , alors que la tche 9 est ordonnance une vitesse suprieure, puisque [r9 , d9 ) est un intervalle dense. prsent, montrer quil existe une tche Ja telle que toutes les tches Ja ... Jb soient ordon-

nances la vitesse critique entre les dates ra et t. Dans le cas o t0 = rb , nous avons a = b. Sinon, admettons que rb < t0 . Dans lordonnancement considr, si le systme, juste avant linstant t0 , est en mode O, alors il sera possible de dcaler lgrement lexcution de la tche Jb dans lintervalle [t0 , t ) an dobtenir un ordonnancement de mme cot, mais en excutant la tche au plutt possible. Sans perte de gnralit, nous pouvons supposer que, juste avant t0 , une tche Jb1 est ordonnance dans un intervalle [t1 , t0 ). Par la proprit du Job Span dans le lemme 6 et par le lemme 8, la tche Jb1 est excute la vitesse critique v . Il sut, donc, ditrer ces mmes arguments pour t1 et Jb1 jusqu obtenir une tche Ja avec les proprits requises. Le mme argument est appliqu dune faon symtrique pour montrer lexistence dun prxe (b + 1, c) si linstant u nest pas la borne suprieure de lintervalle I. Maintenant, si le suxe et

54

le prxe existent tous les deux et rb+1

t, alors il est possible de dcaler lexcution de la tche

Jb+1 de lintervalle [u, wb+1 /v ) lintervalle [t, wb+1 /v ) donnant lieu un ordonnancement avec un cot qui peut tre soit le mme, soit rduit de L, si Jb+1 tait la seule tche dans le bloc correspondant. Nous pouvons, ainsi, supposer que t < rb+1 sans perte de gnralit. Avant de passer la description de notre algorithme bas sur la programmation dynamique, nous avons besoin dune dernire proprit sur les suxes et les prxes et qui peut tre dduite de la dnition suivante.

Dnition 5 Soit une sous-instance (i, j). Nous dnissons deux fonctions f, h : {i, . . . , j} {i, . . . , j} comme suit : f (a) est le plus grand indice de tche a < b k {a, . . . , b 1}, ra + (wa + . . . + wk )/v tche k < c j tel que pour tout

rk+1 , tandis que h(k) est le plus grand indice de d1 . Dans le cas o

j tel que pour tout {k + 1, . . . , c}, dc (w + . . . + wc )/v

il nexiste pas un indice b (resp. c) vriant les conditions dcrites ci-dessus, alors f (a) = a (resp. h(k) = k).

Lemme 10 Chaque suxe (a, b) satisfait b = f (a) et chaque prxe (k, c) satisfait c = h(k). La fonction f requiert un peu plus dattention an de pouvoir dcrire correctement notre algorithme de programmation dynamique. En eet, xons une tche Jb appartenant la sous-instance (i, j) et supposons quil existe plusieurs tches Ja ... Jk telles que f () = b pour tout

{a, . . . , k}. Dans ce cas, tant donn que, par le lemme 8, aucune de ces tches ne peut dpasser la vitesse critique, il est possible de supposer quun suxe (a, b) est tel que a soit le plus petit indice de tche vriant f (a) = b. Ainsi, nous limitons, pour la suite, le domaine de dnition de la fonction f ces tches. Ceci permet f dtre inversible, i.e. a = f 1 (b). Notons que par dnition de f , la the J j est dans le codomaine de f , ce qui implique que f 1 ( j) est bien dnie.

55

2.6

Pour chaque sous-instance (i, j), nous dsignons par Yi, j le cot dexcution cvitesse minimum plus g(r j+1 di1 ), et par Oi, j le cot dune solution optimale donne par le minimum de cvitesse + cmode . Dans le cas o la sous-instance (i, j) nest pas ralisable, i.e. si di1 r j+1 ou di1 = di ou r j = r j+1 , alors nous xons les valeurs de Yi, j et Oi, j +. Pour plus de simplicit, nous dnissons g := (g + (v ) )/v .

Thorme 3 La valeur donne par Oi, j satisfait la rcursion suivante : Si j = i 1, alors Oi, j = min{L, g(r j+1 di1 )}, sinon, soit k = f 1 ( j),

Oi, j

o la minimisation dans le dernier cas porte sur toutes les tches a {i + 1, . . . , j} et {b, c} avec b = f (a), b < j et c = h(b + 1). Sil nexiste pas de telles tches, alors la valeur de cette minimisation sera gale +. Preuve Le cas o j = i 1 est simple, puisque si lordonnancement est vide alors dans la solution optimale le systme sera soit en mode On mais nexcutant aucune tche, ou tout simplement teint, i.e. en mode O. Il est clair que le choix du mode dpend uniquement de la longueur de lintervalle [r j+1 , di1 ).

= min

Yi, j L + g (wi + . . . + wh(i) ) + Oh(i)+1, j Yi,k1 + g (w

k

(2.1)

+ . . . + w j) + L

min Yi,a1 + g (wa + . . . + wb ) + L + g (wb+1 + . . . + wc ) + Oc+1, j ,

Considrons, maintenant, une sous-instance (i, j) telle que i

j. Il est possible de montrer, par

induction sur j i, que pour chacun des quatre cas dcrits dans (2.1) il existe un ordonnancement ralisable ayant le cot correspondant. Dans la suite de cette preuve, nous considrons un ordonnancement S qui minimise cvitesse + cmode pour cette sous-instance, et nous nous proposons 56

que ce cot est donn par un parmi les quatre cas dans (2.1).

Si lordonnancement S ne met jamais le systme en mode O, alors la contribution de cmode dans le cot total est equivalente g(r j+1 di1 ). Par ailleurs, la contribution de cvitesse correspond la valeur minimale donne par Yi, j . Ainsi, le premier cas sapplique.

Supposons maintenant quil existe un intervalle [t, u) pendant lequel la machine est en mode O dans lordonnancement S , et considrons que [t, u) est le premier intervalle maximal par rapport linclusion. Il existe dans ce cas quelques cas considrer en fonction des conditions t = min I, u = max I, o I est lintervalle associ la sous-instance (i, j).

Tout dabord, il nest pas possible que les deux conditions soient vraies car ceci implique que lordonnancement est vide ce qui contredit lhypothse i j. Maintenant, si t = min I et u < max I, alors le Lemme 9 implique lexistance dun prxe (i, c) tel que c = h(i). La portion de lordonnancement S qui stale de linstant t jusqu linstant dc contribue au cot total de la solution par L + g (wi + . . . + wh(i) ), et par composition des ordonnancements, la suite de S , i.e. la portion sur lintervalle [dc , max I) contribue au cot par Oh(i)+1, j . Ainsi, le second cas de (2.1) sapplique.

Si t > min I et u = max I, dune faon similaire il existe un suxe (k, j) et le cot de lordonnancement du dbut de I jusqu rk est donn par Yi,k1 , puisque la machine nest jamais teinte durant cet intervalle, i.e. [min I, rk ). Le reste de lordonnancement stalant de rk jusqu u = max I contribue au cot par g (wk + . . . + w j ) + L. Dans ce cas la troisime alternative de (2.1) est applique.

Finalement, si t > min I et u < max I, de nouveau cause du Lemme 9, il existe un suxe (a, b) et un prxe (b + 1, c) entourant lintervalle [t, u) o la machine est teinte. Par le Lemme

57

10 nous avons b = f (a), c = h(b + 1). Ainsi, le cot de lordonnancement est dcompos en Yi,a1 pour la portion qui prcde ra et qui ne contient pas dintervalle o le mode est O, le cot g (wa + . . . + wc ) + L pour la portion reprsente par lintervalle [ra , dc ), et, enn, Oc+1, j qui correspond au cot du reste de lordonnancement par composition. Il sagit, donc, dappliquer le dernier cas de (2.1).

2.7

Le programme dynamique dcrit dans la section prcdente utilise O(n2 ) variables Oi, j , et pour chacune de ces variables une minimisation sur un ensemble de O(n) valeurs est requise. Ainsi, ce programme peut tre excut en O(n3 ).

Pour une sous-instance xe (i, j), il est possible de calculer les fonctions f et h indpendamment du programme dynamique laide de simples procdures en temps linaire comme suit :

- Initialement, := i et t := ri . Pour chaque k = i, i + 1, . . . , j : si t < rk alors := k, t := rk . Sinon, f () := k et t := t +

wk v .

- Initialement, := j et t := d j . Pour chaque k = j, j 1, . . . , i : si t > dk alors := k, t := dk . Sinon, h(k) := et t := t

wk v .

La dtermination des valeurs Yi, j est, cependant, cruciale puisque il en existe O(n2 ) et le meilleur algorithme dordonnancement pour rsoudre ces problmes retourne la solution optimale en O(n2 ) [81]. Ceci mne un temps total en O(n4 ) pour calculer ces valeurs. Nous dcrivons, dans la suite, une procdure permettant de calculer Yi, j dune faon itrative partir de Yi1, j en O(n), ce qui permettra de calculer tous les sous-ordonnancement cvitesse -optimaux en un temps total en O(n3 ).

58

Calcul des Yi, j

Nous prsentons le schma gnral pour le calcul des valeurs Yi, j . Tout dabord, nous dterminons Y1,n en O(n2 ) en utilisant lalgorithme dcrit dans [81]. Ensuite, nous calculons toutes les valeurs Y1, j pour j = n 1, . . . , 1 en un premier passage de droite gauche. Finalement, pour chaque j = 2, . . . , n x, nous eectuons un passage de gauche droite pour calculer toutes les valeurs Yi, j pour i = 2, . . . , j. Ce dernier passage de gauche droite est calcul de la faon suivante.

Soit en entre lordonnancement cvitesse -optimal S pour la sous-instance (1, j). Lordonnancement S consiste en une squence de blocs telle que chaque bloc stale sur un certain intervalle [t, u) et contienne une squence de tches qui sexcutent une vitesse constante dpendante du bloc en question. Nous appliquons S la procdure de compression que nous dcrivons maintenant.

Durant cette procdure, nous gardons la trace du premier bloc et nous supposons que ce bloc stale sur un intervalle [t, u) durant lequel les tches Ji , . . . , Jb sont excutes une vitesse v.

Initialement, i = 2, et nous considrons lopration qui consiste accrotre la vitesse v dans le but de compresser le bloc de tches lintervalle [u , u), avec := u (wi + . . . + wb )/v.

Tant que i

j et au fur et mesure que lopration de compression est applique, nous

dcidons du premier vnement qui survient parmi les vnements suivants (gure 2.4), et appliqons les actions correspondantes :

vnement de Non Faisabilit : Cet vnement a lieu si di1 = di . tant donn que dans la sous-instance (i, j) toutes les tches sont restreintes lintervalle [di1 , r j+1 ], il sen suit que la tche Ji serait restreinte un intervalle vide et de ce fait, ne peut tre ordonnance une

59

vitesse nie. Dans ce cas, laction consiste annoncer que la sous-instance (i, j) nest pas ralisable, xer Yi, j = +, et incrmenter i. Notons que si cet vnement se ralise, alors a sera le premier vnement puisquil ne dpend pas du changement de la vitesse mais uniquement de la structure de linstance.

vnement de Fusion : Cet vnement a lieu quand la vitesse v devient gale vitesse(u). Dans ce cas, laction consiste fusionner les deux premiers blocs. Notons que si u = db , alors cet vnement sera immdiatement suivi par un vnement de sparation appliqu au nouveau bloc rsultant de la fusion.

vnement de Sparation : un moment donn, la n dexcution dune tche Ji

Jk Jb

appartenant au premier bloc pourrait coincider avec sa date dchance. Ceci peut arriver lorsque la vitesse v atteint une vitesse dnie par s(k, b, u) = (wk+1 + . . . + wb )/(u dk ). Dans ce cas, le bloc sera scind en deux nouveaux blocs avec le premier bloc restreint lintervalle [t, dk ) et les tches Ji , . . . , Jk . On xe b := k, u := dk et on continue compresser le premier bloc obtenu.

vnement dchance : Quand v = (wi + . . . + wb )/(u di1 ), lordonnancement S obtenu sera lordonnancement cvitesse -optimal pour la sous-instance (i, j). Dans ce cas la procdure retourne S comme tant lordonnancement qui correspond Yi, j , limine la tche Ji de S , et incrmente la valeur de i.

Il faut prciser qu chaque instant, lalgorithme maintient un ordonnancement S pour la sous-instance compose de toutes les tches Ji , . . . , J j dont les dates darrive et les dates dchance sont restreintes lintervalle [u , r j+1 ]. Comme il a t mentionn, prcdemment, le calcul des valeurs Y1, j pour j = n 1, . . . , 1 se fait par un premier passage de droite gauche. En eet, lors de ce passage, il sagit dappliquer la mme procdure de compression mais dune

60

compression i t

i+1

b u

fusion

i u- u

sparation

k
dk

chance

di1

F. 2.4 Les dirents vnements durant la procdure de compression faon totalement symtrique. Ainsi, lvnement de Non Faisabilit par exemple aura lieu si r j = r j+1 et dans ce cas on xe Y1, j = + et on dcrmente j.

Il reste spcier la faon avec laquelle les dirents vnements sont dtrmins en un temps constant. Les vnements de Fusion et dchance sont dtrmins chacun par une expression unique et simple donnant la valeur laquelle ces vnements ont lieu. Cependant, en ce qui concerne lvnement de Sparation, la situation est plus subtile.

En eet, il existe b i candidats s(k, b, u), i.e. un pour chaque tche Ji

Jk Jb . Ainsi,

un pr-calcul de ces valeurs est ncessaire. Notons que pour une tche donne Jb , il existe O(n) instants dirents u considrer, et ils sont tous de la forme db , rb+1 et r j+1 pour tout 1 j n.

Ceci est d au fait que chaque bloc dans un ordonnancement optimal se termine soit la n de lintervalle I sil sagit du dernier bloc, soit lune des valeurs db , rb+1 , selon que le bloc suivant possde une plus grande ou plus petite vitesse.

61

Ainsi, il existe O(n3 ) valeurs de la forme s(k, b, u) calculer, et pour chaque paire (b, u), ceci peut tre ralis en un temps linaire en faisant varier k de b 1 1. Dans la procdure de compression, nous avons besoin de dterminer la tche k, i k b, qui minimise s(k, b, u). Il est clair que cette

tche k peut tre calcule en un temps constant pour chaque triplet (i, b, u) en faisant itrer i de b 1 1 pour chaque pair (b, u).

Finalement, dans la procdure de compression dcrite prcdemment, chaque tche peut engendrer au plus 3 vnements. Ainsi, pour une tche J j xe, la complexit est de O(n). Ceci induit un temps dexcution total en O(n3 ).

2.8

C
Nous avons considr dans ce chapitre le problme qui consiste ordonnancer sur une

seule machine un ensemble de tches caractrises par des dates darrive, des dates dchance et des quantits de travail. Lobjectif est de minimiser lnergie consomme en adaptant non seulement la vitesse mais aussi ltat de la machine. Il est ainsi question dteindre la machine aux moments opportuns et de choisir des vitesses dexcution appropries permettant de minimiser le nombre dalternance entre les priodes de veille et dactivit et de favoriser des priodes de veille longues. Nous avons donc propos un algorithme polynomial lorsque les dates dchance des tches sont agrables. Cette hypothse nous a aid dduire des proprits structurelles des solutions optimales faisant apparatre une dcomposition possible du problme et permettant ainsi de construire un algorithme de programmation dynamique qui retourne des ordonnancements sans premption des tches. Nous concluons donc quil nest pas possible de gnraliser cet algorithme pour traiter des instances avec des dates dchance arbitraires. Cependant, nous pensons que la procdure de compression qui permet de calculer les ordonnancements cvitesse -optimaux peut tre amliore davantage an daboutir une complexit en temps plus intressante. Finalement, une perspective intressante de ce travail consiste tendre ce modle dans le cas de plusieurs machines avec ou sans migration et/ou premption des tches. 62

O : `

3.1

I
Dans la littrature, la pluspart des travaux sur les problmes dordonnancement

en rapport avec la minimisation dnergie ont considr des environnements avec une machine unique [72, 6], ou des environnements avec des machines homognes parallles [28, 61, 73, 7]. Cependant, le recours aux systmes composs de processeurs htrognes semble tre une tendance dominante dans les architectures futures [23, 58, 65, 66].

Dans ce contexte, lutilisation de dispositifs de calcul htrognes la place dun unique systme compos de processeurs homognes parallles rend ncessaire lintroduction de modles qui tiennent compte de lhtrognit des processeurs. Nous prsentons dans ce chapitre un modle bas sur une extension naturelle du modle dordonnancement classique sur des machines non uniformes (htrognes) [15]. Nous considrons, ainsi, un ensemble J de n tches {J1 , . . . , Jn } et un ensemble de m machines non uniformes o

63

chaque machine peut changer sa vitesse dexcution en la choisissant parmi un ensemble ni de vitesses V. Chaque tche J j est caractrise par une pondration w j , une date darrive qui dpend de la machine, un temps dexcution et une nergie consomme fonctions de la machine et de la vitesse. Plus prcisment, ri j est la date darrive de la tche J j si elle est excute sur la machine i, tandis que pi jv et Ei jv reprsentent, respectivement, le temps dexcution et lnergie consomme par la tche J j si elle est excute sur la machine i la vitesse v V. Nous supposons que toutes ces valeurs sont entires et positives. Ce modle est bien adapt des architectures composes de machines spcialises qui excutent ecacement des tches de types particuliers. La dpendance des dates darrive aux machines est une hypothse pertinente dans le cas o les machines sont connectes par un rseau de communication. Dans ce cas, nous supposons que toutes les tches sont disponibles linstant 0 sur une machine particulire, et quune dure ri j doit scouler pour quune tche quelconque J j migre sur une machine i. Ce modle dordonnancement dans les rseaux a t introduit dans [14, 38]. Par ailleurs, les temps dexcution ainsi que lnergie consomme sont pr-calculs pour tout triplet de machine, tche et vitesse. Il est clair que le choix des vitesses des machines dpend des tches en excution et la puissance de consommation dnergie nobeit pas une loi particulire comme il tait le cas dans les chapitres prcdents. De plus, la premption et la migration des tches ne sont pas autorises. Le but est de trouver un ordonnancement ralisable minimisant la somme des temps de compltude pondrs plus lnergie consomme, i.e.
n j=1 w jC j

+ E, o C j reprsente le temps

de compltude (ou temps de n dexcution) de la tche J j et E lnergie totale consomme par lordonnancement. Si on tend la notation classique en trois champs de Graham et al. [42], ce problme peut tre not par RS | ri j |E + w jC j .

3.2

T
Gnralement, la minimisation de la consommation dnergie dans les systmes

informatiques est en opposition avec les critres doptimisation classiques qui traduisent la qualit 64

dun ordonnancement donn. Dans ce contexte, une multitude de problmes ont t tudis. Dans [72], Pruhs et al. ont initi ltude des problmes o un budget nergtique est donn, le but tant doptimiser une fonction objectif classique savoir le temps de rponse total1 (total ow time) sans dpasser ce budget. Dans le cas o les quantits de travail des tches sont unitaires, les auteurs ont prsent un algorithme polynomial lorsque les tches sont ordonnancer sur une seule machine. Loptimalit de cet algorithme a t prouv en modlisant le problme sous la forme dun programme convexe et en appliquant les conditions de Karush-Kuhn-Tucker (conditions KKT) [54, 57] pour dduire les conditions doptimalit. Par aileurs, Albers et Fujiwara se sont intresss dans [6] au problme de minimisation du temps de rponse total plus lnergie consomme. En utilisant une approche de programmation dynamique, les auteurs ont dcrit un algorithme optimal dans le cas o-line. Dans le cas on-line ils ont prsent une solution comptitive si les quantits de travail sont unitaires. Ils ont galement montr quaucun algorithme on-line ne peut raliser un rapport de comptitivit constant si les quantits de travail sont arbitraires. Dans [30], Chan et al. considrent le modle dadaptation de la vitesse (speed scaling) et imposent une borne maximale sur la vitesse des machines. tant donnes des tches avec des dates dchance, lobjectif est de maximiser le dbit, i.e. le nombre de tches excutes, tout en minimisant lnergie consomme lorsque la fonction de puissance est cubique. Il sagit en dautres termes de choisir parmi tous les ordonnancements qui maximisent le dbit, ceux qui dpensent le moins dnergie. Dans ce contexte, Chan et al. prsentent un algorithme on-line dont le rapport de comptitivit est constant.

Dans le modle classique sur plusieurs machines et sans introduction de lnergie, il existe un nombre important de travaux sur les problmes dordonnancement visant minimiser la somme des temps de compltude pondrs [33]. Dans le cas o les machines sont homognes (related) et en prsence de dates darrive, Chekuri et Khanna [32] ont prsent un shma dapproximation polynomial (PTAS) pour le problme Q| r j | w jC j . Dans le cas des machines

htrognes (unrelated), la situation est la suivante : si le nombre de machines est une constante
1

tant donn un ordonnancement quelconque, le temps de rponse dune tche Ji est le temps qui scoule entre sa

date darrive ri et sa date de compltude Ci .

65

xe, Rm||

w jC j , un shma dapproximation polynomial a t prsent par Afrati et al. dans

[1]. Dans le cas gnral o le nombre de machines fait partie de lentre du problme, il existe une (3/2 + )-approximation pour le problme R|| problme R| r j | w jC j et une (2 + )-approximation pour le

w jC j proposes par Shulz et Skutella [75]. Ces derniers rsultats sont bass sur

lapproche de lArrondi Alatoire [74].

Lapproche de larrondi alatoire prsente par Shulz et al. [75] consiste proposer une relaxation du problme en utilisant un programme linaire dont les variables sont indexes sur le temps. Ensuite, en se basant sur la solution fractionnaire du PL, on construit une solution entire laide de larrondi alatoire qui mne une 2-approximation. Dans le cas o toutes les tches sont relaches simultanment, cette technique donne une 3/2-approximation. tant donn que le nombre de variables indexes sur le temps est exponentiel dans la relaxation linaire du problme, les auteurs ont propos un autre PL de taille polynomial dont les variables sont indexes par des intervalles de tailles gomriques.

En utilisant la mme technique de lArrondi Alatoire, nous sommes capables de proposer un algorithme randomis donnant une 2(1 + )-approximation pour le problme qui tient compte de lnergie consomme. Avec cette mme technique, nous trouvons le mme rapport dapproximation pour le problme dordonnancement avec minimisation de la somme des temps de compltude pondrs avec un budget dnergie xe ne pas dpasser. laide de la notation de Graham, ce dernier problme peut tre not par RS |ri j , E| w jC j .

Indpendamment, Carrasco et al. [29] ont considr un modle proche au notre mais dans le cas dune machine unique. Plus prcisment, ils ont dcrit des algorithmes dapproximation avec des facteurs constants pour le problme dordonnancement sur une machine unique et visant minimiser la somme des temps de compltude pondrs plus lnergie consomme. Dans ce problme, la premption nest pas autorise et les fonctions de consommation dnergie sont dpendantes des tches qui possdent des dates darrive et dchance. Ils ont aussi tendu ces algorithmes pour le

66

problme de minimisation de la somme des retards pondrs plus lnergie (le retard dune tche est nul si sa date de compltude ne dpasse pas sa date dchance, et il est gal la dure de dpassement sinon). Pour tablir ces rsultats, les auteurs ont eu recours la technique des -points, base sur la programmation linaire entire.

3.3
I , 0

Dans cette partie du chapitre, nous prsentons une relaxation linaire de taille polynomiale du problme RS |ri j |E + w jC j . Soit T = maxi j ri j +
J j J

maxiv pi jv lhorizon du temps. On

discrtise lintervalle [0, T ] en des intervalles de tailles gomtriques comme suit : soit un rel > 0 et soit L le plus petit entier tel que (1 + )L L, par : [0, 1] I = (1 + )1 , (1 + ) I = (1 + )1 pour 1 T . On dnit, ainsi, lensemble des intervalles

si = 0, si 1 L.

Pour tout {0, . . . , L}, on note par |I | la taille de lintervalle I , et on a I0 = 1 et L. Par ailleurs, notons que puisque la taille de ces intervalles aug-

mente dune faon gomtrique, leur nombre est polynomial en la taille de linstance du problme.

Soit yi jv pour tout i = 1, . . . , m, J j J, = 0, . . . , L et v V lensemble des variables tel que yi js .|I | soit la dure de temps que prend lexcution de la tche J j pendant lintervalle |I | sur la machine i si celle-ci tourne la vitesse v. Ainsi, la variable yi jv peut tre considre comme tant la fraction de lintervalle |I | occupe par la tche J j sur la machine i lorsquelle tourne la vitesse v. Dune faon quivalente,
yi jv .|I | pi jv

est la fraction de la tche J j excute pendant I sur la machine

i la vitesse v. Nous considrons, galement, un second ensemble de variables : C LP pour tout j j = 1, . . . , n o chaque C LP correspond la date de compltude de la tche J j dans la relaxation. j Finalement, pour > 0, le programme linaire que nous notons par LP est dcrit comme suit :

67

min
i=1 J j J =0 vV

Ei jv

yi jv |I | + w jC LP j pi jv J J
j

s.c.
i=1

yi jv |I | = 1, pi jv =0 vV yi jv 1,
J j J vV

pour tout j, pour tout i et ,

(3.1) (3.2)

C LP j
i=1 m L

1 1 yi j0v |I0 | 1 + + 2 pi jv vV pour tout j, (3.3)

i=1 =1 vV

yi jv |I | 1 (1 + )1 + yi jv |I | , pi jv 2
m L

C LP j
i=1 =0 vV

yi jv |I |,

pour tout j,

(3.4)

yi jv = 0, pour tout i, j , (1 + ) ri j , v, (3.5) yi jv 0, C LP 0, j pour tout i, j , , et v, pour tout j. (3.6) (3.7)

Proposition 1 Le programme linaire LP est une relaxation du problme RS | ri j |E +

w jC j .

Preuve Lensemble des galits 3.1 garantissent que chaque tche sera excute en sa totalit. Les ingalits 3.2 expriment le fait que la dure dexcution totale sur une machine i et pendant un intervalle I ne dpasse jamais sa dure, i.e. |I |. En dautres termes, chaque machine peut excuter au plus une seule tche chaque instant. Lensemble des contraintes 3.3 donne une borne infrieure sur le temps de compltude de chaque tche dans tout ordonnancement ralisables. Lexactitude de cet ensemble de contraintes dcoule du lemme 11 quon dcrit dans la suite. La partie droite de chaque ingalit dans 3.4 reprsente le temps dexcution total de la tche J j J correspondante, et il sagit, ainsi, dune borne infrieure sur son temps de compltude. Finalement, les contraintes 3.5 impliquent que chaque tche J j peut tre excute dans nimporte quel intervalle condition

68

que sa date darrive sur une machine quelconque ne dpasse pas la borne suprieure de lintervalle en question. Notons que dans LP , le nombre de variables est polynomial en la taille de linstance du problme. Notons, aussi, que le programme linaire LP est en eet une relaxation du problme RS | ri j |E + w jC j , puisquil autorise la premption et lexcution parallle des tches, i.e. une tche peut tre excute simultanment sur deux machines direntes. Finalement, le lemme suivant termine la preuve.

Lemme 11 Pour chaque tche J j J, lingalit

m

C LP j

i=1

1 1 yi j0v |I0 | 1 + + 2 pi jv vV

i=1 =1 vV

yi jv |I | 1 (1 + )1 + yi jv |I | pi jv 2

est une contrainte valide dans la relaxation donne par le programme linaire LP . Preuve Dans [75], les auteurs ont prsent, dans un premier temps, une relaxation du problme R|ri j | w jC j o les variables sont indxes sur le temps et o la contrainte qui correspond

lingalit (3.3) de LP a t donne par :

C LP j

i=1 t=ri j vV

yi jtv 1 1 (t + ) + yi jtv , pour tout j = 1, . . . , n, pi jv 2 2

(3.8)

o la variable yi jtv reprsente la dure de temps octroye lexcution de la tche J j durant lintervalle de temps (t, t + 1] et sur la machine i lorsque celle-ci tourne la vitesse v V.

Considrons, par la suite, un ordonnancement quelconque ralisable dans lequel la tche J j est totalement excute et sans interruption sur une machine k entre les dates C pk js et C , j j C tant la date de n de la tche J j dans lordonnancement . Dans ce cas, la partie droite de j lingalit (3.8) correspond la date de n exacte C de la tche J j si on attribue des valeurs aux j variables yi jtv comme suit : yi jtv = 1 si i = k, v = s et t {C pk js , . . . , C 1}, et yi jtv = 0 sinon. j j

69

Finalement, nous remarquons que la partie droite de lingalit (3.8) domine celle de lingalit (3.3) puisque la borne infrieure t de tout intervalle = (t, t + 1] dans la relaxation indxe sur le temps est avance la borne infrieure (1 + )1 de lintervalle I tel que t I dans le programme linaire LP .

3.4

A ` RS | ri j |E + w jC j

Dans cette partie, nous nous inspirons de [75] an de proposer un algorithme randomis bas sur la relaxation linaire dcrite dans la section prcdente. Cet algorithme, not , tente de minimiser la somme des temps de compltude pondrs plus lnergie consomme et il est dcrit comme suit,

ALGORITHME (1) Calculer une solution optimale y de LP . (2) Attribuer chaque tche J j un triplet machine-intervalle-vitesse (i, I , v) dune faon indpendante et alatoire en utilisant la probabilit t j la valeur max{ri j , (1 + )1 }. (3) Ordonnancer sur chaque machine i les tches qui lui ont t aectes sans premption et dans lordre croissant des valeurs t j ; en cas dgalit la slection de la tche se fait dune faon indpendante et alatoire. Chaque tche est ordonnance le plus tt possible en tenant compte sa date darrive. Considrons par exemple linstance suivante : soit 4 tches J1 , J2 , J3 et J4 et soit deux machines M1 et M2 telles que chaque machine puisse fonctionner avec deux vitesses direntes, i.e. V = {v1 , v2 }. Le tableau 3.1 donne les dirents paramtres relatifs cette instance.
yi jv |I | pi jv ,

xer, ensuite,

Dans lexemple du tableau 3.1, lhorizon du temps est T = 24 et si nous xons = 1 alors 70

Ji J1 J2 J3 J4

wi 1 2 4 6

r1i 2 1 1 4

r2i 0 2 1 2

p1iv1 2 3 4 3

p1iv2 4 4 7 5

p2iv1 4 3 2 1

p2iv2 6 5 4 2

E1iv1 3 4 5 6

E1iv2 2 1 5 3

E2iv1 5 4 4 7

E2iv2 1 3 2 5

T. 3.1 Exemple dapplication de lalgorithme : instance avec 4 tches, 2 machines et 2 vitesses direntes pour chaque machine. nous obtenons six intervalles de tailles gomtriques dcrits dans la gure 3.1.

16

32

I0

I1

I2

I3

I4

I5

F. 3.1 Lensemble des intervalles gomtriques dduits de linstance du problme RS | ri j |E + w jC j rsume dans le tableau 3.1.

En appliquant, tape par tape, lalgorithme cette instance, nous obtenons une solution optimale du programme linaire LP1 donne par y = {y1121 = 1; y1222 = gure 3.2.
1 6 ; y1232 5 6 ; y2102

= 1; y1212 =

2 3 ; y2311

= 1; y2321 =

1 2 ; y2421

1 2 }.Cette

solution est schmatise dans la

Ensuite, une aectation alatoire suivant les probabilits

yi jv |I | pi jv

peut conduire placer :

la tche J1 sur la machine M2 , dans lintervalle I0 et la vitesse v2 . la tche J2 sur la machine M1 dans lintervalle I1 et la vitesse v2 . la tche J3 sur la machine M2 dans lintervalle I1 et la vitesse v1 . la tche J4 sur la machine M2 dans lintervalle I2 et la vitesse v1 .

Ainsi, les valeurs t j xes pour chaque tche sont donnes par : {t1 = 0; t2 = 1; t3 = 1; t4 = 2} 71

v1 v2 J2 J1 J2 J2

v1 v2 J1 I0

J3

J3 I2

J4 I3

I1

F. 3.2 Solution optimale du programme linaire appliqu sur linstance du problme RS | ri j |E + w jC j rsume dans le tableau 3.1. et lordonnancement nal est dcrit dans la gure 3.3.

v2 J2

Machine 1

v1 v2 J1 I0 0 1 I1 I2 5 I3 6

J3

J4 I4 8 9

Machine 2

F. 3.3 Solution retourne suite lexcution de lalgorithme sur linstance du problme RS | ri j |E + w jC j du tableau 3.1.

Dans la suite, nous tendons lanalyse prsente dans [75] pour inclure lnergie consomme.

Lemme 12 Leprance sur le temps de compltude de chaque tche J j J dans lordonnancement construit par lalgorithme est au plus 2(1 + )C LP pour tout > 0. Dans le cas j o toutes les tches sont disponibles la date 0, cette esprance est majore par 3/2(1 + )C LP . j Preuve Soit une instance quelconque du problme RS | ri j |E + w jC j , et soit une tche J j J.

Notons par (i, h, v j ) le triplet machine-intervalle-vitesse auquel la tche J j est aecte dans lordonnancement construit par lalgorithme et soit t j = max{ri j , (1 + )h1 } la valeur attribue J j . Par ailleurs, soit K lensemble des tches excutes sur la machine i durant lintervalle de temps (, C j ], tant la date au plutt telle quil nexiste pas de priode dinactivit dans 72

lordonnancement construit durant (, C j ]. Supposons aussi que chaque tche Jk K est excute une vitesse vk . Ainsi, nous avons :

pikvk = C j .
Jk K

(3.9)

tant donn quaucune des tches Jk K ne commence aprs la tche J j , alors elles ont forcment t tries suivant les valeurs tk attribues par lalgorithme tel que tk t j Jk K. En particulier, rik tk t j Jk K, et puisquil nexiste pas de priode dinactivit durant lintervalle (, C j ], on a t j si t j < alors il existerait une priode dinactivit durant [t j , ), or ceci nest pas possible tant donn que les tches sont excutes au plus tt et quon aurait dans ce cas rik pout toute tche k K . Avec lgalit (3.9) nous obtenons : Cj tj +
kK

pikvk .

An danalyser lesprance sur le temps de compltude E[C j ] de la tche J j , nous commenons par xer laectation de J j au triplet machine-intervalle-vitesse (i, Ih , v j ), et prouvons, par la suite, lexistence dune borne suprieure sur lesprance conditionnelle Ei,h,v j [C j ] :

Ei,h,v j [C j ] t j +Ei,h,v j
Jk K

pikvk t j +pi jv j +
Jk J j vV

pikv .Pr[Jk aecte i avant J j la vitesse v]

h1

= t j + pi jv j +
Jk J j vV

pikv
=0 yikhv |Ih | pikv

yikv |I | 1 yikhv |Ih | . + pikv 2 pikv

(3.10)

Notons que le facteur

1 2

qui prcde le terme

rsulte de la slction alatoire en cas dgalit

des valeurs t j . Ensuite, en utilisant les contraintes (3.2), nous obtenons :

h1

Ei,h,v j [C j ] t j + pi jv j +

1 |I | + |Ih | 2 =0

Dans le cas o h = 0, en utilisant les contraintes 3.5 du LP et comme les dates darrive sont entires positives, nous avons ri j = 0, donc t j = max{ri j , 0} = 0. Ainsi,
h1

t j + pi jv j +

1 1 |I | + |Ih | = pi jv j + |I0 | 2 2 =0 73

sinon (h 1), nous avons :

h1

t j + pi jv j +

1 |I | + |Ih | = t j + pi jv j + (1 + )(1 + )h1 2 2 =0

(comme t j < (1 + )h pour tout h = 0, . . . , L)

Ei,0,v j [C j ] pi jv j + et si h > 0,

1 2

Ei,h,v j [C j ] pi jv j + (1 + )h + (1 + )(1 + )h1 pi jv j + 2(1 + )h 2 Finalement, lesprance sur le temps de compltude de la tche J j peut tre formule comme suit :

E[C j ] =
i=1

yi jv .|I | .Ei,,v[C j ] pi jv =0 vV
m i=1

=
i=1

yi j0v .|I0 | .Ei,0,v [C j ] + pi jv vV

m i=1

yi jv .|I | .Ei,,v[C j ] pi jv =1 vV

i=1

yi j0v .|I0 | 1 .(pi jv j + ) + pi jv 2 vV

yi jv .|I | .(pi jv + 2(1 + ) ) pi jv =1 vV

=
i=1

1 1 )+ yi j0v .|I0 |.(1 + . 2 pi jv vV

yi jv .|I | + 2(1 + )
i=1 =1 vV i=1

yi jv .|I | (1 + )1 pi jv =1 vV

= 2(1+)
i=1

1 1 1 .yi j0v .|I0 |.(1+ . )+ 2(1 + ) 2 pi jv i=1 vV

1 .yi jv .|I |+ 2(1 + ) i=1 =1 vV

yi jv .|I | (1+)1 pi jv =1 vV

2(1+)
i=1

1 1 .yi j0v .|I0 |.(1+ )+ 2(1 + ) pi jv i=1 vV

1 .yi jv .|I |+ 2(1 + ) i=1 =1 vV

yi jv .|I | (1+)1 pi jv =1 vV

74

2(1 + )
i=1

1 1 .yi j0v .|I0 |.(1 + )+ 2 pi jv vV

m i=1

1 .yi jv .|I | + 2 =1 vV

m i=1

yi jv .|I | (1 + )1 pi jv =1 vV

Cette dernire ingalit est valide tant donn que > 0. En utilisant les contraintes (3.3) de LP , on obtient : E[C j ] 2(1 + )C LP . j Maintenant, notons que si toutes les tches sont relaches la date 0 alors = 0. En utilisant les mmes arguments, nous avons :

Ei,0,v j [C j ] pi jv j + dans le cas o h > 0,

1 2

Ei,h,v j [C j ] pi jv j + (1 + )(1 + )h1 pi jv j + (1 + )h 2 Ensuite, lesprance sur le temps de compltude peut tre borne par :

E[C j ] (1+)
i=1

1 1 1 .yi j0v .|I0 |.(1+ . )+ (1 + ) 2 pi jv i=1 vV

1 .yi jv .|I |+ (1 + ) i=1 =1 vV

yi jv .|I | (1+)1 pi jv =1 vV

= (1+)
i=1

1 1 .yi j0v .|I0 |.(2+ )+ 2(1 + ) pi jv i=1 vV

1 .yi jv .|I |+ (1 + ) i=1 =1 vV

yi jv .|I | (1+)1 pi jv =1 vV

= (1+)

1 2

m i=1

1 1 .yi j0v .|I0 |+ (1 + ) 2 vV

m i=1 L

m i=1

1 .yi jv .|I |+ (1 + ) i=1 =1 vV

m i=1 L

1 1 .yi j0v .|I0 |.(1+ )+ 2(1 + ) pi jv vV

1 .yi jv .|I | + 2(1 + ) =1 vV

yi jv .|I | (1 + )1 pi jv =1 vV

tant donn que > 0, 75

1 (1+) 2

m i=1

1 yi j0v .|I0 |+ 2 vV

yi jv .|I |+
i=1 =1 vV m i=1 L i=1

1 1 .yi j0v .|I0 |.(1+ )+ 2 pi jv i=1 vV

1 .yi jv .|I |+ 2 =1 vV

yi jv .|I | (1 + )1 pi jv =1 vV

1 = (1+) 2

yi jv .|I |+
i=1 =0 vV i=1

1 1 .yi j0v .|I0 |.(1+ )+ 2 pi jv i=1 vV

1 .yi jv .|I |+ 2 i=1 =1 vV

yi jv .|I | (1+)1 pi jv =1 vV

Finalement, les contraintes (3.4) et (3.3) conduisent :

E[C j ] (1 + ) .

1 LP 3 C j + C LP = (1 + )C LP j j 2 2

Notons par OPT la valeur optimale de la fonction objective dnie par OPT = E +
J j J

w jC , o E est la consommation dnergie optimale et C est le temps de compltude j j

optimal pour chaque tche J j J. Thorme 4 tant donne une instance du problme RS | ri j |E + rithme construit un ordonnancement tel que E[E + w jC j et un rel > 0, lalgow jC j ] 2(1 + )OPT .

Preuve Par le lemme 12, nous avons E C j 2(1 + )C LP . Par ailleurs, tant donn que les poids j w j sont positifs, il sen suit que E
J j J

w jC j 2(1 + )

J j J

w jC LP. j

Rappelons que Ei jv reprsente la quantit dnergie que la machine i consomme si elle excute la tche J j la vitesse v. Soit E j lnergie totale consomme suite lexcution de la tche J j dans lordonnancement retourn par lalgorithme . Nous avons alors, E[E j ] =
m i=1 vV

Pr[J j aecte la machine i la vitesse v] Ei jv avec Pr[J j aecte la

L yi jv |I | =0 pi jv .

machine i la vitesse v] =

Ainsi, E[E j ] =

m i=1

L =0

vV

yi jv |I | pi jv E i jv .

Lesprance

sur lnergie totale consomme par toutes les machines dans lordonnancement est donne par :

76

E[E] =

J j J

E[E j ]. Donc, E[E] = E LP o E LP est la consommation de lnergie calcule par le

programme linaire LP .

Comme le programme linaire est une relaxation du problme R| ri j |E +

w jC j , la solution

optimale de LP reprsente une borne infrieure pour la solution dun ordonnancement optimal. Donc : E E+
J j J

w jC j E LP + 2(1 + )
J j J

w jC LP j w jC . j
J j J

2(1 + ) E LP +
J j J

w jC LP 2(1 + ) E + j

Pour le problme RS ||E +

w jC j o toutes les tches sont disponibles la date 0, lalgorithme

jJ

retourne une solution qui vrie E

w jC j 3 (1 + ) 2

J j J

w jC LP . Ce rsultat j

peut tre prouv dune manire simple en utilisant le lemme 12 et les mmes arguments dans la preuve du thorme 4.

3.4.1 Drandomisation
Lalgorithme , dcrit pralablement, est un algorithme randomis qui retourne une solution ralisable dont la valeur de lesprance de la fonction objectif est borne en fonction de la solution optimale. Ainsi, ne fournit pas une garantie ferme sur la qualit de la solution retourne. Il est donc intressant de concevoir un algorithme dterministe dans le but davoir une performance xe dans le pire cas. Ceci peut tre fait laide de la drandomisation qui consiste slctionner le meilleur choix des valeurs attribues aux variables alatoires qui minimise le cot global de la solution. Une mthode classique de drandomisation appele la mthode des probabilits conditionnelles considre les dcisions alatoires une une et choisit toujours lalternative la plus intressante. Une alternative est dite plus intressante si lesprance conditionnelle sur la valeur de la solution correspondante est la plus petite possible. Dans la suite, nous allons utiliser cette mthode pour drandomiser lalgorithme o

77

lobjectif est de minimiser la somme des temps de compltude pondrs plus lnergie.

An dutiliser la technique des probabilits conditionnelles, nous avons besoin de calculer chaque tape les valeurs exactes des esprances conditionnelles dnies plus loin dans cette section. Nous avons, donc, besoin de faire une lgre modication sur lalgorithme en remplaant sa dernire tape par :

(3 ) Ordonnancer sur chaque machine i les tches qui lui ont t aectes sans premption et dans lordre croissant des valeurs t j ; en cas dgalit la slection de la tche se fait dune faon indpendante et alatoire. Chaque tche est ordonnance le plus tt possible en tenant compte de sa date darrive et de telle manire ce que, sur la machine i, la priode dinactivit totale avant le dbut dexcution dune tche J j , aecte cette machine, soit gale t j . An dexpliquer brivement cette modication, supposons qu on aecte un ensemble de tches J1 , . . . , J p une machine i et aux vitesses v1 , . . . , v p avec une valeur t j attribue chaque tche J j . Supposons, aussi que ces tches sont donnes dans lordre croissant des t j . Ltape (3 ), stipule quau dbut de lexcution de chaque tche J j , la priode totale dinactivit sur la machine est gale t j . Ainsi lordonnancement retourn respecte les rgles suivantes :

1. Excuter la premire tche J1 la date t1 la vitesse v1 . Cette tche se termine donc la date t1 + pi1v1 . 2. Supposons, qu la n dune tche J j , la priode totale dinactivit sur la machine i est gale t j et soit f j la date de n de la tche J j . Maintenant, pour ordonnancer la tche J j+1 , il faut considrer deux cas dirents :

si t j+1

f j , alors excuter la tche J j+1 la date f j + (t j+1 t j ).

si t j+1 > f j , alors excuter la tche J j+1 la date t j+1 + pi jv j . Si on applique cette modication sur lordonnancement retourn par pour

78

s2

J2

Machine 1

Machine 2
s1 s2 J1 I0 0 1 I1 I2 5 I3 6 7 9

J3 I4 10

J4

11

F. 3.4 Solution retourne suite lexcution de lalgorithme modi sur linstance du problme RS | ri j |E + w jC j du tableau 3.1.

linstance du tableau 3.1 dcrite dans les sections prcdentes, nous obtenons un second ordonnancement qui, dans ce cas, scarte lgrement du premier. Ce nouvel ordonnancement est schmatis dans la gure 3.4.

Dans la preuve du lemme 12, nous avons born le temps dinactivit avant la date de dbut de la tche J j par t j . Donc, cette analyse reste valable dans le cas de la modication apporte sur lalgorithme . Lavantage principal de la modication de ltape (3) est la possibilit dexprimer dune faon prcise les esprances sur les temps de compltude des tches. Soit y une solution optimale du programme linaire LP retourne par la premire tape de lalgorithme . En utilisant les mmes arguments que dans la preuve du lemme 12, lalgorithme modi construit une solution pour laquelle lesprance sur le temps de compltude de chaque tche J j est gale :
m

E[C j ] =
i=1

yi jv .|I | . t j + pi jv + pi jv J =0 vV

yikhv .|Ih | +
J j vV h=0 Jk J j

1 yikv .|I | 2 vV

Rappelons, aussi, lesprance sur la consommation dnergie pour chaque tche J j donne dans la preuve du thorme 4 est :

E[E j ] =
i=1

yi jv |I | Ei jv pi jv =0 vV

Par ailleurs, nous dnissons lesprance conditionnelle sur le temps de compltude et sur la consommation dnergie dune tche J j si les tches dans un sous ensemble K J ont dj t

79

aectes des triplets de machine-intervalle-vitesse. Pour chaque tche Jk K on associe une variable binaire (0/1) ikv qui indique si la tche Jk a t aecte un triplet machine-intervallevitesse (i, , v) ( ikv = 1) ou pas ( ikv = 0). Ceci nous permet de donner les expressions suivantes pour formuler les esprances conditionnelles sur le temps de compltude et la consommation dnergie des tches J j . Dans le cas o J j K nous avons :

EK, [C j] =
i=1

yi jv .|I | . t j + pi jv + pi jv =0 vV +

ikhv .pikv +
Jk K vV h=0 1 Jk K

1 ikv .pikv 2 vV 1 yikv .|I | , 2 vV

yikhv .|Ih | +
Jk J\(K{J j }) vV h=0 Jk J\(K{J j })

et,

EK, [E j ] = E[E j ]. Dans le cas o J j K, alors on a :

EK, [C j] = t j + pi jv +
Jk K\{J j } vV h=0

ikhv .pikv +
Jk K\{J j } 1

1 ikv .pikv 2 vV 1 yikv .|I |, 2 vV

+
Jk J\K vV h=0

yikhv .|Ih | +
Jk J\K

et,

EK, [E j ] = Ei jv . o (i, , v) est le triplet machine-intervalle-vitesse auquel la tche J j est aecte, i.e. i jv = 1, et t j = max{ri j , (1 + )1 }. Notons que lesprance conditionnelle sur lnergie consomme est gale lesprance non conditionnelle puisque la consommation de lnergie dune tche dpend uniquement de son aectaion une machine et une vitesse. Finalement, lesprance conditionnelle 80

sur le temps de compltude plus lnergie pour une tche quelconque J j peut tre calcule par EK, [C j + E j ] = EK, [C j ] + EK, [E j ].

tant donne une tche J j

K, le lemme suivant montre quil existe toujours une aectation

dterministe de J j qui amliore lesprance conditionnelle correspondante. Lemme 13 Soit une solution optimale y du programme linaire LP et soit K J. Soit, aussi, une aectation xe des tches dans K des triplets de machine-intervalle-vitesse. Considrons, par ailleurs, une tche J j J\K. Il existe, alors, une aectation de la tche J j un triplet de machine-intervalle-vitesse (i, , v) (i.e. i jv = 1) avec ri j (1 + )1 tel que : EK{J j },
Jk J

wkCk + Ek EK,
Jk J

wk C k + E k .

(3.11)

Preuve Lesprance conditionnelle dans la partie droite de lingalit (3.11) peut tre formule comme tant une combinaison convexe des esprances conditionnelles EK{ j},
Jk J

wk C k + E k

sur toutes les aectations possibles de la tche J j des triplets de machine-intervalle-vitesse (i, , v) comme suit :

EK,
Jk J

wk C k + E k =
i=1 =0 vV

EK{J j },
Jk J

wk C k + E k .

yikv .|I | . pikv

Finalement, la version drandomise de lalgorithme peut tre dcrite par :

81

ALGORITHM (1) Calculer une solution optimale y de LP . (2) Fixer K := ; = 0 ;J j J faire i) pour toute aectation possible de la tche J j un triplet machine-intervallevitesse (i, , v) (i.e., i jv = 1) calculer EK{J j }, [ wk C k + E k ] ;
Jk J

ii) attribuer la tche J j au triplet machine-intervalle-vitesse (i, , v) qui minimise lesprance conditionnelle EK{J j }, [ iii) xer K := K {J j }. (3) Ordonnancer sur chaque machine i les tches qui lui ont t aectes sans premption et dans lordre croissant des valeurs t j ; en cas dgalit, la slection de la tche se fait dune faon indpendante et alatoire. Chaque tche est ordonnance le plus tt possible en tenant compte sa date darrive et de manire ce que, sur la machine i, la priode dinactivit totale avant le dbut dexcution dune tche J j , aecte cette machine, soit gale t j . Nous obtenons ainsi une version dterministe de lalgorithme et qui prserve la qualit des solutions retournes. Thorme 5 Lalgorithme est un algorithme dterministe et polynomial dont la garantie de performance est au moins aussi bien que la garantie de performance espre de lalgorithme probabiliste . Preuve Le thorme dcoule directement du lemme 13 et du thorme 4. wk C k + E k ] ;
Jk J

3.5

E ` RS |ri j , E|

w jC j

Dans cette partie, nous montrons quil est possible dtendre lapproche prcdente w jC j . Ce problme consiste ordonnancer, sous le mme

pour approcher le problme RS |ri j , E|

modle, un ensemble des tches J pour minimiser la somme des temps de compltude pondrs sans que lnergie consomme ne dpasse une borne xe B. 82

Il est possible de relaxer ce problme en considrant une lgre modication du programme linaire LP prcdemment dcrit :

min
J j J

w jC LP j

s.t.
i=1

yi jv |I | = 1, pi jv =0 vV
J j J vV

pour tout j,

(3.12) (3.13)

yi jv 1, pour tout i et ,
m

C LP j
m L

i=1

1 1 yi j0v |I0 | 1 + + 2 pi jv vV pour tout j, (3.14)

i=1 =1 vV

yi jv |I | 1 (1 + )1 + yi jv |I | , pi jv 2
m L

C LP j
i=1 =0 vV m L

yi jv |I |, Ei jv yi jv |I | B, pi jv

pour tout j,

(3.15)

(3.16) (3.17) (3.18) (3.19)

i=1 J j J =0 vV

yi jv = 0, pour tout i, j , (1 + ) ri j , et v, yi jv 0, C LP 0, j pour tout i, j , , et v, pour tout j.

Tout dabord, notons ce programme linaire par LP (B) et remarquons que la contrainte supplmentaire 3.16 a t ajoute pour exprimer le fait que la consommation globale dnergie ne doit pas dpasser un budget donn B. Dans la suite, nous allons appliquer lalgorithme probabiliste dcrit prcdemment et exhibons une borne probabiliste sur la somme des temps de compltude pondrs avec un dpassement du seuil dnergie autoris. Soit OPT (B) la valeur optimale de la fonction objective Thorme 6 Soit une instance du problme RS | ri j , E | w jC j pour un seuil dnergie x B. w jC j et un rel > 0. Lalgorithme

83

 construit un ordonnancement ralisable tel que E[ w jC j ] 2(1 + )OPT (B) et E[E] B. Preuve E
J j J

Nous montrons, de la mme faon que dans la preuve du thorme 4, que w jC j 2(1+)OPT (E) et que E[E] =
J j J

E[E j ] =

J j J

m i=1

L =0

vV

yi jv |I | pi jv E i jv .

Nous concluons laide de la contrainte 3.15 que E[E] B. Il faut noter que le thorme 6 ne garantit pas que ces bornes sur la somme des temps de compltude pondrs et sur lnergie sont respectes simultanment pour toute instance du problme. Dans le but de pallier cet inconvnient, nous proposons une garantie probabiliste sur les deux critres pour toute instance du problme.

Thorme 7 Soit une instance du problme RS | ri j , E |

1 u

w jC j et soit deux rels u, w > 0 tels que

1 w

1 et un rel > 0. Lalgorithme construit un ordonnancement ralisable qui

vrie : Pr[
j

w jC j < 2u(1 + )OPT (B) et E < wB] 1

1 1 . u w

Preuve Rappelons qutant donne une variable alatoire X et un rel a > 0, lingalit de Markov stipule que Pr[X a] E(X)/a. Ainsi, nous avons : Pr[
j

w jC j uE(
j

w jC j )] 1/u

et Pr[E wE(E)] 1/w. Dans le thorme 4 nous avons montr que, E(

j

w jC j ) 2(1 + )OPT (B)

et E(E) B,

84

do, Pr[

j w jC j

2u(1 + )OPT (B)] 1/u et Pr[E wB] 1/v. En utilisant lingalit de

Boole [22], nous avons : Pr[

j

w jC j 2u(1 + )OPT (B) ou E wB] 1/u + 1/w,

et nalement, Pr[
j

w jC j < 2u(1 + )OPT (B) et E < wB] 1 1/u 1/w.

3.6

C
Dans ce chapitre nous avons introduit une extension naturelle du problme dordon-

nancement classique sur des machines htrognes en tenant compte de lnergie consomme. Nous avons, donc, considr le modle qui consiste ordonnancer sur des machines htrognes, sans premption, des tches caractrises par des dates darrive, des dures dexcution et des quantits dnergie consommes. Dans ce modle, nous avons introduit un ensemble ni de vitesses auxquelles les machines peuvent tourner et tel que chaque tche soit excute dune faon non-premptive et une vitesse constante. Lhtrogneit des machines rside dans le fait que pour chaque tche la dure dexcution ainsi que la quantit dnergie consomme dpendent de la machine et de la vitesse dexcution. En revanche, les dates darrives des tches dpendent uniquement des machines auxquelles elles sont aects.

Dans un premier temps, nous avons considr le problme baptis RS |ri j |E +

w jC j qui

consiste minimiser la somme des temps de compltude pondrs plus lnergie totale consomme par toutes les machines. Nous avons prouv que lanalyse de la performance de lalgorithme randomis prsent dans [75] et bas sur la technique de larrondi alatoire peut tre tendue pour le problme en question et que la qualit de la solution retourne reste prserve avec ou sans des dates darrive. Nous avons aussi drandomis cet algorithme en utilisant la mthode des probabilits conditionnelles.

85

Dans un deuxime temps, nous avons condidr le problme RS |ri j , E|

w jC j dans lequel

nous xons un seuil dnergie total ne pas dpasser et nous cherchons minimiser la somme des temps de compltude pondrs. En utilisant le mme algorithme randomis, nous avons propos une borne probabiliste intressante sur la fonction objectif avec un dpassement du seuil dnergie.

Pour ce dernier problme, i.e. RS |ri j , E|

w jC j et dun point de vue pratique, une question

intressante serait de savoir sil est possible de concevoir un moyen ecace de drandomisation permettant de prserver les bornes obtenues. Dans ce contexte, la dicult rside dans laspect antagoniste entre la minimisation du temps de compltude et lnergie consomme, et aussi dans labsence de corrlation entre ces deux critres dans le modle tudi. Ainsi, la mthode de drandomisation base sur les probabilits conditionnelles savre inecace tant donn que pour faire un choix une tape donne, la notion de solution intressante nest pas dnie.

Par ailleurs, nous soulignons que Skutella a propos dans [77] une approche alternative base sur la relaxation quadratique et sur la mme technique darrondi alatoire pouvant amliorer la qualit de la solution du problme de minimisation de la somme des temps de compltude pondrs. Ainsi, une autre question intressante est de savoir si cette approche pourrait tre adapte dans le cas des problmes traits dans ce chapitre.

Finalement, une perspective de cette tude consiste considrer le cas o chaque machine peut choisir sa vitesse dans un spectre continu de valeurs relles et positives. Il serait, ainsi ncessaire de dnir des fonctions continues de la vitesse dcrivant, dune part, lvolution des temps dexcution des tches, et, dautre part, lvolution des quantits dnergie consommes par chaque tche.

86

4.1

I
Le dploiement largi des architectures parallles a fait que les problmes dordon-

nancement sur des machines parallles soient au coeur du dveloppement et de lecacit de ces architectures. Ce type de problmes a t sujet de recherches intensives depuis plusieurs annes [46]. En particulier, les problmes dordonnancement qui visent minimiser le temps dexcution total (makespan), sur des machines identiques et en prsence de contraintes de prcdence ont t largement tudis. Dans ce type de problmes, les contraintes de prcdence sont modlises par un graphe orient et acyclique DAG dont les sommets reprsentent les tches ordonnancer et les arcs reprsentent les contraintes de prcdence. Ainsi, sil existe un arc partant dune tche a vers une tche b dans le graphe de prcdence : a b, alors lexcution de b ne peut commencer que si lexcution de a prend n. Gnralement, les contraintes de prcdence sont issues de la paralllisation dun programme squentiel et traduisent des dpendances de donnes entre les tches, i.e. une tche ne peut commencer que si ses prdecesseurs lui fournissent des donnes ncessaires pour son excution. La gure 4.1 montre un ordonnancement possible sur deux machines dans un graphe de prcdence avec 4 tches unitaires. Notons que cet ordonnancement est optimal par rapport la minimisation du makespan.

87

b a c d

b c

M1 M2

F. 4.1 Ordonnancement dun graphe de prcdence avec 4 tches unitaires : les tches a, b et d sexcutent sur la machine M1 et la tche c sur la machine M2 . Un modle plus raliste considre des dlais supplmentaires ncessaires au tranfert des donnes entre deux tches dans le cas o elles sont relies par une contrainte de prcdence et sont excutes sur deux machines direntes. Il sagit en eet dun dlai qui doit scouler la suite de lexcution dune tche et avant que lexcution de son successeur ne puisse commencer sur une autre machine. La valeur de ce dlai, connu sous le nom de temps de communication, dpend de la paire des tches considre et elle est nulle si les tches successives sexcutent sur la mme machine. Dans la gure 4.2, nous reprenons lexemple de la gure prcdente en imposant des temps de communication unitaires pour les paires des tches (a, b), (b, d) et (c, d), et un temps de communication gal 2 pour la paire de tches (a, c). Nous considrons la minimisation du makespan et prsentons deux solutions : une solution optimale et une autre non optimale. Notons, aussi, que ces temps de communication sont dits grands si leurs valeurs dpassent les dures dexcution des tches.
1 2

b
1 1

a d 0 1

M1 M2

Ordonnancement optimal

b c

M1 M2

Ordonnancement non optimal

F. 4.2 Ordonnancement dun graphe de prcdence en prsence des temps de communication entre les tches. Les arcs sont pondrs par les temps de communication.

88

Par ailleurs, nous considrons un systme de tches types o chaque tche est caractrise par un type x lavance et qui dtermine une seule machine sur laquelle la tche peut sexcuter. On parle alors dun modle de machines ddies o chaque machine est spcialise dans lexcution dun seul type de tche et tel quil existe une seule machine par type. Dans ce cas, laectation des tches aux machines est connue au pralable ce qui permet de savoir lavance si les temps de communication sappliqueront ou non entre toute paire de tches relies par un arc de prcdence. La gure 4.3 montre deux exemples dordonnancement de 3 tches types sur 2 machines ddies avec des temps de communication unitaires. Dans le premier exemple, les tches a et b sont de type 1 et la tche c est de type 2. Dans le second exemple, la tche a est de type 1 et les tches b et c de type 2.
b (type 1) a (type 1)
1 1

b d

M1 M2

c (type2)
b (type 2) a (type 1)
1 1

a b c 3 4

M1 M2

c (type2)

F. 4.3 Ordonnancement dun graphe de prcdence avec 3 tches unitaires types, des temps de communication unitaires et 2 machines ddies : la machine M1 excute les tches de type 1, et la machines M2 excute les tches de type 2. Nous nous intressons, dans ce chapitre au problme dordonnancement dun ensemble de tches unitaires et types sur des machines ddies avec des contraintes de prcdence et des grands temps de communication entre les tches. Aussi, nous allons nous focaliser sur un type particulier de graphe de prcdence, savoir les ordres dintervalles. notre connaissance, cette classe de graphes a t introduite par Papadimitriou et Yannakakis dans [71]. En eet, un graphe est un ordre dintervalles sil est possible dassocier chacun de ses sommets un intervalle de rels de telle sorte ce que deux sommets soient relis par un arc si et seulement si les intervalles

89

correspondants ne se chevauchent pas. En dautres termes, si lintervalle [a1 , a2 ) (resp. [b1 , b2 )) est associ la tche a (resp. b), alors la tche a prcde la tche b dans le graphe de prcdence si et seulement si a2 < b1 . Un exemple montrant un ensemble dintervalles et le graphe dordre dintervalles correspondant est illustr dans la gure 4.4. a d g h g h b e f d e f c a b c

F. 4.4 Un graphe dordre dintervalles et les intervalles correspondants. Les arcs transitifs ne sont pas reprsents. Pour un ensemble de tches caractrises par des dates darrive et des dates dchance, le but sera, donc, de construire un ordonnancement ralisable.

4.2

D N

4.2.1 Formulation du modle

Nous considrons un ensemble J constitu de n tches types avec des dures dexcution unitaires, des dates darrive ri N et des dates dchance di N, pour toute tche Ji J. Dautre part, nous considrons K types de tches tels que chaque tche Ji J soit caractrise par un type not mi {1, . . . , K}. Nous limitons cette tude un graphe de prcdence orient et acyclique G = (J, A) ayant la structure dordre dintervalles : chaque tche Ji J on associe un intervalle non vide Ii = [ai , bi ) avec (ai , bi ) R2 , ai < bi . Comme il a t expliqu dans lintroduction de ce chapitre, il existe une relation de prcdence entre deux tches Ji , J j J, i.e. (Ji , J j ) A, si bi < a j (voir gure 4.4). Dans ce cas, un temps de communication entier ci j N

90

est associ larc (Ji , J j ).

Nous considrons, galement, K classes de machines telles que chaque classe p {1, . . . , K} contienne exactement une seule machine ddie lexcution des tches de type p. Ainsi, un ordonnancement est dni uniquement par le vecteur = (t), o ti reprsente la date de dbut dexcution de la tche Ji . et il est ralisable si les trois conditions suivantes sont vries :

1. Les dates de dbut dexcution des tches respectent les dates darrive et les dates dchance correspondantes, i.e. Ji J, ri ti < di . 2. Les relations de prcdence entre les tches sont aussi respectes, i.e. (Ji , J j ) A, soit xi j = 0 si mi = m j , et xi j = 1 sinon. Lingalit suivante doit tre vrie, ti + 1 + xi j ci j t j . 3. chaque instant t, au plus une tche est excute par chaque machine.

Le problme gnral que nous considrons consiste construire un ordonnancement ralisable pour un graphe de prcdence ayant la structure dordre dintervalles avec des temps de communication, des dates darrive, des dates dchance et des machines ddies.

4.2.2 Temps de communication monotones

Pour chaque tche Ji J, on note par + (i) (resp. (i)) lensemble des successeurs (resp. prdcesseurs) de la tche Ji dans le graphe G.

Proprit 1 [71] Soit un graphe de prcdence G = (J, A) ayant la structure dordre dintervalles. Pour toute paire de tches Ji , J j J, (i) ( j) ou ( j) (i). Dnition 6 Soit un graphe de prcdence G = (J, A) ayant la structure dordre dintervalles. Les temps de communication associs G sont dits monotones si ((Ji , J j ), (Ji , Jk )) A2 , ( j) (k) ci j cik . 91

Il faut noter que ( j) (k) est quivalent a j ak , donc a j bi ak bi . Ainsi, la monotonie des temps de communication implique que pour tout arc (Ji , J j ) J, le temps de communication ci j est croissant en fonction de la distance entre la borne suprieure bi de lintervalle Ii et la borne infrieure a j de lintervalle I j . En reprenant lexemple du graphe dordre dintervalles illustr dans la gure 4.4, nous prsentons dans le tableau 4.1 des temps de communication monotones possibles entre les tches avec des contraintes de prcdence. ci j a b d e g h b 1 * * * 2 * c 3 2 2 1 3 1 e 2 * 1 * 2 * f 3 2 2 1 3 1 h * * * * 2 *

T. 4.1 Temps de communication monotones pour le graphe dordre dintervalles prsent dans la gure 4.4

4.2.3 Algorithmes de liste

Les algorithmes de liste sont des algorithmes gloutons dont le principe est assez intuitif. Une liste de priorit est une bijection L : J {1, . . . , n}. Pour les problmes dordonnancement, cette liste est souvent construite laide de la structure dun graphe, des dates darrive, des dates dchance et des contraintes de ressources. La dtermination dune liste de priorit pour notre problme dordonnancement utilise une extension de lalgorithme LPP [62] et sera aborde dans la Section 4.5. Supposons quune liste de priorit L est xe. Un ordonnancement de liste avec des temps de communication peut tre construit comme il est dcrit dans [47] : soit une tche Ji J telle que sa date de dbut dexcution ti ne soit pas encore xe linstant t. La tche Ji est dite prte tre 92

excute linstant t par la machine de classe si : 1. t ri ; 2. Chaque tche J j (i) est ordonnance avant la date t. Par ailleurs, si une tche Jk (i) nest pas excute sur la machine alors le temps de communication entre Ji et Jk est pris en compte si la tche Ji est ordonnance linstant t ; 3. La machine est inactive linstant t.

Pour chaque couple de valeurs (t, p), pour t N et p {1, . . . , K}, lalgorithme de liste ordonnance, sur la machine de la classe p, la tche prte de type p possdant la plus haute priorit (i.e. la valeur L(Ji ) est minimale) en xant ti = t si une telle tche existe. Le droulement de lalgorithme dbute linstant t = 0 et incrmente la valeur de t ds quaucune tche nest prte et/ou ds quaucune machine nest disponible linstant t. Il faut noter que si le pas du temps est unitaire alors lalgorithme de liste, dcrit ci-dessus, possde une complexit non polynomiale gale O(nK. max(Ji ,J j )A {ci j }). Cependant, il a t prouv dans [47] que les valeurs prises par t peuvent tre limites de faon obtenir un algorithme de liste polynomiale dont la complexit est gale O(nK 2 ).

4.3

T
Il existe beaucoup de travaux dans la littrature portant sur lordonnancement dun

ensemble de tches partiellement ordonnes et modlises par un graphe de prcdence orient acyclique [59, 25, 40]. Pour un graphe de prcdence quelconque, le problme de minimisation du makespan sur des machines identiques est NP-dicile [40]. Cependant, Papadimitriou et al. [71] ont construit une solution optimale dans le cas o le graphe de prcdence possde une structure dordre dintervalles. Plus rcemment, Jansen [51] a tendu ce rsultat pour des systmes de tches types. Dans le modle le plus gnral des tches types, les machines sont partitionnes en plusieurs classes, chaque tche doit tre excute sur une machine dune classe xe, et chacune de ces classes peut contenir plusieurs machines. Il est noter quun systme de tches types inclut les modles de machines identiques (une seule classe de machines) et de machines ddies 93

(une seule machine par classe).

Par ailleurs, lintroduction des temps de communication entre les tches rajoute une couche de complexit supplmentaire au problme mme dans le cas de graphes de prcdence particuliers tels que les ordres dintervalles. Rappelons dans ce contexte que les temps de communication sont dits grands sils sont plus grands que les temps dexcution des tches. Les problmes dordonnancement sous cette hypothse sont trs diciles rsoudre de faons exactes. Par exemple, pour des temps dexcution unitaires et un dlai de communication xe gale c 3,

Giroudeau et al. ont prouv dans [41] que lexistence dun ordonnancement de taille infrieure c + 4 est NP-complet pour un graphe de prcdence gnral sans limitation de ressources. Dans la littrature, des articles de synthse sur les problmes dordonnancement avec des temps de communication peuvent tre trouvs dans [35, 80]. Il faut noter que les temps de communication monotones incluent les dlais constants. Dans ce contexte, la plupart des auteurs limitent leurs tudes des dures dexcution et des temps de communication unitaires. Ali et Rewini [8] ont dvelopp un algorithme polynomial pour la minimisation du makespan pour un graphe de prcdence dordre dintervalles, m machines identiques et des temps de communication unitaires. Verriet [80] a dvelopp un algorithme polynomial dans le but de rsoudre le problme de dtermination dordonnancements ralisables pour un graphe de prcdence dordre dintervalles avec des dates darrive, des dates dchance, des temps de communication unitaires et m machines identiques.

Dans ce chapitre, nous tudions le problme de dtermination dun ordonnancement ralisable pour un graphe de prcdence dordre dintervalles avec des grands temps de communication, des dates darrive, des dates dchance et des tches types. Nous montrons dans la section 4.4 que le problme est NP-complet au sens fort pour deux machines ddies et des temps de communication quelconques. Dans la suite du chapitre, nous considrons uniquement des temps de communication monotones. Dans la section 4.5, nous nous intressons au problme dordonnan-

94

cement dun ensemble de tches modlises par un graphe de prcdence dordre dintervalles avec des dates darrive, des dates dchance, des temps de communication monotones et des machines ddies. Pour cel, nous prsentons une extension de lalgorithme dcrit dans [62] par Leung, Palem et Pnuelli (algorithme "LPP" en abrviation) o les auteurs dcrivent un algorithme gnrique capable de dterminer cacement un ordonnancement pour un ensemble de tches avec des dates darrive et dchance, sur m machines identiques et en prsence dun graphe de prcdence dordre dintervalles avec des dlais de latence. Il faut noter, dans ce contexte, que le dlai de latence est une quantit de temps qui doit scouler entre la n dune tche et le dbut de son successeur et que sa valeur est indpendante des machines sur lesquelles les deux tches sont excutes [26]. En eet, lalgorithme dordonnancement LPP est un algorithme de liste qui calcule ses priorits en fonction des dates dchance des tches. Dans cette perspective, la priorit est donne la tche qui possde la date dchance la plus courte. Ltape de construction de la liste des priorits sera prcde par une tape de modication des dates dchance qui consiste relaxer le problme dorigine et rsoudre un sous-problme de maximisation des dates de dbut dexcution des tches. Il sagit, en eet, de calculer et dattribuer une nouvelle date dchance chaque tche, moyennant une procdure de calcul au plus tard. Le schma de modication des dates dchance prsent dans [62] ainsi que les preuves seront aussi simplis. Dans la section 4.6, nous prouvons brivement que lalgorithme LPP ne peut pas stendre pour m machines identiques puisque, dans ce cas, les algorithmes de listes ne peuvent pas fournir des solutions optimales pour de grands temps de communication.

4.4

C `
Dans cette section, nous prouvons que le problme dordonnancement sur deux

machines ddies dun graphe dordre dintervalles avec des temps de communication quelconques est NP-complet au sens fort. Ce rsultat justie la limitation de notre tude aux temps de communication monotones. Ainsi, nous considrons les deux problmes dnis comme suit :

95

SCHEDULING BIPARTITE GRAPH WITH COMM. DELAYS (SBC) Entre : Soient A = {J1 , . . . , Jk } et B = {Jk+1 , . . . , J2k }, k N deux ensembles de k tches de dures unitaires. (Ji , J j ) A B, un dlai ci j N. Ji A B, mi {1, 2}. 2 machines ddies. Un entier D 0. Question : Existe-il un vecteur t = (ti ), Ji A B tel que, (Ji , J j ) (A B)2 , si mi = m j alors ti t j , max Ji AB{ti } < D, et (Ji , J j ) AB, xi j = 0 si mi = m j , xi j = 1 sinon, et ti +xi j ci j +1 t j ?

SEQUENCING COUPLES WITH LATENCIES (SCL)[84] Entre : Soient A = {J1 , . . . , Jk } et B = {Jk+1 , . . . , J2k }, k N deux ensembles de k tches de dures unitaires. k valeurs i N, i {1, . . . , k}. Une seule machine. Un entier D 0. Question : Existe-il un vecteur t = (ti ), Ji A B tel que, (Ji , J j ) (A B)2 , ti maxJi AB {ti } < D et i {1, . . . , k}, ti + 1 + i ti+k ? Thorme 8 Il existe une rduction polynomiale du problme SCL vers le problme SBC. Preuve Soit une instance du problme SCL. Une instance f () du problme SBC est construite en xant, (Ji , J j ) A B, ci j = i si j = k + i et ci j = 0 sinon. En plus, Ji A, mi = 1 et Ji B, mi = 2. Cette transformation est illustre dans la gure 4.5. 1. Soit t = (ti ), Ji A B une solution de linstance . Nous montrons que toutes les tches dans A peuvent tre excutes entirement et sans interruption dans lintervalle de temps [0, k] : Supposons quil existe deux tches successives Ji et J j avec Ji B et J j A. tant donnes les relations de prcdence entre les tches de A et les tches de B, il est possible de permuter les tches Ji et J j sans inuencer lexcution des autres tches. Ainsi, nous pouvons supposer que toutes les tches de lensemble A peuvent tre excutes avant les tches de lensemble B. Au pire cas, le nombre de permutations est born par k2 . Les tches de lensemble A nont pas de prdcesseurs. Il est donc possible de les excuter sans interruption. Ainsi t = (ti ), Ji A B, est aussi une solution de f (). 96 t j,

A 1 2 3 5 4 1

B 5 6 7 1 2 3

A 5 4 1

B 5 6 7

Instance du problme SCL

Instance f () du problme SBC

F. 4.5 Transformation dune instance du problme SCL en une instance du problme SBC avec des temps de communication. 2. Inversement, supposons que t = (ti ), Ji A B est une solution de f (). Par construction du graphe, la premire tche de lensemble B est excute la suite de la dernire tche de lensemble A. Ainsi, pour tout couple de tches (Ji , J j ) (A B)2 , ti Ji A B est aussi une solution ralisable pour . t j et t = (ti ),

Finalement, il faut noter quun graphe biparti complet constitue clairement un ordre dintervalles tel que chaque tche dans A (resp. dans B) soit associe un intervalle I = [a, b) (resp. I = [a , b )) avec b a . Dautre part, le problme SBC est clairement dans NP. Du fait que le problme S CL est NP-complet au sens fort [84], on a le corollaire suivant :

Corollaire 3 Le problme dordonnancement pour des graphes de prcdence dordre dintervalles, avec des temps de communication quelconques et sur 2 machines ddies est NP-complet au sens fort.

4.5

E LPP

97

Lobjectif de cette section est de prsenter une extension de lalgorithme LPP [62] pour un graphe de prcdence dordre dintervalles avec des temps de communication monotones et des machines ddies. Nous prsentons, tout dabord, un algorithme polynomial simple pour calculer une borne suprieure sur le temps de compltude dune tche. Cet algorithme est bas sur la rgle de Jackson1 [50, 46], et sera par la suite appliqu dune faon itrative dans le but damliorer la date dchance de chaque tche. Finalement, nous prouvons quun algorithme de liste bas sur la priorit EDF (Earliest Deadline First) ainsi que sur les dates dchance modies mne une solution ralisable si elle existe.

4.5.1 Une borne suprieure sur les temps de compltude des tches
Soit Jk J et S k = + (k) indep(k), o indep(k) reprsente lensemble des tches dans J sans relations de prcdence avec la tche Jk . Supposons que chaque tche J S k {Jk } possde une date darrive r et une date dchance d . Dautre part, tant donn quil existe une seule machine par type de tches, nous xons, pour chaque arc (Ji , J j ) A, xi j = 0 si mi = m j , xi j = 1 sinon. Soit t {rk + 1, . . . , dk }. Nous considrons, alors, le problme de dcision E xistence(t, k, r, d) o r (resp. d) reprsente le vecteur des dates darrive (resp. dchance) de lensemble des tches S k {Jk }. Ce problme est dni comme suit : il sagit de xer un ordonnancement de la tche Jk linstant t 1 et de retourner la valeur "vrai" sil existe un ordonnancement ralisable des tches de lensemble S k {Jk } en considrant les dates darrive, les dates dchance, les contraintes de ressources et les relations de prcdence entre la tche Jk et ses successeurs.

Existence(t,k,r,d) : Entre : Lensemble des tches S k {Jk } avec des dures dexcution unitaires, des dates
dchance dnies par dk = t et J j S k , dj = d j . Chaque tche J j S k {Jk } doit tre
1

Dans la rgle de Jackson, les tches sont ordonnes selon leurs dates dchance croissantes et sont ordonnances

par un algorithme de liste qui suit la discipline Earliest Deadline First(EDF)

98

excute par la machine de la classe m j . Les dates darrive des tches sont calcules comme suit :
1. rk = t 1 ; J j indep(k), rj = r j ;

2. J j + (k), rj = max(r j , t + xk j ck j ). Question : Existe-il un ordonnancement des tches de lensemble S k {Jk } respectant les dates darrive, les dates dchance et les contraintes de ressources ?

Soit lexemple suivant : considrons le problme E xistence(5, e, r, d) pour linstance dnie par lensemble des tches illustres prcdement dans la gure 4.4 avec les temps de communication reports dans le tableau 4.1. Les dates darrive initiales ainsi que les dates dchance initiales et les types des tches sont donns dans le tableau 4.2. Ji J ri di mi a 0 3 2 b 1 3 1 c 2 7 1 d 0 3 1 e 4 6 2 f 1 6 2 g 0 3 1 h 1 6 2

T. 4.2 Dates darrive, dates dchance et types des tches pour lexemple de la gure 4.4 Ainsi, S e = {c, f } {b, h} et E xistence(5, e, r, d) consiste trouver un ordonnancement des tches J = {b, c, e, f, h} avec des dates darrive et des dates dchance prcalcules. Ces dates sont rsumes dans le tableau 4.3. La rponse cette question est clairement positive. Nous donnons un exemple de solution ralisable dans la dernire ligne du tableau 4.3. Ji J ri di ti b 1 3 1 c 6 7 6 e 4 5 4 f 5 6 5 h 1 6 1

T. 4.3 Dates darrive, dates dchance et dates de dbut dexcution dune solution ralisable pour le problme de dcision E xistence(5, e, r, d).

99

Si un problme E xistence(t, k, r, d) retourne une rponse ngative alors il nest pas possible dexcuter la tche Jk linstant t 1 sans violer une contrainte de prcdence ou de ressource du problme initial. Ainsi, la valeur maximale t {rk + 1, . . . , dk } telle que E xistence(t , k, r, d) soit vrai constitue une borne suprieure sur le temps de compltude de la tche Jk . Dans la suite, ces valeurs t seront calcules pour chaque tche Jk an damliorer les dates dchance des tches, i.e. la date dchance di de chaque tche Ji sera remplace par ti , di := ti . Dun point de vue algorithmique, nous notons par BS (k, r, d) un algorithme qui calcule la valeur t si elle existe. Le problme E xistence(t, k, r, d) peut tre rsolu simplement en O(n log n) par un algorithme utilisant la rgle de Jackson. Cependant, comme il a t expliqu dans [37, 62], deux recherches binaires sur lintervalle [rk , dk 1] bases sur la rgle de Jackson sont ncessaires pour calculer la date t . Ceci mne un algorithme dont la complexit en temps est borne par O(log(dk rk ) n log n). Une proprit intressante de la fonction BS est dcrite dans le lemme suivant : Lemme 14 Soit d1 et d2 deux lments de Nn avec d1 d2 (i.e. Ji J, di1 di2 ). Pour chaque vecteur r Nn tel que r d1 et pour chaque tche Ji J, BS (i, r, d1 ) BS (i, r, d2 ). Preuve Pour chaque valeur entire t [ri , di1 ], si E xistence(t, i, r, d1 ) est vrai alors

E xistence(t, i, r, d2 ) est aussi vrai. Ainsi, puisque BS est un algorithme de maximisation on conclut que BS (i, r, d1 ) BS (i, r, d2 ).

4.5.2 Modication des dates dchance

Lide dans cette partie est damliorer les dates dchance de toutes les tches en calculant dune faon successive des bornes suprieures sur les temps de compltude laide de lalgorithme 2.

Si un appel la fonction BS ne retourne pas de solution, alors lAlgorithme 2 sarrte. Dans la suite, nous supposons quil est possible de calculer le vecteur d . Pour chaque couple
(i, k) {1, . . . , n}2 , on note par dk (i) la date dchance modie de la tche Jk la n de la ime

100

Algorithme 2: Modication des dates dchance des tches Donnes : Un graphe de prcdence G avec des temps de communication, dates darrive r, dates dchance d et K machines ddies. Rsultat : Des dates darrive r et des dates dchance d modies. dbut Calculer i {1, . . . , n}, ri = max J j (i) (ri , r + 1 + x ji c ji ) suivant un ordre j topologique;
Renumroter les tches telles que r1 r2 . . . rn ;

Calculer i {1, . . . , n}, di = minJ j + (i) (di , d 1 xi j ci j ) suivant un ordre j topologique inverse; pour i = 1 n faire di = BS (i, r , d );
Calculer k {1, . . . , n}, dk = min J j + (k) (dk , d 1 xk j ck j ) suivant un ordre j

topologique inverse; n n

itration de la boucle pour.

Nous considrons comme exemple lexcution de lAlgorithme 2 sur linstance du problme dordonnancement prsente dans la gure 4.4. Le tableau 4.4 prsente le vecteur r et une nou velle numrotation possible des tches. Les valeurs dk (i), (i, k) {1, . . . , n}2 sont rapportes dans

le tableau 4.5. Ji J ri i a 0 8 b 2 5 c 6 1 d 0 7 e 4 3 f 5 2 g 0 6 h 3 4

T. 4.4 Dates darrive r amliores et une nouvelle numrotation des tches.

101

Ji J di (0) di (1) di (2) di (3) di (4) di (5) di (6) di (7) di (8)

1 7 7 7 7 7 7 7 7 7

2 6 6 6 6 6 6 6 6 6

3 5 5 5 5 5 5 5 5 5

4 5 5 5 5 4 4 4 4 4

5 3 3 3 3 3 3 3 3 3

6 2 2 2 2 1 1 1 1 1

7 3 3 3 3 1 1 1 1 1

8 1 1 1 1 1 1 1 1 1

T. 4.5 Dates dchance amliores dk (i), (i, k) {1, . . . , 8}2 . Les lemmes suivants caractrisent les vecteurs d (i) = d1 (i), d2 (i), . . . , dn (i) , pour toute

itration i {1, . . . , n} :
Lemme 15 Pour chaque tche Jk J, la fonction i dk (i) est dcroissante pour i {1, . . . , n}. De plus, pour chaque valeur i {k, . . . , n}, dk (i) = dk (k) = BS (k, r, d (k 1)).

Preuve Par dnition de la fonction BS , BS (k, r , d (k 1)) {rk + 1, . . . , dk (k 1)}, do BS (k, r , d (k 1)) dk (k 1). Par ailleurs, lajustement des valeurs de d en suivant un ordre

topologique inverse ne fait que dcroitre le vecteur d . Ainsi, d ne peut que dcroitre et la premire partie du lemme est prouve.
Maintenant, par lAlgorithme 2, pour chaque k {1, . . . , n}, dk (k) = BS (k, r , d (k 1)). Comme rn rn1 . . . rk , la tche Jk nadmet pas de successeur dans lensemble des tches Jk+1 , . . . , Jn . Ainsi, la modication de d , j {k + 1, . . . , n} ninuence pas la valeur de dk et j dk (i) = dk (k) pour toute valeur i {k, . . . , n}.

Lemme 16 Pour chaque arc (Jk , J j ) A et pour chaque i {1, . . . , n}, dk (i) < d (i). j

Preuve Ce lemme dcoule de la procdure dajustement appele chaque tape en suivant un 102

ordre topologique inverse. Le lemme suivant prouve qu la n de lAlgorithme 2, il nest pas possible damliorer
davantage les valeurs d , pour J J en utilisant la fonction BS :

Lemme 17 Soit r et d les vecteurs des dates darrive et des dates dchance retourns par
lAlgorithme 2. Si un ordonnancement ralisable existe, k {1, . . . , n}, dk = BS (k, r , d ). Preuve Supposons, par labsurde, quil existe une tche Jk J telle que dk

BS (k, r , d ) o

r et d sont les veteurs des dates darrive et des dates dchance calculs par lalgorithme 2.
Par le lemme 15, on a dk = dk (k) = BS (k, r , d (k 1)) et d (k 1) d . Ainsi, par le lemme 14, dk = BS (k, r , d (k 1)) > BS (k, r , d ). Par consquent, E xistence(dk , k, r , d ) est fausse. Soit r et d les dates darrive et les dates

dchance dnies pour cet appel de la fonction E xistence. J S k {Jk }, soit t la date de dbut dexcution de la tche J dnie par un ordonnancement de liste rgi par la rgle de Jackson. Soit t le premier instant tel quune tche J j S k rate sa date dchance dj , i.e. t = dj .
1. Si t < dk , alors il nexiste pas dordonnancement ralisable pour lensemble A = {J S k {Jk }, d t} avec les dates darrive r et les dates dchance d . Il est clair que Jk De plus chaque tche J A vrie d < dk , ainsi, par le lemme 16 J

A.

+ (k).

La consquence est que A indep(k) et donc J A, r = r . Nous pouvons dduire quil

nexiste pas dordonnancement ralisable pour le problme dordonnancement initial.

2. Sinon, t dk . Soit la plus petite valeur dans {1, 0, . . . , dj 1} telle que la machine de

la classe m j soit occupe durant chaque slot de temps dans [ + 1, dj ] par une tche J avec
d dj . Soit B = {J j } {J S k {Jk }|m = m j et < t < dj }. Il est clair que |B| = dj . De plus, J B, r + 1 et d dj . Nous prouvons, dans la suite, que J B, r + 1 et d dj . Chaque tche J B\{Jk } vrie r = r et d = d . Ainsi, par dnition de B, r + 1 et d dj . Maintenant, si Jk B, dk = dk dj . Supposons, par labsurde, que rk < + 1. Alors, par lAlgorithme 2, rn rn1 . . . rk < + 1 et donc, J B {Jk }, < k. Par le

103

 lemme 15, d (k 1) = d = d . Ainsi, E xistence(dk , k, r , d (k 1)) doit excuter toutes

les tches de lensemble B durant lintervalle de temps [ + 1, dj ], ce qui est impossible.

Do, E xistence(dk , k, r , d (k1)) est fausse, et ceci constitue une contradiction puisque dk (k) = BS (k, r , d (k 1)). Nous concluons que rk + 1.

Donc, toutes les tches dans B avec les dates darrive r et les dates dchance d doivent tre excutes sur la machine m j durant lintervalle de temps [ + 1, dj ], ce qui est impossible en considrant |B|. Ainsi, il nexiste pas dordonnancement ralisable pour le problme initial.

4.5.3 Optimalit de lextension de lalgorithme LPP

Lextension de lalgorithme LPP consiste modier les dates dchance des tches en utilisant lAlgorithme 2 puis construire un ordonnancement bas sur une liste de priorit L telle que pour chaque couple de tches (Ji , J j ) J 2 , L(Ji ) < L(J j ) di d . j Nous considrons, comme exemple, lordonnancement obtenu pour linstance illustre par la gure 4.4 avec les dates dchance modies listes dans le tableau 4.5. Cet ordonnancement est prsent dans la gure 4.6. Nous montrons dans le thorme suivant que dans le cas de machines ddies et de temps de communication monotones, il existe un ordonnancement ralisable si et seulement si lordonnancement retourn par lextension de lalgorithme LPP est ralisable. M1 g d b c

M2

F. 4.6 Extension du LPP pour lexemple de la gure 4.4 avec les dates dchance modies reportes dans le tableau 4.5.

Thorme 9 La version tendue de lalgorithme LPP rsout dune faon polynomiale le problme de la dtermination dun ordonnancement ralisable pour un ensemble de tches unitaires et types avec des dates darrive et dchance arbitraires, des temps de communication monotones,

104

des contraintes de prcdence dnies par un graphe dordre dintervalles et un nombre limit de machines types avec une seule machine par type. Preuve Supposons, par contradiction, que lextension de lalgorithme LPP retourne un ordonnancement = {t1 , . . . , tn } qui ne soit pas ralisable. Soit Ji la premire tche qui rate sa date dchance modie dans lordonnancement , i.e. ti di . Nous nous proposons de montrer dans la suite quil doit exister une tche Jk antrieure Ji dans qui rate aussi sa date dchance
modie dk .

Une tche J j J est dite sature si m j = mi et d di . Soit [, +1], pour < di , le dernier j slot de temps qui ne soit pas occup par une tche sature sur la machine de type mi . Nous consid rons alors les ensembles de tches = {J sature : < t < di } {Ji } et = {J : r }.

Nous prouvons, tout dabord et par contradiction, que

et 0. En eet, si =

alors J , r > . On a || = di > 0 et il existe exactement di ( + 1) slots de temps

disponibles entre + 1 et di sur la machine mi . Ainsi, le problme dordonnancement nest pas ralisable et, par consquence, tant donn que lensemble et, donc, 0. est ni, il existe une tche J j telle que | ( j)| est

minimal dans le sens de linclusion. Du fait que J j nest pas ordonnance la date ou avant, il existe ncessairement une tche critique Jk ( j) qui empche J j dtre excute avant .
Notons que, J , on a Jk (). De plus, la suite du calcul de r , on a rk < r . Comme j J j , alors r . Ainsi, rk < . j

La tche Jk est soit de type mi ou dun type dirent de mi : Cas 1 Supposons que mk = mi . Dans ce cas, il nexiste pas de dlai de communication entre Jk et les tches dans . En outre, la tche Jk contraint la tche J j tre excute aprs la date , ainsi tk . Nous prouvons que Jk ainsi, Jk : puisque Jk ( j), alors on a (k) ( j) et, .

. Etant donn que rk < , nous avons Jk

Maintenant, puisque dk < d di , alors Jk est une tche sature. Aussi le fait que Jk j

implique que tk et donc tk = , or ceci est impossible par dnition de . Cas 2 Supposons maintenant que mk mi . Dans ce cas, un delai de communication addition-

105

nel entre les tches Jk et J j sera pris en compte, i.e. tk + 1 + ck j > . Maintenant, nous nous proposons de prouver que S k . En eet, par la structure de graphe dordre dintervalles, on a :

J = (k) {Jk } + (k) indep(k) = S k {Jk } (k)

Nous montrons que (k) = . Pour chaque tche J (k), lingalit r < rk est valide. tant donn que rk < , nous avons que r < . Ainsi, si J , alors J .

Cependant, si J , alors Jk () et, donc, il existe un circuit dans le graphe G, ce qui est impossible. Ainsi, S k .
Maintenant, en utilisant le lemme 17, on a dk = BS (k, r , d ) et E xistence(dk , k, r , d ) est

vrai. tant donn que S k , un algorithme de liste suivant la rgle de Jackson calcule des dates de dbut dexcution ralisables pour les di tches de avant la date di . Ainsi, il existe au moins une tche J j excute la date t par ce dernier algorithme. De
ce fait, on a dk + ck j t . Maintenant, le fait que ( j) ( j ) et que les temps de communication sont monotones impliquent que ck j ck j , do dk + ck j . Finalement, puisque tk + 1 + ck j > et dk + ck j , alors on a tk + 1 > dk et ainsi la tche

Jk rate son chance, do une contradiction.

4.6

Dans cette section, nous nous proposons dtudier linuence du nombre de machines de chaque classe {1, . . . , K} sur la rsolution du problme dordonnancement. En eet, tous les rsultats prcdents ont t tablis sous lhypothse dune seule machine par classe (machines ddies), i.e. p {1, . . . , K}, p = 1 o p reprsente le nombre de machines dans la classe p. La gure 4.7 montre quaucun algorithme de liste ne peut retourner une solution optimale pour m machines identiques. Ainsi, lextension de lalgorithme LPP plusieurs machines identiques par

106

J1

3 3 3

J3

J1 J2

J3 J4

J2 3

J4

Un ordonnancement de liste non optimal

J1

J2

J3

J4

Un ordonnancement optimal

F. 4.7 Les algorithmes de liste ne sont pas optimaux pour 2 machines identiques : exemple dordonnancement de tches unitaires sur 2 machines identiques avec des temps de communication grands. classe nest pas optimale mme en absence des dates darrive et dchance.

La question reste, nanmoins, ouverte dans le cas o les dlais de communication sont unitaires, i.e. ci j = 1, (Ji , J j ) A. Dans ce cas, Jacques Verriet [80] a prsent un algorithme polynomial pour le problme de faisabilit avec des machines identiques. Cependant, la modication des dates dchance vue dans ce chapitre ne conduit pas une solution ralisable comme le montre la gure 4.8. En eet, lalgorithme de modication des dates dchance namliore pas les dates dchance xes initialement, et ainsi lalgorithme LPP pourrait retourner un ordonnancement non ralisable.

4.7

C
Nous avons montr dans ce chapitre que lalgorithme LPP introduit par Leung et al.

[62] pouvait bien stendre pour rsoudre le problme dordonnancement sur des graphes de prcdence ayant la structure dordre dintervalles avec des dlais de communication monotones, des tches unitaires caractrises par des dates darrive et des dates dchance et excutes sur des machines ddies (une seule machine par type).

107

J2

ci j = 1, (Ji , J j ) A d1 = 1 d2 = d3 = d4 = 1 d5 = 4

J1

J3

J4

J5

Ji J, di = di

J1

J2

J3 J4

J5

J1

J4

J3 J2

J5

Un ordonnancement LPP non ralisable

Un ordonnancement ralisable

F. 4.8 Lalgorithme LPP risque de retourner un ordonnancement non ralisable si les temps de communication sont unitaires. Dans le cas o lhypothse sur la monotonie des temps de communication est relache, nous avons exhib une rduction polynomiale partir du problme SCL et nous avons ainsi montr que le problme devient NP-complet au sens fort. Dans le cas monotone, la construction dun ordonnancement ralisable repose sur une procdure de modication des dates dchance travers un calcul successif de bornes suprieures sur le temps de compltude de chaque tche. Ensuite une liste de priorit base sur les nouvelle dates dchance est constitue et conduit la construction dun ordonnancement ralisable laide dun algorithme de liste classique. Nous avons nalement montr que lextension obtenue de lalgorithme LPP rsout dune faon polynomiale le problme avec des temps de communication monotones. Enn, nous nous sommes intresss au nombre de machines par classe et lventuelle inuence sur la rsolution du problme par un algorithme de liste. Ainsi, nous avons construit un contre exemple avec deux machines du mme type permettant de conclure quil nexiste pas dalgorithme de liste qui retourne une solution optimale du problme. La question reste donc ouverte

108

quant la rsolution cace du problme avec un nombre quelconque de machines identiques sur des ordres dintervalles en prsence de dlais de communication monotones et des tches dures dexcution unitaires. Nous avons aussi montr travers un exemple simple que la procdure de modication des dates dchance namliore pas les dates dchance des tches dans le cas o les temps de communication sont unitaires. Ceci nous conduit vers une perspective intressante qui consiste en lextension de ce travail au cas du systme de tches types avec des dlais de communication unitaires. Nous sommes, en eet, convaincus quune lgre modication dans la procdure de calcul des dates dchance peut donner lieu un algorithme polynomial.

109

110

A `

5.1

Les rseaux de partage de chiers pair--pair sont devenus un aspect trs populaire de lutilisation quotidienne de linternet. Le succs de tels systmes est bas sur lexploitation dune nouvelle ressource : le stockage distribu. Lutilisation massive de cette nouvelle ressource est de au fait que des capacits de stockage plus importantes sont actuellement disponibles avec un cot trs faible et avec des temps daccs trs rapides. Ainsi les utilisateurs ragissent entre eux en installant un stockage local (cache), en rpliquant les contenus les plus populaires et en les mettant disposition des utilisateurs du voisinage. Ceci conduit une diminution dans la consommation de la bande passante ncessaire pour accder aux donnes partir des serveurs originaux qui les hbergent. Le problme du placement de donnes (DP) ore un modle abstrait appropri pour modliser cette situation : un ensemble de clients (machines ou utilisateurs) relis par une topologie est considr o chaque client dispose dune capacit de stockage donne. Pour un ensemble de donnes (objets) disponibles et tant donne la prfrence de chaque client pour chaque sous ensemble dobjets, le but est de proposer un schma de rplication dobjets, autrement dit un placement dobjets (et de leurs copies) sur les machines qui minimise le cot total daccs pour

111

tous les clients et tous les objets. Dans un modle gnral du problme de placement de donnes, ce cot total daccs est une fonction des cots dinstallation des objets et de leurs copies sur les noeuds utilisateurs et des cots de transfert des donnes entre les dirents utilisateurs du rseau (cot de communication). Or dans un rseau tendu, ce cot de communication est fonction de divers paramtres incluant les dlais et les capacits des liens de connexion, les tailles des mmoires tampons et des enttes de communication et les prols dutilisation du rseau par les dirents noeuds. Cependant, il faut noter que tous ces paramtres du rseau interagissent de faon complexe ce qui rend non ralisable leur introduction dans le modle [17].

5.2
rpliqus.

D `

On considre un rseau constitu dun ensemble M de M utilisateurs, relis entre eux selon une certaine topologie N, ainsi quun ensemble O de N objets de tailles unitaires qui peuvent tre

Chaque utilisateur i M demande accder un ensemble Ri O dobjets selon une certaine frquence. On note wio la frquence daccs de lutilisateur i un objet o Ri . Le cot daccs dun utilisateur i un objet o Ri est nul dans le cas o celui-ci a t rpliqu dans le cache de i. Sinon, si lobjet o est stock dans le cache dun utilisateur voisin j (selon la topologie N), alors le cot daccs est dni comme tant gal d j,i wio , avec d j,i la distance entre lutilisateur j et lutilisateur i. Si, par contre, lobjet o nest pas stock localement, ni dans le cache dun utilisateur voisin, alors lutilisateur i doit faire appel un serveur distant de capacit non borne avec un cot daccs dwio , o d est une constante qui peut tre gale +.

Il existe plusieurs variantes du modle en fonction des distances entre les utilisateurs. Nous pouvons ainsi citer le modle despace mtrique o les distances entre les noeuds sont non nga112

tives, symtriques et respectent lingalit triangulaire, i.e. di, j

di,k + dk, j . Nous pouvons citer,

galement, lespace ultramtrique o, en plus des proprits de la non ngativit et de la symtrie, les distances respectent lingalit ultratriangulaire, i.e. di, j max{di,k , dk, j }. Dans notre tude,

nous considrons le modle gnral o les distances entre les noeuds utilisateurs sont quelconques. Par ailleurs, chaque utilisateur i M peut stocker au maximum Ci objets dans son cache. Lobjectif est de dterminer un placement optimal minimisant le cot total daccs des utilisateurs aux objets.

5.3

Le problme du placement de donnes a t largement tudi dans la littrature. Dans [17], Baev et al. ont considr des distances mtriques, i.e. vriant lingalit triangulaire, entre les noeuds utilisateurs et ont montr que le problme est MAX SNP-dicile, cest dire quil nexiste de schma dapproximation polynomial (PTAS). Par ailleurs, ils ont propos un algorithme 20.5-approch dans le cas o les objets sont de tailles uniformes, i.e. la taille est identique pour tous les objets. Ce rsultat a t obtenu en se basant sur larrondi dune solution optimale dun programme linaire appropri. Dans le cas dobjets de tailles non uniformes, les auteurs ont prouv que le problme de dcision est NP-complet et ont donn un algorithme polynomial 20.5-approch qui fournit une solution dans laquelle la capacit de stockage de chaque utilisateur dpasse sa capacit dans la solution optimale par au plus la taille max du plus grand objet. Ces rsultats ont t amliors dans [16] o un algorithme 10-approch a t propos dans le cas dobjets de tailles uniformes et 10-approch avec dpassement de capacit de stockage dans le cas dobjets de tailles non uniformes.

Plus rcemment, un algorithme optimal a t propos dans [13] dans le cas o tous les objets sont de tailles uniformes et le nombre de clients est born par une constante. Les auteurs de [13] ont galement propos un algorithme optimal dans le cas o les tailles des objets sont non-uniformes condition dautoriser un dpassement de la capacit des clients par au plus max 113

o > 0 est un rel arbitrairement petit.

Nous dcrivons, dans ce chapitre, un algorithme optimal, bas sur la programmation dynamique, dans le cas o la topologie du rseau est une ligne et sans violation de la capacit des clients. Nous tendons ce rsultat lorsque la topologie est un anneau et une toile gnralise. Ces rsultats restent valides dans le cas o le nombre de clients est une entre du problme (i.e. non-born par une constante). Finalement, nous prouvons quil nest pas possible dtendre cet algorithme dans le cas dune topologie quelconque o le nombre des noeuds de degr suprieur ou gal 3 est constant.

5.4

Dans cette partie, nous prsentons un algorithme de programmation dynamique optimal dans le cas dun rseau de connexion dont la topologie est une chane. Nous tendons, par la suite, cet algorithme dans le cas dune topologie en anneau puis en toile gnralise.

5.4.1 Placement de donnes sur une chane

Notons par Pi un placement dobjets sur lutilisateur i, i.e. Pi est un sous-ensemble dobjets quon choisit de rpliquer localement sur i. Pour simplier la prsentation, nous introduisons deux utilisateurs ctifs 0 et M + 1 avec des placements vides sur chacun deux, i.e. P0 = P M+1 = , et nous supposons que les utilisateurs sont rpartis le long dune chane, avec lutilisateur i (1 i M) voisin des utilisateurs i 1 et i + 1 (voir la gure 5.1).

Soit Pi lensemble de tous les placements dobjets ralisables sur lutilisateur i. Pour un utilisateur donn i, nous avons |Pi | N Ci N C , avec C = maxiM (Ci ). Pour 1 k M, nous

notons Ck (Pk1 , Pk , Pk+1 ) le cot daccs induit par le placement Pk sur lutilisateur k, quand ses 114

0 1 k-1 k k+1 M

M+1

Serveur distant(s)

F. 5.1 Problme de placement de donnes sur une chane. utilisateurs voisins k 1 et k + 1 ont reu des placements Pk1 et Pk+1 respectivement. La fonction Ck est dnie comme suit :

Ck (Pk1 , Pk , Pk+1 ) =
oRk Pk1 Pk+1 o Pk

min{dk1,k , dk+1,k }.wko +

oRk Pk1 o Pk Pk+1

dk1,k .wko +

dk+1,k .wko +
oRk Pk+1 o Pk Pk1 oRk o Pk Pk1 Pk+1

d.wko

Linterprtation de la fonction Ck pour des placements donns sur les utilisateurs k 1, k et k + 1 consiste classer les objets requises par lutilisateur k, i.e. Rk en 4 classes selon lendroit o ces objets sont rpliqus. Nous considrons, ainsi, un premier sous ensemble dobjets qui sont rpliqus sur les utilisateurs k 1 et k + 1 mais pas sur k et dans ce cas, ce dernier accdent chacun de ces objets en sollicitant soit k 1, soit k + 1 selon la proximit de ces utilisateurs voisins. Le deuxime et le troisime sous ensembles correspondent au cas o lobjet est rpliqu uniquement sur le voisin k 1 ou le voisin k + 1, et le dernier sous ensemble dobjets de Rk correspond aux objets qui ne se rpliqus sur aucun des trois utilisateurs. Dans ce cas, lutilisateur k fait appel au serveur distant pour rcuprer les objets requis. Le cas o les objets sont rpliqus localement sur lutilisateur k nest pas pris en compte car le cot dun accs local est nul.

Pour k {1, . . . , M}, tant donn le placement Pk1 (resp. Pk ) sur lutilisateur k 1 (resp. k),
nous notons Ck (Pk1 , Pk ) le cot dune solution optimale minimisant la somme des cots dac-

115

cs des utilisateurs k, k + 1, . . . jusqu M. Le cot total optimal recherch est alors donn par
minP1 P1 C1 (P0 , P1 ), et nous avons les relations de rcurrences suivantes :

An de calculer Ck (Pk1 , Pk ) pour des placements xs sur les utilisateurs k 1 et k, nous supposons que toutes les valeurs Ck+1 (Pk , Pk+1 ) sont dtermines pour tous les placements

min Pk+1 Pk+1 {C k (Pk1 , Pk , Pk+1 ) + C k+1 (Pk , Pk+1 )} Ck (Pk1 , Pk ) = Ck (Pk1 , Pk , Pk+1 )

k {1, . . . , M 1},

si k = M.

possibles pk+1 sur lutilisateur k + 1. Il sut donc de rajouter le cot daccs induit par le placement Pk sur k et de minimiser la somme rsultante par rapport aux placements Pk+1 Pk+1 . Le cas initial correspond k = M et donc C (P M1 , P M ) = Ck (P M1 , P M , P M+1 ). Rappelons, M aussi, que P M+1 = . partir de ces relations il est possible den dduire un algorithme de programmation dynamique, donn par Algorithme 3.

La complexit de Algorithme 3 est dduite partir du deuxime ensemble de boucles imbriques et qui consiste eectuer M 1 tapes de calcul. Dans chacune de ces tapes, il sagit pour chaque combinaison possible de placements dobjets sur deux noeuds voisins k1 et k, i.e. O(N 2C )
combinaisons, de minimiser Ck (Pk1 , Pk ) par rapport tous les placements possibles sur le noeud

k + 1, i.e. O(N C ) possibilits de placement. Ainsi, Algorithme 3 retourne une solution optimale en temps O(MN 3C ).

5.4.2 Placement de donnes sur un anneau

De manire similaire, il est possible dobtenir un algorithme de programmation dynamique pour une topologie en anneau. On note OPT (P M , P1 ) le cot dune solution optimale sous rserve davoir choisi le placement P M (resp. P1 ) pour lutilisateur M (resp. 1). Lide consiste construire une instance du problme de placement de donnes sur une chane en ajoutant deux noeuds ctifs 1 et M , respectivement voisins des utilisateurs M et 1 et en liminant larc (M, 1). 116

Algorithme 3: Le programme dynamique pour le problme de placement de donnes sur une chane Donnes : Une instance du problme de placement de donnes sur un rseau dutilisateurs relis suivant une chane. Rsultat : Un placement de donnes optimal.

dbut P0 = {P0 }, PM+1 = {P M+1 } avec P0 = P M+1 = ;

pour chaque P M1 PM1 faire pour chaque P M PM faire C (P M1 , P M ) = C M (P M1 , P M , P M+1 ) M n n

pour k = M 1 1 par pas de 1 faire pour chaque Pk1 Pk1 faire pour chaque Pk Pk faire
Ck (Pk1 , Pk ) = minPk+1 Pk+1 {Ck (Pk1 , Pk , Pk+1 ) + Ck+1 (Pk , Pk+1 )} ;

n n n
Retourner minP1 P1 C1 (P0 , P1 ) ;

117

Le contenu de lutilisateur 1 (resp. M) est rpliqu sur le noeud ctif 1 (resp. M ). Cette nouvelle instance est illustre par la gure 5.2.

k-1

k+1

Serveur distant(s)

F. 5.2 Problme de placement de donnes sur une topologie danneau.

tant donn les placements sur les noeuds utilisateurs 1 et M, il est possible de trouver une faon optimale de placer les objets sur les utilisateurs allant du noeud 2 jusquau noeud M 1 et de calculer ainsi son cot OPT (P M , P1 ). En eet, cette solution est donne par lapplication du programme dynamique dcrit dans la section prcdente sur la nouvelle instance construite pour le problme sur une chane. La solution optimale sur lanneau est donne simplement par minPM PM ,P1 P1 OPT (P M , P1 ).

Nous dcrivons ci-dessous un algorithme polynomial, not Algorithme 4, et qui pour chaque instance du problme de placement de donnes sur un rseau en anneau, retourne une solution optimale en temps O(MN 5C ).

118

Algorithme 4: Le programme dynamique pour le problme de placement de donnes sur un anneau Donnes : Une instance du problme de placement de donnes sur un rseau dutilisateurs relis suivant une topologie danneau. Rsultat : Un placement de donnes optimal. dbut pour chaque P M PM faire pour chaque P1 P1 faire pour chaque P M1 PM1 faire C (P M1 , P M ) := C M (P M1 , P M , P1 ) ; M n pour k = M 1 3 par pas de 1 faire pour chaque Pk1 Pk1 faire pour chaque Pk Pk faire
Ck (Pk1 , Pk ) = minPk+1 Pk+1 {Ck (Pk1 , Pk , Pk+1 ) + Ck+1 (Pk , Pk+1 )} ;

n n n pour chaque P2 P2 faire

C2 (P1 , P2 ) = minP3 P3 {C2 (P1 , P2 , P3 ) + C3 (P2 , P3 )} ;

n
OPT (P M , P1 ) = minP2 P2 {C1 (P M , P1 , P2 ) + C2 (P1 , P2 )} ;

n n Retourner minPM PM ,P1 P1 OPT (P M , P1 ) ; n

119

5.4.3 Placement de donnes sur un graphe en toile gnralise

Dans cette partie, nous nous proposons de rsoudre le problme de placement dobjets lorsque la topologie du rseau N considr est en toile gnralise. Dans une telle topologie, les noeuds utilisateurs sont rpartis sur un nombre xe de chanes qui se coupent en un unique noeud central. Le nombre total de chanes constituant le rseau est dnit par le degr du noeud central. Ainsi, pour identier ces chanes, il serait utile de les numroter en dnissant une chane de dpart et un sens de parcours. Une ide intuitive est de considrer le cercle ctif form par le voisinage immdiat du noeud central, et de parcourir ce cerle dans le sens des aiguilles dune montre (gure 5.3).

chane 5
(M5 )5 (M1 )1

chane 1

(3)5

(3)1

(2)5

(2)1

chane 4
(M4 )4 (3)4 (2)4

chane 2
1
(2)2 (3)2 (M2 )2

(2)3

(3)3

(M3 )3

chane 3 F. 5.3 Problme de placement de donnes sur une topologie en toile gnralise : exemple dtoile avec 5 chanes. Nous supposons que, sur chaque chane, les noeuds sont numrots en partant du noeud central dont le degr est not par . Ainsi, le graphe sera constitu de chanes numrotes de

120

1 , et chaque noeud du rseau est identi par le numro de la chane laquelle il appartient et son ordre au sein de cette chane en partant du noeud central. On note par (i) j j {1 . . . } le ime noeud de la chane numro j. On note, aussi, par M j la taille de la jme chane. Lobjectif est de placer les objets sur les noeuds du rseau de faon minimiser le cot total daccs des utilisateurs aux objets.

En utilisant le programme dynamique, dnie prcdement pour calculer un placement optimal sur une chane (Algorithme 3), lide consiste minimiser la somme des cots optimaux sur chaque chane j, j {1 . . . }. Cette minimisation est eectue par rapport aux dirents placements ralisables P1 P1 sur le noeud central. On dnit, ainsi, la fonction CotChane( j, M j , P(1) j ) qui, tant donne un placement P(1) j sur le premier noeud de la chane j (qui correspond au noeud central du rseau), retourne le cot total daccs optimal de placement dobjets sur la chane j de taille M j (Algorithme 5). On dnit, galement, la fonction TailleChane( j) qui, pour une chane j donne, retourne la taille correspondante. A laide de ces fonctions, nous prsentons lalgorithme de minimisation de cot daccs sur une topologie en toile gnralise de complexit O(MN 3C ) (Algorithme 6).

5.5
constant.

Nous nous intressons dans cette partie au problme de placement de donnes dans un contexte plus gnral dans lequel nous considrons un ensemble dutilisateurs relis suivant une topologie quelconque et telle que le nombre dutilisateurs avec un degr suprieur ou gal 3 est

Une ide naturelle pour rsoudre ce problme consiste dcomposer le rseau en un ensemble de sous graphes connexes ne contenant que des chanes est des anneaux et dappliquer le 121

Algorithme 5: CotChane(h, Mh , P(1)h ) "Calcul dun placement optimal sur une chane dans un rseau en toile gnralise" Donnes : h, Mh , P(1)h . Rsultat : Cot total dun placement de donnes optimal sur la chane Mh .

dbut P(0)h = {P(0)h }, P(Mh +1)c = {P(Mh +1)h } avec P(0)h = P(Mh +1)h = ; pour chaque P(Mh 1)h P(Mh 1)h faire pour chaque P(Mh )h P(Mh )h faire
C(M )h (P(Mh 1)h , P(Mh )h ) = C(Mh )h (P(Mh 1)h , P(Mh )h , P(Mh +1)h )
h

n n

pour k = Mh 1 2 par pas de 1 faire pour chaque P(k1)h P(k1)h faire pour chaque P(k)h P(k)h faire
C(k)h (P(k1)h , P(k)h ) = minP(k+1)h P(k+1)h {C(k)h (P(k1)h , P(k)h , P(k+1)h ) + C(k+1)h (P(k)h , P(k+1)h )} ;

n n n
Retourner minP(2)h P(2)h C(1)h (P(0)h , P(1)h , P(2)h ) + C(2)h (P(1)h , P(2)h ) ;

122

Algorithme 6: Algorithme de placement de donnes optimal sur une toile gnralise" Donnes : Une instance du problme de placement de donnes sur un rseau dutilisateurs relis suivant une topologie dtoile gnralise. Le neoud central est not . Rsultat : Un placement de donnes optimal.

dbut pour chaque P P faire CotTotal(P ) = 0 ;

pour j = 1 faire M j =TailleChane( j) ;

CotT otal(P ) =CotTotal(P )+CoutChane( j, M j , P ) ; n n

Retourner minP P CotTotal(P ) ; n

123

programme dynamique dni prcdement pour tous les placements possibles sur les noeuds supprims.

Le problme de suppression de noeuds partir dune proprit de graphes , le problme de suppression de noeuds est dni de la manire suivante : il sagit, dans dun graphe donn, de supprimer un minimum de noeuds an de trouver un sous-graphe vriant la proprit .

Dans la suite, nous allons considrer le problme de suppression de noeuds pour des proprits de graphes vriant les hypothses suivantes :

hrdit : si est vraie pour un graphe G, alors elle reste vraie galement pour tous les sous-graphes induits par la suppression de certains noeuds.

non triviale : est vraie pour un noeud isol, mais ne lest pas pour tous les graphes.

Facile : le problme de dcision pour savoir si un graphe donn vrie ou non est dans P.

Intressante : les taille des graphes vriant la proprit ne sont pas bornes. Thorme 10 ([82]) Le problme de suppression de noeuds pour une proprit hrditaire, non triviale, facile et intressante, est NP-complet. Corollaire 4 Soit la proprit sur les graphes contenant uniquement des chanes et des anneaux. Le problme de suppression de noeuds pour la proprit est NP complet. Preuve Il sut de remarquer que la proprit est hrditaire, non triviale, facile et intressante.

124

5.6

C
Nous nous sommes intresss dans ce chapitre au problme de placement de donnes

sur un nombre quelconques dutilisateurs connects entre eux par un rseau et o les donnes sont modlises par un ensemble dobjets de tailles uniformes. Dans un premier temps, nous avons construit un algorithme polynomial bas sur la programmation dynamique pour rsoudre dune faon optimale le problme lorsque les utilisateurs sont relis par une chane. Ensuite, nous avons adapt cette approche pour rsoudre ecacement le cas o la topologie du rseau de connexion est un anneau puis une toile gnralise. Finalement, nous avons considr un cas plus gnral o la topologie du rseau est quelconque et telle que le nombre dutilisateurs avec un degr au moins gal 3 est constant. Nous avons prouv dans ce cas quil nest pas possible dutiliser lalgorithme de placement de donnes sur une chane pour aboutir une solution optimale. Nous avons en eet montr que le problme de suppression de noeuds pour aboutir un graphe ne contenant que des chanes et des anneaux tait NP-complet. Ainsi, le problme de placement de donnes reste ouvert dans le cas de topologies quelconques. Il serait, aussi, intressant de considrer dautres variantes du problmes o par exemple on rajoute une contrainte conomique qui consiste allouer chaque utilisateur un budget limit pour convaincre les autres utilisateurs de rpliquer localement des donnes spciques.

125

126

Conclusion
Dans cette thse, nous avons tudi, en deux parties, plusieurs problmes doptimisation combinatoire poss dans le contexte des architectures parallles ainsi que dans le contexte des rseaux informatiques.

Problmes de minimisation de lnergie La premire partie de la thse a t consacre ltude de problmes dordonnancement dans le but de minimiser lnergie consomme. Dans ce contexte, lordonnancement constitue un moyen parmi dautres pour tenter de matriser la consommation dnergie dans les systmes informatiques. En eet, lecacit nergtique devient de plus en plus un paramtre important dans la conception des protocoles et des mcanismes de calcul et dchange des donnes.

Dans un premier temps, nous avons considr le modle dadaptation de la vitesse (Speed Scaling). Nous avons propos un algorithme optimal bas sur une rduction en un problme de maximisation de ot pour calculer un ordonnancement qui minimise lnergie consomme par un ensemble de machines identiques tout en respectant les dates darrive et les dates dchance des tches. Notons que le passage dun problme dordonnancement un problme de ot maximum constitue une technique qui a t longtemps utilise pour rsoudre des problmes dordonnancement classiques dans le contexte de machines parallles. Nous avons donc montr quil est possible dadapter cette approche pour rsoudre une nouvelle catgorie de problmes dordonnancement o, en plus des objectifs classiques, on cherche optimiser le critre de lnergie. Ceci nous conduit poser comme perspective lutilisation des ots pour tenter de 127

rsoudre dautres variantes du problme de minimisation de lnergie consomme sous le modle dadaptation de la vitesse ou sous dautres modles de calcul de lnergie comme ceux o on introduit des tats de veilles.

Dans un deuxime temps, nous nous sommes intresss au cas o on rajoute un tat de veille au modle dadaptation de la vitesse. Dans ce cas, le problme devient plus compliqu car il faut xer tout instant ltat de chaque machine, i.e. en activit ou en veille, en plus de sa vitesse et de la tche en excution. Nous avons donc propos, dans le cas dune machine unique et dinstances agrables, un programme dynamique permettant de retourner une solution optimale qui minimise la consommation dnergie. Une extension naturelle de ce travail serait donc de considrer le cas de plusieurs machines identiques ou htrognes. Une autre direction explorer consiste tudier dautres modles o on autorise plusieurs tats dirents de basse consommation dnergie.

Finalement, nous avons considr le cas o les machines sont htrognes dans le sens o, la date darrive et la dure dexcution de chaque tche ainsi que lnergie consomme suite son excution dpendent de la machine daectation. Nous avons aussi suppos quil existe un ensemble ni de vitesses pour les machines et que chaque tche est excute sans premption une vitesse constante. Dans ce modle, en plus de la machine daectation, la dure dexcution et lnergie pour chaque tche sont aussi fonctions de la vitesse dexcution. Notons que par rapport aux problmes prcdents, nous navons impos aucun modle de calcul de lnergie consomme dans ce problme. Par ailleurs, nous avons adapt un algorithme dapproximation randomis bas sur la technique de larrondi alatoire pour rsoudre le problme de minimisation de lnergie plus la somme des temps de compltude pondrs ainsi que le problme de minimisation de la somme des temps de compltude pondrs avec un budget xe dnergie quon ne souhaite pas dpasser. Ayant russi proposer une version drandomise de lalgorithme pour le premier problme, la question reste ouverte quant la drandomisation pour le problme avec budget dnergie. Une

128

autre question intressante consiste tendre ce travail dans le cas o les vitesses des machines forment un spectre continu de valeurs positives. Enn, en la prsence des dates darrive pour les tches, il semble judicieux dtudier le cas o on cherche minimiser une fonction objectif qui, en plus de lnergie, tient compte des temps de rponse des tches, i.e. le temps total pass par une tche dans le systme entre sa date darrive et sa date de compltude.

Problmes doptimisation classiques Dans la deuxime partie de cette thse nous avons tudi deux problmes doptimisation classiques. Nous avons considr, en premier lieu, le problme dordonnancement dans un graphe dordre dintervalles sur des machines ddies et en prsence de dlais de communication. Nous avons aussi considr des tches unitaires avec des dates darrive et dchance. Tout dabord, nous avons montr que le problme est NP-complet au sens fort dans le cas o les temps de communication sont quelconques. Ensuite, dans le cas des temps de communication monotones, nous avons prsent une extension dun algorithme de liste de la littrature et nous avons montr quelle est capable de retourner une solution ralisable en un temps polynomial. Enn, nous avons montr travers un exemple simple quil nexiste pas dalgorithme de liste pour rsoudre le problme avec des machines types, i.e. plusieurs machines identiques pour chaque type de tches. On en dduit donc une premire perspective qui consiste tudier le problme dans le cas des machines types et concevoir des algorithmes ecaces pour le rsoudre. Par ailleurs, en essayant dappliquer notre algorithme dans le cas des machines types et des temps de communication unitaires, nous nous sommes aperus que la procdure de modication des dates dchance namliore pas forcment celles des tches. Ainsi, lalgorithme risque de retourner des solutions non ralisables. Il serait donc intressant dadapter cet algorithme dans le cas des machines types et des temps de communication unitaires.

Le dernier problme que nous avons tudi est le problme de placement de donnes dans un

129

rseau pair--pair. Le but tant de minimiser le cot daccs des utilisateurs aux donnes, nous avons dcrit un algorithme de programmation dynamique pour rsoudre ce problme lorsque la topologie du rseau est une chane et lorsque les donnes sont modlises par des objets de tailles uniformes. Nous avons adapt, par la suite, cet algorithme pour rsoudre le problme pour des topologies en anneau et en toile gnralise. Finalement, nous navons pas russi tendre cette approche pour des graphes quelconques avec un nombre constant de noeuds de degr suprieur ou gal 3. En eet, nous avons prouv que le problme de suppression de noeuds pour dcomposer le graphe en des sous graphes connexes en chanes et en anneaux est NP-complet. Pour poursuivre ce travail, il serait intressant dtudier les cas o le problme de placement de donnes peut tre rsolu pour des graphes plus gnraux. Une autre perspective consiste rajouter une dimension conomique au problme comme par exemple lattribution dun budget chaque utilisateur pour convaincre les autres noeuds de rpliquer des donnes spciques.

130

Bibliographie
[1] F. Afrati, E. Bampis, C. Chekuri, D. Karger, C. Kenyon, S. Khanna, I. Milis, M. Queyranne, M. Skutella, C. Stein, and M. Sviridenko. Approximation schemes for minimizing average weighted completion time with release dates. In Proceedings of the 40th Annual Symposium on Foundations of Computer Science, FOCS 99, pages 3244, Washington, DC, USA, 1999. IEEE Computer Society. [2] F. Afrati, E. Bampis, L. Finta, and I. Milis. Scheduling trees with large communication delays on two identical processors. In Proceedings from the 6th International Euro-Par Conference on Parallel Processing, Euro-Par 00, pages 288295, London, UK, 2000. Springer-Verlag. [3] S. Albers. Algorithms for dynamic speed scaling. In T. Schwentick and C. Drr, editors, 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011), volume 9 of Leibniz International Proceedings in Informatics (LIPIcs), pages 111, Dagstuhl, Germany, 2011. Schloss DagstuhlLeibniz-Zentrum fuer Informatik. [4] S. Albers and A. Antoniadis. Race to idle : new algorithms for speed scaling with a sleep state. In Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 12, pages 12661285. SIAM, 2012. [5] S. Albers, A. Antoniadis, and G. Greiner. On multi-processor speed scaling with migration : extended abstract. In Proceedings of the 23rd ACM symposium on Parallelism in algorithms and architectures, SPAA 11, pages 279288, New York, NY, USA, 2011. ACM. [6] S. Albers and H. Fujiwara. Energy-ecient algorithms for ow time minimization. ACM Trans. Algorithms, 3, November 2007.

131

[7] S. Albers, F. Mller, and S. Schmelzer. Speed scaling on parallel processors. In Proceedings of the nineteenth annual ACM symposium on Parallel algorithms and architectures, SPAA 07, pages 289298, New York, NY, USA, 2007. ACM. [8] H. Ali and H. E. Rewini. An optimal algorithm for scheduling interval ordered tasks with communication on n processors. Journal of Computer and System Sciences, 51(2) :301 306, 1995. [9] E. Angel, E. Bampis, and V. Chau. Low complexity scheduling algorithm minimizing the energy for tasks with agreeable deadlines. In The 10th Latin American Symposium on Theoretical Informatics (LATIN2012), 2012. [10] E. Angel, E. Bampis, F. Kacem, and D. Letsios. Speed scaling on parallel processors with migration. CoRR, abs/1107.2105, 2011. [11] E. Angel, E. Bampis, and A. Kononov. A fptas for approximating the unrelated parallel machines scheduling problem with costs. In F. auf der Heide, editor, Algorithms - ESA 2001, volume 2161 of Lecture Notes in Computer Science, pages 194205. Springer Berlin / Heidelberg, 2001. [12] E. Angel, E. Bampis, and A. Kononov. On the approximate tradeo for bicriteria batching and parallel machine scheduling problems. Theor. Comput. Sci., 306 :319338, September 2003. [13] E. Angel, E. Bampis, G. G. Pollatos, and V. Zissimopoulos. Optimal data placement on networks with constant number of clients. CoRR, abs/1004.4420, 2010. [14] B. Awerbuch, S. Kutten, and D. Peleg. Competitive distributed job scheduling. In Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, STOC 92, pages 571580, New York, NY, USA, 1992. ACM. [15] C. P. B. Chen and G. Woeginger. A review of machine scheduling : Complexity, algorighms and approximability, pages 21169. Kluwer Academic Publishers, d.-z. du and p. pardalos edition, 1998.

132

[16] I. Baev, R. Rajaraman, and C. Swamy. Approximation algorithms for data placement problems. SIAM Journal on Computing, 38(4) :14111429, 2008. [17] I. D. Baev and R. Rajaraman. Approximation algorithms for data placement in arbitrary networks. In Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, SODA 01, pages 661670, Philadelphia, PA, USA, 2001. Society for Industrial and Applied Mathematics. [18] N. Bansal, T. Kimbrel, and K. Pruhs. Speed scaling to manage energy and temperature. J. ACM, 54 :139, March 2007. [19] N. Bansal, K. Pruhs, and C. Stein. Speed scaling for weighted ow time. In Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, SODA 07, pages 805813, Philadelphia, PA, USA, 2007. Society for Industrial and Applied Mathematics. [20] P. Baptiste, M. Chrobak, and C. Drr. Polynomial time algorithms for minimum energy scheduling. In L. Arge, M. Homann, and E. Welzl, editors, Algorithms - ESA 2007, volume 4698 of Lecture Notes in Computer Science, pages 136150. Springer Berlin / Heidelberg, 2007. [21] B. D. Bingham and M. R. Greenstreet. Energy optimal scheduling on multiprocessors with migration. In Proceedings of the 2008 International Symposium on Parallel and Distributed Processing with Applications ISPA 2008, pages 153161, 2008. [22] C. E. Bonferroni. Teoria statistica delle classi e calcolo delle probabilita. Pubbl. d. R. Ist. Super. di Sci. Econom. e Commerciali di Firenze. 8 Firenze : Libr. Internaz. Seeber. 62 S., 1936. [23] F. A. Bower, D. J. Sorin, and L. P. Cox. The impact of dynamically heterogeneous multicore processors on thread scheduling. IEEE Micro, 28 :1725, May 2008. [24] D. M. Brooks, P. Bose, S. E. Schuster, H. Jacobson, P. N. Kudva, A. Buyuktosunoglu, J.-D. Wellman, V. Zyuban, M. Gupta, and P. W. Cook. Power-aware microarchitecture : Design and modeling challenges for next-generation microprocessors. IEEE Micro, 20(6) :2644, nov 2000. 133

[25] P. Brucker. Scheduling Algorithms. SpringerVerlag, 2004. [26] P. Brucker and S. Knust. Complexity results for single-machine problems with positive nish-start time-lags. Computing, 63 :299316, 1999. [27] J. Bruno, E. G. Coman, Jr., and R. Sethi. Scheduling independent tasks to reduce mean nishing time. Commun. ACM, 17 :382387, July 1974. [28] D. P. Bunde. Power-aware scheduling for makespan and ow. In Proceedings of the eighteenth annual ACM symposium on Parallelism in algorithms and architectures, SPAA 06, pages 190196, New York, NY, USA, 2006. ACM. [29] R. A. Carrasco, G. Iyengar, and C. Stein. Energy aware scheduling for weighted completion time and weighted tardiness. CoRR, abs/1110.0685, 2011. [30] H.-L. Chan, J. W.-T. Chan, T.-W. Lam, L.-K. Lee, K.-S. Mak, and P. W. H. Wong. Optimizing throughput and energy in online deadline scheduling. ACM Trans. Algorithms, 6 :122, December 2009. [31] S.-H. Chan, T.-W. Lam, L.-K. Lee, H.-F. Ting, and P. Zhang. Non-clairvoyant scheduling for weighted ow time and energy on speed bounded processors. In Proceedings of the Sixteenth Symposium on Computing : the Australasian Theory - Volume 109, CATS 10, pages 310. Australian Computer Society, Inc., 2010. [32] C. Chekuri and S. Khanna. A ptas for minimizing weighted completion time on uniformly related machines. In F. Orejas, P. Spirakis, and J. van Leeuwen, editors, Automata, Languages and Programming, volume 2076 of Lecture Notes in Computer Science, pages 848861. Springer Berlin / Heidelberg, 2001. [33] C. Chekuri and S. Khanna. Approximation algorithms for minimizing average weighted completion time. Handbook of Scheduling : Algorithms, Models, and Performance Analysis. CRC Press, Inc., Boca Raton, FL, USA, 2004. [34] J.-J. Chen, H.-R. Hsu, K.-H. Chuang, C.-L. Yang, A.-C. Pang, and T.-W. Kuo. Multiprocessor energy-ecient scheduling with task migration considerations. In Proceedings of the 16th

134

Euromicro Conference on Real-Time Systems, pages 101108, Washington, DC, USA, 2004. IEEE Computer Society. [35] P. Chrtienne and C. Picouleau. Scheduling with communication delays : A survey. Scheduling Theory and Its Applications, 1995. [36] S. A. Cook. The complexity of theorem-proving procedures. In Proceedings of the third annual ACM symposium on Theory of computing, STOC 71, pages 151158, New York, NY, USA, 1971. ACM. [37] B. D. de Dinechin. Scheduling monotone interval orders on typed task systems. In 26th Workshop of the UK Planning and Scheduling Special Interest Group, pages 2531, 2007. [38] X. Deng, H.-N. Liu, and B. Xiao. Deterministic load balancing in computer networks. In Proceedings of the 1990 IEEE Second Symposium on Parallel and Distributed Processing, SPDP 90, pages 5057, Washington, DC, USA, 1990. IEEE Computer Society. [39] M. J. Flynn, P. Hung, and K. W. Rudd. Deep-submicron microprocessor design issues. IEEE Micro, 19(4) :1122, jul 1999. [40] M. R. Garey and D. S. Johnson. Computers and Intractability : A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., New York, NY, USA, 1979. [41] R. Giroudeau, J. Knig, F. Moula, and J. Palaysi. Complexity and approximation for the precedence constrained scheduling problem with large communication delays. In J. Cunha and P. Medeiros, editors, Euro-Par 2005 Parallel Processing, volume 3648 of Lecture Notes in Computer Science, pages 622622. Springer Berlin / Heidelberg, 2005. [42] R. Graham, E. Lawler, J. Lenstra, and A. Kan. Optimization and approximation in deterministic sequencing and scheduling : a survey. In E. J. P.L. Hammer and B. Korte, editors, Discrete Optimization II Proceedings of the Advanced Research Institute on Discrete Optimization and Systems Applications of the Systems Science Panel of NATO and of the Discrete Optimization Symposium co-sponsored by IBM Canada and SIAM Ban, Aha. and Vancouver, volume 5 of Annals of Discrete Mathematics, pages 287 326. Elsevier, 1979.

135

[43] G. Greiner, T. Nonner, and A. Souza. The bell is ringing in speed-scaled multiprocessor scheduling. In Proceedings of the twenty-rst annual symposium on Parallelism in algorithms and architectures, SPAA 09, pages 1118, New York, NY, USA, 2009. ACM. [44] A. Gupta, R. Krishnaswamy, and K. Pruhs. Scalably scheduling power-heterogeneous processors. In Proceedings of the 37th international colloquium conference on Automata, languages and programming, ICALP10, pages 312323, Berlin, Heidelberg, 2010. SpringerVerlag. [45] L. A. Hall, D. B. Shmoys, and J. Wein. Scheduling to minimize average completion time : o-line and on-line algorithms. In Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms, SODA 96, pages 142151, Philadelphia, PA, USA, 1996. Society for Industrial and Applied Mathematics. [46] W. A. Horn. Some simple scheduling algorithms. Naval Research Logistics Quarterly, 21(1) :177185, 1974. [47] J.-J. Hwang, Y.-C. Chow, F. D. Anger, and C.-Y. Lee. Scheduling precedence graphs in systems with interprocessor communication times. SIAM J. Comput., 18 :244257, April 1989. [48] S. Irani and K. R. Pruhs. Algorithmic problems in power management. SIGACT News, 36 :6376, June 2005. [49] S. Irani, S. Shukla, and R. Gupta. Algorithms for power savings. ACM Trans. Algorithms, 3, November 2007. [50] J. Jackson. Scheduling a production line to minimize maximum tardiness. Research report. University of California, 1955. [51] K. Jansen. Analysis of scheduling problems with typed task systems. Discrete Applied Mathematics, 52(3) :223 232, 1994. [52] K. Jansen and L. Porkolab. Improved approximation schemes for scheduling unrelated parallel machines. In Proceedings of the thirty-rst annual ACM symposium on Theory of computing, STOC 99, pages 408417, New York, NY, USA, 1999. ACM. 136

[53] R. M. Karp. Reducibility among combinatorial problems. In M. Jnger, T. M. Liebling, D. Naddef, G. L. Nemhauser, W. R. Pulleyblank, G. Reinelt, G. Rinaldi, and L. A. Wolsey, editors, 50 Years of Integer Programming 1958-2008, pages 219241. Springer Berlin Heidelberg, 2010. [54] W. Karush. Minima of functions of several variables with inequalities as side conditions. Masters thesis, Department of Mathematics, University of Chicago, Chicago, IL, USA, 1939. [55] J. Kleinberg and E. Tardos. Algorithm Design. Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA, 2005. Exercice 23, Chapter 7 and its solution. [56] J. G. Koomey. Growth in data center electricity use 2005 to 2010. The New York Times, 3(3) :24, 2011. [57] H. W. Kuhn and A. W. Tucker. Nonlinear programming. In Proceedings of the Second Berkeley Symposium on Mathematical Statistics and Probability, pages 481492. Berkeley, California, 1951. [58] R. Kumar, D. M. Tullsen, P. Ranganathan, N. P. Jouppi, and K. I. Farkas. Single-isa heterogeneous multi-core architectures for multithreaded workload performance. SIGARCH Comput. Archit. News, 32 :6475, March 2004. [59] Y.-K. Kwok and I. Ahmad. Benchmarking and comparison of the task graph scheduling algorithms. J. Parallel Distrib. Comput., 59(3) :381422, dec 1999. [60] T.-W. Lam, L.-K. Lee, H.-F. Ting, I. K. To, and P. W. Wong. Sleep with guilt and work faster to minimize ow plus energy. In Proceedings of the 36th International Colloquium on Automata, Languages and Programming : Part I, ICALP 09, pages 665676, Berlin, Heidelberg, 2009. Springer-Verlag. [61] T.-W. Lam, L.-K. Lee, I. K. K. To, and P. W. H. Wong. Competitive non-migratory scheduling for ow time and energy. In Proceedings of the twentieth annual symposium on Parallelism in algorithms and architectures, SPAA 08, pages 256264, New York, NY, USA, 2008. ACM.

137

[62] A. Leung, K. V. Palem, and A. Pnueli. Scheduling time-constrained instructions on pipelined processors. ACM Trans. Program. Lang. Syst., 23 :73103, January 2001. [63] M. Li, A. C. Yao, and F. F. Yao. Discrete and continuous min-energy schedules for variable voltage processors. Proceedings of the National Academy of Sciences of the United States of America, 103(11) :39833987, 2006. [64] J.-H. Lin and J. S. Vitter. epsilon-approximations with minimum packing constraint violation (extended abstract). In STOC92, pages 771782, 1992. [65] R. Merritt. Cpu designers debate multi-core future. EE Times, February 2008. [66] T. Y. Morad, U. C. Weiser, A. Kolodny, M. Valero, and E. Ayguade. Performance, power eciency and scalability of asymmetric cluster chip multiprocessors. IEEE Comput. Archit. Lett., 5 :417, January 2006. [67] A. Munier, F. Kacem, B. D. de Dinechin, and L. Finta. Minimizing the makespan for an interval ordered precedence graph on m processors with communication delays and unit execution time tasks. In 9th Workshop on Models and Algorithms for Planning and Scheduling Problems (MAPSP09), pages 810, Rolduc, Pays Bas, Juin 2009. [68] Y. Nesterov and A. Nemirovskii. Interior-Point Polynomial Algorithms in Convex Programming. Society for Industrial and Applied Mathematics, Philadephia, PA, 1994. [69] E. Nron, P. Baptiste, and F. Sourd. Modles et algorithmes en ordonnancement. J. ACM, pages 198201. [70] K. V. Palem and B. B. Simons. Scheduling time-critical instructions on risc machines. ACM Trans. Program. Lang. Syst., 15 :632658, September 1993. [71] C. H. Papadimitriou and M. Yannakakis. Scheduling interval-ordered tasks. SIAM Journal on Computing, 8(3) :405409, 1979. [72] K. Pruhs, P. Uthaisombut, and G. Woeginger. Getting the best response for your erg. ACM Trans. Algorithms, 4 :38 :117, July 2008. [73] K. Pruhs, R. van Stee, and P. Uthaisombut. Speed scaling of tasks with precedence

constraints. Theor. Comp. Sys., 43 :6780, March 2008. 138

[74] P. Raghavan and C. Tompson. Randomized rounding : A technique for provably good algorithms and algorithmic proofs. Combinatorica, 7 :365374, 1987. [75] A. S. Schulz and M. Skutella. Scheduling unrelated machines by randomized rounding. SIAM Journal on Discrete Mathematics, 15(4) :450469, 2002. [76] D. B. Shmoys and E. Tardos. An approximation algorithm for the generalized assignment problem. Math. Program., 62 :461474, December 1993. [77] M. Skutella. Convex quadratic and semidenite programming relaxations in scheduling. J. ACM, 48 :206242, March 2001. [78] M. A. Trick. Scheduling multiple variable-speed machines. Operations Research,

42(2) :234248, 1994. [79] B. Veltman, B. Lageweg, and J. Lenstra. Multiprocessor scheduling with communication delays. Parallel Computing, 16(2-3) :173 182, 1990. [80] J. Verriet. Scheduling interval-ordered tasks with non-uniform deadlines subject to non-zero communication delays. Parallel Computing, 25(1) :3 21, 1999. [81] W. Wu, M. Li, and E. Chen. Min-energy scheduling for aligned jobs in accelerate model. In Y. Dong, D.-Z. Du, and O. Ibarra, editors, Algorithms and Computation, volume 5878 of Lecture Notes in Computer Science, pages 462472. Springer Berlin / Heidelberg, 2009. [82] M. Yannakakis. Node-and edge-deletion np-complete problems. In Proceedings of the tenth annual ACM symposium on Theory of computing, STOC 78, pages 253264, New York, NY, USA, 1978. ACM. [83] F. Yao, A. Demers, and S. Shenker. A scheduling model for reduced cpu energy. In Proceedings of the 36th Annual Symposium on Foundations of Computer Science, FOCS 95, pages 374382, Washington, DC, USA, 1995. IEEE Computer Society. [84] W. Yu, H. Hoogeveen, and J. K. Lenstra. Minimizing makespan in a two-machine ow shop with delays and unit-time operations is np-hard. Journal of Scheduling, 7 :333348, 2004.

139