UNIVERSITÉ DE BORDEAUX 2ème année Licence Eco-Gestion

Semestre 2 2024/2025

Épisode III : Ordonnancement et coloration

1 Ordonnancement

E XERCICE 1
La mise en service d’un nouvel équipement routier demande la réalisation d’un certain nombre de tâches. Le
tableau ci-dessous représente ces différentes tâches avec leurs relations d’antériorité.

Tâche Description Durée en jours Prérequis

A Marquage CE 6 –
B Certification NF 3 –
C Homologation 6 –
D Déclaration de conformité par le fabricant 2 B
E Attestation d’équivalence 4 B
F Autorisation d’emploi à titre expérimental 3 A, D
G Tests avant la mise en service 1 C, E, F

1. Déterminer le niveau de chacune des tâches.

2. Construire le graphe d’ordonnancement du projet et calculer les dates au plus tôt et au plus tard de
chaque tâche.
3. Quel est le chemin de tâches critiques ? Quelle est la durée minimale de réalisation du projet ?
4. Calculer la marge totale de la tâche E. Quelle est sa signification ?
5. Calculer la marge libre de C. Quelle est sa signification ?

E XERCICE 2
La construction d’un entrepôt nécessite la réalisation des dix tâches suivantes :

Tâche Description Durée en jours Prérequis

A Acceptation des plans 4 –
B Préparation du terrain 2 –
C Commande des matériaux 1 A
D Creusage des fondations 1 A, B
E Commande des portes et fenêtres 2 A
F Livraison des matériaux 2 C
G Coulage des fondations 2 D, F
H Livraison des portes et fenêtres 10 E
I Pose des murs et du toit 4 G
J Mise en place des portes 1 H, I

1. Combien de jours sont nécessaires pour construire l’entrepôt ?

2. Quel est le chemin de tâches critiques ?
3. Calculer les marges libres et totales de chaque tâche. Interpréter.
 E XERCICE 3
Une université a été dotée de postes informatiques et de logiciels. Le président de l’université envisage donc de
transformer une salle de cours en salle informatique. Pour ce projet, les tâches suivantes ont été identifiées :

Tâche Description Durée en jours Prérequis

A Vider la salle de cours et démonter le matériel inutilisé 2 –
B Nettoyer et repeindre la salle 4 A
C Installer les tables et fixer un tableau 1 B
D Commander et réceptionner le matériel de câblage 10 –
E Déballer et contrôler le matériel de cablâge livré 1 D
F Câbler la salle 3 B, E
G Installer et brancher les postes informatiques 1 C, F
H Installer les logiciels, configurer les postes et tester leur fonctionnement 7 G

Le but de cet exercice est de proposer un ordonnancement des tâches, de telle sorte que la salle informatique
soit opérationnelle le plus rapidement possible.
1. Déterminer le niveau de chaque tâche.
2. Construire le graphe d’ordonnancement du projet selon la méthode MPM.
3. Quelle est la durée minimale du projet ? Quel est le chemin critique ?
4. Donner les marges libres et totales de chaque tâche.
5. La réalisation de la tâche B a nécessité 10 jours au lieu de 4 car il a fallu enduire un mur et le laisser
sécher avant de le peindre. Quelle est l’incidence sur la durée du projet ?

2 Coloration

E XERCICE 4
Déterminer le nombre chromatique des graphes suivants et proposer une coloration optimale.

E XERCICE 5
Une faculté doit organiser les horaires des examens. On suppose qu’il y a 7 épreuves à planifier, correspondant
aux cours numérotés de 1 à 7 et que les paires de cours suivantes ont des étudiants communs : 1 et 2, 1 et 3, 1 et
4, 1 et 7, 2 et 3, 2 et 4, 2 et 5, 2 et 7, 3 et 4, 3 et 6, 3 et 7, 4 et 5, 4 et 6, 5 et 6, 5 et 7 et enfin 6 et 7.
Comment organiser ces épreuves de façon qu’aucun étudiant n’ait à passer deux épreuves en même temps et
cela sur une durée minimale ?

