Approche multiniveau et ordonnnancement d’activités dans un contexte de production à la commande Jose Fernando Hernandez-Silva To cite this version: Jose Fernando Hernandez-Silva. Approche multiniveau et ordonnnancement d’activités dans un contexte de production à la commande. Automatique / Robotique. Institut National Polytechnique de Toulouse - INPT, 2008. Français. �tel-00245958� HAL Id: tel-00245958 https://tel.archives-ouvertes.fr/tel-00245958 Submitted on 7 Feb 2008 HAL is a multi-disciplinary open access archive for the deposit and dissemination of scientific research documents, whether they are published or not. The documents may come from teaching and research institutions in France or abroad, or from public or private research centers. L’archive ouverte pluridisciplinaire HAL, est destinée au dépôt et à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d’enseignement et de recherche français ou étrangers, des laboratoires publics ou privés. ! ! " ! #$# % %%&# tel-00245958, version 1 - 7 Feb 2008 % ' ' tel-00245958, version 1 - 7 Feb 2008 tel-00245958, version 1 - 7 Feb 2008 ! " # $ $ %! %& '( ) %! # (*+ " ! , - %! . /.01 ' % " / ' + - %/'+ - ! , $ $ 2 3 $ " %! %00" .3 $ + * %! ' 4/*" .3 $ +. *! " " " - - $ 2! , # 5 " - . . . %6( '+! , $ 2 2 #" 7 % '6+0*" .3 $ + 86." .3 $ 6 ) 2 9" " % ) ')/*" .3 $ 0 +- *" #" % %/6+" %: 3 " $ + % ." 2! , - ; " %2 " 3 ! $ - 8 ' 0 * - # $ " " + * - ( ! , $ - ' %/'+ $ - ! , - ( '()+ # " -" " ! , 2 $ %! % /6800" 8 + . +." $ 7 %! . ) . '! , 2 ! , # < $ * 7 ' 5" -" 8 4 5 % 0" -5" 8 ( ( 5 " / )5 4" # " %" 5 & .5 ! , - - $ 3 7 -" 2 % 0 = $ 2 > ! tel-00245958, version 1 - 7 Feb 2008 4" # 2 - 2 7 $ / 4 # $ " $ # ! > $ !!! (## tel-00245958, version 1 - 7 Feb 2008 ) )* ( $# % %% $+ ! " ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! # ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! $ ! ! ! ! ! ! ! ! ! ! ! ! ! & ' ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! " () "' * ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! !! # ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! !! " +, () ' * ! ! ! ! ! ! ! ! ! ! ! ! ! !! * () ' * ! ! ! ! ! ! ! - . / ' ! ! ! ! ! ! ! ! ! ! ! ! !! # ' ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! !! & ' ' ! ! ! ! ! ! ! ! !! 0 ' * ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! 2 ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! !! # * ! ! ! ! ! ! !! ! # ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! !! ! 3 4 ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! !! ! 5 ! ! ! ! ! ! ! ! ! !! ! 6 ' - ! ! ! ! ! ! !! & ( * ' ( !!! 0 ! ! ! ! ! ! ! ! ! ! ! ! !!! 0 7# 8 ! !! 9 ( * ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! !!! " '( ( .6& ! ! ! ! ! !!! ; * ( * ! ! ! ! ! ! ! ! ! ! ! !!! .' ! ! ! ! ! ! ! ! ! ! ! ! ! 9( , - . $ . ! ! ! ! !! . < ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! !! 9'' ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! !!! 9'' !!! 9'' ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! !!! 9'' ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! !! , / ( ! 3 # ( , ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! !! . # ( ( ! ! ! ! ! ! ! ! ! ! ! ! ), ! ! ! ! ! ! % ! ! % ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! 1 ! ! ! ! ! ! ! ! ! ! ! ! * ! ! ! ! ! ! ! ! : ! ! 1 ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! : !: tel-00245958, version 1 - 7 Feb 2008 - * !! ' # ! ! ! ! ! ! ! ! !! 2 ( ( ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! 2 4 ( ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! %% $+ % . % / 0 ! . * ! ! ! ! ! ! ! * ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! 9( ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! = ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! 0 0$ ! ! ! ! ! ! ! ! ! ! ! ! ! ! !! 2 4 ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! !! " ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! !! " ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! !! " ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! !! " ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! 0 '' ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! !! 3 ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! !! # ' ! ! ! ! ! ! ! ! ! !! 0 $ # ! ! ! ! !! 9'' ! 0 ' ' ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! !! . ' ' ! ! ! ! ! ! ! ! ! ! ! ! !! - ' # ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! !! - ' # ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! 0 > , 7+ $ # 8 ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! !! , # ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! !! , # ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! $ %% ! 3 ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! . ' ! ! ! ! ! ! ! ! ! " ' ? $0. ! ! ! ! ! ! ! ! ! ! ! ! ! ! . ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! 4 ! ! ! ! ! ! ! ! ! ! ! ! ! ! !! 6 5 ( @ , , ! ! ! ! ! ! ! ! ! ! ! ! !! = ( ! !! A ( ! ! ! ! ! ! ! ! ! ! ! ! !! 6 ' ' ! ! ! ! ! ! ! ! ! ! ! ! !! B ' ' ! ! ! ! ! ! ! ! ! ! ! ! ! ! C , ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! !! - , ! ! ! ! ! ! ! !! 3 , ! , ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! $ ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! : : 12 : : : : : : : : : 1 1 1 3* : % % % % % % % % %1 !! !! !! 1 1 . * ! ! ! ! ! ! ! ! ! ! ! ! . 5 ! ! ! ! ! ! ! ! ! ! ! ! 6 4 ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! %1 % %% ))4 9 ' ' ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! : ! ! 0 ' ' 7 8 ! ! ! ! ! : ! ! 0 ' ' 7 8 ! ! ! , ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! % ! ! 9 ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! 9 7 $ 8 ! ! !! . ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! !! ' ! ! ! ! ! ! ! ! ! ! ! ! !! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! : !! , ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! 1 ! # ' ! ! ! ! ! ! ! ! ! ! ! !! . ! ! ! ! ! !! # / 9( $ ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! tel-00245958, version 1 - 7 Feb 2008 ! 4 50 $ ! 0$ ! ! ! ! ! ! ! ! ! ! ! ! = ! ! ! ! ! 0 $ 5 ! !! " ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! !! " ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! !! " ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! 9'' $ '' ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! !! 0 '' ! ! ! ! ! ! ! ! !! , '' ! !! 0 $ '' ! ! ! ! ! ! ! ! ! ! ! ! ! , * ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! !! 2 4 , ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! !! ' ! ! ! ! ! ! ! ! ! ! ! ! ! ! !! , ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! !! 3 , ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! 3 ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! %%$ 6.% ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! )*2 ! ! ! ! ! ! ! ! ! ! : : 1 )4)71 tel-00245958, version 1 - 7 Feb 2008 tel-00245958, version 1 - 7 Feb 2008 ! ! ! ! ! !: !1 ! !% ! ! ! ! ! ! ! : ! 1 ! ! ! ! ! ! !: !1 ! !% ! ! ! ! ! ! ! : ! 1 4 , ! ! ! ! ! ! ! D ( * E9 $; F G 6 () ' * E" !F %%G ! ! ! ! ! 5 () ' * ! ! ! ! ! ! ! ! ! ! ! D * ' ! ! " ' 4 ! 3 # ( ( * E (F %%G ! ! ! ! ! 0 ' * ' EH G ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! 3 ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! 6 ' - " H< ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! EH !F G ! ! ! ! ! ! ! ! ! ! ! ( ( E ( I F %%%G ! ! ! ! ! 9'' 7 8 ! ! ! ! ! ! ! ! ! ! ! ! ! ! 9'' ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! 9'' ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! 6 ( E0 J F G ! ! ! ! ! ! ! ! ! '' E ( I F %%%G ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! @ , , = 2J ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! 4 < ! ! ! ! ! ! ! ! ! ! ! # ! ! ! ! ! ! ! ! ! ! ! 3 ! ! ! ! ! ! ! ! ! 3 '' ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! = ( ! ! ! ! ! ! ! ! ! ! ! # ' ! ! ! ! ! ! ! ! ! ! ! ! , rdG i ! ! ! ! ! ! # ' ! ! ! ! ! ! ! ! # ' ! ! ! ! ! ! ! ! 0$ 7lg = 128 ! ! ! ! ! ! ! ! ! ! ! 2 ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! 0$ # ! ! ! 2 ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! 4 < $ ! 4 < % ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! % : ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! !F ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! : : : : :: :1 : :% 1 1 1 1: 1 ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! : % ! ! ! tel-00245958, version 1 - 7 Feb 2008 ! ! !: !1 ! !% ! ! ! ! ! ! ! ! ! ! ! " , ( ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! 4 '( * . ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! J < , 5 ( $ ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! J < @ ( ! ! ! ! ! ! ! ! ! ! ! ! ! * ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! 0$ 2J ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! 2 (i, 1) (j, 1) ! ! ! ! ! ! ! ! ! ! ! ! ! ! 2 (j, 1) (i, 1) ! ! ! ! ! ! ! ! ! ! ! ! ! ! B ! ! ! ! ! ! ! 0$ lg = 4 ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! 2 ( lg = 4 ! ! ! 2 ( lg = 4 ! ! ! 0$ lg = 7 ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! 2 ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! 4 < 2J ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! 3 $2J ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! 3 $2J ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! 0$ 7lg = 128 ! ! ! ! 0$ @ ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! 0$ @ ' $ (α = 0, 7) ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! !: 0$ @ ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! !1 $ (β = 0, 7) ! ! ! ! ! ! ! ! ! ! ! ! ! ! 0$ ! ! ! ! ! ! ! ! !% 2 ! ! ! ! ! ! ! ! " , ( 7 8 ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! : % % % % % % % ! ! ! ! : ! ! ! ! ! ! : : = . ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! = '' ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! 3 , ( ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! 1 tel-00245958, version 1 - 7 Feb 2008 ! ! ! , # A K6 E3 !F :G ! 3 4 E-' F G ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! 6' ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! !: !1 ! !% ! ! ! ! ! ! J < ! ! * ! ! ! J < '' ! ! # ! ! J < ! ! * ! ! ! J < '' 7 J < '' ! ! ! ! ! ! ! ! ! ! J < ' ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! # ! ! J < '' 7 J < '' ! ! ! ! ! ! ! ! ! ! J < ' ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! !: !1 ! !% ! ! ! ! ! ! ! : ! 1 3 B ' ' ! ! ! ! ! ! ! ! ! J < ! ! ! - 7 * 3 * ! ! ! ! ! ! ! ! ! ! 4 , ( ' ! ! ! ! ! ! ! ! ' ! ! ! ! ! ! ! ! J < ! ! ! - 7 $ * 8 3 * ! ! ! ! ! ! ! ! ! ! 4 ( ! ! ! J < ! ! ! - 7 * 3 * ! ! ! ! ! ! ! ! ! ! 4 , ( 3 * ! ! ! ! ! ! ! ! ! ! 4 , ( ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! lg = 128 ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! lg = 128 ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! % % : : 1 1 1 1 1 1 1 1: 11 11 1% ! ! ! ! 8 ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! 8 ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! % % % % %% : : 1 1 1 ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! tel-00245958, version 1 - 7 Feb 2008 ! ! % ! ! ! ! ! ! J < P BCT F ! ! ! ! ! ! ! ! ! ! ! ! ! - 7 * 8 ! ! ! ! ! ! ! ! ! ! ! ! 3 * ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! 4 , ( ! ! ! ! ! ! ! ! ! ! ! ! ! ! D OP LP er , PBCM ! ! ! ! ! ! ! ! ! D OP LP er , PBCF1 FPBCF2 FPBCTF &, * ( ! ! ! ! ! ! ! 6 ' ' ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! % % % ! ! ! ! ! !: !1 ! !% ! ! ! ! ! ! ! : ! 1 ! ! % ! ! ! ! ! 3 $2J ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! . 4 ( (P BCF 2 ) ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! . 4 ( (P BCF 2 ) ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! 3 ' ' 7* ( 8 (P BCF 2 ) ! ! 3 ' ' 7 ( 8 (P BCF 2 ) 6 ( 7α = 18 ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! 6 ( 7α = 0.88 ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! 6 ( 7α = 18 ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! 6 ( 7α = 0.88 ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! 6 ( 7α = 18 ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! 6 ( 7α = 0.88 ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! J < ! ! ! ! ! ! ! ! ! ! ! ! 7 2J8 ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! 3 * ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! . 4 ( , ! ! ! ! ! ! ! ! ! ! ! ! ! A ( P BCAL 7 8 ! ! ! ! ! ! ! ! ! ! ! ! ! ! J < ! ! ! ! ! ! ! ! ! ! ! ! - 7 * 8 ! ! ! ! ! ! ! 3 * ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! . 4 ( , ! ! ! ! ! ! ! ! ! ! ! ! ! J < ! ! ! ! ! ! ! ! ! ! ! ! 3 * ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! . 4 ( , ! ! ! ! ! ! ! ! ! ! ! ! ! A ( 7 M.8 ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! 1 1 % % % : : : 1 ! ! ! ! ! !: '' ! ! ! ! ! 3 * '' 7'' 8 ! 3 4 2. ! ! ! ! & 3.N 4 2.7 D 3 ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! & 3.N 7 8 ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! % % ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! 8 ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! tel-00245958, version 1 - 7 Feb 2008 * * F 4 4 4 @ $ ! ' # $ # 5 (! ( * F ( , ' *$ , B @ ' ! 4 F ' ' ! 3 @ @ 4 ! " B (' 4 , 4 $ 7 , F () ' * 8 ' @ ! @ ) * , 4$ / , F F ! < ( '' '' ! , '' @ '' * '' B 4 , 4 ! " ( ' # O ! " # +, @ ! " ! 3 , ' ' @ @ * ( * ' ! 5 F ' +, 7 # * 8 F 4 , F ! @ ( O ! " ( ( @ * P( # @ @ ! ( @ , , * # (' $ * P( ! " $ 7 8 # '$ 7 # 8 @ 4$ tel-00245958, version 1 - 7 Feb 2008 7OF 8 ( O ! 3 7 ( 8 @ ! 3 @ # '' * ' 7 8! 3 ' , ! 9# @ F '' * 5 '' ! " 7 4 8F # $ F ! F ( O $ ! 3 (' '' ! 9 F , OF $ ! < @ $ * B ! " , * ( / " ( # ' F * @ ( ! , ! #F # ( ' ! 3 # # ( @ ! 3 ! " , ( F @ , , @ * ! N , $ 7 8 ! 3 @ ! 3 @ '' 7( O 8 4 4 * 7# @ 8 * '' 7# 8! 9# ' , , F ' ' ' OF 7' ' 8! " 4$ (' ' ' Q # $ @ , R ' R $ ! #F , $ , ! " ( @ 4 ( @ , ,! " ' @ (* ! " , @ B ( 4 ( @ tel-00245958, version 1 - 7 Feb 2008 ! 9# F $ 4 ! * 4 F $ B ' ' ! , * 4 # $ 4 ( 4 @ 5 / $ F ' F F (' F !!! " * ( @ 4 ( $ , / ' ' F # * ! 3 , F ' , ' ' 4$ ( ! 5 F 4 $ < 5 ! , 5 ' ' '! " $ 7' ' $OF 8 5 7' $ ' 8! , * , # , ' ' ! . , , F , ! , F , , ' ' S , # @ 7 8! , * ' # ( ! J F * ( , ' 7 8! $ ! , F , , $ ! " , 5 F '' ! , , * # 4 , $ ! F , $ (' # '' ! tel-00245958, version 1 - 7 Feb 2008 : tel-00245958, version 1 - 7 Feb 2008 3 @ 'F # ( # ! 3 * 4 4 ! ", ( ( * @ @ @ , , @ ! . # * @ ! F ( F F , # $ ' ! 3 # * # ' ! F @ $ ! = # * ( * ! " * * , ( , # 4 ! 3 @ ( * ( ! 3 ( ' '' - . ! #F # , ! F 4 ( * ( ! 1 ' , ' ! ! "! ! #"$ '( * * F ' ! . # ! 9 # , # , / . ! , # R R ! = * * F * F ' F ! . # < ! tel-00245958, version 1 - 7 Feb 2008 ?6 " # 3" = " -? E0 F %G! T F . < # ? 3 $ 3 $ ? E- F G! @ 4 ! N , 4 4 U +, 5 7 F F 4 F ,F. . .8! EH F G ( #' ! / Stocks Magasins Commande client O.F. Achats Bureau Méthodes Boîte noire = Système de production de l’entreprise Livraison Facturation Production Ordo-lancement Bureau d’études ! V 4 , ' F < # * 4 ! !%!&# % . F ' . ( E' . (F :G # 4 F ' *@ 4 ! N F (F ( F 4 F 4 F # F F F * ,! * F $ ! E;' F %%G S E $0 F G / V * ! tel-00245958, version 1 - 7 Feb 2008 V 3 ! V @ 4 < $ E; ,F %%:G $ * ' 4 F @ F * $ * F @ 4 $ 4 F 4 $ ! Système de décision Système d’information Réception de matières et composants Système physique de production Expédition de produits ! V D ( * E9 $; F G " #* # ! N # ' * $ @ ! ' 4 F ( , ( ' * ! , ' E6,F %%1G S E (F %%GF ' 4$ ' # * ! ! "! ! #"$ 4 * ! . # * # $ ' E03 ( J F G! E3 !F :GF # 4 / 7 8 * 4 * S 7 8 ' +, S 7 8 ! • %. 8 #9!#%#$# tel-00245958, version 1 - 7 Feb 2008 " 5 ! " * < / V S V S V S V ' ! W @ . ( * F < 4 F * ' ' ' ! 2 7 ! 8 / # ( #0 #%#8 . #%#8 0 0( . 9 9 ! V , # A K6 E3 !F :G • %. 8 . :+ % ' ' F ( * , ! 3 ' # ' EH F %1GF E3( - 4F %% G E3 !F :G! V * * 4 ! " ' F * +, ! $ F ( @ 4 * * F 'F ' + , ! ' ' F ' $ * ! . * / ( * F F ' F ! !%!&# V V * * $ 4 , F @ ( @ ' ! F ( ' , S $ #* @ F * ' + , ! " * ! 4 # * U 4 ) ! " $ ' #* ! F 4Q 4 ! 9 F ' < , F # ! , $ ,F 4 F F ! tel-00245958, version 1 - 7 Feb 2008 • %. 8 %& 8 @ ! V V ' , / X . & ( , Q * # 4 ! F ( , X ! . ' XF , E- F G S 7 8 # < S 7 8 (* < B $ ! * F 'F ' X * 5 # ! $ * '' $ 4 ! 2 74 8 X # ! 3 4 XF @ XF 4 # ! N $ * ' * F * ' F , E;X !F G! = $ * * * * F * E I XF :GF E I XF 1 GF ' E& !F :GF $ EY' " F 1G R( '( (R E I XF 1G! , ' @ EC F G! V J F , , F X @ 7 E& !F GF E !F G8! ! ! "! ! #"$ * @ ! ( @ 4 ! "# #$ " % 7 , ( F $ 4 # 8 , 8! . ) ' @ tel-00245958, version 1 - 7 Feb 2008 ););1;) , ( 4 7 > R( ' * R! #< # () ' * $ ! '( ! . 7 E" !F %%GF E6 $JO !F G8F () ' $ * @ * 4 $ F 4 # F # ! . E& !F %%%GF () ' * # $4 ! . F E0 O !F G # * F E0( !F G! Fournisseur Client Producteur Stockage Stockage Assembleur Stockage Client Producteur Distributeur Stockage Stockage Fournisseur ););1;- ! V 6 () ' * E" Client !F %%G :+ = .& 3 $'( , E0 F G E- F G! " @ < () ' * @2 " @2 3 @2 ! V @2 < +, ! 3 +, / 4 F !%!&# tel-00245958, version 1 - 7 Feb 2008 F $ F $ ! @2 3 V K4 ! 3 +, < +, +, ! @ F 4 (' , , () ' * ! " +, F , F @ 4 F * +, , @ 4 ! " +, 4 < , , ! V @2 ' ' # 7$ F F !8 4 ! ! ););1;* %& = .& B # 5 () ' * + , $ ! E-F 1G * () ' * * ' E;' !F G! " #' ! * / F ' F * F 3 ' ! Entreprise Fournisseur Entreprise Grossiste Détaillant Sous-traitant Grossiste Détaillant Dyadique Détaillant Fournisseur Divergente Grossiste Donneur d’Ordre Fournisseur Fournisseur Détaillant Fournisseur Fournisseur Fournisseur Client Fournisseur Fournisseur Entreprise Série Convergente Fournisseur Fournisseur Entreprise Grossiste Détaillant Grossiste Détaillant Détaillant Réseau ! V 5 () ' * " @ 4 ! " ' 4F , F ! " - ' * ( , 4 < ! " ' ' () ' $ * , ! #F < $ ! ! "! ! #"$ () @ , ' F K4 K$ ! ! " # $ % tel-00245958, version 1 - 7 Feb 2008 @ EH !F G * E- F G # ' . 4 ( ( ' B $ ! ' () ' * F # ' ) +, 7 8 +, 7 8 4 ' ! " @ @ # 4 * @ *@ ! 3 ( F * ' F 4 4 @ +,F +, F +, F +, F +, ' * ! " +, F F F B ! = * '( ! ! $ * ! * F $ 4 $ 4 ' * , * $ 74! #' !8 / V - * V - K * 7 @ 4 $# V V * X' 7# $# 8 4 *! - * 7 8 ' 8 ! * Q ( ! - ' ,F * ' @ 4 ( * * 4 ! ' ! ( ) ! *! Fournisseurs Client Gestion des données Gestion des données commerciales Gestion des données du travail Suivi de fabrication tel-00245958, version 1 - 7 Feb 2008 Stocks Gestion des matières Système physique de fabrication ! V D * ' " ' ' # 4 * * F ( * ! * ' ' 4 7!4! !:8! Direction Objectifs stratégiques Commercial Etudes Commandes, offres Nomenclatures, spécifications Appro-Achats Méthodes Consultation, commandes Gammes, implantations Gestion de la Production Personnel Embauche, compétence, formation, motivation Maintenance Maintenance des moyens Informatique Fabrication Traitement de l’information Fabrication des produits Contrôle de gestion Magasins Suivi des coûts Matières premières, composants, produits finis, en-cours Comptabilité Qualité Bilan, comptes des résultats Assurance qualité, contrôles !: V " ' 4 " ' F ( * F # ! 0 F ( ! ! "! ! #"$ : 4 @ F $ 4 @ 4 F * 5 ! 3 * ' ,! "' ' * F , / ' * F * E9 ( F %:GF EH & F %%G! 7 #' !18! tel-00245958, version 1 - 7 Feb 2008 Niveau Stratégique Objectifs de Production Planification Agrégée Niveau Tactique Plan Directeur ou Planification Détaillée Ordonnancement Prévisionnel Niveau Opérationnel Ordonnancement Temps Réel Système Physique Décision Remise en cause de Information V !1 V 3 # ( ( * E (F %%G - ' ( 4 * @ ' 7 @ , F '8 # F ( * F 4 ( * * ! , , / F * * 4F ( , ' F ! tel-00245958, version 1 - 7 Feb 2008 ' ! ( ) ! *! V V 1 ' ( $ ' * 4Q @ B ! 3 , ' ! . , F * @ '' 4 4 4 $ $ ! @ @ $ F K > ' ) , ! " ! " @ > # F F * #, F * '' $ 4 ! " * / F ' X' F ! 4( 5 , F F < T ( ( ! 3(* 4 * F * 4 , @ ( E( & F %G! " ( O 5 F @ ( ( * F ' ! . ( O 'F * * E- F G! & @ 4 4 7 $I8! F 4 < # $ ! & % A * 7 ' * F * F $ 8F ' ' ( , R RF [email protected]$ ( F * 4 * F F R R * ! " ( , ' 5 / ( F F F * F ! F 4 @ ,$ R R W ! . EH !F G ( 4Q 7#' !8 / V , 4 * @ ( O / P roduit × T empsF * (P × T ) S V # ! 768 @ 7 F * 8F , 5 4 ' ( S ! ! "! ! #"$ V ( * $ / Ressource × T emps/P roduit((R × T )/P )! 3 4 F # % / V % ! / 7. K76 , & 8 (P/(R × T )) S < , ' - S V 5< # ! / , F $ * F ( S V T )! . ( O / Ressource×T emps(R× R (R x T) / P tel-00245958, version 1 - 7 Feb 2008 Gammes Données Ressources P xT Modif. Décisions de production Demande Plan de Charge P : Produit R : Ressource T : Temps ! V 0 ' * Plan de Production RxT P / (R x T) ' EH !F G & ' % ? - " - #" - " 2 ? E* " OF %%%G! '#% # );*;);) #< 9 # 4 * 7? - ?F ' 8! E3I !F %:1G , * ( , * < , ! " * 3I , / ! α * '' , P( 9 F H! + ,# % ! β * '' , P( H F ! α 4 @ β 7* 8 ?" )? 9! ! " @ * * P( F ' $ ! # ? ? ! #< ) E6 M( F %G ?/ 3 $ - $ " 3 2 ?! #< - E3 3( F %G tel-00245958, version 1 - 7 Feb 2008 ?/ " - 2 2 A 2 2 ?! #< * E F %%G ?6 A ! / A " - 2 2 ?! #< 1 E* " OF %%%G ? $ - A " " :". . . ?! # , F , EHX F %1GF EHO I O !F %%G EHX F %%G! " * T 4 ! " 4 , ' 5 / F F F 4 * F . . . = * , ! , ( ( F , / V % >? ' (' ( +, 7 8 $ 7 8 4 7' 8F F W 7 48! V %@ ' @ P( , 4 #,! V ' * ' 5 , ( F * , ! ' F [email protected]$ #' 5 * ! , 4Q @ 4 $ # ( * * ! ! "! ! #"$ 9# , ' @ ' / OFi / A / NOPi / ' 4 72J8 ! 2 J ! 2 J ! 5 ! / # %# pij - ' # 4 ! tel-00245958, version 1 - 7 Feb 2008 $ %# rdi ' * , ! T @ * - ' # sdi , ! ! * 8 ' @ * cdi ' # 5 @ * ddi < # ! < 4 ' Li = Ci − di ! Ti * ' Ti = max(0, Ci − di )! ! .#& Li ! $ );*;);- A ' U = %8 i U Ui = 0 Ti = 0F Ui = 1 ! " 4 7* 4 * 48! "* ( $ ( 7 X F F. . .8F 4 < $ ( * ' ( ! " ! 4* ! , ' 4 F !! F , F # F ! 4 4 / R, R * , 4 F R R * 4 R R * 4 ! + ,# ' R R & (' Z (' 4 $ F & 7+I 8 wi seti Oi F =C −r Wi = Ci − ri − m pij j=1 Ei = max(0, di − Ci ) Cti Uit Uie tel-00245958, version 1 - 7 Feb 2008 & 7I ' 8 9 @ # ( 7 8 3W # @ Ci Z (Ci ≥ di ) F Z (Ci ≤ di ) F 5+ Cmax = max Ci C= 1 N OF ' Lmax = max Li L= 1 N OF 6 Tmax = max Ti T = 1 N OF 9 Emax = max Ei E= 1 N OF Fmax = max Fi F = 1 N OF J i=1,N OF i=1,N OF i=1,N OF i=1,N OF i=1,N OF . setmax = max seti set = 1 N OF 3W Ctmax = max Cti Ct = 1 N OF Wmax = max Wi W = 1 N OF U= 1 N OF & i=1,N OF i=1,N OF i=1,N OF = = ' = (' $ N OF i=1 N OF i=1 N OF i=1 N OF i=1 N OF i=1 N OF i=1 N OF i=1 N OF i=1 N OF i=1 N OF i=1 Ci Cw = Li Lw = Ti Tw = Ei Ew = Fi Fw = seti setw = Cti Ctw = Wi Ww = Uit Uw = (Uit + Uie ) N OF O=( i=1 Oi ) ! V 3 4 E-' F G N OF i=1 ## N OF i=1 N OF i=1 N OF i=1 N OF i=1 N OF i=1 N OF i=1 N OF i=1 N OF i=1 N OF i=1 wi Ci wi L i wi Ti wi Ei wi Fi wi seti wi Cti wi W i wi Uit (Uit + Uie ) N OF Ow = ( i=1 wi O i ) ! ! "! ! #"$ );*;);* B# 'F < * ' / * * F 3F 3 ! * # ( ' E9F G! tel-00245958, version 1 - 7 Feb 2008 $ - B ? = - B - ; B?! ? = B B?! ? ?! " #' !% # , P( / F F F ! " / [[ [! Consommation ressource k Capacité ressource k 1 2 Consommation ressource k 4 Capacité ressource k 5 3 1 2 temps a) semi-actif 5 4 3 b) actif temps Consommation ressource k Capacité ressource k 3 1 2 5 4 temps c) sans délai );*;);1 !% V 3 !%# % . ( " 4 @ $ ' - 7 ( @ ; "! - F : $ % %8! " #' ! ! 3 ' F ! " ' @ ! F $ F (* F $ 7 8 4 7 8! 3 $ + ,# tel-00245958, version 1 - 7 Feb 2008 * * ! F < 7 < 8 ! 2 < # , R( R! ! V 6 ' - 3 4 ! ( F F ( ! 0( F , B () $ F $ ! % '# # ## # #% , , ( ( ( * ! @ * * ' ( * @ ' $ ! 3 @ , / 4 * ' 4 4 * F @ 4 $ ( ( * ! 3 4 $ ! 3 ( * ( * , ' < 4 $ ! * * ( ! N ( * ' ' , ! '( , $ ' ( * F ! 3 , * F ..! = ! ! "! ! #"$ * $ F F < EH !F G! );*;-;) 5# % = 4 E9 O$DF %%G 4 EHF %1G * $ P( C ∈ Cm * E F GF EH !F G! N C P( * P( C , * F * $ C * ! tel-00245958, version 1 - 7 Feb 2008 ' / / P( ! / / P( / B ' xij pij E Si M P( P( #! P( ! ! ! 7 ! 8 minSn+1 / xij = 1 Sj − Si ≥ −M + (pi + M )xij xij ≥ 1 ∀ij ∈ E i, j = 0, . . . , n + 1 7 !8 ∀C ∈ CC 7 !8 i, j = 0, . . . , n + 1 7 !8 7 !8 (i,j)∈C 2 xij ∈ {0, 1}, xii = 0, Si ≥ 0 " 4 * F , P( (* < , 7 !8! " , 7 !8 ! " 7 !8 , / M B ' 7 , M = T 8F * F xij = 1F , P( j i! 9 F xij = 0F Sj − Si (Sj − Si ≥ −M )! 3 4 , 7 !8 Cm * ! F R' 0R 7 !8 5 , ' ! );*;-;- 5# % >< ##? " 4 @ 4 R# R ( O T ! , * * F + ,# ' ' ' ! " 63. . ' @ . X ! E. X !F %:%G! D / yit = 1 ! " P( @ P( i @ t i −1 t At = {i =1, . . . , n| t+p yis = 1} F * s=t i∈At rik ≤ Rk 7∀t = 0, . . . , T, k = 1, . . . , m8 ' 7 !%8! " 7 !8 $ 7 !18 4 7 !:8 T , Si t=0 yit ! min T t=0 7 !:8 ty(n+1)t / tel-00245958, version 1 - 7 Feb 2008 T yit = 1 i = 0, . . . , n + 1 7 !18 ∀(i, j) ∈ E 7 !8 k = 1, . . . , m, t = 0, . . . , T 7 !%8 t=0 T t(yjt − yit ) ≥ pi t=0 n t rik yiτ ≤ Rk i=1 τ =t−pi +1 yit ∈ {0, 1} i = 0, . . . , n + 1, t = 0, . . . , T 7 ! 8 = , 4 * ! , # @ ' ( * ! E- - ' F G! ' ($ * * , 4$ 4 EH , M F GF EM 3( F GF E I XF GF EHX ; OF :G! . F * ' # $ E3( C F 1G E&' " F 1G! ,( 4 ( * S @ E.( M F :GF , F , F # ( ' ( * E0 O !F :G! ( % , ( * * ' ( * ! 3 '( ( Q F ' ! ! ! "! ! #"$ : );*;*;) .% % # ! tel-00245958, version 1 - 7 Feb 2008 " '( ! , F ( * ! 3 '( * < 7'( 4F. . .8 , ! " ( .6& ( ' ! 9 F * 7 P( 8 * ! . F ! 2 # (* ! " F $ ( .6& 4 ! - F $ * H< * P( ! . 4 pi @ F $ P( iF μi @ pi @ 7#' ! 8! PI pi ! V " H< " ( .6& 4 / E(pi ) = pi pi + 4μ + pi 6 var(pi ) = pi − pi 6 7 ! 8 2 7 ! 8 2 '( @ (* P( ! < 4Q * F # P( ( * ! * ( F * $ P( * ! 4 $ F * ! E(pi ) ( * l! P i∈l F / + ,# 1 E(pi ) i∈l V / var(P ) = var(pi ) V / E(P ) = i∈l tel-00245958, version 1 - 7 Feb 2008 );*;*;- C& & " # < ' ( * ! < ' ( ! . F , , B @ 7=.$ B 8! , ' ' ( * ! 4 F R R ( ! , ( * * -F ( F ' ( * ( * - ! - P( P( T F P( , ! - P( t @ ! 9 (* F ' ( P( t P( F ! A P( @ tF t ' ! ( - ! N ( * F @ * F @ P( * ' ! " 5 ( ( @ F E.IX X F %11G ' ! $ = ' ' E\ !F %%1G E !F G ' C (! " ! ' 7 $ ( 8 / J F ( * ! N $ ( * 7 ' 8 ! " ( 7 ( & F 6 F. . .8 ' F 5Q , , # ,! ( $ 79' ( - * 8 , * ! ( * , 7 ( $ + 8 F 4 ( ( ' ' F U ( ( $ =.$ B F ( ( * ! . $ ( * ( * F E. F G! < E !F G ( * B ! ! ! "! ! #"$ 1||Lmax 1||Tmax ! !" # $ % & ' pij /wi !# " $ " ()(* " " %)(* + ) ! ! #, " # tel-00245958, version 1 - 7 Feb 2008 );*;*;* . ! V 6' % " ' 7..38 F ' F ! "( ..3 @ # ( * * ! " B ' ' ( $ ' * * ' ! ' B @ @ F ( ( # ' # ! 9 (* > ( ( ( * 7 * $ * 8 #, @ ! 2 * (* * * ! ' ' ( ( 4 * ! • 5# " 4 @ ..3! F EH !F G! • $# > D? . (* Ai F # F S(Ai )F C(Ai )F proc(Ai )F $ , Ai ! 3 ri T di Ai F [ri , di ] 4 < U Ai + ,# % < , ! 9F S(Ai ) C(Ai ) [ri , lsti ] [eeti , di ] F U lsti eeti # T Ai ! " , # 5 # / proc(Ai ) = C(Ai ) − S(Ai )! pi ! proc(Ai )! " #' ! " ' 4 < [ri , di ] ' , ! tel-00245958, version 1 - 7 Feb 2008 ri eeti di pi lsti ! V EH !F G • ! % " , # ! . , F , Ai Aj / C(Ai ) ≤ S(Ai ) • 7 ! 8 " 4 * * , ! Ai R Capa(R)F Capa(Ai , R) * * R Ai ! . F E(Ai , t, R) * R Ai @ t! F Q * * B < 5 , ' / E(Ai , R) = E(Ai , t, R) 7 ! 8 t . Ai , 4 E(Ai , t, R) X(Ai , t) 7X(Ai , t) Ai , @ t8 / E(Ai , t, R) = X(Ai , t)Capa(Ai , R) 7 ! 8 ! ! "! ! #"$ 'F n E(Ai , t, R) ≤ Capa(R) / 7 ! :8 i=1 9 F EH !F G # S(Ai ) C(Ai ) @ (* Ai ! ( ) %* + ! " , " tel-00245958, version 1 - 7 Feb 2008 ! ) * " ' , ' ! 0< @ 4 F , $ / ! " 4* @ ' ( * ' ! . , F ( ' ( * 7 O '$M4 F H F , '$ ' F !8 ( * '' $'' ( * EJ !F %%1G! N ( , ( ( * ' U @ , 4 74! #' ! 8! 9 ( ( F $ ' 7'' 8F F ( O '! F F ( O ! , F '' '' * ' > , , $ @ ( * ! ' * - - * - - ! ' , ' ( ) ( . .- (..! " , , EH ;,F %11GF E;, - F %1G EH !F % G! Niveau Supérieur Décisions Etat Niveau Inférieur ! V ( ( E ( I F %%%G - ! #"$ ! ( . (! tel-00245958, version 1 - 7 Feb 2008 " ' ( ( ( * , ' ! E9 ( F %:G F F ( ( ( $ ' @ , 7 ' * F * 8 5 $ F * # 4$ ! F ( ' , 4 ( ( $ 4 E !F % GF E ( I F %%GF E ( I F %%%GF E ( I F G! " * $ EHI C F %%GF E]O !F %%1GF E3I 'F GF E= ( !F GF ( E3 OF %%GF * E9, C^F %GF E]O !F %%GF $ ( * EA H(F %%1GF EA !F GF ( $ * EY F %%:GF E-_ ( F %:GF E]O \O'QF %%%GF ' E; !F 1G 5 E-I !F G E- 3( F GF EC !F G! " ( ( , 5 $ ,F @ 4 ! " 7 '' 8 @ ( $ + F ( @ F ( ( , ( O ! #F , F @ ( F , @ E I XF GF E0 J F GF EJ !F %%1G J ! EJ !F G! ! ( # " '' ' # 4 * * $ < '' EJ !F %%1G! ' F '' F F F ! 5 '$ ' F # ! );1;-;) .#. % 3 '' ' @ ' 5 * * ' F 4 4 ( ! " ' < '' 74! #' ! 8! ! ! "! ! #"$ Produit A Produit A Produit A Produit B Produit B Produit B Option 1 Option 2 Option 3 Option 1 Option 2 Option 3 Entités Détaillées Entités Agrégées Produit A );1;-;- Produit B ! V 9'' 7 8 .#. $ tel-00245958, version 1 - 7 Feb 2008 "'' @ 5 P( $ F $ P( 74! #' ! 8! Entités Détaillées Tâche a2 Tâche a1 Entités Agrégées Macro-tâche A );1;-;* Tâche a3 .#. ! V 9'' % "'' ' 74! #' $ ! :8! Période élémentaire Entités Détaillées 1l … 1W Entités Agrégées l … 1k tl … t W … tk Tl … T W … Tk t T Macro-période ! : V 9'' - ! #"$ ! ( . (! ! +# ,#- . ' tel-00245958, version 1 - 7 Feb 2008 "* ' @ , 7(* ' ' 5 ' 8 B 4 $ ! 5 F ' U , 4 , , ' * * 4 @ 4 ! . F ( $ ( ,! E( !F %G * 4 4 , 4 * / 8 " , 4 F 8 & 4 4 ! 3 E0 # , ' * ,! J F G , # / F 7 ? - - 2 ?! 7 ? - - ?! " > , @ 4 ! 3 ' @ $ '' 7 '' $ ''! " 8F '' $'' , ( ! 3 $ F 4 ( * 4 F 4 7#' ! 18! 3 * * * @ , $ ( @ $ ! EJ !F %%G 'P @ * '' ! EO $. " F G ( # ' * * ! " $ ' $ @ EJ !F G @ , ,! ! ! "! ! #"$ R O B U S T E S S E Modèle Agrégé + Conditions de Robustesse Décisions agrégées robustes Modèle de Désagrégation + Conditions de Cohérence Décisions détaillées cohérentes tel-00245958, version 1 - 7 Feb 2008 ! 1 V 6 ( E0 C O H E R E N C E J F G "* @ , , 5 7 @ F @ 8F < $ * ! , F ( 4 ' 4 EJ F %GF E" F %%G! 5 # ! , E- !F 1G , F @ * ! - .% / ) %* + '( * $ , * * * , ( ( ! " , ( ( > ' / . " + - / ! / )## # # " , , . # ; ( . 7 ;.. ( . .- ' 8! , $ # , U (* $ '' 7 !'! EH ;,F %11GF E( !F %GF EJ !F %%G8! "'' * ' / ' " 4 + 7 !'! #' ! 8! #' ' $ F ( $ ! ' , $ @ , ,F , E-4 `a4 F %%G $ / !!0 ! ! #"$ tel-00245958, version 1 - 7 Feb 2008 A B C Groupes de Produits a b c Familles de Produits D E J Items de Produits ! V '' E ( I F %%%G # ' 4$ 4 ! . , , E& !F GF E9( F GF E\ !F GF E QX !F :G * $ , 4 ! E0 ( !F %%:GF < [email protected] , ,8 F '' 4 F ( ! = ' @ ,! E6 F %%G ( ( * '' E3 OF %%G ( ! / + # # ## # " , ' 4 # $ < ! , $ , 4 (' 4 5 ' $ ! E\ !F G @ , , U ' ' ( * * 4 @ ' ( ! = ' @ , EHI C F %%GF E !F G! 9 EHI C F %%G @ , ! " * @ F 4 5 , ' # 4 ( ( P( ! . E2 & F 1G @ , U 4 F , @ * @ 4 ! " , ! ! "! ! #"$ : # ( ( ! " ! 2 > E !F GF # , 7 !'! E6 !F :GF EJ !F :G8! tel-00245958, version 1 - 7 Feb 2008 / 0 # # $ ( ( ! F '' ! F ( ( 4 * EM4 3( F %%G! $ ( ( E( F %%:G! ' '' $ , 4 * E&X !F %%:GF EJ !F GF E I XF :G 4* , 4 + , E9 !F %%GF E&' !F %%%G! ( ! 0 '123 % ) • ( , ' @ ! " @ 3 @ ! ' * F F * 4 F ! " ( O @ * ' 7 8 5 / 3 $ V ' V ' V / 5 F ( F ( $ F . . . V , / $ F F . . . V ' # / ' F ' # F ' F . . . @ 5 ' F @ ( * 7 8 *@ @ * 7 @ # +,8! 1 ,234 &! 1 ( * F @ 4 ( ( 7 8 $ ! • 9 F @ 2 2! " 4 @ ( O F ! ( 2J 4 @ ! ' $ 7 8 ! " $ # $ F ' F. . . , tel-00245958, version 1 - 7 Feb 2008 " 3 (' # ! . F / V # R' R F V R# R F * $ ! " 4 (' F * O < @ 4 ( ! F $ < ! "($ 3 F $ / , , 5 ,F @ $ , F @ , , - -F @ * ( 2 @ 3 ! • " 2 ' F @ * ' ! # ' '' * b , ! 4 - -! N , ( ! " @ 4 ( ! 4 ! # , * 3 ,! * @ ( * ! ! "! ! #"$ tel-00245958, version 1 - 7 Feb 2008 F $ F ' ' F. . . 3 ( ' , + ' F , 7(' F 4 F. . .8 * ! " ( ( / $ ( ' ' F F 7 # $ 8! ' 5 4 @ ( ! ( * , $ " ! , 5 '' 5 $ ! , ' ! 3 ( 4 # * * ! " # # F U '' * F $ ! = , ' ' 5 , ! 3 ( , 2 ! 3 ( ' 5 ( * $ ! " < - * ! * ( , $ , * , ' ! 3 ! #F 4 ' ( F , ' ( ! tel-00245958, version 1 - 7 Feb 2008 J , # * 4 7 F F F!!8 F $ , 4 7 , F () ' * 8! 4 F ' 4 ! @ ) * , 4$ / , F F ! > ( , '' '' ! , '' @ '' * '' B 4 , 4 ! " ( , 4 4 , * , 4 * ! . 5 '' $ '' F * , ! 3 ( * / V F ' * * * @ , , @ * ! V , F $ ! " 4$ @ ' , F * , ( 4 , 5 ! V " F @ 4 * ( @ , , / '' ! = , * '' * ! " $ 4 @ '' ' ! . F # ! # % ' #"$ *! 5 ## '' @ '' ! V " * ' ' $ ' 2JF # 0$ ! N , ( # ! V J F * > $ , '' ' ' ( ! N < , # < # ! tel-00245958, version 1 - 7 Feb 2008 " % 1% 4 % %% = * ( * ! F 4 , 5 , # T (* ! # '#% = @ U < ' , W ! , F * 4 72J8! N T F @ F # ( 7 8 @ (* 2J! 3 # 4 < 2J! N 2J 72.8 () # ' ! " ' ! ! " S 7 8! . ' , F # @ 5 ! 9 F 2J < 4 * $ (' ! ' @ ( ! < ' * ' # @ ( 2JF @ ' F ! " 4 5 7W 8 * ! " 4 # * ' 7 F $ F F , ( 8 4 , * ' $ ( ! tel-00245958, version 1 - 7 Feb 2008 ' (! 2#6 ! ! F (' * 7' F 8 7 F #8! ' ) 5 7 ' (' F ' $ ( F 8! 9 F 5 ' ! 0( F ' , * @ (' $ ' ( , ! " , , $ @ ! . F 5 ' * @ 4 ' * ' ! 5 F @ F * > $ ' ! ' ' ! " # * 9. 7 .- 8 @ # ' P( * (' $ ! ( F ( @ , , '' @ ( ( ! ( " , , ! " $ ( O F * ' * 7 # 8! " ' ' * , @ ! 3 2J $ ( O ' ! ' * $ F ' ( F F ! # ' * ' ! " @ @ ! R$ R! " $ 4 0 % # / ! " * $ 4 # R' R $ ( $ ! " 4 4 ..F * ! " 4 E R' R # ! 9 F ( ( ( * # ! 3 B $ < > $ 7 ( O 8 < @ * ! 4 @ $ 7* ' $ tel-00245958, version 1 - 7 Feb 2008 ' #"$ *! 5 ## 8 ' ! " 4 ' ' * ! 9 ' ' F ' , + , $ ! " 4 4 F 8 % $ % # .. $ %#! " #' ! 5 ( ! "( @ , , * @ * * F ' ( * * ! # ' 2J ( O $ @ 7 8! "( F ' 4 7 8! " B @ ' ' * 7'( ( ' ' 8! " ' ' R R @ R * R * < ( @ 7 ( , ( * 8 4 @ ' ! DonnéesAgrégées AGREGATION MODULE DE MACRO-ORDONNANCEMENT MacroͲOrdonnancement Tempsdiscrétisé (périodes) GUIDAGE Données détaillées Donnéesissuesdu guidage Temps continu MODULE D’ORDONNANCEMENT désagrégation Ordonnancement Détaillée ! V @ , , * * 4 ( ' @ '' @ '' 7 , ''F + , $ 8! 0 * '' ' (! 2#6 ! ! ' , 4! 9 F 4 ' ( < * , $ E ( I F %%%G! # $ $ EO $. " F G E0 J F G! J F F , ( 4 @ 5 ' $ ! 5 F ' 5 * * S , * 5 ! 1 # tel-00245958, version 1 - 7 Feb 2008 . 4 < > 5 F / V * $ V # 7 @ $ 8 < @ 7 , 8 '' V ' ' 4 V ( ( 4 ! " '( ( ! " ( @ 4 4 ' ( ! 5 F ( , 4 / # R '' R #, ' $ ! ! 2# '# ! • , =2J N OPi =6 • i rdi ddi / 2 J / 2J / , 2J / 2J (i = 1 . . . N OF ) / T 2J i 7rd R R8 / # ( 2J i 7dd R R8 ' #"$ *! 5 ## • , i, j pij mijr / 2J 7 ' 8 / # 2J / # 2J = * * 8 * , 8 7 ( 4 $ * 7 ! " #' ! ! tel-00245958, version 1 - 7 Feb 2008 Durée opératoire pi,j mijrm i, 1 i, j i, NOPi fin souhaité temps de l’OFi début OFi rdi Fenêtre de l’OFi ! V = ddi 2J 5 % * 5 , '( $ ! = 4 ( * ! 0'34 6 * $ # $ 2J 2. ( O ' @ * 4 $ ! " $ * # 4 ' , * , 2J ( O! 9 F ' * 2J # # @ 4 , # T ( ! " 4 $ W 7 4 5 8F W ( O ! ' ' ! " .# 4 * ( 4 R * R W 2JF , ( K @ $ ! ( * * , $ 4 @ * , $! * * * $ * '' @ @ ! " '' * $ R'' R @ '( ! ! 7'( ( 8! tel-00245958, version 1 - 7 Feb 2008 " # # " $ * / " 2 " 2 /4 2 /. 2 C! • T t lg # % / ( O / (t = 1, . . . , T ) / ' 3 $ ' ( O ' $ ' ! . ' F '' > ! " + ( , ( ! • # # + A i N OF N OPi RPi DPi / 2J (i = 1, . . . , N OF ) / 2 J / 2J / %# T 2J 72 '' 8 / %# # ( 2J 72 '$ ' 8 • # # + %# i, j pij mijr / 2J (j = 1, . . . , N OPi ) / 2. # 2J / 2. # 2J : ' #"$ *! 5 ## • # # + / / r t 7 ( ' 8 $ '' / , ( r t NR Capart HrsLM axrt • G # + $ # CtLreti tel-00245958, version 1 - 7 Feb 2008 CtLavai CtLsti CtLhsuprt / W @ 2J @ / W @ 2J @ / W @ $ 2J / W ( @ " ,##' " $ / Xijt Sti Reti Avai HSuprt / 2. # 2J F / 2J $ F / 2J / 2J / ( $ " Xijt Sti ( , @ $ ! Reti Avai 2J @ ! HSuprt @ ( ! ! " # 9 F + F 4 '' * F * 7 4 < F ' F * F !8! " ( * 4 / T Xijt + Sti = 1 t=1 ∀i ∈ 1 . . . N OF ∀j ∈ 1 . . . N OPi 7! 8 ' ' ! " .# t Xijn ≥ n=1 t Xij+1n ∀i ∈ 1 . . . N OF 1 ∀j ∈ 1 . . . N OPi ∀t ∈ T 7!8 n=1 OPi N OF N i=1 mijr × Xijt ≤ Capart + HSuprt ∀r ∈ N R ∀t ∈ T 7!8 j=1 T t × XiN OPi t − DPi (1 − Sti ) = Reti − Avai ∀i ∈ 1 . . . N OF 7!8 t=RPi RP i −1 Xijt = 0 ∀i ∈ 1 . . . N OF ∀j ∈ 1 . . . N OPi 7!8 tel-00245958, version 1 - 7 Feb 2008 t=1 HSuprt ≤ HrsLM axrt N OPi ∀r ∈ N R ∀t ∈ T pij × Xijt ≤ lg ∀i ∈ 1 . . . N OF ∀t ∈ T 7!:8 7!18 j=1 Xijt , Sti ∈ {0, 1} Reti , Avai , HSuprt ≥ 0 ∀i ∈ 1 . . . N OF ∀j ∈ 1 . . . N OPi ∀i ∈ 1 . . . N OF ∀r ∈ N R ∀t ∈ T 7!8 ∀t ∈ T 7!%8 "* 7! 8 * 2J $ ! " 7!8 # () (* 2JF @ ' ! 2 * * < 2J < < ! " () %# ' ''F ! "* 7!8 * ( ! " 7!8 (* 2J ! 3 ' %# * ' 2J @ %# DPi ! " 7!8 2J! 2 T # 7 8! 5 F T (RPi ) * ' 4 F * ! @ F 2J! "* 7!:8 # * ( , ! #F 7!18 # * 2. @ < 2J 5 @ < * ' #"$ *! 5 ## ' ! 4 F < 2J 5 @ < ! 3 * ( ! 3 ' ! 3 F ' lg ( 4 @ F < 5 @ 2J < $ ! 3 * * ' (lg) ' @ ! / " '# tel-00245958, version 1 - 7 Feb 2008 " F 4 4F 5 W F F F F $ ( ! 3 @ ( O! , ( * / min N OF CtLreti × Reti + CtLavai × Avai + CtLsti × Sti i=1 + T NR CtLHsuprt × HSuprt 7! 8 r=1 t=1 3 ( * * ' $ ( O! 3 $ ' 4 ' ' '( ( ! & 5 6 $$ % " '' * $ @ ! 9 4 < < # ( O $ ' * ! 3 # $ , 4 ! 5, # 3 '( '' ( F @ 7 8 ' %#! 3 4 4 4 ' ( ! ' lg ( F t(∀t ∈ [1, T ]) @ [(t − 1) × lg, t × lg)]! . 4 7'' 8 T (rdi ) (ddi ) T (RPi ) (DPi ) * $ F ' + !# 7** # % 4 7! 8 7! 8 ! , 7 #8 ,* ! rdi RPi = +1 lg tel-00245958, version 1 - 7 Feb 2008 DPi = 7! ddi lg 8 7! 8 /x 7 x 8 @ 7 4 8 ,! 9 F '' 4 < , 2J * , # , ! " , 2J ! 4 < , @ (* 2J! " 2J @ F 4 ' S ! * * (* ! ! OFi rdi ) * 1 V J < ddi : PP PP PP PP A P ) * 1 ! V ) 6 6 6 6 - : 6 6 6 6 * : : 6 6 6 6 1 4 6 6 $ :6 $ $ $ 6 * 3 lg = 6! * 4 7! # ! / 8 7! 8F " #' ! 4 < 4 < '' ! ) * '' * @ 4 < , 2J S '' R P( R @ ! " $ * ' ) ! : ' #"$ *! 5 ## OFi RPi DPi ) * 1 ! V J < 1 '' 1 2 2 3 3 tel-00245958, version 1 - 7 Feb 2008 4 rd4=3 rd1= rd2 = rd3=0 4 dd2=21 dd3=10 dd1=12 dd1=26 AGREGATION 1 1 2 2 3 3 4 t=1 RP1= RP2= RP3= RP4=1 Temps (continu) 4 t=3 t=2 DP1= DP3=2 ! V t=5 t=4 DP2=4 DP4=5 périodes 4 < " R # R ( '' @ S # ' < '' 7' ' 8F ' 4 ! + # , # # '( F 5 '' , * $ ! 9# 4 < F ' @ 2J , R # R / # ' (i, 0) # # ' (i, N OPi + 1)! 3 # mi,N OPi +1,r = 0 F ∀iF ∀r8 * , * 7mi,0,r = 0 # ! " @ $ '' ! " 4 , ' + !# 7** # : # / pi,0 = rdi − [(RPi − 1) × lg] 7! 8 pi,N OPi +1 = [(DPi × lg) − ddi ] 7! 8 . , 4 7! 8 7! 8F $ # , ! " #' ! 4 < '' # ! 1 1 2 2 3 3 tel-00245958, version 1 - 7 Feb 2008 4 4 dd3=10 dd1=12 rd4=3 rd1= rd2 = rd3=0 dd2=21 dd1=26 temps continu AGREGATION 1 1 2 2 3 Op. fict ( 2 , NOP2 + 1 ) 3 Op. fict ( 3 , NOP3 + 1 ) 4 4 Op. fict ( 4 , NOP4 + 1 ) Op. fict (4, 0) t=1 t=3 t=2 RP1= RP2 =1 RP3= RP4=1 DP2=4 DP1= DP3=2 ! V OFi ) * 1 OPi H PP PP H0 H0 H0 H0 ! V ) 6 6 6 6 DP4=5 périodes # " ' # '! PP PP P t=5 t=4 !F * - : 6 6 6 6 * : : 6 6 6 6 1 4 7 6 6 -0 :6 H0 *0 $ 6 $ $ $ 10 # 9 '' lg = 6F 2J , ! ! * '' , ! 74 < 8 ! 7' 8! : ' #"$ *! 5 ## " # ' 2J $ < * ! * 7 7!188! " , ' ' '( !! $ * tel-00245958, version 1 - 7 Feb 2008 & # # #, # , " $ , 2J ( O , # T ! " # 4 # #F , 7 , 8! " 4 # ' 2J * # ! 9# ' # 0$ $ '( !! 3 $ ' @ # 7j 0 . . . N OPi + Reti,N OPi +1 # (i, N OPi ) 18! " Reti,N OPi # # (i, N OPi + 1) @ 2J! 3 * 2J # ! T Xijt + Sti = 1 ∀i ∈ 1 . . . N OF ∀j ∈ 0 . . . NOPi + 1 7! 8 t=1 t Xijn ≥ n=1 T Xij+1n ∀i ∈ 1 . . . N OF ∀j ∈ 0 . . . NOPi + 1 ∀t ∈ T 7!8 n=1 OPi N OF N i=1 t mijr × Xijt ≤ Capart + HSuprt ∀r ∈ N R ∀t ∈ T 7!8 j=1 t × Xijt − DPi (1 − Sti ) = t=RPi Reti − Avai RP i −1 Xijt = 0 ∀i ∈ 1 . . . N OF ∀i ∈ 1 . . . N OF ∀j ∈ NOPi , NOPi + 1 7!8 ∀j ∈ 0 . . . NOPi + 1 7!8 ∀r ∈ N R ∀t ∈ T 7!:8 t=1 HSuprt ≤ HrsLM axrt ' + !# 7** # NOP i +1 pij × Xijt ≤ lg : ∀i ∈ 1 . . . N OF ∀t ∈ T 7!18 j=1 Xijt , Sti ∈ {0, 1} Reti , Avai , HSuprt ≥ 0 ∀i ∈ 1 . . . N OF ∀j ∈ 1 . . . N OPi ∀i ∈ 1 . . . N OF ∀r ∈ N R " < # # ! min N OF N OP i +1 ∀t ∈ T 7!8 ∀t ∈ T 7!%8 $ CtLreti × Retij + CtLavai × Avaij + CtLsti × Sti i=1 j=N OPi + NR T CtLHsuprt × HSuprt 7! 8 tel-00245958, version 1 - 7 Feb 2008 r=1 t=1 4 * * 2J i (i, N OPi ) T ! $ # (i, N OPi + 1)! 3 @ # * @ ' ! ( # # ' ## # 3 , * '( F '' @ * * 7 8! 9 F @ < @ ! 9 , F #' ! ! "'' 4 ( ' ! 3 ' Capart * ! 7 !8 $ ! " #' !: '' ' :! (* '' 7* , F , 4 < F , '' F. . .8! $ F < ' ( 4 2J! 3 '' * ' ' 4 (' $ ! 3 < '' ! N ( ( ! : ' #"$ *! 5 ## capacité instantanée 3 2 1 1 2 3 4 5 6 7 ! V 3 8 9 10 11 12 13 14 15 16 17 18 temps continu capacité par période 16 Capa 14 14 tel-00245958, version 1 - 7 Feb 2008 12 10 Capa 10 Capa 7 8 6 4 2 t=1 t=2 !: V 3 ( 5 $ t=3 périodes '' $ 1 9 F $ @ * ! 3 $ < 5 R' R R R 4 ! 3 $ R R , ' ' ! " $ 4 4 7 # # (* 2JF F * F !8! 3 < R' R 4 ! 4 4 '' , F ' ' < '! ' ' * # 2J $ ! . F R' ' R! ! ) # # # # " .. % ' ' @ 4 * ' 2J 7 2J8! B 4 < @ (* * # # 2J @ ' - !# ** 2! ! : ! 4 < ' ' 4 S $ ( ( @ 4 < ! ' ' F 4 4 @ R * R ' * 7 ( 8 b 5 ( 7 F ( * F. . .8! " ( ! ! 6 # # # , tel-00245958, version 1 - 7 Feb 2008 8 4= - - 9 $ F Xijt F i ∈ [1, N OF ]F j ∈ [N OPi ]F t ∈ [1, T ] 4 ! " 4 < 2J # $ # * 2J ! 2 / SPi CPi / * 2J i 7SP / * 2J i 7CP 3 $ R R8! $ R R8! $ SPi = T t × Xi1t / 7! 8 t=1 CPi = T t × Xi,N OPi ,t 7! :8 t=1 " 4 < [SPi , CPi ]! 2J i # . 4 < R' R R R 4 8F * '( !! ! 7 @ # :: ' #"$ *! 5 ## 8 4= ?- ? G ErdG i , ddi G 4 < ' @ (* 2J i * rdG i 2J iF R'' R %# 2J $ 7rdG i R R ' 8! ddG i # 2J '' %# # 2J $ 7ddG i R R ' 8! " #' !1 , 4 < ( ! tel-00245958, version 1 - 7 Feb 2008 Fenêtres agrégées RPi et DPi étape 2 : macroordonnancement # rd iG et dd iG rd i et dd i !1 V = • Fenêtres agrégées optimisées étape 3 : guidage étape 1 : agrégation Fenêtres initiales SPi et CPi @ (* Fenêtres guidantes ( < . ddG i . # ' 2J i @ 4 $ F 4 4 # 74! #' !8 / ddG i = CPi × lg • # 7! 18 # . rdG i " T < R R * # ! 5 # < 7 8 * T < ! 4 * @ #* ' ! " ' 2J i $ * 2JF * $ < ! ' - !# ** 2! ! :1 i, NOPi CPi périodes temps continu dd iG tel-00245958, version 1 - 7 Feb 2008 ! V # ' / V ri1 * (i, 1) 2J V SPi * ! (i, 1) V Oi (k, l) ri $ SPi ! $ = / rdG i = max rdi , pk,l 7! 8 (kl)∈Oi / rdi / T . , F , * #' ! + % '3 2J i * rdi = 3 * (i, 1) * r ! " #' !% $ r ' lg = 10! , F * (k, l)F (m, n)F (p, q) F @ 2J < ! " ' 2J i / rdG i = max(3, 4 + 2 + 2) = 8 : ' #"$ *! 5 ## p ,q r i ,1 m,n k ,l périodes i r rd iG !% V , temps continu 8 rdG i tel-00245958, version 1 - 7 Feb 2008 ! 6 # #, # , 8 4= - - 3 i ∈ [1, N OF ]F # 2 SPif CPi '( j ∈ [N OPi ]F t ∈ [1, T ] 4 ! # 7# 8 2J Xijt F " 4 < 2J * ! / / * $ # 2J i / * $ 7# 8 2J i! 3 $ SPif = T t × Xi0t / 7! %8 t=1 CPif = T t × Xi,N OPi +1,t 7!8 t=1 " 4 < 2J i # [SPif , CPif ] # F [SPi , CPi ] * ! ' - !# ** 2! ! 8 4= ?- ? G ErdG i , ddi G 4 < ' :% @ (* 2J i * rdG i 2J iF R'' R %# 2J i $ ! ddG i # 2J i '' %# # 2J i $ ! • # < . ddG i tel-00245958, version 1 - 7 Feb 2008 . # ' 2J i @ 4 $ F , * ) 4 (i, N OPi ) # # ' (i, N OPi + 1)! # # ' 8 2J i < F # ' 2J i @ # U 74! #' ! 8! # # ' 8 2J i < F # ' 2J #, # # 74! #' ! 8! 3 # # ' # # ' ! ( # 7 8! i, NOPi i, NOPi+1 CPi CPi f dd iG ! V # ' périodes temps continu 1 ' #"$ *! 5 ## i, NOPi i, NOPi+1 CPi CPi f dd iG ! tel-00245958, version 1 - 7 Feb 2008 temps continu V # ' " . périodes ( / < . f CPi = CPi ddG i = CPi × lg ddG i = (CPi × lg) − pi,N OPi +1 A • # # . rdG i " ' < * '( !! 7' ' # 8 4 7! 8! - 5 7* % +% % 89 /*: . 5 ( F $ > , # 7 $ F ( 8! . + < # F , # , # ! " , 4 ! " $ @ ? $0. 4 @ F ' . ! 3 , ( ! " , * C ( * (* 4 (* ( S ' 2J 5 ! " , 2 J 72J8 (! " 4 < 7 #8 (* 2J !! ' / ! 8" ! ! $# !# 9 : ! ! 0"!; 1 " * !:! " (* @ S , Rx @ * ! 2 * (* * S mijr = 1 × pij = pij ! A ) * 1 4 7 , 3 tel-00245958, version 1 - 7 Feb 2008 ! V J < rdi ddi : 1 PP PP PP PP A P ) * 1 4 7 , 3 1 1 : 1 !: V ) 6 6 6 6 6 6 6 6 - : 1 6 6 6 6 6 6 6 6 * 1 6 6 6 6 6 6 6 6 1 1 6 6 6 6 6 6 6 6 4 : 6 6 6 6 6 6 6 6 * , F ( ' lg = 12! " ( O 7 8! t! 2 Capart = 12 r / 1- # # # , 8 - - 3= 4 4 * 7 #8! . F * 4$ 7! 8 7! 8 ( ! " !1 $ # 74 < '' 8 @ (* 2J! " ' !: (' 7 $ # 8! 1 ' #"$ *! 5 ## !1 V J < AI .#.# OFi rdi ddi RPi DPi ) * 1 4 7 , 3 : 1 ) ) ) ) ) ) ) ) * 1 1 1 * * 4 '' 7 lg = 128 3= - - 8 tel-00245958, version 1 - 7 Feb 2008 AI 9 * '' F $ ' ? $ #' ! ! 4,2 3,3 2,3 8,2 1,5 5,5 M1 7,2 6,3 7,1 3,4 1,2 2,4 5,3 8,5 M2 6,5 5,1 3,2 4,4 1,4 7,4 8,4 2,5 M3 6,1 4,5 4,1 2,1 3,5 5,4 1,3 M4 8,1 7,3 3,1 M5 6,4 2,2 4,3 1,1 6,2 1 5,2 8,3 7,5 2 ! 3 4 5 6 V 0$ 7lg = 128 " # ' 4 , # ! " ! # $ ! ' / ! 8" ! ! $# !# 9 : ! ! 0"!; AI AI .#.# AI .#.# % # OFi rdi ddi RPi DPi SPi SPi ) * 1 4 7 , 3 : 1 * ) ) ) ) ) ) 4 1 * 1 7 * * 7 tel-00245958, version 1 - 7 Feb 2008 ! V J < 8 1 '' - " ' ' ' 9 # ' 4 7! 18 # ' '( !! > ! # 7SPi CPi 8 G G # 7rdi ddi 8 7! 8 '( !!! " !%! AI AI .#.# AI .#.# % # OFi rdi ddi RPi DPi SPi CPi ) * 1 4 7 , 3 : 1 : : !% V J < AI . rdG i -H )) H H H H H H ddG i 7H 13 *7 13 ,*7 *7 ,- ' 2 * * 4 < ' 5 4 < ! " ' 2J , ! " # ' ' 5 , # ! " $ + 4 4 < ! 3 W @ 4 , , 7 # @ 2J8 @ ' ( ! 1 ' #"$ *! 5 ## 8 / " # 4 < ' ' . F 7'' 8 #' ! # ! ! M1 tel-00245958, version 1 - 7 Feb 2008 M2 3,3 8,2 7,1 5,1 4,1 3,2 8,1 2 4 6 8 10 12 14 16 5,3 20 2,4 24 ! 26 2,2 28 30 8,5 1,2 8,4 5,4 6,4 7,5 22 6,5 1,5 2,5 3,5 5,2 18 5,5 4,5 2,1 4,3 6,2 2,3 3,4 7,4 7,3 3,1 M5 6,3 4,4 6,1 M3 M4 4,2 7,2 1,3 1,1 32 34 1,4 36 8,3 38 40 42 44 46 48 50 52 54 56 58 60 62 64 66 68 V 2 AI AI .#.# AI .#.# % # OFi rdi ddi RPi DPi SPi CPi ) * 1 4 7 , 3 : 1 : : ! AI . 0 # rdG i sdMN i ddG i V : : 1 : : 1 *)2 H H 7 H H 1 cdMN i 7* 1, -3 -4 1H *, -2 7H 70 72 tel-00245958, version 1 - 7 Feb 2008 ' / ! 8" ! ! $# !# 9 : ! ! 0"!; 1 = * * # 5 ! " # 2J @ # F < 2J :! 3 W , ' $ * ! ' ' 74 < ' 8 * # 7 2J8 , ( # 2J 7 ,! 2J F : 1 < # @ :8! B 5 2J! 3 ) ( @ # ! * F # ' 2J F: F ' O P( , 72J F F : 8! " @ ' # (* 2J , ! . , ( 43 @! / 1- # #, # , 8 - - 3= - 0 < # ( * '( !! ( ! " ! ' #$ 7 ' 8! PP PP P OF ) * 1 4 7 , 3 OP PP PP ! H H H H H H H H H ) 0 0 0 0 0 0 0 0 1 1 : 1 6 6 6 6 6 6 6 6 - : 1 6 6 6 6 6 6 6 6 * 1 6 6 6 6 6 6 6 6 1 1 6 6 6 6 6 6 6 6 4 : 6 6 6 6 6 6 6 6 7 1 0 - 0 * 0 7 0 )) 0 3 0 4 0 , 0 V # 3 * F # 2J @ ! . # # * ! " 5 4 7! 8 7! 8! F 5 $ # 4 " 4 < '' (' @ , # F ! / 1: ' #"$ *! 5 ## tel-00245958, version 1 - 7 Feb 2008 ! 8 AI AI .#.# OFi rdi ddi RPi DPi ) * 1 4 7 , 3 : 1 ) ) ) ) ) ) ) ) * 1 1 1 * * 4 V J < '' 7 lg = 128 3= - - " ? '' #$ $ #' ! ! " 4 < '' $ ! ! 4,2 3,3 8,2 1,5 5,5 5,6 M1 7,2 2,3 6,3 1,6 7,1 1,2 3,4 5,1 M3 2,4 5,3 8,5 6,5 8,6 M2 4,4 3,2 6,1 6,6 (8) 2,5 1,4 2,6 4,5 7,4 4,6 8,4 4,1 2,1 5,4 1,3 6,4 M4 8,1 7,3 3,5 3,6 1,1 3,1 5,2 8,3 6,2 2,2 M5 7,5 7,6 4,3 1 2 ! 3 4 5 V 0$ # 6 ' / ! 8" ! ! $# !# 9 : ! ! 0"!; AI AI .#.# AI .#.# % # OFi rdi ddi RPi DPi SPi SPi ) * 1 4 7 , 3 : 1 ) ) ) ) ) ) 1 1 * 1 4 7 * 4 tel-00245958, version 1 - 7 Feb 2008 ! 8 11 V J < '' - 9 $ #' ! $ ' '( !!! 3 , # F @ $ f # # 7SPi CPif 8 ' # 7rdG ddG $ i i 8 4 7! 8 ' ( # ' '( !!! " ' ! ! AI AI .#.# AI .#.# % # OFi rdi ddi RPi DPi SPi CPi ) * 1 4 7 , 3 : 1 : ! AI . rdG i , )) H H H H H H ddG i 11 17 ** 17H ,*) 7H V J < ' 2 * 4 * 4 < ' 5 4 < ! " ' 2J , ! " # ' ' 5 , # F 5 * , @ , # * 2J 72J F 18! 9 * 4 < ' * # 2J 4 2J F * < # ' ! " # 1 ' #"$ *! 5 ## + 4 # 4 < F * ' ' 7* ( 8! 8 / " # 4 < ' ' . F 7'' 8 #' ! # ! ! tel-00245958, version 1 - 7 Feb 2008 M1 M2 M3 M4 4,2 7,2 7,1 1,2 5,1 6,1 4,1 2 4 6 8 10 14 16 20 7,5 22 5,5 5,3 2,1 5,2 18 2,3 24 ! 26 6,3 2,4 8,5 8,4 1,4 4,5 1,3 4,3 12 3,4 7,4 7,3 1,1 1,5 4,4 3,2 8,1 3,1 M5 3,3 8,2 2,5 5,4 3,5 2,2 28 30 6,5 6,4 8,3 32 34 6,2 36 38 40 42 44 46 48 50 52 54 56 58 60 62 64 66 68 70 72 V 2 = @ * # $ 2J , F 2J :! 0' F 2J F , < 2J * ! * * * 4 ! " 1, @F * ( # 7 8! 9 , > ' ' ! = 4 2J $ ' ! F # $ @ ' ! ' / ! 8" ! ! $# !# 9 : ! ! 0"!; AI AI .#.# AI .#.# % # OFi rdi ddi RPi DPi SPi CPi ) * 1 4 7 , 3 : 1 : tel-00245958, version 1 - 7 Feb 2008 ! % + AI . 0 # rdG i sdMN i 1 ddG i : : 1 : , -1 H H H 1 H 1 1% cdMN i ** 1, *-2 1) 43 -3 4- V % N * # * 4 # #' ! : ! 1! " #' ! : 4 < $ # ! 2 * 2J 4 < 5 , ! " ' ' 4 5 ! " #' ! 1 4 < 7 # 8! @ F ' #' ! " 4 < # ( F 4 2J ! N @ ' * # ! " , * # * '' ! , # ! F # ! J F E; O$ !F 1G! ' #"$ *! 5 ## 1 OF 1 OF 2 OF 3 OF 4 1 1 1 2 2 2 2 3 3 3 3 4 4 4 4 OF 5 5 5 OF 6 6 6 6 7 7 7 OF 7 OF 8 5 5 6 7 8 8 8 8 tel-00245958, version 1 - 7 Feb 2008 1 2 3 4 Macro-ordo sans op. fict. ! 1 1 1 1 2 2 2 OF 2 Dates initiales 2 2 3 2 3 3 3 3 Ordo sans op. fict. 3 4 4 4 4 4 4 5 Ordo avec op. fict. 5 5 OF 5 5 5 5 6 OF 6 6 6 6 6 6 7 OF 7 Périodes 1 1 OF 4 6 Opération fictive : V 4 < $ OF 1 OF 3 5 Macro-ordo avec op. fict. 7 7 7 7 7 8 8 8 OF 8 8 8 8 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32 34 36 38 40 42 44 46 48 50 52 54 56 58 60 62 64 66 68 70 72 temps ! 1 V 4 < ' / ! 8" ! ! $# !# 9 : ! ! 0"!; tel-00245958, version 1 - 7 Feb 2008 ( F @ , , , ! N @ $ @ (' $ F 5 '' ! " ( ( F F ! @ ' N , ! N * F F ( F $ F ! "( , * ''$ 7'' F 8 '' # ! 3 4 * * ! 3 4 4 $ 7 8 4 7 8F 4 # ( 4 ! . $ * ' $ #$ ! " 4 ! J F ' ' F ' ' * # ' 2J ! N , ' > '' ' ' ( ! " , # ! tel-00245958, version 1 - 7 Feb 2008 ' #"$ *! 5 ## ! " # tel-00245958, version 1 - 7 Feb 2008 " ( ( ! ' > , * ! " , 4 < # ' ! ( F ' 4 ( @ , * ! " 4 ( 4 , 4 ( R R > < ! . 4 ( F , $ 4 * * ( 4 ( ( 7 8 * 4 * ' ' ! 5 , ( ! 5 ' 2J * (' $ ! . ' ( $ 4 ( F $ 5 ' ! 3 ( * / V ' , * ( * ! V , # 4 ( ! 3 * 7 8F ' ' 7 ' $ 8 B ' ' 7 ' 8! V F , * * # 7(' F F. . .8! + " 7 V # * ( ! & . 4 , $ %6* % ( > , F $ ( ! , , 5 F * $ ( > 5 ! tel-00245958, version 1 - 7 Feb 2008 ) # ,## " ( @ , 4 ( ! * 4 ! " ( @ ( ( @ , , , ( R R * @ ! . F @ R$ * R 4 F ( ( @ * '( !! 7 @ $ F , ( 8! ' ( * ' $ F @ ! " < ' < ( @ , * 4 4 * 7 , @ ( 8! F , ( 4 ! # ' @ ( ( @ 2J! , F 5 ' ! 3 ' $ * ' * ! ( ( ' @ $ 4 ' * ( @ ! 2 @ 5 '' $ S $ 4 , ! " ' J%05 '( ! N 4 * 7'' 8 F ' ' , 7 ( 8 4 ' ' ! ' ' ' ' @ ! . , F ' . + 7" S ( ' . ' ' ! 4 * * F ( F ( F 7W * 2J! " #' ! ( ( ! ' , $ $ 8 Approche Directe Données Détaillées Minimisation des retards Ordo Preactor Comparaison Approche Multiniveaux tel-00245958, version 1 - 7 Feb 2008 Données Détaillées Données Agrégées Agrégation de données Guidage Optimisation MacroOrdo Suivi du guidage Elaboration du guidage Preactor Xpress-MP ! Ordo V " , ( " 7&) ? 9 ; 2 6 N # 4Q / 9 ! ? $0. ' * ! " B ' ( > ? $0. ! ' # 'P $ ? $0 ! 3 '' ( * F ( '' ( * , * ! " $ ? $0. * * F * F , ! ? $0. ' * / V 0 ( , * * ! V 0 ( ' ! * * V 0 ( H($$HKH($$3 7 * * * 8! ? '( * ' / ? $D! F ' , ! -P @ ? $DF 7$ F F F. . .8 ! 3 * $ ! " + " 7 : ? $0. , .3 ;. . D @ F -(O! tel-00245958, version 1 - 7 Feb 2008 )# . R&( 30 3 " RF @ 3( (F 6 N ! . 4 '( * * ' * ! " 4 . Q 4Q @ * ' ' 4 ! " ' '! " (* B( @ ! " $ @ # 4 T R R! B( F 5 $ @ 7. # * ( ( ' () 8! " #' ! B(' ! ! V 4 '( * . . ' ! . , ( 5 / R9' ( * 'R R $H * 'R! + 7" ? . 1 &. F . 2J $ 7 8! & 2J $ ' @ 2J ! " 4 ' $! # . . 8 / . 7 4 8 7 8 ( R. R 7 ! ! F 8! " ( (* 2J < ' ! tel-00245958, version 1 - 7 Feb 2008 . 8 0 / . ( R R @ (* 4 ! . - 4!+!4!/! / . * #( ! !. / . *B / 4 ' % K * (* # ' 7R * R8! / . * / 4 ' % * (* @ 7R$ * R8! ) / D / $ * $ # @ @ # ! ? 06 &. >$ ? , F # @ (* S < * * 4 ,* ! " ' * ! 3(* 4 * 7 8F * , # F # ' # (' ( ! 3 *@ * ! + " 7 " ' . 9. / . - . / * F ' # * < ' * # ! .3 . tel-00245958, version 1 - 7 Feb 2008 / ' 4 @ ' ." R4 < ( ( R 7"X ( I I8! 3 4 < # * < # #* ! A F ' 4 < ( ( @ ! N < # * @ @ 4 < ! F # @ ! " $ < * ! 3 ' # ! ' * ' ( ! " ' P( @ / V . 7 '8 V . 7 '8 '' V . 7 ' 8 V . 7 ' 8 * V . ' 7 8 * / * (i, j) (i, j) ' 5 4 ! "* ( F ' # * ' * # * < ! . F ( ' R. 4 * R R * R! 5 ' 2J @ F * $ 7 ( 8 ' ' 7( @ ,8! 3 ( , ( 4 ( ! & 3 9# 4 F 5 4 ! * # R * ' ( R * R R R B R $ ! 3 ( ( @ , + ' ! 4# ( O! % ( @ , , 5 # # # 8 # # 9 - ,#"( @ , , @ ( F * # $ @ (* 2J! " #' ! ( ! Fenêtres agrégées RPi et DPi étape 2 : macroordonnancement tel-00245958, version 1 - 7 Feb 2008 étape 1 : agrégation Fenêtres initiales rd i et dd i SPi et CPi Fenêtres agrégées optimisées étape 3 : guidage rd iG et dd iG Fenêtres guidantes étape 4 : ordonnancement détaillé et suivi du guidage sd iMN et cd iMN ! V J < , 5 ( 0 9! - -! " T # 4 %# 5 '' $ ! " '' '( ddi * # 4 < 2J T # RPi DPi ! 3 rdi * !! 0 E! % ! " '' $ 5 2J @ ( O # ! 5 ' '' < @ $ # SPi CPi , 5 2J! 0 F! ' -! " $ , ' $ ! ' ' F %# # G G 4 # ' rdi ddi 7 ' < ' ' 8! " 5 4 '( !! ! 0 G! / ! F ' # $ ' ' ( ! ' ' , F , + " 7 % ' * @ ! A * ( F * # # 2J ! 3 ( , N N sdM cdM ! i i " '( 4 4 ! , $ 2# # # tel-00245958, version 1 - 7 Feb 2008 "( @ 74! #' !8! 3 * '( ! ! F ' . ! 2 / sdD i . . . D cdi . . . 2J ( ! # 2J ( ! Fenêtres initiales rd i et dd i Ordonnancement détaillé Direct sd iD et cd iD ! V J < @ ( :# # N ' 4 R* R ( @ R* R # ! " R* R 5 # ! 3 * < ( , ( ! = # / MN Q = N OF N max(0, cdM − ddi ) i 7! 8 i=1 * 5 2J ( ! 3 * ( @ , ,! + ' ! 4# D Q = N OF % max(0, cdD i − ddi ) 7!8 i=1 * 5 2J ( ! 3 * ( ! " 4 , * * * ( , ( 7 8! " #' ! ( ( ! étape 2 : macroordonnancement tel-00245958, version 1 - 7 Feb 2008 RPi et DPi étape 3 : guidage étape 1 : agrégation rd iG et dd iG rdi et ddi QD Q MN sd iD et cd iD étape 4 : ordonnancement détaillé et suivi du guidage sd iMN et cd iMN Approche Directe ! V SPi et CPi Approche Multiniveau * ! ' # " * *@ ( S ' ' ' $ ! 7 - - 3 - - 3 - ! * * $ ' @ < 2J * < ! F < 4 F $ ! " , #' , 4 ' * '' 4 ! + " 7 % % / , 2J i j , ( S (i, 1) (i, 2) S (i, 1) * r1 F (i, 2) * r2 ! " (j, 1) (j, 2) r2 ! r1 " ' ! " ! " #' !: $ 4 , 2J! " * 5 @ < ! tel-00245958, version 1 - 7 Feb 2008 + r1 i ,1 r2 i ,2 j ,1 j ,2 !: V 0$ 2J 5 F F % F * ! * < 2J 5 @ < F 2J 2J # %F * 4 @ $ ' ! " #' !1 ! * , 4 $ ! r1 i ,1 j ,1 i ,2 r2 !1 V 2 r1 r2 j ,1 j ,2 (i, 1) (j, 1) i ,1 j ,2 ! V 2 i ,2 (j, 1) (i, 1) " #' * F F '' $ ! #$ + ' ! 4# % "* 4 ) F $ ' ! " ' ' ! 2 * ' ' 7 $ ' ' 8 ! " RobG ' ' # ' # 2J # ( ! # , ' F * $ '' 4 ' ' ! " , / tel-00245958, version 1 - 7 Feb 2008 RobG = N OF N max(0, cdM − cdG i i ) 7!8 i=1 " , @ $ F 4 * ' ! 2 * * ' F < 2J < * ! / 1;# # 3 F #* ( R B R $ 4 < 2J ! " $ R B R # ' ' ' 5 2J! G E = N OF F ( ( @ ' # ' $ ! " E G B # max(0, ddG i − ddi ) 7!8 i=1 . , B ' ' , $ '( !! ( ! . F 4 , ! 7 # ddi 8 ! 7 # ' ddG i 8! " ! B F G F E ! " ! * # ' 5 ! 3 # 5 $ ! " * 2J , 7 @ 8 * T * 72J 8! + " 7 % A ) * 1 4 7 , 3 ddG i tel-00245958, version 1 - 7 Feb 2008 ! : : 1 : ddi : 1 max(0, ddG i − ddi ) 1 EG = 98 V 3 B ' ' RPi et DPi étape 2 : macroordonnancement SPi et CPi étape 3 : guidage étape 1 : agrégation EG rdi et ddi QD Q MN sd iD et cd iD rd iG et dd iG étape 4 : ordonnancement détaillé et suivi du guidage sd iMN et cd iMN Approche Directe !% V B Rob G Approche Multiniveau " #' !% 4 < 5 ! B , * ! " ' # 4 74 < F (' 4 F. . .8! 5 P( 7 8F O! 3 @ F * * $ @ ' 4 ( ! '( ! * + , 4 ( ! + + <$ ! && % + 6# 3- tel-00245958, version 1 - 7 Feb 2008 . ( ' 5 ! 3 ' ' '$ * (X 7 9= 38 E X !F %%G! " ' ' 5 F 5 7JI ( C (8 @ < 5 7 X 8 S ' ( 7 8 ! 3 ' 4 ( ! ' #, , μ ! 9 F ' 7* ' ' 8 (* 2J! ( F 2J (! ! 3(* 2J (! "5 , 4( E$G ! 5### 3- . 4 F ! " * @ , / 8 * , * ' ! 8 * ' ( ! ? #& # + # .## % " p 2J! 3 * @ ( ' ( ! p= ij N OF i=1 pij 7!8 N OPi mr F r ! Or = r {(i, j)/mijr = 0}F F + " 7 %: mr = ij∈Or mijr 7!:8 card(Or ) Chr F $ ' * ( O ! ( O @ ' 2J! ( F $ * (* ( O 7 8! " ' ( O / Capar = maxi (ddi × 1) tel-00245958, version 1 - 7 Feb 2008 Chr = ij∈Or mijr 7!18 Capar , < / V ' ' 4 < , 2J! (' ( O @ 4 < ! V #, ( O ! F ( O ( @ , 2J! = ' / N R Ch = * N R r=1 , (' Chr 7!8 NR ! Deni F 2J 4 < ! 3 R R 2J @ R' R 2J 2J! . ( F ! N OPi Deni = j=1 pij f eni 7!%8 + - $#! %!! %1 * f eni 4 < 2J i / f eni = ddi − rdi " 2J , / N OF Den = i=1 Deni 7! 8 N OF " , (' 2J ( ( ! ? #& # / # >. %#? tel-00245958, version 1 - 7 Feb 2008 " OPLPer , () ' ( ! 3 @ ( 7!18 !!! 6 * F ' F < 2J * < ! * ' 4 $ * ' < 2J $ * < ! = , / OP LP er = lg p 7! 8 & * ,$ # , @ ! &( + % F 5 ( ! 3 8 * F B $ ! , 4 5 '' * ' 7 $ ' ' ! )' #, # % N > ( U * ! 3 # 4 5 * ( @ ,! 9# + " 7 % ( , 4 @ F , 5 ' ! " @ '( ! * 7 2JF 2J ( 8! " 5$ * #, @ ! " , ! ' 8 S ! 74 < ! (* 2J! tel-00245958, version 1 - 7 Feb 2008 ) * 1 4 7 , 3 ! V J < PP P OF PP ) * 1 4 7 , 3 OP PP PP ) ! V - ddi : 1 - 6 6 6 6 6 6 6 6 rdi 6 6 6 6 6 6 6 6 * 1 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 7 4 6 6 6 6 6 6 6 6 pij Deni !: ! !% !1 ! !1 !: !1 * 8 , F # * (* F * mijr * * ! F $ ( O! " ! 4 * @ 2JF (' ! Den p Ch !% ! !: ! V 3 * + - $#! %!! %% 3 * O @ 4 4 < , 2J , (' ! ? %% 9 F . ! . F * ( ! " QD * , / QD = 0 ! tel-00245958, version 1 - 7 Feb 2008 ? %% / - $+ % B# # 9 ( F ( @ , , 5 ' @ lg Z F 1F F F :! " ! 4 @ ( ! 6 * QM N * 7 , G 8F Rob ' ' 7 # ' 8 E G B ' ' 7 ' 8! % %% 5$ ! V Q MN QD Rob G EG 1 , 3 )H )7 $ 1 : : $ $ 4 , ( , #F # 4 ( ! 2 * * ( $ 4 lg = 4F lg = 8 lg = 7! . ' 7lg = 4, 8, 168F $ * EG ! 3 4 * $ , '' ' ' R R! . lg = 7F 2J $ ' , 7 B ' ' 8! 5 F (* 1 F * 7 7!18 8! " lg = 10 * ' 7 8 , 7 4 8! 2 * ' * 4 RobG = 0 lg = 4 lg = 7! 3 4 * ' F * 4 ! " + " 7 # lg = 4 tel-00245958, version 1 - 7 Feb 2008 lg = 7! ! 9 '' F ' # * 5 '' F '' 4 ? 0. * $ #' ! ! 2 * $ $ * ' * 4 ( ( ! 9 F # F * * , #$ S 2J @ @ ! N 4 $ F # # 4 ' ' ' ( ! " # 5 ' F ' ' ( # ' 7 8 '( !!! " !: ' ' * 4 ! A ) * 1 4 7 , 3 rdi ddi : 1 !: V rdG i ddG i : max(0, ddG i − ddi ) EG = 0 ' 2 * * ' ' # 4 < * $ B 72J 8! 9 , F 4 < 2J # ! " 4 < 2J 4 # # @ 2J! 3 ' 4 ' . * ! " #' ! . ! 2 * * 4 * @ $ ! 3 ( ' ' ! 5 F ' # * 4 ' * ! " ' , + - $#! %!! ' F @ 4 ! 3 * (* * 4 ' ! J F #' ! ( 4 < 4 $ < F 4 < ' $ 4 < ! M1 M2 7,2 7,1 3,3 4,2 6,3 1,2 3,4 5,3 2,3 1,5 6,5 5,5 8,2 4,4 2,4 8,5 8,6 5,6 M3 6,1 3,2 5,1 M4 2,1 4,1 7,3 1,4 7,4 3,5 6,4 4,5 2,5 8,4 tel-00245958, version 1 - 7 Feb 2008 4,6 1,3 8,1 7,6 3,6 M5 3,1 1,1 6,2 1 2 3 5,2 2,2 4 5 6 ! M1 7,2 3,3 6,3 4,2 1,2 3,4 5,3 7,5 4,3 7 8 2,3 8,2 5,5 6,5 4,4 2,4 M3 6,1 3,2 5,1 7,4 1,4 M4 2,1 4,1 7,3 1,3 3,5 6,4 8,1 M5 3,1 1,1 6,2 5,2 2,2 4,3 7,5 ! 6 8 10 12 14 16 18 9 1,5 7,1 4 8,3 10 13 12 14 15 16 17 18 19 8,5 4,5 20 11 V 0$ lg = 4 M2 2 2,6 5,4 22 24 26 8,4 2,5 5,4 8,3 28 30 32 34 36 38 40 42 44 46 48 50 52 54 56 58 60 62 64 66 68 70 72 74 V 2 ( lg = 4 76 + " 7 1 1 1 OF 1 1 1 1 tel-00245958, version 1 - 7 Feb 2008 2 2 OF 2 2 2 2 2 3 Dates initiales 3 OF 3 3 3 3 3 Dates guidantes. 4 4 OF 4 4 4 4 4 5 Dates Ordonnancées 5 OF 5 5 5 5 5 6 6 OF 6 6 6 6 6 7 OF 7 7 7 7 7 7 8 8 OF 8 8 8 8 2 4 ! 6 8 10 12 14 16 18 20 22 24 8 26 28 30 32 34 36 38 40 42 44 46 48 50 52 54 56 58 60 62 64 66 68 70 72 74 76 V 2 ( lg = 4 + - $#! %!! " tel-00245958, version 1 - 7 Feb 2008 = ' ! " #' ! ! $ @ (* ! " !1 4 ' #' ! ( 4 < ( ! A ) * 1 4 7 , 3 rdi ddi : 1 rdG i : !1 V 4,2 M1 7,2 3,3 1,5 ddG i : : 11 : 8,2 1 $ $ , 5 max(0, ddG i − ddi ) % % 1 EG = 121 ' 2,3 5,5 6,3 1,6 5,6 8,6 M2 1,2 7,1 4,4 3,4 5,3 1,4 7,4 4,5 2,4 8,5 8,4 2,5 6,5 2,6 M3 5,1 3,2 6,1 7,6 M4 4,1 2,1 1,3 7,3 8,1 3,5 5,4 M5 1,1 3,1 4,3 5,2 2,2 7,5 8,3 1 2 3 ! 4 5 6 6,4 6,2 7 8 9 10 11 V 0$ lg = 7 " $ 2J @ S B ' ' ! 3 @ ' lg ( ! 5 F < (* F * ' R R (* 2J! " ' , ! " T 4 @ ' F ' # * $ ! " 4 ! 3 F ' ' P( B * ' $ , * ' ( ' ! 9 , U * F ) $ ( ( F * + " 7 M1 4,2 M2 7,1 M3 7,2 M5 1,5 8,2 4,4 3,4 5,3 3,2 1,4 7,4 4,5 1,2 5,1 M4 3,3 4,1 2,1 1,3 7,3 8,1 3,5 1,1 3,1 4,3 5,2 2,2 7,5 2 4 6 8 10 12 14 16 18 20 22 2,3 6,1 6,3 2,4 8,5 8,4 2,5 6,5 5,4 8,3 24 26 ! tel-00245958, version 1 - 7 Feb 2008 5,5 6,4 6,2 28 30 32 34 36 38 40 42 44 46 48 50 52 54 56 58 60 62 64 66 68 70 72 74 76 V 2 $ R R * F < 2J 5 @ < # 4 ' ' ! " ' < ( 4 ! "* $ F ( ( , ! 1 1 OF 1 1 1 1 1 2 2 2 OF 2 Dates initiales 2 2 2 3 3 3 OF 3 3 3 Dates guidantes. 3 4 4 4 OF 4 4 4 4 5 Dates Ordonnancées 5 OF 5 5 5 5 5 6 6 OF 6 6 6 6 6 7 7 OF 7 7 7 7 7 8 8 OF 8 8 8 8 2 4 6 8 10 12 14 16 8 18 20 22 ! 24 26 28 30 32 34 36 38 40 42 44 46 48 50 52 54 56 V 4 < 2J 58 60 62 64 66 68 70 72 74 76 + - $#! %!! ! )' #, # 8 , > ! " * (' ! • / . P BCM tel-00245958, version 1 - 7 Feb 2008 " P BCM : 2JF : 2J : $ ! & (* 4 , ! " * , 74 < ' 8 , ! !% / A ) * 1 4 7 ! V J < PP P PP OP PP OF PP ) * 1 4 7 ) % 6 6 6 6 6 6 - 6 6 6 6 6 6 !% V - rdi ddi * 1 4 : 6 6 6: 6 6 % 6: 1 6 6: %6 6 6: 6 6: 6 6 6 6 6 7 : 1 % 6 6 6 6: 6 6 pij : 1 Deni !: ! !: !1 !1 !: 7 $ * 8 " * 7 2JF (' 8 4 ! ! ! Den p Ch !1: ! !: V 3 * " * , * 4 Den = 0.76 S * (' F Ch = 0.56! + " 7 : " , 5 ! ! " * ( F ( @ , , 5 ' ! % %% 5$ tel-00245958, version 1 - 7 Feb 2008 ! Q MN QD Rob G EG )H )4 -H -4 *H $ 1H *, 1, % 1 1 1 1 $ : $ V 4 ( 2 , F * ' 7 ' 8F * ( ' @ ( ! " @ F * * ! . F 5 ' ' * ! . F ' @ ' ' * 7 8! , ( ' 4 @ * ' ! • / . 8 2JF P BCF 1 ! N @ (' 4 S T F F ' * , ! F ! ! / ) * 1 4 7 , 3 ! V J < rdi ddi : 1 1 & F * * , @ F 2J 4 F Den = 0.69 Ch = 0.72 ! + - $#! %!! PP PP P OF ) * 1 4 7 , 3 ! tel-00245958, version 1 - 7 Feb 2008 OP PP PP ) : 1 - 6 6 6 6 6 6 6 6 1 : 1 * 6 6 6 6 6 6 6 6 1 1 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 V - 7 ! Den p Ch !:% !1 !1 : : 6 6 6 6 6 6 6 6 pij % : % 1 Deni !1 !: !% !11 !% ! !1 * 8 V 3 * " , ( * ! ! % %% 5$ ! 4 Q MN QD 3 ))7 -H -1 *1H $ *) *H *1 : : : , F 4 , $ Rob G : $ EG % : 1 $ V 4 , ( 3 , F ( @ ' F * $ ( 7 ' ! 8! , @ ' , $ / 8 . F 2J 7 ' ' ' ( 8 * < 7 8! " * ! 8 "* ' F $ + " 7 7E G 4 8 ' @ 4 7 8 @ '' ! #F * * F B ' ' @ F * * , ' ' S ' < * ( ! P BCF 2 ! = * $ 74! '( !!8! " , 4 < , ' , ! !:! " ! 1 4 , 5 ' * * ( ! tel-00245958, version 1 - 7 Feb 2008 ! Den p Ch !1 ! !1 : V 3 * % %% 5$ ! Q MN QD 3 ))7 -H -1 *1H $ 17 1, 42 : 1 11 : : Rob G EG 1 % : :1 % 1 $ : $ 1 V 4 , ( " , , $ ( , ' F * lg = 8F lg = 12 lg = 16 :F 1 % 4 , : ( ! . F * 4 @ * ' ' F * ' * ! / . 8 P BCT F ! " P BCT F 2J (F ' ! " 5 ' 2J # ( ! " * P BCT F , ! F ! % ! / + - $#! %!! % rdi ddi 1 ) * 1 4 7 , 3 tel-00245958, version 1 - 7 Feb 2008 ! PP PP P OF ) * 1 4 7 , 3 V J < OP PP PP ! ) 1 : : 6 6 6 6 6 6 6 6 - 1 6 6 6 6 6 6 6 6 P BCT F * 1 6 6 6 6 6 6 6 6 1 6 6 6 6 6 6 6 6 % V - 7 Den p Ch !1 !1 !11 ! V 3 4 6 6 6 6 6 6 6 6 pij Deni !11 !%: !: !1 ! !: !% !: * 8 * " * * * 4 2J 7Den = 0.728 S (' 7 8 4 7Ch = 0.778! 3 , , * @ ( / ! " ! 5 ' ! 5 + " 7 % %% 5$ tel-00245958, version 1 - 7 Feb 2008 ! Q MN QD 3 ))7 -H -1 *1H $ *7 1* Rob G EG 1 :% $ $ V 4 , ( . 7lg = 88F ( @ $ * 1 ( F * 4 ! = ' , 7 8 * $ < * * , * ( ! N * * 4 * ' ' , * ( ! 5 F ' ' 7 2J , E G 8F ' F * < 7 , lg = 128! ' ' ( F * ( ) 7lg = 408! . F @ * @ ( ! ! ##4 . 4 , 4 F ( ( @ # 5 , * OP LP er @ ' ! 6 * OP LP er * , $ < 2J * < 5 @ < $ ! " , ! ! 4 * 5 5 ' ! = 4 * ( ' ' ! • &# . (* F * 4 * OP LP er ! F @ 5$ ( * B @ F , 7 8 ( @ , ,! 3 , * T Q 7! 8 / + - $#! %!! XX XXX PBCM XXX X lg XXX p = 5.47 )H ! )4 !1 -H !: -4 !1 *H ! tel-00245958, version 1 - 7 Feb 2008 ! V D OP LP er , PBCM XXX XXX PBCF1 XX XXX p = 4.37 lg X 3 ! )!1 )7 !1 -H !: -1 ! *1! ! V D PBCF2 p = 4.8 PBCTF p = 4.27 !: ! ! ! ! :!: !% ! !1 !1 !: 1! OP LP er , PBCF1 FPBCF2 FPBCTF T Q(en%) = QD − QM N × 100 QD 7! 8 9 , ( @ ' , * $ ( F , c! N T Q ( $ S @ F ' @ ' * ( ! " , , * ! (* (* OP LP er ! 5 @ $ ! . @ (' 4 F ( * ' # * OP LP er 4 @ ! 3 < ' # 7*@ c8! 3 ! 1 < OpLP er < , ' P BCF 1 2 / ( ' 4Q ! 3 $ B 4 / , * R R @ $ * 5 ! . , F , $ * 4 4 < 5$ + " 7 . @ (' 7P CCM 8 'K 1 < OP LP er 2 < OP LP er 3 < OP LP er 4 < OP LP er 5 < OP LP er 6 < OP LP er <2 <3 <4 <5 <6 <8 Den Ch 0.77 0.56 +14% +21% 0% −4% 0% $ tel-00245958, version 1 - 7 Feb 2008 ! V &, . @ (' 4 7P CCF 1 8 . @ (' 4 7P CCF 2 8 . @ (' 4 7P CCT F 8 Den 0.69 Den 0.70 Den 0.72 Ch 0.70 $ %c d c d :c d c $ c $11c Ch 0.72 dc dc dc $ c $ c $:c Ch 0.77 d :c $ c $c c $c $ :c * ( 2J! @ ' $ ' 5 5 ! 4 * '' * < , * ' ! # * , B * * 4 ! • %% < F ( ( @ ( ( 4 @ 4 , ! " RobG ' ' # 2J $ # ' ! . F * $ @ ' 4 < ' 7 , 8! 2 7! 8 / RobG rel (en%) = RobG × 100 N OF G f eni avec G G f enG i = ddi − rdi 7! 8 i=1 "* 4 ' 72J @ , ' 8F 4 7 48! " ! ' @ 4 ! . 4 ' F ! 2 * ' 4 4 @ * OP LP er ' ! 3 # ( * / $ < 2J 5 @ < $ F 4 F $ , * ! + - $#! %!! . @ (' 7P CCM 8 'K 1 < OP LP er 2 < OP LP er 3 < OP LP er 4 < OP LP er 5 < OP LP er 6 < OP LP er <2 <3 <4 <5 <6 <8 Den Ch 0.77 0.56 2.8% 0% 6.3% 12% 18% $ tel-00245958, version 1 - 7 Feb 2008 ! V 6 . @ (' 4 7P CCF 1 8 . @ (' 4 7P CCF 2 8 . @ (' 4 7P CCT F 8 Den 0.69 Den 0.70 Den 0.72 Ch 0.70 !c !c !:c 1!c :c c Ch 0.72 c !c !c !%c !c %!c Ch 0.77 c !c %c %c !c c ' ' ) * (' + ! F ( , ' ' ! " OP LP er < B ' *$ ( @ $ ( 4! = * * F 4 7 4 8 ' ! , F $ * F OP LP er < ( 4 ' @ ! 3 ( 4 ( ! 3 , * * 7 , (' F 2J8! . (* F ( > 5 ' $ ! 3 4 4 ( ! & @ * $ * F B ' ' ! " , * ( * ( @ * ' ! , < '! F , $ B * # ! F , , 7 8 4 ( ! tel-00245958, version 1 - 7 Feb 2008 + " 7 tel-00245958, version 1 - 7 Feb 2008 $ % # # " ( ( ( 4 ( ! " ( $ ( 4 4 @ 5 ! > ' ' $ ! " 4 ! ,$ # ( 4 @ #' / 5 ' $ F 5 , F. . . 9# ( ( ( ' ' ! = ' ! = ' ( @ $ * ! 3 ( / V " F , , ' ' ! 3 ' ' # 2J $ ! " , ' ' ' ' R$2JR ' ' R R! " , , '( ! V " , ! 3 R R $ * 4 7' F 8 3 4 $ ! , * # '( ! V J F @ * * # ' ! " ! N * @ ' ! , F - (! 7!!# 7 : # ! , * ' ! ( $ $ tel-00245958, version 1 - 7 Feb 2008 ( ' ' R! F R' ' = ( ' ' R#R 4 ( ! . 5 F $ , * # 2J ( O! " * @ ' ' @ $ * $ < '' ! " , ' $ * * @ $ ! # (* '( , 4 5 ! ! &# # # # # <= " 4 $ < 5 ! ' ' * ' 2JF @ (* 2J 74! ( 8! 9 # $ , 5 , 4 ! ' ' * , # F @ ' $ ! 9 ( ' ' # R $2JR! N $2J k (SOFik ) 2J i (i, j) 2J * < $ ! 9 F 2J $2J * * ! " #' ! $ 7 @ 2J F 8 4 $2J '! i, 1 i, 2 SOF i3 SOF i2 SOF i1 i, 3 t=1 i, 4 i, 5 i, 6 t=2 ! V 3 t=3 $2J - ! #! ** 1 * 2J i < 7 2J < 8 $2J! 9 F , $2J! . F 5 4 3 4 * 7 ' * ! tel-00245958, version 1 - 7 Feb 2008 F (* $2J 74! '( rdG ik $2J 2J ! # ' $2J $ ,! $2J 2J 4 < 8 ' ' R( R $2J 74! '( !!8 # !!8! 9 F ' ' 4 5 (* $2J # ddG i = @ # 2J 7 # 2J 8 @ 4 4 < 2JF * < ! " 2J 2J! . , F , #' ! ! = 2J : F / F F F F ! T # ! = ' @ ! " #' ! $ ($ O 2JF #' ' ! 9 $ * F F $2J i1F 2J i < 4 $2J i2F # : $2J i3! " * ! / 0A k ) * ! rdG ik : ddG ik V 3 $2J " ' ' 2J @ F $ ! " ' ' 7 '( 8 #' 4 ! 3 , 4 $ 7 4 R R , 2J8! <( * ' ' < 5 ! " , ' ' ) $ ! 4 ,F * 4 '( ! - (! 7!!# 7 ! &# # # # < = 3 @ * ( F 4 4 $ !2 * 5 7#$ ' !8! r i, j m,n k ,l p ,q tel-00245958, version 1 - 7 Feb 2008 t1 t+1 ! V 3 $2J '( R ' < ! R Ort (i, j)F i ∈ [1, N OF ]F j ∈ [1, N OPi ] r t $ ! 3 $ F Or,t−1 ≺ Ort * ' # * ∀r ∈ 1 . . . N R F ∀t ∈ 2 . . . T Ort−1 Ort ! 3 < < $ 4Q @ @ 2J 5 ! " < ( ' ' ! #' ! * (i, j)F (k, l)F (m, n)F (p, q)F * ! " * / i, j ≺ m, n k, l ≺ m, n i, j ≺ p, q k, l ≺ p, q - ! #! ** "' ( . ( ' ' % / .## %## tel-00245958, version 1 - 7 Feb 2008 r = 1 . . . N R t = 1 . . . T Ort = {ij/mijr = 0 Xijt = 1} < % t = 1 . . . T − 1 (ij) ∈ Ort - (ij) ≺ (kl) ∀kl ∈ Ort+1 < % < % < % ! 1-# • (. % # ' ' @ ' $2J! 3 @ F ( ' ' 5 @ (* $ 2J ! , # , '' ! 3 @ (' 4 P BCF 2 7 '( !! ( 8 * ' ' ! " @ 4 2J $2J ! 3 $2J ! 3 ( @ . ! 2 ( ,! , 7. 8 * 2J @ < 2J ! . , 5 ! . F $2J (* ! " , $2J !! = * ' F * * ( ' ' ' 7 ! 1 '( !!8! = * * ' ' $2J ' ' ' ! . , lg = 8 : F * ' ' : 7 1 8! N lg = 12F : ' ' $2J 1 ' ' ! 9 ( ' ' * : lg = 12F * < - (! 7!!# 7 $ Rob G EG $ $ $ ! V . 4 tel-00245958, version 1 - 7 Feb 2008 Q MN QD ( (P BCF 2 ) ( ! " ' ' lg = 8 * : ! * F ' ' ' ! * 4 $2J $ $ B @ '' ! 4 F F ' ' @ , ' ' F ' : 71 8! = # F * * ' ' @ ' ! • (. % %## '( * * , ' ' ! 3 ' ' * ! = * ( @ , * ( ' ' ' ' ! " , * # $ , @ (' 4 P BCF 2 ' @ ! . , # '( F !! #' ! $ ? ! = ' 7 +( 8 5 @ < ( ! 9 #' ! / 0 / Op42 , Op72 ≺ Op23 , Op33 ≺ Op82 ≺ Op15 ≺ Op55 , Op63 0 / Op71 ≺ Op12 , Op34 ≺ Op24 , Op44 ≺ Op53 ≺ Op85 ≺ Op65 0 / Op51 , Op61 ≺ Op32 , Op74 ≺ Op14 ≺ Op25 , Op45 , Op84 - ! #! ** 2,3 4,2 R1 7,2 8,2 1,5 5,5 6,3 3,3 7,1 1,2 5,3 2,4 3,4 5,6 6,5 8,5 6,6 (8) 4,4 R2 1,6 5,1 3,2 2,5 1,4 2,6 6,1 R3 7,4 8,6 4,5 8,4 2,1 4,1 8,1 R4 1,3 5,4 3,5 7,3 3,6 8,3 6,2 7,5 2,2 R5 4,6 5,2 1,1 3,1 6,4 7,6 tel-00245958, version 1 - 7 Feb 2008 4,3 2 4 6 1 8 10 14 16 18 20 22 26 28 2 ! V 0$ 30 32 34 38 40 3 42 44 46 50 52 4 54 56 58 62 5 64 66 68 70 6 7lg = 128 0 / Op41 , Op81 ≺ Op21 , Op73 ≺ Op13 , Op35 ≺ Op54 ≺ Op64 0 / Op31 ≺ Op11 , Op22 , Op43 ≺ Op52 , Op75 ≺ Op83 , Op62 " ' (* 7. 8 * # (* 2J 7 $ 8! . . # #( #' * ' ! " ! 5 ' ' ! 6 * (* $ F $ ' 5 ! $ ! V . 4 Q MN QD Rob G EG $ $ ( (P BCF 2 ) - (! 7!!# 7 tel-00245958, version 1 - 7 Feb 2008 9 5 ' ( F * * , ( ' ' F * ( ' ! 3 ' ' $2J * ' * ( 7 8 ! = , lg = 8F :: 4 , : ' ' ! F , ' ' ' ' : ' ' ! 9 * ' ' * ! = ' ' 7 ' ' 8 ' F : 71F 1 : 8! !! (# 9# B ' ' ( !! 3 4 @ 5 ' ' ( 7 * ' ' 8! " ' ' 7 F $2J 8 * P BCF 2 ( ! = ' QM N 7* ( 8F MN N N F , (Q F QM QM M in M ax 8 5 ' ' ! " ( (+) ' (−) * ( 4 ( ! 3 @ F ( $ ' ' F , ! 9 ' ' ' @ * ( * , ' ' ' ! ' ' ' 24% 4 @ ( F * ' ' 14%! . , ' $ * ( ' ' $2J 41% 8! 732% ``` ``` ``` `` ` ``` MN Q N QM M in N QM M ax $ ! V 3 (+1.63%) (+24%) (−26%) (−11%) (0%) (−32%) (−13%) (+14%) (−41%) ' ' 7* ( 8 (P BCF 2 ) - ' # 2!!! 9# # !.; = ! 4 $ , 5 ' ' ! " ' @ 4 ! = * O ( ' ' F < ' ' * ' * , ' ' ! ``` ``` ``` Rob N RobM M in M N RobM ax tel-00245958, version 1 - 7 Feb 2008 ! V 3 • MN $ ``` `` ` : : : ' ' 7 ( 8 (P BCF 2 ) " , * ' ! ) 5 * 4 ! " ' * . 7( * 8 < , @ P( '' * ! ( % % 1 8 , , : " $ ,! @ * F ( F F $ 4 F 7 2J8 ! F , 2J! = ' ' '' ! " ' ' ( ! 6 * ' ' # 5 2J! 9 (' * '' 7 @ 8! " , ( ' ' ' 4 * 7* 8 7' ' 8 7' ' $48! F ' F 4 ' $ 7 ' R R - (! 7!!# 7 ' < 8! " ' ' * $ ! . , F 7 ! 8 P BCM '( !! ( * * ' 500%! < .H3J ' 300%! . @ (' 4 ' F * ' F 1300%! . , * 4 B @ $ E ( I F %%%G! . F '' EJ !F %%GF * '' @ 4 ( ( ! tel-00245958, version 1 - 7 Feb 2008 ! ) " * ' EJ !F G! ' $ '' 7 $ 8 @ ' ! 3 ' * ''! 3 < > , / • ' (* • $ '' (* ! " $ $ * 7! 8 $ ' 7!8 7 Q 7!18 7!8 '( !!! " B $ * B α ' β '' ! "* B ', @ F 7! 8 7!8 7 7!18 7!88 * ! N OPi pij + Xijt ≤ α × lgt ∀t ∈ T 7! 8 j=1 OPi N OF N mijr × Xijt ≤ β × Capart + HrsLSuprt ∀r ∈ N R ∀t ∈ T 7!8 i=1 j=1 ! # # # 3 '( , , ( $ ' ! 3 2J $ ! " 1F F F ! " ' - ' # 2!!! 9# # !.; ( ! " $ * * #' !! F $ * $ B α #' !! lg lg i, 1 i, 2 i, 3 t=1 i, 4 tel-00245958, version 1 - 7 Feb 2008 i, 1 ! V 0$ 0, 7) D u lg i, 2 t=1 i, 5 t=2 ! V 0$ D u lg lg i, 3 t=2 t=3 @ D u lg i, 4 i, 5 t=3 @ ' $ (α = 3 #' !F # $ # / 2J i < ! . F B α $ 4 @ '' 7!4! #' !8F < ! 5 F #' F $ #' ! < ! 3 4 ' ! . #' !F $ $ 7 , , 8F ) 4 * ! F ' 4 $ ! J F #' ! $ ' ! " 4 5 $ 4 ' ' ' ! - (! 7!!# 7 : ! # # ## " B β ' @ B α F 4 ! " # ! 3 $ B β ' ' ! 3 ' , * @ ! " + , $ 5 (' K ! 3 #' !: !1F 4 B β @ α , * ! 5 @ < $ ! tel-00245958, version 1 - 7 Feb 2008 Capart = 10 i, 2 i, 5 i, 4 Capa rt i, 1 i, 3 t=1 t=2 !: V 0$ t=3 @ Capart = 10 i, 3 i, 5 i, 1 E .Capa rt i, 2 t =1 !1 V t=2 i, 4 t=3 $ (β = 0, 7) N * < 4 B $ 7 α β 8! 3 * ' , $ B ! < ' * ! ' $ [email protected] ' 2J 7 B α8 S < < 4 @ 4 * 7 B β 8! = F 7!8 7!8 @ B ! - ' # 2!!! 9# # !.; 1 α × lg ≥ max(pij ) 7!8 β × Capa ≥ max(mijr ) 7!8 " 7!8 * ' # 7 α8 < ' @ ' * 2J! " 7!8 ' F , * # < ' @ 4 r ! tel-00245958, version 1 - 7 Feb 2008 !! 1-# ' * * $ * ' ( 7 @ 8! 9 R4 R ' # * '' , * # ! N (' * 7'P 4 8 4 7 8 ( # ! = , @ 7 ( 8 @ ! !17α = 0.808F , !:7 α = 18 5 P BCF 1 ! • / . 8 (P BCF 1 ) $ !: V 6 Q MN QD Rob G EG $ $ ( 7α = 18 9# 5 ' F $ 5 ' ! 9 $ * , * ( ( F %! 7α = 0.88 4 :! 7α = 18! ' * ' # F 7α = 18 F ( @ @ ! 7α = 0.88! = * ' 4 7 !18! - (! 7!!# 7 Q MN QD $ tel-00245958, version 1 - 7 Feb 2008 !1 V 6 Rob G EG $ $ ( 7α = 0.88 * * ' ' * 5 $ $ ' , 7α = 18 @ : 7α = 0.88! 3 , * # '( !!!F * , * * ' ! F , * 4 ( ! " * ' :F @ !1! • / . 8 (P BCF 2 ) $ ! V 6 Q MN QD Rob G EG $ $ ( 7α = 18 , ! !%F * ' $ ! = F α = 1 @ : α = 0.8! . # F α = 0.8 ' # @ lg :! F * ( F < 7 :! @ :!8! . F * * ' ' $ , ! = ' * ' * ' ' ! - ' # 2!!! 9# # !.; $ !% V 6 tel-00245958, version 1 - 7 Feb 2008 • Q MN QD Rob G EG $ $ % ( 7α = 0.88 / . 8 (P BCT F ) ! Rob G EG $ $ V 6 ( 7α = 18 ! $ Q MN QD $ Q MN QD Rob G EG $ $ V 6 ( 7α = 0.88 , F * 4 (! " ( ( ! * * ( 7(Z!8 ! * * ( F 1! 7 (8 @ ! 7 (8! - (! 7!!# 7 J F F $ 4 ( 5 * ( 4 ! (& */ 1% $%1 % 6 , tel-00245958, version 1 - 7 Feb 2008 '( , , ( * F , ' * ! " , 7 8! " , F $ M. 7MX . 8! 3 '( F , 4 ( 4 @ * ! ! ) # , '( F ! F 'F (' #' ( F F , ( F. . . * ( @ , , ' ' ! " , F F @ 4 4 @ ( @ 5 ! . , 5 ' F * * , $ ! • $ (P BCAL ) 3 , 2JF 2. 2JF 6 ! 3 , F (* 2J ( 4 F 2J 5 ' #! & 2J @ ! " ' , ! F ! F ! ! 3(* * #' , 7#' ! !%8! ) * 1 4 ! V J < rdi ddi - + "!0 2&# *2 7# PP PP P OF ) * 1 4 OP ) PP PP : ! 6 6 6 6 6 * 6 6 6 6 6 1 6 6 6 6 6 4 6 6 6 6 6 6 6 6 6 6 Deni pij % : 1 !:1 !11 !: ! !: V 7 2J8 ! tel-00245958, version 1 - 7 Feb 2008 - Den p Ch !: ! !% V 3 * 3 4 , , 5 ' 4 ( 4 ( ! 3 4 ' 4 ( ! " ' ( 1! 3 $ $ !%8! 7#' ! 2,5 5,2 1,2 3,4 2,6 M1 4,3 1,5 2,3 4,1 5,5 5,6 M2 3,1 2,4 1,3 4,4 M3 3,3 1,1 M4 5,4 4,2 3,2 5,3 2,1 5,1 3,5 2,2 M5 1,4 1 2 3 4 1 5 6 8 9 3,6 4,5 10 11 12 13 2 15 16 17 18 19 20 22 23 24 25 26 27 29 30 31 32 33 34 36 37 38 39 40 41 3 4 5 6 ! V 0$ " , ! F ' ( ' ' * ! - (! 7!!# 7 3,1 M2 M4 1,1 M5 2,1 5,1 1 2 3 3,2 4 5 6 8 3,3 4,2 2,2 1 5,5 2,4 1,3 4,4 9 3,5 10 11 12 13 !% V 2 4,5 15 16 17 18 19 20 22 23 24 25 26 27 29 30 31 32 33 34 36 37 38 39 40 41 3 4 5 6 5,4 5,3 1,4 2 ! 3,4 4,3 1,5 2,3 4,1 M3 tel-00245958, version 1 - 7 Feb 2008 2,5 5,2 1,2 M1 $ Q MN QD Rob G EG $ $ V . 4 ( , " ( , ' 7lg = 7 lg = 108! 4 ( @ @ 4 ' @ 1 ! 3 $ # * F U < ' ! . F ' * F ' < ! • &# %% $ $ " 5 ' F 4 ' ( ! :! = * ( 4 $ ! " ' * ( %c @ 4 , ( ! " ( * ! - + "!0 2&# *2 7# ``` ``` ! tel-00245958, version 1 - 7 Feb 2008 ! ``` ! ``` ``` MN Q N QM M in N QM M ax P BCAL $ (+39%) (+100%) (−21%) : V A ( P BCAL 7 8 ,# . ( # " , # ' 4 ' ! 3 4 @ ! 3 F R R 2JF @ $ 2J! ( F ( # 7 8 $ * 5 R ' R @ 2J 7 4 < 2J8! " $ (' , $ 7 2J8! . > 4F 4 # 4 $ 7 ( 8! 7W ctetali 8 * 2J i! " F min + N OF CtLreti × Reti + CtLavai × Avai + CtLsti × sti i=1 N R T r=1 t=1 CtLhsuprt × HSuprt + N OF i=1 ctetali × T t=1 t × XiN OPi t − T t=1 t × Xi1t 7!8 '( > # ( , , , ! " P BW IP 1 @ P BCF 2 F P( ! < P BW IP 2 < P( ' ! " 4 , 7 * 8 2J! " ( , < * , ' ' ! " #' ! , , $ , ( @ ' ! - (! 7!!# 7 Approche Directe Données Détaillées Minimisation des encours Ordo Preactor Comparaison Approche Multiniveaux Données Détaillées Données Agrégées Agrégation de données Guidage Optimisation des encours Elaboration du guidage MacroOrdo V " , ( 7 8 ' * .693&26 , 5 / tel-00245958, version 1 - 7 Feb 2008 Ordo Preactor Xpress-MP ! Suivi du guidage b V ( (' ( * / ' 7 M.8! V ' ' F '( R R ' / ' R R! • (P BW IP 1 ) # L " , * ' , ! 1F ! F ! %! ) * 1 4 7 , 3 ! 1 V J < rdi ddi : 1 : $ F ( > ! * F * 4 F 2J! * * ' : 7QD = 268!3 4 5 5 ( ! 4 * 4 ( F ( ( !3 * @ 4 ' ! - + "!0 2&# *2 7# PP PP P OF ) * 1 4 7 , 3 ! tel-00245958, version 1 - 7 Feb 2008 OP PP PP ) 1 1 : 1 - 6 6 6 6 6 6 6 6 : 1 6 6 6 6 6 6 6 6 * 1 1 6 6 6 6 6 6 6 6 1 6 6 6 6 6 6 6 6 : V - 7 ! Den p Ch !: ! !: 6 6 6 6 6 6 6 6 pij Deni : : ! ! !11 ! ! !1: !11 !:: * 8 % V 3 * 4 $ ! V . 4 Q MN QD Rob G EG WIP $ $ ( , 3 F * * ( * ( * ! . , F M. ' ( 7M.Z: 8 @ ( 7M.Z8F * ( 1 10%! N 4 ( ' ( 7M.Z%F 'Z 8 * % 15%! • # L (P BW IP 2 ) " , * , 7< ' 8F P( ! " ! ! * ! - (! 7!!# 7 : rdi ddi : : 1 ) * 1 4 7 , 3 tel-00245958, version 1 - 7 Feb 2008 ! V J < Den p Ch ! ! !1 ! V 3 * = * ' , ( !! $ ! V . 4 Q MN QD , F Rob G EG WIP $ $ ( , = ( $ 4 , 4 ( ! = * F , @ : * M. % ! " ( ' ! N * @ 4 * F 4 F F ( ' < $ ' ( ! 3 @ 4 * P BW IP 1 ! 3 * ' ( F $ ' * F 4 $ ! = ' * * * F - + "!0 2&# *2 7# 1 ( @ ! 3 W 4 * * 2J F $ O R* R 2J! 3 B ( ' 4 @ ( ! • &# %% 8 L , 5 , , $ ! " ! ' F $ F 7 8! ``` ``` ``` ! ``` ``` tel-00245958, version 1 - 7 Feb 2008 MN Q N QM M in M N QM ax P BW IP 1 $ ! V A (+9%) (+13%) (+5%) P BCAL (+15%) (+23%) (+6%) ( 7 M.8 , , 4 ( $ ! . P BW IP 1 10% @ ( ! . P BW IP 2 * ' 20%! 2 * * ( 4 , ! ( , 5 ' ' ! " ' ' ' ' $2J * 2J $2J ! " , ' ' ' ' * # 5 < ( ! " 4 , , ' ' ' ' ( ! " , * * ' ' ! " 4 ' ' R #R * ' ' ( ! " $ ' ' ! 3 ) ' * ( * $ ! 4 4 * 4 ' ! ( F 7 8! 3 R' R * - (! 7!!# 7 tel-00245958, version 1 - 7 Feb 2008 4 $ ! " , * * ! " ' ! " , * ( 4 $ ! J F ' * / ! = #$ ' @ 2J! * 4 ! " 4 4 ! & tel-00245958, version 1 - 7 Feb 2008 ' ( " ( ' * ($ @ 4 R R! N 5 $ < 4 5 ! 9 F 4 ( * 5 7 5 8 ! , ( F * 4 ( , , ! F @ $ * ! = $ * # # 5 , ! , F ' '$ ' $ R''R! $ $ @ * 5( 5 ! " 4 , * * , * ! " '( $ ! " , '( '' @ '' $ ''! " '( , * * 4 '' $ '' 4 @ $ 5 ! % / .# !!! "! - 5 , * % * / 2 ##, 4* , * 5 < 4 5 ! 9 , F ( F , 4 F 5 F P( 5 ( ! 2 R R @ ' R R! tel-00245958, version 1 - 7 Feb 2008 ?6 3 ; 3 ? E9 ' F %%G! N < ( ! " ! Gij @ j me l OF i @ $ r 7 ij 8! " * 7 8 * 5 ! N * ! 2 / V pijr 7ij 8 * 5 r Gij V mijr mijr = 0 si 7 ij 8 r ! 2 / r ∈ Gij ; mijr = 0 si r ∈ Gij " #' ! ! 2 , OF ! " 7ij 8 r1 F r2 r3 ! " r6 ! 7i, j + 18 r1 F r5 OFi OPj OPj+1 r1 : pij 1r1 , mij 1r1 r1 : pijr1 , mijr1 ou Gij r2 : pijr2 ,mijr2 ou Gij 1 r5 : pij 1r5 , mij 1r5 ou ou r3 : pijr3 , mijr3 ! r6 : pij 1r6 , mij 1r6 V = . * < @ 5 7 , r1 * @ Gij @ Gij+1 8 * 4 , , ! , F 5 @ (* ( $ ( 5 $ / .# " !!! "! ! 3 * # $ ! ' F F 4 ! / & # # #, #8# 4;);-;) $ Xijrt * * * r 5 @ 7 8 * # ! tel-00245958, version 1 - 7 Feb 2008 Xijrt = 1 7ij 8 Gij S Xijrt = 0 ! 5 t r " $ ( * Reti 7 OF i8F Avai 7 OF i8F Sti 7$ OF i8 HSuprt 7 ( 8 ! " 4;);-;- X ' ! " ( @ 5 ! T Xijrt + Sti = 1 ∀i ∈ 1 . . . N OF, ∀j ∈ 1 . . . N OPi 7! 8 i=1 r∈Gij t Xijrn ≥ n=1 r∈Gij t Xij+1rn ∀i ∈ 1 . . . N OF, ∀j ∈ 1 . . . N OPi , ∀t ∈ 1 . . . T n=1 r∈Gij 7!8 OPi N OF N i=1 T mijr × Xijrt ≤ Capart + HSuprt ∀r ∈ 1 . . . N R, ∀t ∈ 1 . . . T 7!8 j=1 t × XiN OPi rt − DPi (1 − Sti ) = Reti − Avai ∀i ∈ 1 . . . N OF 7!8 t=RPi r∈GiN OPi RP i −1 t=1 r∈Gij Xijrt = 0 ∀i ∈ 1 . . . N OF, ∀j ∈ 1 . . . N OPi 7!8 / .# !!! "! HSuprt ≤ HrsLM axrt N OPi ∀r ∈ 1 . . . N R, ∀t ∈ 1 . . . T 7!:8 ∀i ∈ 1 . . . N OF, ∀t ∈ T 7!18 ∀i ∈ 1 . . . N OF, ∀j ∈ 1 . . . N OPi , ∀t ∈ T 7!8 ∀i ∈ 1 . . . N OF, ∀r ∈ N R, ∀t ∈ T 7!%8 pijr × Xijrt ≤ lg j=1 r∈Gij Xijrt , Sti ∈ {1, 0} Reti , Avai , HSuprt ≥ 0 tel-00245958, version 1 - 7 Feb 2008 3 $ * 75 8 # ! F !F !F !F ! !1! 4;);-;* , ( ( $ * , F (' 4 < * $ 7!4! '( !!8! N OF (CtLreti × Reti + CtLavai × Avai + CtLsti × Sti ) i=1 + T NR CtLHsuprt × HSuprt 7! 8 r=1 t=1 - $$ % % , $$ 3 4 * @ ( O ' 7 ( O8 OF F < $ * 4$ 4( 5 , ! $ F * $ F (' 7 8! 3 (' , 5 , # ! = (' $ 4 R'' R 5 (' ! 3 @ $ * 7 8 ! " $ ! 3 '' # ( ( ! 3 / ' ** ! ! !!! #& #.# ** 4 '' ! 3 '' F $ 4 '' * ) ( ! / &# # # " '' * @ ' 5 7 * 8 * 7 8 ! tel-00245958, version 1 - 7 Feb 2008 R'' R Mijr 7ij 8 (* r Gij / Mijr = mijr card(Gij ) Mijr = 0 ∀r ∈ Gij 7! 8 si r ∈ Gij ' F '' Pij 7ij 8 $ @ , ! Pij = r∈Gij Pijr 7! 8 card(Gij ) " #' ! ( '' * 5 ! $ / 1- ## # # # + % ' 9 , F OF i! " ! , , ! " ! @ F 4 * * ( 7 8! ' 5 5 F ! $ $ (* / .# !!! "! OPj OFi OPj+1 r1 : p ij 1 r 1 , m ij 1 r 1 r1 : p ijr 1 , m ijr 1 ou ou Gij Gij 1 r 2 : p ijr 2 , m ijr 2 ou r 5 : p ij 1 r 5 , m ij 1 r 5 ou r6 : p ij 1 r 6 , m ij 1 r 6 r 3 : p ijr 3 , m ijr 3 Agrégation des Pools OPj OFi OPj+1 r1 : Pij 1 r 1 , M ij 1 r 1 r1 : Pijr 1 , M ijr 1 tel-00245958, version 1 - 7 Feb 2008 et Gij r 2 : Pijr , M ijr 2 2 et Gij 1 r 5 : Pij 1 r 5 , M ij 1 r 5 et et r 3 : Pijr 3 , M ijr 3 ! V = OP (i, j) (1, 1) (1, 2) ! r6 : Pij 1 r 6 , M ij 1 r 6 '' #& $ $ r ∈ Gij mijr pijr $ r1 {r1, r2, r3} r2 % % r3 : : r1 {r1, r5, r6} r5 r6 V '' * '' 4 ! '' !! ! " , ! (* ! 5 F 5 #* 7 8 7 8! / ' ** ! ! !!! #& #.# ** OP (i, j) (1, 1) (1, 2) #& $ .#. r ∈ Gij mijr > ? r1 {r1, r2, r3} r2 r3 r1 : {r1, r5, r6} r5 r6 ! V 3 Pijr % * '' 7'' 8 tel-00245958, version 1 - 7 Feb 2008 / & # # # 3 '' @ $ '' $ * 5 ! " ( * '' '( ! 3 $ ! T Xijt + Sti = 1 ∀i ∈ 1 . . . N OF, ∀j ∈ 1 . . . N OPi 7! 8 ∀i ∈ 1 . . . N OF, ∀j ∈ 1 . . . N OPi , ∀t ∈ T 7! 8 t=1 t Xijn ≥ n=1 T Xij+1n n=1 NOF NOP i i=1 t Mijr × Xijt ≤ Capart + HSuprt ∀r ∈ N R, ∀t ∈ T 7! 8 ∀i ∈ 1 . . . N OF 7! :8 j=1 t × XiN OPi t − DPi (1 − Sti ) = Reti − Avai t=RPi RP i −1 Xijt = 0 ∀i ∈ 1 . . . N OF, ∀j ∈ 1 . . . N OPi 7! 18 t=1 HSuprt ≤ HrsLM axrt ∀r ∈ N R, ∀t ∈ T 7! 8 / .# !!! "! : NOP i Pij × Xijt ≤ lg ∀i ∈ 1 . . . N OF, ∀t ∈ T 7! %8 j=1 Xijt , Sti ∈ {1, 0} tel-00245958, version 1 - 7 Feb 2008 Reti , Avai , HSuprt ≥ 0 ∀i ∈ 1 . . . N OF, ∀j ∈ 1 . . . N OPi , ∀t ∈ T 7!8 ∀i ∈ 1 . . . N OF, ∀r ∈ N R, ∀t ∈ T 7! 8 3 F * '' ! " ! '' 7Mijr 8 * , * @ ij @ ! " ! % , * '' ' ! " * @ '( !! (' F OF ! min N OF (CtLreti × Reti + CtLavai × Avai + CtLsti × Sti ) i=1 + NR T CtLHsuprt × HSuprt 7!8 r=1 t=1 -& + 4 / 0'34 -# ' '' '' $ F * $ ! " * $ '' $ $ 5 , ! " ' @ ! 2 @ U 5 5 , @ * ''! " #' ! ( ( , ! " , * ' 5 $ + , * '' / (' ' @ # ! " , $ E; O F G @ ' ? 0. * 4 @ F 7(' ' 8F 5 OP F 4 < OF F * OP F !!! / + $#! #6! 1 , F ) 4 # 4 ' 5 , * ' ! . 5 7 8 @ # < # OF ' ! @ ! Résolution du problème de macroordonnancement avec affectation des ressources tel-00245958, version 1 - 7 Feb 2008 Données liées aux pools Processus d’agrégation macroordonnancement avec affectation comparaison Résolution du problème de macroordonnancement agrégé Données Agrégées ! V 3 macroordonnancement agrégé , ( / + # # " * # ! 9 7& 68R! $ F @ $ , 5 4 * ) F R&, 6 3 ' ! ' r r ( O! " F N OF N OPi T SRr = i=1 T t=1 j=1 mijr Capart 7!8 / .# !!! "! . , * 5 F T SR ! 9# ) , F ' * @ 5 ( @ * OF F E; O$ !F G! @ $ ! 3 ' , OF $ tel-00245958, version 1 - 7 Feb 2008 / 1-# , * @ $ '' * ! " 4 5 , 7 @ 8 4 @ '' 7 @ 8! " 4 * 7 8 ! ? +%# 8 % %#? > N , 5 T SR! " , F F 1F F $ ! /A ; TSR 5 $ B 5 .#.# ! V 3 !: 1 1 ! 4 /A ; TSR 5 $ B 5 .#.# ! V & 3.N ! ! !: 1 1 ! 4 ! " , !1 : !% : % ! : 2. !1 % !% % ! :% %: 2.7 8 3 ' F , ' * ' F 5 F ' / + $#! #6! % ( O F ' $ ' ! N @ , * ( ! " '' 4 ' * < ' # , @ !! tel-00245958, version 1 - 7 Feb 2008 F '' * , 4 @ !% ! 9 @ B ''! " ' * * (' 4 , * B $ '! 5 * (' @ U * ! ? +%# $ T SR B# J F ( ! " , , < ! " $ / F 1F ! 5 F @ , T SR 7!F !F !18F * @ (' 4 F 4 ! hhh NOF × ΣNOPi hhhh hh TSR h H;-4 H;4 H;,H *4 ,4 ! ! ! ! V D hhh NOF × ΣNOPi hhhh hh TSR h H;-4 H;4 H;,H *4 )4H 1 1 *HH %: : %: 1 :% 3 ,4 )4H *HH 1! ! % ! %:! ! :!: %! 1! :! %: ! 1 %! !: V & 3.N 7 8 / .# !!! "! , ! = * (' 4 7T SR = 0.25 8 * F (' 7T SR = 0.50 8F O ( F * * < ' ''! J F 4 (' 7T SR = 0.708 4 '' * , 5 ! tel-00245958, version 1 - 7 Feb 2008 = ' 3.N ' , ! = * (' '' F 4 T SR = 0.70 F ! J * 4 @ * ' (' 4 F , ! /! 5 -# " * / • $ % = * < 7< $ 8 ' 4 7 T SR8 , ! . , 4 F , 4 5 ' 7 8! " '' 4 S , 4 7T SR = 0.508! 3 (' 7T SR = 0.708! • $ $ . 4 , ( F , @ ! " @ / 3 ' # * * * * ! , $ ( ( # T SR 4 @ !:! F ( F ' ''F * R$ R $ ''! 3 , * $ * ! 3 ( , ' 4 ! $ * * * * * 5 # ! 9 , F '' < @ 4 5 ! / + $#! #6! " , , U ! 5 < * ( ! , $ , 4 (' 7T SR = 0.78! , F $ R( * R W , $ ! , ! tel-00245958, version 1 - 7 Feb 2008 .% ) 3 ( * $ ' ! $ ! ' 5 ! " ( 5 @ ' $ * ! 3 @ ' * @ ' @ ! "'' ' @ ! " * '' ( ) 4 @ *@ ! + , * $ '' @ 4 $ 5 ! , F (' ' ( ! " , , * @ 7 8! " < @ ! " , * * '' @ 4 4 T SR 4 @ F1 5 ! 3 ' ! F ' ' '' < / 5 F ' ' @ 4 ( ( 4 ( ' ' ! . T SR @ F1 7 (' 8 '' @ 7 8 F 4 ' ! tel-00245958, version 1 - 7 Feb 2008 tel-00245958, version 1 - 7 Feb 2008 , ( F 4 * ( @ P( , @ ! 3 # $ * ' @ ! 9 @ # 7 8F (* @ ' #* @ ' 5 ! $ < ( * F 4 ! " ( , , ' ! ' F @ $ @ * ' ! 9 F ( @ ( ' * ! 3 ( @ , ,! 3(* $ * @ #! 5 7$ 8 * ' $ # OF ! " 4 (' # 7 4 8 ' ' @ '' $ ! " F # @ (* F * ! 9 7$ 8 ' , ! " @ OF ( O $ ! 3 ( * ' ! . 7 8 $ F '' * 4 * , * ! @ 4 @ ( '' F # OF ! # ' tel-00245958, version 1 - 7 Feb 2008 " 4 7 8 (' '' $ ! " '' 5 , OF ! 3 < @ (' ! @ 4 * , , R' ' R! 4 7 OF 8 # '' 5 4Q 4$ ! " ' ' 7R' ' R8 ' # # OF ! " , 7R' ' $OF R8 # ! #F ' ' 7R' ' R8 4 5 2J @ < ! , * b 4$ ( ! " 4 ' * F @ ! " $ @ $ ? @ . 7 ' R R 8! 3 , 4 , ( / ( 7. 8F ( 7? . 8! 3 4 $ / * ' F B ' ' ! " @ 5 / $ 7' 8F * 7 , (' F OF F !!!8! " @ ' * F , , F ' ' ' 4 @ * * 4 , (' 7 4 @ !18! " , @ ' * ' ' ' 4 , , ' ' ! 3 R ' $ R * $ ' ' 4 ( * ! " ' ' 4 ' @ ( * 7 ( * < 8! " $ ' * * @ ! 5 '$ ' < 4 ! F 4 ( ! . $ R$ ' R * '' $ F ' K '$ ' ! " , < ( 4 ' # ' * ' ( @ * ' ! tel-00245958, version 1 - 7 Feb 2008 & , ( @ ( , * ! 3 F , $ * * ! " , @ F @ ' F 4 ! "( $ 4 4 4 @ ( * @ ! " , , 4 ' '$ F 4 ! " $ OF ! " (' , ' $ 4 ' ' ! "( b ' $ ! . 4 ( F ( 4 < OF ! # , @ * 5 7 $ 8! 3 @ @ $ ! , ! " , 5 $ ! " '' (* @ ! , $ 4 , F $ '' * 4 4 ( $ 5 ! 3 , ' $ 4 @ ( ! 3 , * * ' ! 4 , F : 4 F , F ' F ( O F * 7( O ' , F!!!8! tel-00245958, version 1 - 7 Feb 2008 ' + 4 ( ' ! = ( * ! + ( * ( , @ , , ' ' R R / ' ' $ @ 4 ' ! F $ ! ' b 4 F (* (' $ 5 # ! 3 ( R(R , * $ < 4 ! 3 ,$ , ' $ ! " < @ ( * 4 74! < # $ @ * 8! " < @ * ! 5 F * , ! H ** F $ * @ $ 5 @ ' ' 5 ! ( * '' b F 4 ' $ ' ' ( @ 4 ( * ! B '' @ ' $ @ ( * '' ! 3 ' < + , $ ' $ ! 3 + , 4 4 @ , * 4 7 F $ F (' F F!!!8! ) E9 $; F G E9F G F 9! 78! / @2 ! ! F 0! 9! 78! @2 $ 3 B - ! tel-00245958, version 1 - 7 Feb 2008 F = . &( ( * " F J ! E9 O$DF %%G F 6! 7 %%8! &( ( ' ( $ / 4 4 ' ( ! 0 , 3 / F 7:18/V! E9 ( F %:G F 6! 7 %:8! ! ; N . ! .- 7 3H& 3 E9 !F %%G F !F F -!F F 0! F 6! 7 %%8! ; $ ( ( ' 4 + , 4 ' ! + , 3 42 +- %3 -F 78/ V :! F / ! &( F N E9 ' F %%G . 3! 7 %%8! & ! E9( F G F C! F M! 78! 9 ' 4 ( ( ( ( ! + , 3 - 7 F 7:8/1V%! ! "# E9, C^F %G F ! F ;! 7 %8! 9' ' $ '' ' ( ( '! 0 , 3 / F 7 18/V! EHX F %1G $F Y! 7 %18! + - -! C( M ! $F ! 7 %18! .# - H ! 9 $ EHF %1G 4 0 ( .' ' & ( * ! 9 ! !F G $ F .!F F D!F % F 9! &F J! 78! ' ! . . ( * ! EH !F G $ F .!F ' (F 3! ) F M! 7 8! ) - 7 - .-- - .! Y$ EH I ! $! *F "! 7 EH , M F G F -! O ' , $ ' '! $ EH !F % G F -!F ' / 9 ' ' ! F ! !F 9! 7 / 1 8! 0 ' $ 1! %- F 718/%%V % 8! ; ( F 7%8/1 1V1! , $ !F EH ;,F %11G F -! ' ! 8 $ 9! 7 %118! 2 ( F 78/V! F ! 7 EH & F %%G F -! 'F ' 4 ! - F 78! (= ' 4 ( ( %%8! ; ( ( & !F %%G $+,F C!F -,F Y!F ,& F -! *F - 3 - ! ' $D '! EH F G $F J! 78! ' ! ! EH F %1G $F C! 7 %18! - ! ; ! EHO I O 7 %%8! $+F EHI C F %%G ' ( ' ! "F 0! C! 7 %%8! ; ( F 78/ V %! 8 %%8! - - ! $F .! 7 ; OF :G $F tel-00245958, version 1 - 7 Feb 2008 EHX F %%G ' $D '! 6! F C! 7:8! 9 , ( ( ' ( ( ! F 7 18/ :V ! EHX ( 4 , 3 / C! . 0 E3 OF %%G F 0! F C! 7 %%8! ; ( ' X $ $ / 9 ! 0 , 3 / F 7:8/V:! E3 3( F %G ! 0! . .F C! . F .! 7 %8! . " E3( C F 1G F Y! F .! 718! 9 , ' ' ' 4 ' ( ' 78! , 3 / F 7 8/ V ! !F %:1G .+F 6!F /!+F M! /F "! 7 %:18! * 3 -! . ! E3 !F :G . F 9!F ( F 0! / $0F 3! 7:8! ' ! ! E3I .+ E3I 'F G F .! 78! 9 + , 4 ' ( '! I + 0--F 78/1V ! E3( - 4F %% G .F 0! 0F 0! 7 %% 8! ' ! 0 ! 7 E !F G F H!F 1,F C!F F =! /,, F 2 (2 ' ( - ! 78! 9 $ ' ' 4 '' ' 'F ( $ ' ( $ ( ' 4 ( ('( ! I 0--F 78/ :V : ! EO $. " F G F ! F C! 78! 2 ( 4 * ' ' ( '! + * / F 7%8/11%V1% (Z! & E F G F ! 78! 0 ( ( ' ' $ @ ! * 8 " 6 -" -" 4 ! , (= % &F !F / F E X !F %%G ( ( ' ! E F C! 3F 6! 7 ! 0 , 3 %%8! H (X 4 F 7 %8/ 1V ! % G & F 0!F F 0!F "F "!F '+F H!F ' 1F 9! 7 % 8! 9 4 ( ( ' ! !F / F 7%8/11V1 :! ,& E (F %%G F C! 7 %%8! - ( ( + , $ ' / F ! * 8 " 6 . *" 4 ! / E $0 F G F ! 78! 9 @ $ @ ! * 8 " 6 . *" *" 4 ! E' ( F C! 7:8! . (F :G F 9! F ! " ! !F G F C!F ( +F 9!F F .! F ! 78! % > ! ! E !F G - F 0!F 4 F ;!F $F .!F +F 0! tel-00245958, version 1 - 7 Feb 2008 E F &! 78! 0 , $ ' ' ' ( ( 4$ 4 $ ' ' ( ' ! + , 3 . F 78/1 V ! -, , E( & F %G F C! F -! 7 %8! J , T ( ' ! " *" 4 ! -, /,F 3! 7 E( !F %G F C!F F -! ( '' ' ( ( '! E* ! " OF %%%G -5F .! %8! 3 4 / F 7 8! 'F .! 7 %%%8! ! $ !F :G F ;!F /F =!F .&F 3! .F 3! 7:8! . # ! J - 4< / $ 8 /804 KL" " 4 ! /,F 3! 7 %%8! 3 EJ !F %%G F -!F !F -! 4 $ ' / ! +000 + 3 " % F / V ! EJ EJ F %G F -! I$ 4 X ' 6& F ! 7 %8! I ( - 06/ D+" )-! EJ !F %%1G F -!F /,F 3! 'F C! 7 %%18! " F - 3 ,!! (! 3 ! EJ !F G F -!F /,F 3!F 'F C! F C! 78! ; ( ( ' 4 ! , 3 +- %3 -F :/V! (! E-F 1G F J! 718! 9 @ # () ' * + , ! * 8 " + . *" *" 4 ! , : 0 (= 780 E-4 `a4 F %%G F ;! F -! 7 %%8! ; ( 4 ' ( 4 ! 0 , 3 / F 7:8/ V : ! E- - ' F G F =! F 0! 78! B ( ' 4 ' 4 ' ( ! I F 78/ :1V ! F D! 78! ' @2! ! %:G 4 F ;! 7 %:8! * - 3 3 E- F G E-_ ( F - -! " ( ! ' $D '! E F %%G 7 %%8! K2 (! ! 6962$6 ( ( tel-00245958, version 1 - 7 Feb 2008 E-' F G F =! 7 8! 0 ( * +I$( ( ( ( / , , ($ * ! * 8 " 6 ) . 4 ++! + 4 9 E-I !F G F 0!F F ;! F -! 78! 4 4 ( ' ' ' $ ! ( %- F 718/V 1! E- ! !F 1G F .!F &F 9! '&F ! 718! ;I ' ' I ( ! , 3 +- %3 -F 7 8/%V E- 3( F G '! + , .F F 9! 3 . 0 ' ! 78! 2 ' ( F 78/:%V ! *F -! 718! E; !F 1G F !F F M!F F 6! ( ( ( $ ' ! , 3 %- F 78/:V11! :& 9 * + * E;X !F G F 9!F F H! F ! 78! . $ 4 4 X $ $ 4 ' 5 IX ' ! + , 3 . 0 F 7%8/ :%V :! ! - F %1G F 9! 7 %18! ( ! ' ! = ( ;! E;, E; O F G ! - F 80" C! 78! 2 '' ! /, F -!F F 3! E; O$ !F G F C!F F ;! 78! 0$( ' I ( ! + 3 + 0-- %-! %& " % ! /, E; O$ !F 1G F C!F F 3! 9 ( 4 ( ' ' ! F -! 718! + 3 + 0-- %-! )#-" ! ! E; ,F %%:G F -! 7 %%:8! , $ # / ( ! * 8 " + *" 4 ! , (= : :' / E;' !F G F -!F F C! F Y! 78! &( 4 ($ ' 4 ( / I 4 ( ! + , 3 . F 7 8/ V 1! E;' F %%G F 0! 7 %%8! 9( @ @ ' ! * 8 " + *" 4 ! 6,& E( F %%:G F &! 7 %%:8! &( 4 4 ( ( ( $ ' 4 ! + , 3 . 0 F 78/1V ! EC " EC F G "F ;! 79 ) ' : 3 F .! 79 ) 8! 3 . 0 ! 8! 3 '! ! + , 3 . 0 tel-00245958, version 1 - 7 Feb 2008 ' !F G F 9!F F 9! '! + , F \! 718! 0X $ $ ( ' 4 EY' " F 1G F Y! 4 ! + , 3 . F 78/: V :! : & EY F %%:G F ;! 7 %%:8! 2 I$ ' ( ( $ ' 4 ! + , 3 . 0 F 78/:V1! ' E" F %%G F C! 7 %%8! 9 ' 4 $( ' ( '! %- F 78/ V ! E" ' !F $ F %%G F ;!F ' 4 ! . 3! F H! 7 %%8! ; I $X ('( ' 4 O ! +3 F 78/ V /,. E03 ( J F G F H! F J! 78! 9 $ # 4 4 ( ' 4 $ ' ! . .- " 99! /& ;F C! 78! E0( !F G F C!F F J! # ( ' ! 2 8M'+NKO!KE! / / ( F C! 7 E0 ( !F %%:G F 9!F F ! ' 4 , 4 ' ! %V ! E0 F %G & ( * ! /2F C! 7 %8! / 0 %%:8! ; ( 0-- 3HF 7:8/ - ! .< 3 & ; E0 O !F :G F 3!F F C!F F !F F ! F 0! 7:8! $4$ ( $ I 4 O ( 4 ( $ ( ' 4 ( ! I 0--F 78/% V%:! E0 O 4 G / F C!F + F M!F :F C!F /F !F )!F =!F 7,F `! 7 8! # ' ( ( ' !F & F 3! ' ! , 3 - F 78! /,F 3! F -! 7 ( 3 " F - /- - ! E0 ; J F G ! 8! , : / E0 F G F &! 7 8! 3 / $4 ! + . '" '" 4 ! ) (F -! E= ( !F G F H!F ( 4 X $ $ - I F 7 8/V! & (= * 8 " F =! 78! 9 ( $ 4 ! . E2 & F 1G F 0! F ! 718! ; ( ' ( ' $ F ( ! + , 3 . F 78/ %V 1! (+F E.IX X F %11G ( ' ! / 6F M! 7 ! F 78/V: ! %118! 9 4 (F 0! 78! .- - %3 - E. F G ! ' ! tel-00245958, version 1 - 7 Feb 2008 E.( M F :G (, 2 - --! E. X !F %:%G (F ( ' I ( F 78/%V ! F \! ' ! *F "! 7:8! . - * *0 9!F F 9! F .! 7 %:%8! 0 $ / O $ ' ' (! %- = $, EA H(F %%1G F 0! F ! 7 %%18! ; ( ' ( ' $ F $( ! + , 3 . F 78/V! = 7 EA !F G F 0!F F "! F `! 7 8! 9 4 ( ( $ ' F ( ! + , 3 . F 7%8/V :! 1 ' ( !F :G F 9!F F 3! '' ' ' # ! J - 4< 8 /804 KL" " 4 ! E6 1&&F J! E6 M( F %G ( '! +000 F J! 7:8! " ' $ / $ * F Y! 7 %8! 9 F 7:8! " 4 !F G 1 F Y!F $F -! F 3! 7 8! ' @2 : - ! 8 3 - @2! E6 $JO ; ! 1! E6,F %%1G F M! 7 %%18! N ( ( , ! . *" 4 ! # $ * 8 " 6 1 E6 F %%G F M! 7 %%8! ; ( ( ' ' 4 $ ' ! 0 , 3 / F 7:8/:V:%! + E I XF G F &! 78! 0 ( ! ( ( ' ( ' 4 + , ! 0 , 3 / F 7 8/ V ! + E I XF G F &! 78! ' ' ' ( ( $ ' 4 X $ $ 4 '! % -F 7 8/%%V ! , (= : + E I XF :G F &! 7:8! ; ( ( ( ' X $ $ ! + , 3 . F 78/ V! + E I XF 1G F &! 718! 0 $ ( ' X $ $ 4 '! + , 3 . F 78/:%V :! + E I XF 1 G F &! 71 8! ' ' ' ( ( ' X $ $ 4 '! % -F 7:8/ 1V 1! ,+F 3! 7 E ( I F %%G 9 4 IX! E ( I F %%%G &-! ' ! ,+F 3! tel-00245958, version 1 - 7 Feb 2008 7 %%%8! ,+F 3! 78! E ( I F G (! 0 E 0 %%8! ; ( ' O / , 3 / F 7:8/V ! ( X ' $ # F 7 8/1V! , 3 / ; & QX !F :G F H!F F C! F ! Y! 7:8! &( 5 4 ' ( 4 4 ( ( ' ! + , 3 . 0 F 7 8/1V! & E !F G F 3!F F ! F -! 78! 3 X $ $ X $ $ X 4 ! + , 3 . 0 F 7%8/V! && ' E !F G F D!F F -!F F -!F F &! 78! 4 ( ' 4 . .- F 7 8/1V ! & *F \! 1 ( ( '! ' E&' " F 1G F "! F -! 718! 9 ( ' ' $ 4 ( ' (' ( ,! 0 , 3 / F 7 8/ V :! !F %%%G F !F F 6! /F 0! 7 %%%8! P 3 -! YI 9 . ( ! E& !F :G F D!F 6F Y! )&F ! 7:8! . ' ( ' 4 X $ $ ! +. %3 - -F 78/%V%:! E& !F G F ;!F 6+F \! 9&& F ;! 78! .$ E& ' 4 4 X $ $ X X $ $ ! + , 3 . F 78/ V ! E&X !F %%:G &F 0!F /F Y! F &! 7 %%:8! ; ( ' ( 4 ' 4 ' ! +4 +4/% +% +4+. - 7 " ." ' ! E&' !F %%%G F "!F 'F "! )F 6! 7 %%%8! 0 $ ( $ ' 4 ( ( ( 4 + , 4 ' ! * + , 3 42 %3 - F 7 8/1%V%! *0F C! EM4 3( F %%G * ( '! %! .F 0! 7 +000 * %%8! 9 ( ( ( F 7:8/1V , : * . EM 3( F G F "! F 0! 78! ' $ I ( ' # 4 ! F 78/ 1V :! 9 7 "F 0! E\ !F G F ;!F F ?! ' I ( ! ! E\ !F %%1G ' ! +000 V ! 9F 6!F 7F `! I (= $ O ' %- 78! ; ( --F 7:8/V =0F M! 7 + 3 +- %%18! 9 4 ( $ . - F ' >& $ $ >& )4 tel-00245958, version 1 - 7 Feb 2008 E]O !F %%G F "!F F 0! F ! 7 %%8! 9 ( ( 4 ' 7I ( 8! 0 , 3 / F 7 8/V! E]O !F %%1G F "!F F \! F 9! 7 %%18! 9 # ( $ ( ' ' I ( / ! . .- I F 78/1V1! >& 9; E]O \O'QF %%%G F "! F &! 7 %%%8! 9 ( ( $ ' ( 4 $ ! + , 3 . F 718/1%V11! : ' C J ;6=9=` ' 9( @ ! ' 3 "D9 , 063 - J2=&9= tel-00245958, version 1 - 7 Feb 2008 ' "99 $3=6 F !# # ' 3 ( # @ @ @ * P( ! ( @ , , (' $ @ 2 J 7OF 8! " 7$ 8 OF ( O $ @ # '' * ' 7( F $ F F !8! 3 ' , ! '' ! '' 7 $ 8 @ $ 7# 8! " ' @ , $ 5 F F!!! " 4 7 8 # 7 F ( O $ 8 < ! (' R R $ ' OF ! 9# ' , , F 5 R' ' R ! 3 '' $ ! 3 ' 4 ! , * 5 # 4 ! 3 , 4 @ 5 ' * ( / F ' ' F , F!!! 5 # ' . # F 2 F 0$ F 2 F F '' F ! % ' :: tel-00245958, version 1 - 7 Feb 2008 5$ %% . 8 $ 8 NM; M00 %0 ' &( ( I ( ( 4 IX 4 $ ' X $ $ ( ' ! I$ ( I ' ( $ 4 ( ( ' 4 ( ' ' I( 4 7P O 8! &( ( '( 7$( '8 P O $ ( O O ( X O '' ' ' X ' ( ' 7 F 'F F 8! &( ' , ! 9'' ' ($ ! &( I ( ( '( '' ' 7 I ( 8 4 7 # 8! &( ( , 4 ( $( ' ( 4 ( X ' 4 4 F 4 ( X ' 4 F ! &( I 7( '8 # 7 F ( $ ( $ O8 ( ! (' R 4IR ( $( ' ( ' O ( ' 4 P O ! ' ( I F 5 ( 4 R' R ! &( ( X '' ' ( X ( ( '( ! &( ( ( 4 ( ' 4 I ( I ! = , ( 4 4 ( ! &( , I ( ( 4 ( 4 5 O 4 ( 4 ( ( / O ' (F ' ( F ! ON ' . 'F ( 'F 0$( 'F 2 O F 0 $ $ F '' ' F ! tel-00245958, version 1 - 7 Feb 2008 :1 tel-00245958, version 1 - 7 Feb 2008
© Copyright 2021 DropDoc