Theorie de l'ordonnancement


Theorie de l'ordonnancement

Théorie de l'ordonnancement

Page d'aide sur l'homonymie Pour les articles homonymes, voir Ordonnancement.

La théorie de l'ordonnancement est une branche de la recherche opérationnelle qui s'intéresse au calcul de dates d'exécution optimales de tâches. Pour cela, il est très souvent nécessaire d'affecter en même temps les ressources nécessaires à l'exécution de ces tâches. Un problème d'ordonnancement peut être considéré comme un sous-problème de planification dans lequel il s'agit de décider de l'exécution opérationnelle des tâches planifiées.

Sommaire

Définition

Un problème d'ordonnancement consiste à organiser dans le temps la réalisation de tâches, compte tenu de contraintes temporelles (délais, contraintes d'enchaînement) et de contraintes portant sur la disponibilité des ressources requises.

En production (manufacturière, de biens, de service), on peut le présenter comme un problème où il faut réaliser le déclenchement et le contrôle de l'avancement d'un ensemble de commandes à travers les différents centres composant le système.

Un ordonnancement constitue une solution au problème d'ordonnancement. Il est défini par le planning d'exécution des tâches (« ordre » et « calendrier ») et d'allocation des ressources et vise à satisfaire un ou plusieurs objectifs. Un ordonnancement est très souvent représenté par un diagramme de Gantt.

Les tâches

Une tâche est une entité élémentaire localisée dans le temps par une date de début et/ou de fin, dont la réalisation nécessite une durée, et qui consomme un moyen selon une certaine intensité.

Selon les problèmes, les tâches peuvent être exécutées par morceaux, ou doivent être exécutées sans interruption ; on parle alors respectivement de problèmes préemptifs et non préemptifs. Lorsque les tâches ne sont soumises à aucune contrainte de cohérence, elles sont dites indépendantes.

Plusieurs tâches peuvent constituer une activité et plusieurs activités peuvent définir un processus.

Les ressources

La ressource est un moyen technique ou humain destiné à être utilisé pour la réalisation d'une tâche et disponible en quantité limitée, sa capacité.

Plusieurs types de ressources sont à distinguer. Une ressource est renouvelable si après avoir été allouée à une ou plusieurs tâches, elle est à nouveau disponible en même quantité (les hommes, les machines, l'équipement en général); la quantité de ressource utilisable à chaque instant est limitée. Dans le cas contraire, elle est consommable (matières premières, budget) ; la consommation globale (ou cumul) au cours du temps est limitée. Une ressource est doublement contrainte lorsque son utilisation instantanée et sa consommation globale sont toutes deux limitées (l'argent en est un bon exemple).

Qu'elle soit renouvelable ou consommable, la disponibilité d'une ressource peut varier au cours du temps. Sa courbe de disponibilité est en général connue a priori, sauf dans les cas où elle dépend du placement de certaines tâches génératrices.

On distingue par ailleurs ­ principalement dans le cas de ressources renouvelables ­ les ressources disjonctives qui ne peuvent exécuter qu'une tâche à la fois (machine-outil, robot manipulateur) et les ressources cumulatives qui peuvent être utilisées par plusieurs tâches simultanément ­ mais en nombre limité ­ (équipe d'ouvriers, poste de travail).

Les contraintes

Les contraintes expriment des restrictions sur les valeurs que peuvent prendre simultanément les variables de décision. On distingue :

  • des contraintes temporelles
    • les contraintes de temps alloué, issues généralement d'impératifs de gestion et relatives aux dates limites des tâches (délais de livraisons, disponibilité des approvisionnements) ou à la durée totale d'un projet ;
    • les contraintes de cohérence technologique, ou contraintes de gammes, qui décrivent des relations d'ordre relatif entre les différentes tâches ;
  • des contraintes de ressources
    • les contraintes d'utilisation de ressources qui expriment la nature et la quantité des moyens utilisés par les tâches, ainsi que les caractéristiques d'utilisation de ces moyens ;
    • les contraintes de disponibilité des ressources qui précisent la nature et la quantité des moyens disponibles au cours du temps. Toutes ces contraintes peuvent être formalisées sur la base des distances entre débuts de tâches ­ ou potentiels.

Les objectifs

Dans la résolution d'un problème d'ordonnancement, on peut choisir entre deux grands types de stratégies, visant respectivement à l'optimalité des solutions, ou plus simplement à leur admissibilité.

