Click here to load reader
Upload
lediep
View
212
Download
0
Embed Size (px)
Citation preview
08/11/2015
1
3.1. L’ordonnancement de projet
3.2. Méthodes de résolution
3.3. Quelques variantes
Chapitre 3 : Graphes et application à
l’ordonnancement de projets
III.1. L’ordonnancement de projet (1)
Exemple :
Construction d’un stade *
A quelle date (au plus tôt) le
stade sera-t-il achevé ? =
Quelle est la durée minimale
de construction ?
Données :
Ensemble de tâches
Durée des tâches
Relations de succession
Hypothèse :
Ressources illimitées
Problème central d’ordo
2
Durée en semaines Project scheduling
* Programmation Linéaire, Guéret, Prins, Sevaux, Eyrolles, 2000
III.1. L’ordonnancement de projet (2)
Modélisation
Variables :
Dates de début des tâches
Pourquoi pas les dates de fin ?
2 tâches fictives : (start) et (finish)
Contraintes :
Relations de succession entre tâches :
Relations de succession avec la tâche :
Relations de succession avec la tâche :
Objectif : Minimiser le makespan
minimiser la date de début de la tâche f = minimiser la durée du projet
3
III.1. L’ordonnancement de projet (3)
Modèle mathématique
Données :
Variables :
Contraintes :
Objectif :
Variables réelles : PL
4
08/11/2015
2
III.1. L’ordonnancement de projet (4)
Modélisation par un graphe :
Sommets : dates de début des tâches
Pourquoi pas les dates de fin ?
Arcs : entre 2 dates de début de tâches
Valués par la durée de la relation de succession
Interprétation :
Valeur de l’arc : durée de la tâche « origine » + attente (si existe) entre les 2 tâches
Comment valuer les arcs partant de et les arcs arrivant en ?
Durée totale de l’ordonnancement :
Plus long chemin de la tâche à la tâche
5
Inégalité de potentiels
III.1. L’ordonnancement de projet (5)
Graphe du projet
6 Graphes potentiels-tâches
III.2. Méthode de résolution (1)
Modèle de PL
Simplexe
Modèle de graphe
Algorithme de plus long chemin
Propriété du graphe :
Graphe sans circuit pourquoi ?
Calculer les niveaux
Propager les dates de début au plus tôt par niveau
Algorithme de Bellman sans circuit
7
III.2. Méthode de résolution (2)
Théorème
Il existe un ordonnancement réalisable ssi il n’y a pas de circuit de longueur
positive dans le graphe
Décomposition en niveaux
Initialisation :
Num_Niveau 1; LS Sources (G) ; Niveau(LS) Num_Niveau;
Mise à jour :
Num_Niveau Num_Niveau + 1; G G \ LS;
Itérations :
Tant que G non vide
o LS Sources (G); Niveau(LS) Num_Niveau;
o Num_Niveau Num_Niveau + 1; G G \ LS;
8
Voir Graphes 4 - IS
08/11/2015
3
III.2. Méthode de résolution (3)
Application
9
III.2. Méthode de résolution (4)
Propagation des dates de début au plus tôt
La date de début au plus tôt, notée d’une tâche est égale à
Procédure de calcul pour un graphe sans circuit
Initialisation
Itérations :
Pour tout dans l’ordre des niveaux
Algorithme de Bellman sans circuit
Plus long chemin de vers = date de début au plus tôt de =
Durée totale de l’ordonnancement = fin au plus tôt du projet
10
III.2. Méthode de résolution (5)
Application
11 Durée totale = 64 Ordonnancement au plus tôt
III.3. Quelques variantes (1)
Vu : Ordonnancement au plus tôt
Donne la durée minimale de réalisation du projet ainsi que les dates de début au
plus tôt de toutes les tâches
Chemin critique tâches critiques
Ordonnancement au plus tard
Calculer les dates de début au plus tard des tâches connaissant une date
butoir pour la fin du projet
On se fixe une fin de projet :
La date de début au plus tard, notée d’une tâche est égale à
12
08/11/2015
4
III.3. Quelques variantes (2)
Procédure de calcul pour un graphe sans circuit
Initialisation
Itérations :
Pour tout dans l’ordre inverse des niveaux
ie.
Algorithme de Bellman sans circuit
Plus long chemin de vers dates de début au plus tard
13
III.3. Quelques variantes (3)
Application
14
III.3. Quelques variantes (4)
Marge Totale
La marge totale d’une tâche = retard maximal que peut prendre sans
retarder la fin du projet
Tâches critiques
Tâches ayant une marge totale nulle
Chemin critique
Chemin de à et passant uniquement par des tâches critiques
Rque1 : toutes les tâches du chemin critique sont critiques
Rque2 : il peut y avoir des tâches critiques en dehors du chemin critique
Note : Méthode PERT en gestion de projet
Project Evaluation and Review Technique
15
III.3. Quelques variantes (5)
Ordonnancement de projet avec compression de tâches
La durée de certaines tâches peut être compressée (moyennant des couts)
Un budget total est disponible (30 K€ / semaine d’avance)
Quand peut-on terminer le projet si l’entrepreneur maximise son gain ?
16
Project crashing
08/11/2015
5
III.3. Quelques variantes (6)
Modélisation sous forme d’un programme mathématique
Données :
Variables :
17
III.3. Quelques variantes (7)
Modélisation sous forme d’un programme mathématique
Contraintes :
Objectif :
18
III.3. Quelques variantes (8)
Modélisation / Résolution sous forme de graphes
Même modèle de graphe
Réduire progressivement la durée totale sur le chemin critique
Pour avoir la réduction maximale (ie le gain maximal) :
Sélectionner la compression qui est la moins couteuse.
La méthode est la suivante :
Diminution progressive de 1 unité de temps
Déterminer le ou les chemins critiques
Déterminer les compressions possibles sur ce(s) chemin(s) critique(s)
Sélectionner la compression la moins couteuse
19
III.3. Quelques variantes (9)
Application
20
08/11/2015
6
III.3. Quelques variantes (10)
21
Généralisation des relations de succession
Comment traduire des relations plus générales ?
Contrainte de date de début au plus tôt (Dispo / Release Date)
Contrainte de date de début au plus tard (Délai / Due Date)
III.3. Quelques variantes (11)
22
Contraintes d’antériorité entre paires de tâches
Succession simple
Succession avec attente
Succession avec chevauchement
Succession avec délai maximal
Succession immédiate (no-wait)
Ecrire les contraintes associées
(sous la forme d’inégalités de potentiels)
I J
I J
I J
I
J
I J
III.3. Quelques variantes (12)
23
Exemple :
Problème avec 3 tâches telles que :
Donner les contraintes temporelles
Donner le graphe associé
Succession simple :
III.3. Quelques variantes (13)
24
Contraintes :
Graphe
Rque : pas de circuit de
longueur positive