Cet ouvrage et des milliers d'autres font partie de la bibliothèque YouScribe
Obtenez un accès à la bibliothèque pour les lire en ligne
En savoir plus

Partagez cette publication


AVERTISSEMENT



Ce document est le fruit d’un long travail approuvé par le jury de
soutenance et mis à disposition de l’ensemble de la communauté
universitaire élargie.
Il est soumis à la propriété intellectuelle de l’auteur au même titre que sa
version papier. Ceci implique une obligation de citation et de
référencement lors de l’utilisation de ce document.
D’autre part, toute contrefaçon, plagiat, reproduction illicite entraîne une
poursuite pénale.

Contact SCD INPL : scdinpl@inpl-nancy.fr




LIENS




Code de la propriété intellectuelle. Articles L 122.4
Code de la propriété intellectuelle. Articles L 335.2 – L 335.10
http://www.cfcopies.com/V2/leg/leg_droi.php
http://www.culture.gouv.fr/culture/infos-pratiques/droits/protection.htm
D´epartement de formation doctorale en informatique
Institut National ´Ecole doctorale IAEM Lorraine
Polytechnique de Lorraine
Optimisation de l’ordonnancement sous
contrainte de faisabilit´e
`THESE
pr´esent´ee et soutenue publiquement le 26 octobre 2007
pour l’obtention du
Doctorat de l’Institut National Polytechnique de Lorraine
(sp´ecialit´e informatique)
par
Mathieu Grenier
Composition du jury
Pr´esident : Maryline Silly-Chetto
Rapporteurs : Pascal Richard
Gilles Muller
Examinateurs : Franc¸oise Simonot-Lion
Nicolas Navet
St´ephan Merz
Maryline Silly-Chetto
Jo¨el Goossens
Laboratoire Lorrain de Recherche en Informatique et ses Applications — UMR 7503Mis

la
en
thloria.
page
avecRaoul
déplacemen
Reb
Remerciemen
vier
ts
de
Cette
l'enseignemen
thèse

a
F
été
i
réalisée
Je
au
leurs
sein
p
de
tiens
l'équip
our
e
our
T
Lu,
emps
les
Réel
v
et
mon
In
Jean-Pierre
terOp
hel
érabilité

(TRIO)
merci
du
informa-
LORIA
gestion
dirigée
p
par
San
F
visés
rançoise
Ha
Simonot-Lion.
Jia
Mes
Boughami,
plus
Sh
vifs
Hub
remerciemen
de
ts
our
v
fait
on
er
t
de
à
égalemen
F
Xa
rançoise
et
Simonot-Lion
p
et
et


Na
Un
v

et
ses
mes
lors

et
de
e.
thèse
à
sans
leur
qui


Marques
thèse

n'aurait
senior),
pu
mougin,
ab
et
outir.
rozzen
Leur
Fla
appui
Na
et
Li,
l'in
Ch
térêt
(dit
qu'ils
Philipp
on
et
t
mem
manifestés
e
à
p
mon
m'a
égard
oir
m'on
l'honneur
t
particip
p
à
ermis
jury
de
thèse.
réaliser
remercie

t
thèse
Thomesse,
dans
vier
les
euf
meilleures


Dufner
Ils
our
m'on

t
leur

oration
b
t
eaucoup
t.
de
grand
temps
à
et
Benini
de
our

précieuses

tions
qui
des
m'a
ts
p
la
ermis
administrativ
d'améliorer
Je
l'organisation
aussi
de
remercier
mes
our

agréables
herc
Liliana
hes

et
tos
la
(p

leurs
de
a
mes
de
idées.
Xa
Je
Grand-
tiens
Lionel
à
v
exprimer
(p
mes
F
vifs
bubbles),
remerciemen
Ning,
ts
via
à
elicioni,
Madame
jet
Maryline
Jian
Silly-Chetto
Liping
et
Chen
Messieurs
ung
P
ue

Calvin),

Brito,
hard,
e
Gilles
ert
Muller,
tous
Jo
autres
ël
bres
Go
l'équip
ossens,
TRIO.
Stéphan
MerziiEt
famille.
toute
A
soutien.
Emilie
à
p
ma
our
iii
soniv2.2.3
.
.
able
.
des
.
matières
.
P
.
artie
12
I
d'algorithmes
In
.
tro
.


Chapitre
2.2.1
1
.
Con
.
texte
.
et
.
problématique
.
1.1
.
T
.
emps
.
réel
.
et
.

.
t
.
.
paramètres
.
Syn
.
.
.
paramètres
.
.
.
de
.
.
.
.
.
.
.
.
.
des
.
.
.
des
.
.
.
Conclusion
.
.
.
.
.
.
.
.
.
.
.
9
.
.
.
.
.
.
.
.
.
a
.
p
.
.
.
de
.
.
.
.
3
11
1.1.1
.
Dénitions
.
du
.
temps
nouv
réel
.
.
.
.
.
.
t
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
1
.
.
.
.
.
.
.
.
.
.
.
.
.
Optimisation
4
.
1.1.2
.

.
t
.
temps
.
réel
.
.
.
.
.
.
délisation
.
t
.

.
diques
.
.
.
11
.
l'ensem
.
hes
.
.
.
.
.
.
.
.
.
.
.
Ajuster
.

.
.
.
.
.
.
.
.
.
.
.
Utilisation
.
mo
.
hes
.
.
.
.
.
.
4
.
1.1.3
.
Classication
olitiques
des
.
algorithmes
.

.
t
.
.
.
.
.
.
2.2.4
.
t
.
.
.
.
.
.
.
.
.
2.2.4.1
.
.
.
.
.
.
.
.
.
.
.
.
.
.
5
2.2.4.2
1.2
.
Mo
.
délisation
.
du
.
système
.
.
.
.
.
.
15
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
2.2
.
de
.
t
.
.
.
.
.
.
.
.
5
.
1.2.1
.
Système
.
mono-pro
.

.
:
.
mo
.
dèle
.
de
.

.
he
10
.
Mo
.
et
.
justemen
.
des
.
des
.
hes
.
ério
.
.
.
.
.
.
.
.
.
2.2.1.1
.
thétiser
.
ble
.

.
.
.
.
.
.
.
.
6
.
1.2.2
.
Système
.
distibué
.
:
.
mo
.
dèle
.
de
2.2.1.2
ux
les
.
des
.
hes
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
2.2.2
.
de
.
eaux
.
dèles
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
7
.
1.2.3
.
Génération
13
aléatoire
P
des

ensem
en-ligne
bles
.
de
.

.
hes/ux
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
13
.
Construction
.

.
.
.
.
.
.
.
.
.
.
.
.
7
.
1.3
.
Problématique
.
traitée
14
.
Métho
.
hors-ligne
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
14
.
Métho
.
en-lignes
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
2.3
.
.
.
.
.
.
7
.
Chapitre
.
2
.
État
.
de
.
l'art
.
2.1
.
F
.
aisabilité
.
et
.
optimalité
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
15
.
T
.onse

.
T
.
able
34
des
.
matières
.
Chapitre
.
3
.
Présen
.
tation
.
des
36


tributions
Conclusion
3.1
sous
Optimisation

d'une
.
messagerie
.
sur
.
bus
t
priorisé
.
(c
.
hapitre
.
4)
.
.
.
.
.
.
.
.
.
.
4.5.1
.
.
.
sous
.
.
.
de
.
érimen
.
.
.
.
.
.
.
.
.
34
17
.
3.2
p
Nouv
.
elles
ulation
p
.
olitiques
.
à
.
priorité
de
xe
.
dans
.
les
.
systèmes
.
oset
.
free
.
(c
.
hapitre
.
5)
.
.
2
.
temps
.
el
.
.
.
temps
18
ec
3.3
.
Conguration
Pire

a
t
.
sous
.
P
.
osix
.
1003.1b
.
(c
.
hapitre
.
6)

.
.
.
.
.
.
.
.
.
en
.
.
.
.
.
35
.
.
.
.
.
.
.
4.6.2.2
19
.
P
.
artie
.
I

I
.
Con
.
tributions
.
Chapitre
de
4
.
Optimisation
.
d'une
4.6.3.1
messagerie
.
sur
.
bus
.
priorisé
4.6.3.2
4.1
.
In
.
tro
.

Résultats
.
.
.
.
.
.
.
.
.
ectiv
.
.
.
.
.
.
.
.
.
.
.
du
.
rép
.
:
.
.
.
.
.
.
.
4.5.2
.
rép
.
a
.
erreurs
.
.
.
.
.
32
.
de
.
NP-DD
.
ec
.
dage
.
.
.
.
.
4.6
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

23
he
4.2
.
Etat
.
de
.
l'art
.
.
.
.
.
.
.
.
.
.
P
.
de
.
.
.
.
.
.
.
.
.
.
.
Critères
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
de
.
.
.
.
.
.
.
.
.
.
.
.
.
36
.
paramétres
.
.
.
.
.
.
.
.
.
.
.
.
.
P
.
b
.

.
.
.
.
.
.
.
.
25
erçu
4.3
.
Mo
.
délisation
.
du
.
système
.

.
.
.
.
de
.
.
.
.
.
.
.
.
.
.
.
.
.
40
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
40
.
p
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
26
30
4.3.1
Analyse
Mo
pire
dèle
de
du
onse

NP-EDF
.
rapp
.
.
.
.
.
.
.
.
.
.
.
.
.
31
.
Pire
.
de
.
onse
.
NP-EDF
.
v
.
des
.
de
.
dage
.
.
.
.
.
.
.
.
.
4.5.3
.
temps
.
rép
.
sous
.
A
.
v
.
erreurs
.

.
.
.
.
.
.
.
.
.
.
.
33
.
Exp
26
tations
4.3.2
.
Dénition
.
de
.
l'allo
.

.
des
.
priorités
.
a
.
v
.
ec
.
les
.
fonctions
.
de
.
priorités
.
.
.
.
.
.
.
.
.
.
.
.
4.6.1
26
de
4.4
herc
Domaine
.
d'étude
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
4.6.2
.

.
regard
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
4.6.2.1
.
de
.

.
.
.
.
.
.
.
.
.
.
.
.
27
.
4.4.1
.
P
.
olitiques
.
non-préemptiv
.
es
.
.
35
.
Conditions
.
sim
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
4.6.2.3
.
des
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
28
.
4.4.2
.
P
4.6.3
olitiques


la
t



p
.
our
.
le
.
temps
.
réel
.
.
.
.
.
.
.
.
38
.
Ap
.
de
.

.
.
.
.
28
.
4.4.3
.

.
de
.

.
herc
.
he
.
.
.
.
.
.
.
.
39
.
Critères
.
p
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
4.6.3.3
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
29
.
4.5
.
Analyse
.

.
t
4.7
des
et
p
ersp
olitiques
es
NP-DD
.
A
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
40
.
..
sous
.
Chapitre
.
5
.
Nouv
.
elles
.
p
el
olitiques
.
à
.
priorité
.
xe
.
dans
.
les
.
systèmes
.
oset
osix
free
.
5.1
.
In

tro
.

éhicules
.
.
.
.
.
.
.
.
.
.
.
t
.
du
.
.
.
.
.
.
.
.
.
A
.
et
.
6.4
.
.
.
60
.
.
.
temps
.
.
.
rép
.
64
.
.
.
relativ
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
1003.1b
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
[
.
.
43
.
5.2
:
Allo
.

.
des
.
osets
.
:
.
rapp
quan
el
3
.
.
.
.
.
au
.
.
.
.
.
61
.
.
.
.
.
.
.
Minimiser
.

.
.
.
érimen
.
.
.
.
.
64
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
6
.
6.1
.
.
.
.
.
.
.
.
.
.
45
t
5.2.1
et
Allo
.

.
optimale
1003.1b
d'oset
.
.
.
.
69
.
.
.
.
.
.
.
.
.
6.2.3
.
.
.
.
.
.
.
.
.
.
.
t
.
.
.
.
.

.
de
.
.
.
Algorithme
.
tum
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
45
.
5.2.2
.
Allo
optimal

aux
"Dissimilar
.
oset"
.
.
.
.
.
.
.
.
.
.
Des
.
dèle
.
.
.
.
.
.
.
.
.
.
.
Analyse
.
rép
.
.
.
.
.
.
.
.
.
.
.
63
.
temps
.
:
.
messageries
.
.
.
.
.
Conditions
.
.
.
.
46
.
5.3
.
Réduire
.
la
.

P
dans
des
le
.

.
préemptif
.
.
.
.
5.7
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
65
.

.
osix
.
tro
.
.
.
.
.
.
.
.
.
.
.
.
.
.
47
.
5.3.1
.
Propriétés
.
de
6.2

P
t
mo
à
.
priorité
.
.
.
.
.
.
6.2.1
.
P
.
.
.
.
.
.
.
.
.
.
.
.
.
Mo
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
47
othèses
5.3.2
.
Algorithme
.
d'Audsley
.
a
.
v
.
ec
.
des
.
osets
.
xés
.
.
6.2.4
.
analyse
.
P
.
.
.
.
.
.
.
.
.
71
.
sous
.
:
.
.
.
.
.
.
.
73
.

.
du
.
t
.
.
.
.
.
.
48
6.3.1
5.3.3
.
Utilisation
.
de
.
Audsley
.
p
.
our
.
réduire
.

6.3.2
de
.

.
herc
.
he
.
sous
.
un
.

.
men
.
t
d'allo
préemptif

.
sp
.
hes
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
5.6.2.2
.
ux
.
mo
.
de
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
5.6.2.3
.
des
.
de
.
onse
.
.
.
.
.
.
50
.
5.4
.
Nouv
.
elles
.
heuristiques
.
d'allo
.

.
d'oset
.
.
5.6.3
.
les
.
de
.
onse
.
le
.
des
.
v
.
.
.
.
.
.
.
.
.
5.6.3.1
.
d'exp
.
tation
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
51
.
5.5
5.6.3.2
Exp

érimen
es
tations
heuristiques
:
.
le
.

.
mono-pro
.

.
préemptif
.
.
.
.
.
.
64
.
Conclusion
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
52
.
5.5.1
.
Algorithme
.
d'Audsley
.
p
.
our
.
réduire
.
la
Chapitre

Conguration
.
t
.
P
.
1003.1b
.
In
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
52
.
5.5.2
.
Améliorer
.
la
.
faisabilité
.
a
.
v
.
ec
.
les
.
systèmes
67
à

oset
sous
free
osix
.
:
.
dèle
.
propriétés
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
69
.

.
sous
.
osix
55
.
5.5.3
.
Utilisation
.

.
binée
.
des
.
heuristiques
.
:
.

.
a
.
v
.
ec
.
l'optimal
6.2.2
.
dèle
.
système
.
.
.
.
.
.
.
.
.
.
56
.
5.5.4
.
P
.

.
relativ
.
es
.
des
.
heuristiques
.
.
.
.
.
.
.
.
70
.
Hyp
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
56
.
5.6
.
Exp
71
érimen
Rapp
tations
:
:

le
sous

osix
distribué
1]
non-préemptif
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
6.2.5
.
t
.
P
.
1003.1b
.
propriétés
.
base
.
.
.
.
.
.
.
.
.
.
.
.
.
6.3
59
d'allo
5.6.1
optimale
Dénition

des
quan
systèmes

oset
.
free
.
dans
.
le
.

.
distribué
.
.
.
.
75
.
Algorithme
.
udsley-RR-FPP
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
59
.
5.6.2
.
T
.
emps
.
de
.
rép
76
onse
Complexité
dans
amélioration
les
.
systèmes
.
oset
.
free
.
distribués
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
78
.
Algorithme
.

60
:
5.6.2.1
du
Mo
tum
dèle
écique
des


.
.
.
.
.
.
.
.
80
.
.