L'approche par optimisation suppose que les solutions candidates à un problème puissent être ordonnées de manière rationnelle selon un ou plusieurs critères d'évaluation numériques, construits sur la base d'indicateurs de performances. On cherchera donc à minimiser ou maximiser de tels critères. On note par exemple ceux

  • liés au temps :
    • le temps total d'exécution ou le temps moyen d'achèvement d'un ensemble de tâches
    • le stock d'en-cours de traitement
    • différents retards (maximum, moyen, somme, nombre, etc.) ou avances par rapport aux dates limites fixées ;
  • liés aux ressources :
    • la quantité ­ totale ou pondérée ­ de ressources nécessaires pour réaliser un ensemble de tâches
    • la charge de chaque ressource ;
    • liés à une énergie ou un débit ;
    • liés aux coûts de lancement, de production, de transport, etc., mais aussi aux revenus, aux retours d'investissements.

Problèmes classiques

Références

  • Joseph Y-T. Leung, Handbook of Scheduling: Algorithms, Models, and Performance Analysis, Chapman & Hall/CRC Computer & Information Science Series, 2004.
  • J. Carlier et Ph. Chrétienne, Problèmes d'ordonnancement : modélisation, complexité, algorithmes, Masson, Paris, 1988.
  • Philippe Baptiste, Emmanuel Néron, Francis Sourd, Modèles et algorithmes en ordonnancement, Ellipses, Paris, 2004.
  • Gustave Gotheil, "Théorie de l'ordonnancement du pélec", Technosup, Rennes, 2006
Ce document provient de « Th%C3%A9orie de l%27ordonnancement ».

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Theorie de l'ordonnancement de Wikipédia en français (auteurs)

Regardez d'autres dictionnaires:

  • Théorie de l'ordonnancement — Pour les articles homonymes, voir Ordonnancement. La théorie de l ordonnancement est une branche de la recherche opérationnelle qui s intéresse au calcul de dates d exécution optimales de tâches. Pour cela, il est très souvent nécessaire d… …   Wikipédia en Français

  • Ordonnancement de tâches — Théorie de l ordonnancement Pour les articles homonymes, voir Ordonnancement. La théorie de l ordonnancement est une branche de la recherche opérationnelle qui s intéresse au calcul de dates d exécution optimales de tâches. Pour cela, il est très …   Wikipédia en Français

  • Ordonnancement de taches informatiques — Ordonnancement de tâches informatiques Pour les articles homonymes, voir Ordonnancement. L ordonnancement de tâches informatiques concerne exclusivement la manière de lancer des traitements (batchs) sur un ou plusieurs composants de son système d …   Wikipédia en Français

  • Ordonnancement dans les systemes d'exploitation — Ordonnancement dans les systèmes d exploitation Pour les articles homonymes, voir Ordonnancement. Dans les systèmes d exploitation, l’ordonnanceur désigne le composant du noyau du système d exploitation qui choisit les processus qui vont être… …   Wikipédia en Français

  • Theorie des graphes — Théorie des graphes  Pour la notion mathématique utilisée en Théorie des ensembles, voir Graphe d une fonction. La théorie des graphes est une branche commune à l informatique et aux mathématiques étudiant les graphes et les objets qui lui… …   Wikipédia en Français

  • Theorie de la complexite — Théorie de la complexité des algorithmes La théorie de la complexité des algorithmes étudie formellement la difficulté intrinsèque des problèmes algorithmiques. Sommaire 1 Histoire 2 Généralités 2.1 Présentation …   Wikipédia en Français

  • Theorie des types — Théorie des types La théorie des types est une branche de la logique mathématique qui a pour principales caractéristiques que tout objet (terme, fonction, ensemble) y a un type et que les entités ne peuvent se combiner qu en respectant des règles …   Wikipédia en Français

  • Theorie des langages — Théorie des langages La théorie des langages a pour objectif de comprendre le fonctionnement des langages, vus comme moyen de communication, d un point de vue mathématique. Un langage est un ensemble de mots. Un mot (ou lexème) est une… …   Wikipédia en Français

  • Théorie des langages et automates — Théorie des langages La théorie des langages a pour objectif de comprendre le fonctionnement des langages, vus comme moyen de communication, d un point de vue mathématique. Un langage est un ensemble de mots. Un mot (ou lexème) est une… …   Wikipédia en Français

  • Ordonnancement — Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom. Sommaire 1 Administration 2 Théorie 3 …   Wikipédia en Français


We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.