Bordeaux, mars 2002
Parcourir le cahier 
| 4. Graphes : problèmes d’ordonnancement |
|
| Eric Sopena, Professeur au département Informatique
de l'IUT Bordeaux 1 Bordeaux, mars 2002
Parcourir le cahier
|
La mise en exploitation d’un nouveau gisement minier demande la réalisation d’un certain nombre de tâches. Le tableau suivant représente ces différentes tâches avec leurs relations d’antériorité.
|
Tâche |
Description |
Durée (en jours) |
Tâches antérieures |
|
A |
obtention d’un permis d’exploitation |
120 |
- |
|
B |
établissement d’une piste de 6 km |
180 |
A |
|
C |
transport et installation à pied d’œuvre de 2 sondeuses |
3 |
B |
|
D |
création de bâtiments provisoires pour le bureau des plans, le logement des ouvriers sondeurs |
30 |
B |
|
E |
goudronnage de la piste |
60 |
B |
|
F |
adduction d’eau |
90 |
D |
|
G |
campagne de sondage |
240 |
C,D |
|
H |
forage et équipement de trois puits |
180 |
E,F,G |
|
I |
transport et installation au fond du matériel d’exploitation |
30 |
J,H |
|
J |
construction de bureaux et logements, ouvriers et ingénieurs |
240 |
E,F,G |
|
K |
traçage et aménagement du fond |
360 |
J,H |
|
L |
construction d’une laverie |
240 |
J,H |
¨Déterminez les dates
au plus tôt et les dates au plus tard de chaque tâche.
¨Déterminez le temps minimum de réalisation
de l’ensemble.
(On pourra utiliser ici la méthode des potentiels métra (MPM), puis la méthode
PERT).
Tout ensemble de tâches peut faire l’objet d’un exercice similaire : construction d’un logement, rénovation d’une salle de bains, révisions pour le baccalauréat, etc.
| Fin des exercices sur les problèmes d’ordonnancement |
|
|
Parcourir le cahier
|
La mise en exploitation d’un nouveau gisement minier demande la réalisation d’un certain nombre de tâches. Le tableau suivant représente ces différentes tâches avec leurs relations d’antériorité.
|
Tâche |
Description |
Durée (en jours) |
Tâches antérieures |
|
A |
obtention d’un permis d’exploitation |
120 |
- |
|
B |
établissement d’une piste de 6 km |
180 |
A |
|
C |
transport et installation à pied d’œuvre de 2 sondeuses |
3 |
B |
|
D |
création de bâtiments provisoires pour le bureau des plans, le logement des ouvriers sondeurs |
30 |
B |
|
E |
goudronnage de la piste |
60 |
B |
|
F |
adduction d’eau |
90 |
D |
|
G |
campagne de sondage |
240 |
C,D |
|
H |
forage et équipement de trois puits |
180 |
E,F,G |
|
I |
transport et installation au fond du matériel d’exploitation |
30 |
J,H |
|
J |
construction de bureaux et logements, ouvriers et ingénieurs |
240 |
E,F,G |
|
K |
traçage et aménagement du fond |
360 |
J,H |
|
L |
construction d’une laverie |
240 |
J,H |
¨Déterminez les dates au
plus tôt et les dates au plus tard de chaque tâche.
¨Déterminez le temps minimum de réalisation
de l’ensemble.
(On pourra utiliser ici la méthode des potentiels métra (MPM), puis la méthode
PERT).
En utilisant la méthode MPM, nous obtenons le graphe ci-dessous. Les dates au plus tôt et au plus tard sont calculées « par niveaux »… Les tâches critiques, et le chemin critique sont indiqués en gras. Le temps minimum de réalisation de l’ensemble est lisible sur le sommet FIN : 1170 jours.
Tout ensemble de tâches peut faire l’objet d’un exercice similaire : construction d’un logement, rénovation d’une salle de bains, révisions pour le baccalauréat, etc.
La solution dépendra tout naturellement du problème considéré ;-)