Cours et Exercices d'Ordonnancement de Tâches en Recherche Opérationnelle
Introduction à l'ordonnancement de tâches
Ce document académique propose une étude approfondie de l'ordonnancement de tâches dans le domaine de la recherche opérationnelle. Conçu sous forme de cours comportant de nombreux exercices et problèmes pratiques, il aborde la gestion des contraintes de précédence, l'affectation de tâches sur des processeurs ou des ouvriers, ainsi que les méthodes de résolution exactes ou approchées.
Structure et grands thèmes du document
Le cours s'ouvre sur une étude de cas concrète autour de la construction d'une maison comprenant plusieurs tâches interdépendantes de durée unitaire. Cette mise en situation permet d'illustrer la complexité de l'organisation temporelle selon le nombre d'ouvriers disponibles. Par la suite, le document explore les différentes situations d'ordonnancement selon le nombre de processeurs, qu'il s'agisse d'un processeur unique, d'un nombre illimité de processeurs ou du cas plus complexe à deux processeurs et à processeurs multiples.
Plusieurs algorithmes majeurs sont présentés et analysés en détail, notamment l'algorithme de liste, l'algorithme de Coffman-Graham et l'algorithme de Fuji et al. Le texte aborde également des notions fondamentales telles que les extensions linéaires, les antichaînes, les ordonnancements tassés à gauche, ainsi que des méthodes arborescentes basées sur le principe du branch and bound.
Méthodes polynomiales, PERT et graphes potentiel-tâches
Une partie importante du document est consacrée aux méthodes polynomiales et pseudo-polynomiales, en particulier pour les tâches morcelables ou avec préemption. Les lecteurs y découvrent le fonctionnement des machines identiques, des machines distinctes, ainsi que l'application de la programmation linéaire et du théorème de Birkhoff-Von Neumann.
Le document détaille également la modélisation par graphe potentiel-tâche, proche de la méthode PERT, qui permet de représenter des contraintes temporelles sous forme d'inéquations et d'optimiser la durée totale d'un projet. Les notions de chemins critiques, de potentiels calés à gauche et à droite, ainsi que l'étude de faisabilité basée sur l'absence de cycles de valeur positive y sont rigoureusement démontrées.
Bibliographie et références bibliographiques
Le contenu s'appuie sur des références reconnues en recherche opérationnelle, notamment l'ouvrage de référence de J. Carlier et P. Chrétienne intitulé Problèmes d'ordonnancement, Modélisation, Complexité, Algorithmes, publié dans la collection Études et recherches en informatique.
Questions fréquentes
Quel est le sujet principal de ce document ?
Le document traite de l'ordonnancement de tâches sous contraintes de précédence en recherche opérationnelle, en étudiant des algorithmes pour un ou plusieurs processeurs, ainsi que des méthodes polynomiales comme les graphes potentiel-tâches.
Quels types d'algorithmes sont étudiés pour les processeurs multiples ?
Le cours analyse notamment les algorithmes de liste, l'algorithme de Coffman-Graham avec calcul de priorités récursives, ainsi que l'algorithme de Fuji et al. basé sur la couverture en antichaînes.
Comment sont modélisées les contraintes temporelles sans ressources ?
Le document utilise des graphes potentiel-tâches où les sommets représentent les tâches et les arcs symbolisent des contraintes potentielles de type différences entre dates de début, permettant de se ramener à des problèmes de plus court chemin ou de flot.
Testez vos connaissances
Question 1
Comment appelle-t-on une énumération des tâches t1, ..., tn telle que si la tâche ti précède tj, alors i < j ?
- Une coupe optimale
- Une extension linéaire
- Une antichaîne maximale
- Un graphe potentiel-tâche
Réponse correcte : Une extension linéaire
Explication : Le texte définit une extension linéaire comme une énumération des tâches respectant l'ordre partiel des contraintes de précédence.
Question 2
Quelle est la condition nécessaire et suffisante sur un graphe potentiel-tâche pour qu'il existe une solution faisable ?
- Le graphe doit contenir un cycle hamiltonien.
- Le graphe ne doit pas contenir de cycles de valeur strictement positive.
- Le nombre de tâches doit être supérieur au nombre de processeurs.
- Tous les coefficients des arcs doivent être nuls.
Réponse correcte : Le graphe ne doit pas contenir de cycles de valeur strictement positive.
Explication : Le théorème présenté dans le document indique qu'il existe une solution faisable si et seulement si le graphe potentiel-tâche n'a pas de cycles de valeur strictement positive.
Question 3
Qu'est-ce qu'un ordonnancement tassé à gauche selon la définition du cours ?
- Un ordonnancement où toutes les tâches sont exécutées en même temps.
- Un ordonnancement où il n'y a pas de date avec un processeur inactif alors qu'il restait des tâches disponibles.
- Un ordonnancement réservé exclusivement aux machines indépendantes.
- Un ordonnancement sans aucune contrainte de précédence.
Réponse correcte : Un ordonnancement où il n'y a pas de date avec un processeur inactif alors qu'il restait des tâches disponibles.
Explication : Le cours précise qu'un ordonnancement est tassé à gauche lorsqu'aucun processeur n'est inactif s'il restait des tâches disponibles à cette date.
Télécharger Cours et Exercices d'Ordonnancement de Tâches en Recherche Opérationnelle pdf
