Généralités
Ordonnancement de projets
14
2.1 Ordonnancement de projets (1)
• Projet : un ensemble d'opérations qui doivent permettre
d'atteindre un objectif clairement exprimable et présentant
un certain caractère d'unicité. Exemple : construire une
usine.
• Tâches : opérations qui doivent être effectuées pour que
l'objectif fixé au départ soit atteint.
– Problèmes : jusqu‘à quel niveau de détails ? la fabrication d'une
pièce tout entière ou les opérations élémentaires ?
• Ressources : moyens financiers, matériels, humains
nécessaires pour réaliser les tâches
– consommables : consommées lors de la réalisation d'une tâche
(argent, matières premières)
– renouvelables : ressources qui peuvent redevenir disponibles
(machines, opérateurs).
15
2.2 Types de contraintes
Contraintes entre les tâches
• contraintes de précédence : La tâche A ne peut
commencer avant que la tâche B ne se termine (que trois
jours après la fin de B pour raison de séchage, ou que la
tâche B a été réalisée à 60%).
• contraintes de localisation temporelle : une tâche ne peut
être réalisée que pendant un intervalle de temps précis
(pour des raisons météorologiques, par exemple)
• contraintes disjonctives : Les deux tâches A et B ne peuvent
pas être réalisées simultanément, parce qu‘elles utilisent
le même moyen.
• contraintes cumulatives : Les tâches nécessitent la
présence de ressources pour être réalisées et ces
ressources sont en quantité limitée
16
2.3 Ordonnancement de projets à ressources illimitées – PERT
Graphe PERT (Program Evaluation and Review Technique) ou
graphe potentiel-événement
• Un arc représente une tâche ou une portion de tâche. Il est
orienté dans le sens du déroulement du temps et il va d'un
point événement représentant des débuts ou des fins de
tâches ou des événements particuliers liés au déroulement
des tâches à un autre point événement du même type.
• Evénements particuliers : O et F, instant de début et de fin
des travaux.
17
2.3 Ordonnancement de projets à ressources illimitées – PERT
Exemple : Les opérations dans la construction d'un
ensemble hydro-électrique :
a) Construction des routes d'accès au site,
b) Préparation des carrières et terrassements,
c) Construction d'une cité pour le personnel,
d) Commande du matériel hydraulique et électrique,
e) Construction de la centrale,
f) Construction du barrage et des digues,
g) Construction des galeries et conduites forcées,
h) Montage des machines,
i) Essais.
18
2.3 Ordonnancement de projets à ressources illimitées – PERT
Exemple : Ordre logique de succession des opérations et la
durée de celles-ci chaque opération commence après la
fin de tous ces prédécesseurs
19
2.3 Ordonnancement de projets à ressources illimitées – PERT
Solution
20
2.3 Ordonnancement de projets à ressources illimitées
Graphe potentiel tâches :
Il a été proposé en France par Bernard ROY peu de temps après
le graphe PERT.
• A chaque tâche est associé un sommet représentant l'instant
de début de la tâche.
• S'il y a une contrainte de précédence entre deux tâches, alors
un arc relie les sommets correspondant à ces tâches
• La valeur attribuée à l'arc représente le temps minimum qui
doit s‘écouler entre le début de la tâche origine de l'arc et le
début de la tâche extrémité de l'arc.
21
2.3 Ordonnancement de projets à ressources illimitées
Graphe potentiel tâches :
22
2.3 Ordonnancement de projets à ressources illimitées
Comparaison des deux graphes
• Le graphe potentiel-tâches paraît plus intéressant, moins volumineux.
• Le graphe potentiel-événements présente des difficultés dés que les
problèmes deviennent un peu plus compliqués.
• La tâche c suit la tâche a et la tâche b, alors que la tâche d
ne suit que la tâche a,
23
2.3 Ordonnancement de projets à ressources illimitées
Exemple : calcul des dates de début au plus tôt
et au plus tard
29
2.4 Ordonnancement de projets à ressources consommables
Le problème est similaire au problème
d'ordonnancement de projet à ressources illimitées, sauf
que la réalisation des tâches nécessite des ressources
consommables dont la quantité est limitée au cours du
temps.
30
2.5 Ordonnancement à coût minimal
• La durée de réalisation de certaines tâches peut être réduite,
moyennant un coût qui est fonction de la réduction.
Ex : la réduction est réalisée par des heures supplémentaires
• Méthode PERT coût : Le coût est proportionnel à la réduction
de la durée.
37