Ordonnancement (graphes et projets)

Graphes
Graphes et Projets
et projets
Introduction
1. Introduction
Modélisation
2.
Optimisation
Modélisation
Compléments
3. Optimisation simple
PERT
4. Compléments
1 / 20

---

Graphes
Applications de la théorie des graphes
et projets
Introduction
 Le problème de plus court chemin
Modélisation
 Le problème de transport
 Le problème du flot maximum
Optimisation
 Le problème du voyageur de commerce
Compléments
 Le problème d’ordonnancement
PERT
des tâches d’un projet
 ….
2 / 20

---

Graphes
Ordonnancement des tâches d’un projet
et projets
La réalisation de l’objectif suppose l'exécution
préalable de multiples tâches soumises à de
Introduction
multiples contraintes.
Modélisation
Gestion de projets
Optimisation
Compléments
PERT
Ordonnancement
Il s'agit de trouver un ordre et un
calendrier d'activation de ces tâches tels
que ces contraintes soient satisfaites.
3 / 20

---

Graphes
Exemple
et projets
N° tâche
Description
Durée (en jours)
Introduction
1
Exécution des terrassements
10
2
Mise en place de la grue
2
Modélisation
3
Fondations
5
4
Branchement électrique
3
Optimisation
5
Installation de la fosse septique
6
Compléments
Contraintes
PERT

La grue ne peut fonctionner que si le branchement électrique est
effectué.

On a besoin de la grue pour les fondations.

L'installation de la fosse septique et les fondations ne peuvent
être exécutés que si les travaux de terrassement sont terminés.
4 / 20

---

Graphes
Modèle potentiel-tâches
et projets
Un sommet du graphe correspond à une tâche.
Introduction
On relie deux sommets: i et j par un arc,
Modélisation
si la tâche i doit précéder la tâche j .
Optimisation
10
Compléments
i
j
PERT
Chaque arc (i,j) est porteur d'un "poids"
correspondant à la durée de la tâche i .
5 / 20

---

Graphes
Modèle potentiel-tâches
et projets
Introduction
4
3
Modélisation
0
bcht élec.
Optimisation
0
2
5
0
2
3
6
Compléments
grue
fondations
6
0
10
PERT
10
1
5
terrassements
fosse
6 / 20

---

Graphes
Méthode potentiel-étapes
et projets

Chaque arc correspond à une tâche.
Introduction

Le début et la fin d'une tâche sont les étapes du projet
Modélisation
et correspondent à des sommets du graphe.
Optimisation
Compléments
10
8
1
2
3
PERT
i
j
Représentation des
contraintes de
précédence
7 / 20

---

Graphes
Méthode potentiel-étapes
et projets
B
Introduction
1
terrassements
5
Modélisation
fosse
10
Optimisation
A
6
6
C
Compléments
2
tâche fictive
grue
PERT
3
2
5
4
fondations
bcht élec.
3
D
8 / 20

---

Graphes
Optimisation
et projets
Combien de temps au minimum
pour ce projet ?
Introduction
4
3
Quand démarrer chaque tâche ?
Modélisation
0
bcht élec.
Optimisation
0
2
5
0
2
3
6
Compléments
grue
fondations
6
0
10
PERT
10
1
5
terrassements
fosse
9 / 20

---

Graphes
Mise à niveau des sommets
et projets
Introduction
4
1
3
Modélisation
0
Optimisation
0
2
5
0
2
3
6
Compléments
1
2
3
6
0
10
PERT
10
1
5
1
2
10 / 20

---

Graphes
Recherche du plus long chemin
et projets
0
En vert, les dates au plus tôt
Introduction
4
(As Soon As Possible)
1
3
Modélisation
0
10
Optimisation
0
16
0
2
5
0
2
3
6
Compléments
1
2
3
6
0
10
PERT
0
10
10
1
5
La durée minimale
du projet est
1
2
16 jours.
11 / 20

---

Graphes
Détermination des dates au plus
et projets
tard
0 8

On prend le plus long chemin
Introduction
4
en partant de la fin
1
3
Modélisation
0
0 9
10 1
1

16
Optimisation
16
0
2
5
0
2
3
6
Compléments
1
2
3
6
0
10
PERT
0 0

10 10
10
1
5
1
2
En rouge, les dates au plus tard
(As Late As Possible)
12 / 20

---

Graphes
Marges et tâches critiques
et projets
8
0 8

Introduction
4
1
3
Modélisation
0
9
1
0
0 9
10 1
1

16
Optimisation
16
0
2
5
0
2
3
6
Compléments
1
2
3
6
0
10
PERT
0
0
0 0

10 10
10
1
5
1
2
13 / 20

---

Graphes
Chemin critique
et projets
8
0 8

Introduction
4
1
3
Modélisation
0
9
1
0
0 9
10 1
1

16
Optimisation
16
0
2
5
0
2
3
6
Compléments
1
2
3
6
0
10
PERT
0
0
0 0

10 10
1
10
5
1
2
14 / 20

---

Graphes
Diagramme de Gantt
et projets
Introduction
Modélisation
fosse septique
Optimisation
bcht élec.
Compléments
fondations
PERT
grue
terrassements
temps
0
2
4
6
8
10
12
14
16
15 / 20

---

Graphes
Enrichissements du modèle de base
et projets
Introduction
 Prise en compte du hasard
Modélisation
Méthode P.E.R.T.
Optimisation
 Prise en compte des coûts
Compléments
Méthode C.P.M.
PERT
 Autres types de contraintes
16 / 20

---

Graphes
Méthode P.E.R.T.
et projets
 Program Evaluation and Research Task
Introduction
 On considère que la durée d’une tâche est une variable aléatoire.
Modélisation
 Un modèle de loi couramment employé est la loi Béta
 Pour chaque tâche t, on donne 3 durées
Optimisation
– p(t) = durée la plus probable
Compléments
– a(t) = estimation optimiste
PERT
– b(t) = estimation pessimiste
 l’espérance de la durée de t est (4p(t)+a(t)+b(t))/6
 L’écart-type est (b(t)-a(t))/6
17 / 20

---

Graphes
Exemple de méthode PERT
et projets
N° tâche
Description
p
a
b
1
Exécution des terrassements11 ; 1,67 10
8
18
Introduction
2
Mise en place de la grue
2 ; 0,33
2
1
3
3
Fondations
5,17 ; 0,83 5
3
8
Modélisation
4
Branchement électrique
3 ; 0,33 3
2
4
Optimisation
5
Installation de la fosse septique
6
5
7
6 ; 0,33
Compléments

On calcule l’espérance et l’écart-type de
PERT
chaque durée.

On porte ensuite ces durées espérées sur le
graphe.
18 / 20

---

Graphes
Détermination de la durée espérée
et projets
Théorème central-limite
La durée du projet suit approximativement
une loi normale de moyenne égale à la
Introduction
0
somme des durées espérées des tâches
4
critiques et de variance égale à la somme
Modélisation
3 des variances de ces tâches.
0
Optimisation
0
11
17
Compléments
0
2
5,17
0
2
3
6
PERT
3
0
11
6
0
11
1
11
5
N (17, 1,7)
19 / 20

---

Graphes
Application probabiliste
et projets
P (D<20) ?
Introduction
Modélisation
Optimisation
Compléments
PERT
10
11
12
13
14
15
16
17
18
19
20
21
22
23
20 / 20

---