E XERCICE 6
Sept étudiants, désignés par A, B, C, D, E, F et G, se sont rendus à la bibliothèque aujourd’hui. Le tableau
suivant précise ≪ qui a rencontré qui ≫ (la bibliothèque étant petite, deux étudiants présents au même moment
se rencontrent nécessairement...).

L’étudiant A B C D E F G
a rencontré l’étudiant D,E D,E,F,G E,G A,B,E A,B,C,D,F,G B,E,G B,C,E,F

De combien de places assises doit disposer la bibliothèque pour que chacun ait pu travailler correctement au
cours de cette journée ?
E XERCICE 7
Un musée est constitué de neuf salles A, B, C, D, E, F, G, H, S, organisées comme suit :

Le conservateur du musée souhaite différencier chaque salle de sa ou ses voisines par la moquette posée au sol.
Combien, au minimum, devra-t-il acheter de types de moquettes différentes ?

E XERCICE 8
Le schéma suivant représente un carrefour autoroutier.

Le tableau suivant précise les ≪ franchissements ≫ possibles de ce carrefour.

En arrivant de A B C D E
il est possible d’aller en C,E A,E,D A,D C,A C,D

Les franchissements A-C et B-E ne peuvent naturellement pas être autorisés simultanément, etc...
1. Modéliser ces incompatibilités à l’aide d’un graphe dont les sommets représentent les franchissements
possibles et les arêtes les incompatibilités entre franchissements.
2. Proposer une coloration du graphe ainsi obtenu.
3. Que peut-on dire d’un ensemble de sommets ayant même couleur ?
4. À quoi peut correspondre le nombre chromatique de ce graphe ?

E XERCICE 9
Appliquer l’algorithme de Welsh et Powell aux graphes ci-dessous :
E XERCICE 10
Un site internet comporte 8 pages, notées A, B, C, D, E, F, G, H reliées entre elles suivant le graphe ci-dessous.

Ainsi, par exemple, à partir de la page A on peut directement accéder aux pages B, C et D. Par contre, la page A
ne permet pas d’accéder directement à la page F.
1. (Révisions) Le technicien souhaite tester les liens de pages. En partant de la page A, est-il possible de
trouver un parcours passant une seule fois par tous les liens de pages ? Justifier la réponse.
2. Pour marquer les changements de page, l’administrateur du site souhaite que deux pages reliées aient
des couleurs différentes. On note χ le nombre minimum de couleurs nécessaires.
(a) Donner un sous-graphe complet d’ordre maximal.
(b) En utilisant la question précédente et à l’aide d’un algorithme, montrer que χ = 3.

E XERCICE 11
Le graphe Γ ci-dessous représente le plan d’un zoo. Le sommet A représente son accès. Les sommets B, C, D, E,
F et G désignent les différents secteurs animaliers de ce zoo. Une arête représente l’allée reliant deux secteurs et
est pondérée par la distance de parcours, exprimée en mètres, entre ces deux secteurs.

Partie 1
Pour mieux visualiser sur le plan les différents secteurs du zoo, on veut les colorier de telle sorte que deux
secteurs adjacents ne soient pas de la même couleur.
1. Quel est le nombre minimun de couleurs nécessaires à la réalisation de ce plan ? Justifier la réponse.
2. Donner un encadrement du nombre chromatique du graphe Γ. Justifier la réponse.
3. Proposer alors une telle coloration.
Partie 2 : révisions...
1. Pour nettoyer les allées, les services techniques du zoo utilisent une balayeuse automobile. Est-il possible
que cette balayeuse n’emprunte chaque allée qu’une fois et une seule ? Si oui, proposer un tel chemin,
sinon justifier votre réponse.
2. Les services de sécurité basés au point A doivent intervenir dans le secteur G. Déterminer, à l’aide d’un
algorithme, l’itinéraire le plus court.

E XERCICE 12
Dans un tournoi d’échecs, chaque joueur doit rencontrer tous les autres. Chaque partie dure une heure.
Déterminer la durée minimum du tournoi dans le cas où le nombre de joueurs est 3, 4, 5 ou 6.