6

Click here to load reader

Introduction aux problèmes d’ordonnancement · 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

  • Upload
    lediep

  • View
    212

  • Download
    0

Embed Size (px)

Citation preview

Page 1: Introduction aux problèmes d’ordonnancement · 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

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

Page 2: Introduction aux problèmes d’ordonnancement · 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

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

Page 3: Introduction aux problèmes d’ordonnancement · 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

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

Page 4: Introduction aux problèmes d’ordonnancement · 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

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

Page 5: Introduction aux problèmes d’ordonnancement · 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

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

Page 6: Introduction aux problèmes d’ordonnancement · 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

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