Box Methode M2 R

  • Published on
    06-Jul-2015

  • View
    505

  • Download
    0

Embed Size (px)

Transcript

<ul><li> 1. Universit Franois Rabelais ECOLE POLYTECHNIQUE Dpartement informatique 64 avenue Jean Portalis 37200 TOURS Rapport de stage Application de la mthode des botes pour chantillonnerlensemble des optima de ParetoVincent TKINDTRabah BELADLaboratoire dInformatique DI3 M2R64 Avenue Jean Portalis2007/200837200 TOURS </li></ul><p> 2. Table des matires1 Le problme dordonnancement6 1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .6 1.1.1 Prsentation du problme dordonnancement .. . . . . . . . . . . .6 1.1.2 Etat de lart . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . .7 1.2 Rsolution du Q|ri , pi = 1|Cmax . . . . . . . . . . . . . . . . . . . . . . . .7 1.2.1 pseudo-code de lalgorithme : . . . . . . . . .. . . . . . . . . . . .8 1.3 Rsolution du Q|ri , pi = 1|Lmax . . . . . . . . . . . . . . . . . . . . . . . . 11 1.4 Objectif du travail . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . 11 1.4.1 Optimalit dans les problmes multicritres [5]. . . . . . . . . . . 12 1.4.2 Dtrmination des optima de pareto . . . . . . . . . . . . . . . . . 12 1.4.3 Enumration des optima de pareto . . . . . . . . . . . . . . . . . . 142 La mthode des boites16 2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 2.2 la version lexicographique de lapproche -contrainte. . . . . . . . . . . . . 17 2.3 La mthode des boites . . . . . . . . . . . . . . . .. . . . . . . . . . . . . 17 2.4 La version a posteriori de la mthode des boites . . . . . . . . . . . . . . . 22 2.5 La version a priori de la mthode des boites . . . . . . . . . . . . . . . . . 23 2.6 Qualits de la reprsentation . . . . . . . . . . . . .. . . . . . . . . . . . . 243 Application au Q|ri , pi = p|Cmax , Lmax 26 3.1 la mthode des boites pour le problme Q|ri , pi = p|Cmax , Lmax 26 3.2 Le problme de faisabilit Q|ri , pi = p, di | . . . . . . .. . . . . . . . . . . 28 3.2.1 Modle mathmatique . . . . . . . . . . . . . .. . . . . . . . . . . 29 3.2.2 Pseudo code de Qdec . . . . . . . . . . . . . . .. . . . . . . . . . . 30 3.2.3 Pseudo code de la deuxime version de Qdec : . . . . . . . . . . . . 34 3.3 Exprimentation numrique . . . . . . . . . . . . . . .. . . . . . . . . . . 37 3. Table des gures 1.1 Dtermination par lapproche -contrainte . . . . . . . . . . . . . . . . . . 131.2 Enumration des optima de pareto stricts en utilisant lapproche -contrainte 15 2.1 La bote initiale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 192.2 Partitionnement dune boite . . . . . . . . . . . . . . . . . . . . . . . . . . 202.3 Rsultat du partitionnement dune boite . . . . . . . . . . . . . . . . . . . 212.4 Version a priori de la mthode des boites . . . . . . . . . . . . . . . . . . . 23 4. RemerciementsJe remercie lquipe Ordonnancement et Conduite de mavoir bien accueillie pour ce stage du master 2 de recherche informatique. Je tiens tout particulirement remercier Monsieur Vincent TKINDT, encadrant de mon stage de M2R, pour les connaissances, le soutien quil ma apport, et surtout pour la conance quil a exprim tout au long de ce stage. 5. IntroductionOrdonnancer un ensemble de taches cest leurs aecter des ressources limites dans le temps en vue doptimiser une ou plusieurs critres. Dans le cas des ordonnancements qui sont valus sur un unique critre, la solution optimale est clairement dnie contraire- ment aux ordonnancements valus sur plusieurs critres. En eet, pour de tels problmes, la solution cherche est un ensemble de points correspondants aux meilleurs compromis possibles entre les critres.Le meilleur compromis est x par le dcideur, il nest pas g, il nest pas modli- sable, il volue alatoirement dans le temps. Le prix du ptrole qui augmente implique que le cot du transport devient primordial, la perte de gros clients rend la productivit ngligeable cot du cot de stockage, des accords politiques sur le taux des missions des gaz toxiques dont rsulte une taxe et voila le cot de production qui redevient crucial. Cest dans ce contexte que ce place lnumration des optima de Pareto, orir au dcideur la possibilit de choisir une solution parmi les meilleures.Nous nous intressons dans ce travail lnumration des optima de pareto dans un problme machines parallles uniformes avec des taches identiques, cette conguration concorde avec les industries utilisant des machines neuves et modernes cots dautres, moins ecaces et moins rapides, pour le traitement des mmes taches, des traitements de lots. Le chapitre 1 de ce document est une introduction au problme dordonnancement que nous traitons, nous y rappelons certaines dnitions lmentaires ainsi que des notations de bases qui seront utilises par la suite. Le chapitre 2 est consacr la mthode dnumration utilis dans ce travail, nous y dcrirons ses fondements, son fonctionnement et ses qualits. Le chapitre 3 quand lui est ddi lapplication de la mthode des boites sur le problme dordonnancement bicritres que nous traitons, nous y prsentons lvaluation dun algorithme ncessaire cette application. Nous nirons par une conclusion gnrale et des perspectives. 6. Chapitre 1Le problme dordonnancement1.1 Introduction 1.1.1Prsentation du problme dordonnancementNous nous intressons dans notre travail lnumration des optima de parto dun problme dordonnancement de travaux identiques avec direntes dates de dbuts au plus tt sur des machines parallles uniformes, les critres minimiser tant le Cmax et Lmax .En utilisant la notation introduite par Graham, notre problme serai not Q|ri , pi = p, di |Cmax , Lmax . Nous avons donc n taches i qui seront ordonnances sur m machines parallles j. Chaque taches i est dnie par sa date de dbut au plus tt ri , sa date de n souhait di , et un temps opratoire pi . Toutes les taches ont le mme temps opratoire, nous aurons ainsi i = 1..n pi = p. elles doivent tre totalement excut par une des machines et ce sans aucune interruption.Chaque machine j doit excuter un travail la fois, et ne se direncie des autres machines que par sa vitesse opratoire Vj do le nom machine parallle uniforme. Ceci nous permet de dnir le temps opratoire rel dune tache i ordonnanc sur une machine j, qui serai pi,j = pi /Vj .Rsoudre notre problme consiste dterminer pour chaque tache i la machine j sur la quelle elle sera excuter un instant ti tel que ti ri , lobjectif tant de minimiser deux critres la fois. Le premier critre est le maximum des dates de n des taches Cmax (makespan), il est dni par Cmax = maxi=1..n {Ci }, avec Ci date de n dune tache i. Le second critre est le retard algbrique, il est dni par Lmax = maxi=1..n {Ci di }. Trouver une solution qui permet de minimiser les deux critres simultanment dans un problme bi-critre nest pas trs vident, vu que lexistante dune telle solution nest gnralement pas vri. Nous nous orientons donc vers lnumration des optima de parto stricts que nous dnirons ultrieurement.6 7. 1.1.2Etat de lart Dans la littrature, le nombre de travaux qui portent sur les problmes machines pa- rallles identiques domine largement celui des problmes machines parallles uniformes, ceci dit plusieurs rsultats intressant ont t tablie. [4] on dmontr que Q|ri|Cmax ainsi que Q|ri|Lmax tais NP-dicile. [1] proposent une heuristique avec une garantie de performance indpendante des vitesses des machines pour le Q|ri|Cmax . Pour des problmes avec des taches identiques, [6] prsentent des algorithmes polyno- miaux pour des problmes de types Q|pi = 1|fmax qui sont quivalant au problmes Q|pi = p|fmax . ils proposent un algorithme en O(n + mlog(m)) pour minimiser le Cmax et le C, et en O(nlog(n)) pour minimiser C w , Lmax , Tmax , et U w , et enn en O(nlog 2 (n))w pour Tmax . Lorsque les dates de dbut au plus tt sont direntes, ils proposent un algorithme en O(nlog(n)) pour le Q|ri , pi = 1|Cmax . [3] traite le problme Q|ri , pi = 1|Lmax et propose une Procdure par Sparation et va- luation trs ecace. il insinue que ce problme est NP-dicile en se basant sur le rsultat de [8] , qui ont dmontr que Q|ri , pi = 1, di af f ectable|Cmax est NP-dicile au sens fort, mais il ne le dmontre pas. Ce problme reste donc ouvert. 1.2 Rsolution du Q|ri, pi = 1|Cmax[6] prsentent une mthode squentielle en O(nlog(n)) qui se base sur le principe LST (Latest Start T ime) pour rsoudre le Q|ri , pi = 1|Cmax . Cest un algorithme en deux phases quon rsume comme suit : Dans la premire phase, une date de n imprative commune d , assez grande pour que tous les travaux soient ordonnancs, est x. Le LST dune tache i not Si , i = 1..n est dni comme tant sa date de dbut au plus tard, qui respecte la date de n imprative d. Laectation des taches sur les machines est dtermine en choisissant une tache i et en la plaant sur la machine qui la commencera au plus tard. Le rsultat de cette phase est un ensemble ordonn de date de dbut au plus tard et daectation sur les machines S ={S1 , .., Sn }. Dans la deuxime phase, les taches tries dans un ordre croissant des ri sont ordon- nancer en considrant leurs dates de dbut au plus tt, et ce sur les machines dtermines par lordre inverse de lensemble S. Lordonnancement obtenu ainsi est optimal. 7 8. 1.2.1 pseudo-code de lalgorithme : Etape 1 : /* Initialisation de lalgorithme */ T = {1, ..., n} ; // T ensemble des taches tri dans lorde croissant des ri s AM = ; // AM contient lordre LST daectation sur les machines d ; //deadline assez grande pour ordonnancer toutes les taches M M Cj = d, j = 1, ..., m ; // Cj est le completion time dune machine j = ; Etape 2 : /* Etablissement de lordre LST */ Pour i = 1 a n faireM pM p une machine j est choisie tel que (Cj Vj ) = max1km (Ck Vk ) ; AM = AM {j} ; M M p Cj = Cj Vj ; FinPour Etape 3 : /* ordonnancement des taches */ M Cj = 0, j = 1, ..., m ; Pour k = 1 a n faire soit i la tache T [k] ; soit j la machine AM [n k] ; M ordonnancer i sur la machine j a t tel que : t = max(ri , Cj ) ; CjM =t+ p ; Vj = {i} ; FinPour considerons lexemple suivant : n = 5, m = 2, p = 6, V1 = 3, V2 = 2, [ri ] = [1; 3; 5; 6; 7]1. Premire itration : dbut de la phase daectation. M T = {1, ..., 5}, AM = , Cj = d = 16, = .M la tache 1 est place sur la machine 1, AM = [1], C1 = 14.M M2. Deuxime itration : AM = [1], C1 = 14,C2 = 16. M M la tache 2 est place sur la machine 2, AM = [1; 2], C1 = 14,C2 = 13. 8 9. M M 3. Troisime itration : AM = [1; 2], C1 = 14,C2 = 13. M Mla tache 3 est place sur la machine 1, AM = [1; 2; 1], C1 = 12,C2 = 13.MM 4. Quatrime itration : AM = [1; 2; 1], C1 = 12,C2 = 13.M Mla tache 4 est place sur la machine 1, AM = [1; 2; 1; 1], C1 = 10,C2 = 13.M M 5. Cinquime itration : AM = [1; 2; 1; 1], C1 = 10,C2 = 13. M Mla tache 5 est place sur la machine 2, AM = [1; 2; 1; 1; 2], C1 = 10,C2 = 10.n de la phase daectation. 6. Sixime itration : dbut de la phase de squencement. MMT = [1; 2; 3; 4; 5],AM = [1; 2; 1; 1; 2], C1 = 0,C2 = 0. 9 10. la tache 1 est ordonnance sur la machine 2 t = r1 = 1, AM = [1; 2; 1; 1; ], M M C1 = 0,C2 = 4, = {1}.MM 7. Septime itration : AM = [1; 2; 1; 1; ], C1 = 0,C2 = 4, = {1}la tache 2 est ordonnance sur la machine 1 t = r2 = 3, AM = [1; 2; 1; ; ],M MC1 = 5,C2 = 4, = {2}.MM 8. Huitime itration : AM = [1; 2; 1; ; ], C1 = 5,C2 = 4, = {1, 2}Mla tache 3 est ordonnance sur la machine 1 t = 5, AM = [1; 2; ; ; ], C1 =M7,C2 = 4, = {3}.MM 9. Neuvime itration : AM = [1; 2; ; ; ], C1 = 7,C2 = 4, = {1, 2, 3}la tache 4 est ordonnance sur la machine 2 t = 6, AM = [1; ; ; ; ],M MC1 = 7,C2 = 9, = {4}. 10 11. MM10. Dixime itration : AM = [1; ; ; ; ], C1 = 7,C2 = 9, = {1, 2, 3, 4}M Mla tache 5 est ordonnance sur la machine 1 t = 7, AM = , C1 = 9,C2 = 9, = {5}.Fin de la phase de squencement et arrt de lalgorithme, la solution retourn est optimale. 1.3 Rsolution du Q|ri, pi = 1|LmaxLa complexit de ce problme est une question ouverte dans la littrature, il na pas t dmontr quun problme NP-dicile pouvait se rduire lui et il nexiste pas dalgorithme polynomial pour sa rsolution. [3] propose une procdure par sparation et valuation pour le Q|ri , pi = p, di |Lmax qui trouve une solution optimale en moins de 100 000 itrations pour des problmes dont le nombre de travaux n 80 et le nombre de machines m 3. 1.4 Objectif du travail Comme nous lavons nonc dans la prsentation du problme que nous traitons, notre objectif est de minimiser deux critres simultanment. Dans les problmes dordonnance- ments dont lobjectif est doptimiser un seul critre, la dnition dune solution optimale est vidente. En eet une solution appartient lensemble R, et dans R on dispose dun prordre total qui nous permet de comparer tous couple de solutions et de dterminer la meilleure.Dans les problmes doptimisation multicritres, la dnition dune solution optimale nest pas aussi vidente, car il existe rarement une solution minimisant tous les critres simultanment, on sintresse plutt des solutions de meilleurs compromis. Loptimalit dans les problmes multicritres fera lobjet de notre prochain paragraphe.11 12. 1.4.1Optimalit dans les problmes multicritres [5]Soit S RQ lensemble des solutions, et Z Rk limage dans lespace des critres de S par k critres Zi . Soit la structure dordre associe Rk tel que, x, y Rk :x y xi yi , i = 1..Kx = y xi = yi , i = 1..K Cette structure dordre dnit un prordre partiel sur Rk , k 2, mais ne peut dtermi- ner chaque fois la meilleure solution cause de lincomparabilit de certains vecteurs. Loptimalit dans les problmes dordonnancement multicritres est dnit laide de la notion doptimum de pareto.Denition 1. x S est un optimum de Pareto faible (ou solution faiblement ecace), si et seulement si y S tel que i = 1..k, Zi (y) &lt; Zi (x). Lensemble des optima de pareto faibles est not W E.Denition 2. x S est un optimum de Pareto strict (ou solution ecace), si et seulement si y S tel que i = 1..k, Zi (y) Zi (x). Lensemble des oprima de pareto strict est not E,et on a E W E.Denition 3. un problme doptimisation multicritre est dni comme suit : Z1 (x) Z (x) minf (x) = 2 ... ZK (x) avec x S1.4.2Dtrmination des optima de paretoAprs avoir dnit les optima de Pareto, nous allons maintenant nous intress aux mthodes qui nous permettent de les calculer. Parmi ces mthodes nous dnirons les deux qui sont utilis dans la mthode des boites.12 13. Approche -contrainteLapproche -contrainte est trs souvent utilis dans la littrature. Elle consiste ramener un problme doptimisation multicritre un problme monocritre en xant des bornes suprieures sur k 1 des critres du problme multicritre initial. La fonction objective du problme sera not (Z1 /Z2 , .., ZK ). Z1 sera le critre minimiser et i = 2, .., k Zi . Le problme monocritre rsultant, not (Pk ) , est le suivant : Min Zk (x)sachant que : xS Zi (x) k , i [1; k], i = k iFig. 1.1 Dtermination par lapproche -contrainte Une solution optimale pour le Problme (PK ) est un optimum de pareto faible.Approche lexicographiqueDans la mthode lexicographique, un ordre doptimisation des critres est dnit. Cette mthode est utilise lorsquaucune compensation nest autori...</p>