La ROADEF
R.O.A.D
Événements
Prix
Publications
Plus
Forum
Connexion

stage M2 au LIP6 - Comparison de deux algorithmes pour l?ajustement des dates d?échéance pour un pr

Forum 'Stages' - Sujet créé le 05/11/2019 par Alix (81 vues)


Le 05/11/2019 par Alix :

Descriptif du sujet

On consid?re le probl?me d’ordonnancement classique P |prec, ri, di|? d?fini par un ensemble de t?ches de dur?e quelconque et des contraintes de pr?c?dence ? effectuer sur m processeurs identiques. Chaque t?che poss?de un date d’?ch?ance di et une date de disponibilit? ri. Le probl?me consiste ? d?terminer si il existe un ordonnancement r?alisable, et ? le construire le cas ?ch?ant.

Ce probl?me est NP-difficile, y compris dans le cas o? les t?ches sont de dur?e 1. Deux classes d’algorithmes ont ?t? d?velopp?es dans ce cas particulier pour am?liorer l’?valuation initiale des dates d’?ch?ance en exprimant des conditions n?cessaires sur celles-ci. Ils effecuent alors des modifications des dates d’?ch?ances jusqu’? arriver ? un point fixe.

  1. L’algorithme de Garey-Johnson [2] (GJ) s?lectionne des ensembles de t?ches ? effectuer obli- gatoirement dans des intervalles fix?s. A partir du volume de ces t?ches, il peut d?terminer des conditions n?cessaires sur les dates d’?ch?ances et les modifier.

  2. L’algorithme de Leung, Palem et Pnueli [3](LPP) exprime des conditions sur les dates d’?ch?ance en fonction des contraintes de pr?c?dence et utilise l’algorithme de Jackson pour d?terminer si ces dates sont coh?rentes.

Hanen et Munier [1] ont montr? que ces deux algorithmes aboutissent aux m?mes date d’?ch?ances et une ?tude exp?rimentale a confirm? que l’algorithme LPP est plus rapide que GJ. Le but de ce stage est d’?tudier des extensions de ces deux algorithmes pour le cas o? les t?ches sont de dur?e quelconque, pr?emptives ou non. Ce probl?me, bien que central en th?orie de l’ordonnancement, a ?t? peu ?tudi?. La question est alors de comparer deux extensions possibles :

  1. D’un point de vue exp?rimental, il s’agit de comparer la complexit? de ces deux approches et d?terminer si ces deux algorithmes convergent vers les m?mes valeurs. La r?duction des intervalles d’ex?cution des t?ches ? un impact sur le parrall?lisme du probl?me. Cet impact peut-?tre mesur? en consid?rant le nombre maximum de t?ches ex?cutables ? un instant donn? en fonction des intervalles obtenus.

  2. D’un point de vue plus th?orique, il s’agit de d?terminer si les conditions n?cessaires exprim?es par ces deux approches restent ?quivalentes pour des t?ches de dur?e diff?rentes.

Dans un premier temps, il s’agit d’impl?menter ces deux extensions et de tester leur performance sur des instances al?atoires dans le but de comparer leur vitesse de convergence et la qualit? des dates d’?ch?ances obtenues. Dans un second temps, nous ?tudierons des cas particuliers en fonction de la structure du graphe de pr?c?dence et de la dur?e des t?ches pour comparer de mani?re th?orique les deux approches test?es.

Les r?sultats de cette ?tude pourront ?tre utilis?s dans plusieurs contexte. Tout dabord, l’expression des conditions n?cessaires et des algorithmes pour les mettre en oeuvre peuvent ?tre utilis?s comme un pr?-traitement pour des m?thodes de r?solution exactes ou des algorithmes param?tr?s du probl?me d’ordonnancement. Ces conditions peuvent ?galement servir de base pour l’?tude th?orique d’algorithmes approch?s avec ratio d’approximation pour ce probl?me.

 Conditions du stage

Le stage aura lieu en 2020 au LIP6 sur le campus Pierre et Marie Curie (4 place Jussieu, 75252 Paris) et sera co-encadr? par Claire Hanen et Alix Munier-Kordon pour une dur?e de 6 mois. La gratification pr?vue est de 554.4 Euros par mois.

Le candidat recherch? doit ?tre en Master 2 de recherche op?rationnelle, de math?matiques appliqu?es, d’informatique ou une ?cole d’ing?nieur avec un cursus en informatique. Il doit avoir de solides connaissances en programmation et en algorithmique.

Pour postuler, envoyez par mail aux deux encadrants Claire.Hanen@lip6.fr et Alix.Munier@lip6.fr un CV avec au minimum les notes de M1 et de M2.

R?f?rences

[1] Aur?lien Carlier, Claire Hanen, and Alix Munier Kordon. The equivalence of two classical list scheduling algorithms for dependent typed tasks with release dates, due dates and precedence delays. J. Scheduling, 20(3) :303–311, 2017.

[2] M. R. Garey and D. S. Johnson. Two-processor scheduling with start-time and deadlines. SIAM Journal on Computing, 6 :416–426, 1977.

[3] Allen Leung, Krishna V. Palem, and Amir Pnueli. Scheduling time-constrained instructions on pipelined processors. ACM Trans. Program. Lang. Syst., 23 :73–103, January 2001.

page2image68542912 page2image68546752







Moteur de recherche
Tous les forums


  La Société française de Recherche Opérationnelle et Aide à la Décision ROADEF est une association Loi 1901 Plus d'informations sur la ROADEF