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