L’ordonnancement est une branche de la recherche opérationnelle et de la gestion de la production qui vise à améliorer l’efficacité d’une entreprise en termes de coûts de production et de délais de livraison. Les problèmes d’ordonnancement sont présents dans tous les secteurs d’activités de l’économie, depuis l’industrie manufacturière  jusqu’à l’informatique.

La théorie de l’ordonnancement traite des modèles mathématiques mais analyse également des situations réelles fortes complexes. L’ordonnancement est lié à plusieurs secteurs de recherches et d’activités très variés. En informatique, le choix des tâches à envoyer aux processeurs se modélise comme un problème d’ordonnancement. En production, l’ordonnancement consiste à déterminer les séquences d’opérations à réaliser sur les différentes machines de l’atelier. En gestion de projet, ordonnancer, c’est déterminer les dates d’exécution des activités constituant le projet. Chacun de ces contextes nécessite la détermination des caractéristiques propres des tâches et des ressources, le type des décisions à prendre, les modalités d’exécution des tâches par les ressources, qui déterminent des contraintes sur les décisions et aussi les différents critères à optimiser.

Généralités sur l’ordonnancement 

Ordonnancer le fonctionnement d’un système industriel de production consiste à gérer l’allocation des ressources au cours du temps, tout en optimisant au mieux un ensemble de critères . C’est aussi programmer l’exécution d’une réalisation en attribuant des ressources aux tâches et en fixant leurs dates d’exécution .

Ordonnancer peut également consister à programmer l’exécution des opérations en leur allouant les ressources requises et en fixant leurs dates de début de fabrication. D’une manière plus simple, un problème d’ordonnancement consiste à affecter des tâches à des moyens de fabrication au cours du temps pour effectuer un ensemble de travaux de manière à optimiser certain(s) critère(s), tout en respectant les contraintes techniques de fabrication.

L’ordonnancement se déroule en trois étapes qui sont:
– La planification, qui vise à déterminer les différentes opérations à réaliser, les dates correspondantes, et les moyens matériels et humains à y affecter.
– l’exécution, qui consiste à mettre en œuvre les différentes opérations définies dans la phase de planification.
– le contrôle, qui consiste à effectuer une comparaison entre planification et exécution, soit au niveau des coûts, soit au niveau des dates de réalisation.

Ainsi, le résultat d’un ordonnancement est un calendrier précis de tâches à réaliser qui se décompose en trois importantes caractéristiques :
– l’affectation, qui attribue les ressources nécessaires aux tâches,
– le séquencement, qui indique l’ordre de passage des tâches sur les ressources,
– le datage, qui indique les temps de début et de fin d’exécution des tâches sur les ressources.

Les données d’un problème d’ordonnancement

Les différentes données d’un problème d’ordonnancement sont les tâches, les ressources, les contraintes et les critères.

Ainsi, étant donnés un ensemble de tâches et un ensemble de ressources, il s’agit de programmer les tâches et affecter les ressources de façon à optimiser un ou plusieurs objectifs (un objectif correspondant à un critère de performance), en respectant un ensemble de contraintes.

Les tâches
Une tâche est une entité élémentaire de travail localisée dans le temps par une date de début et une date de fin d’exécution et qui consomme des ressources avec des quantités déterminées. Un coût (ou poids) est attribué à une tâche pour estimer sa priorité, son degré d’urgence, ou son coût d’immobilisation dans les système.

On distingue deux types de tâches :
– les tâches morcelables (préemptives) qui peuvent être exécutées en plusieurs fois, facilitant ainsi la résolution de certains problèmes,
– les tâches non morcelables (indivisibles) qui doivent être exécutées en une seule fois et ne sont interrompues qu’une fois terminées.

Les ressources
Une ressource est un moyen technique ou humain, destiné à être utilisé pour la réalisation d’une tâche et disponible en quantité limitée  . On note en général M= {M1, M2,…, Mm} l’ensemble des ressources. Plusieurs types de ressources sont à distinguer .

Les ressources renouvelables
Une ressource est dite renouvelable, si après avoir été utilisée par une tâche ou allouée à une tâche, elle redevient disponible pour les autres tâches en même quantité. La quantité disponible est renouvelée d’une tâche à une autre, elle peut être constante, comme elle peut varier d’une tâche à une autre. Exemples de ressources renouvelables : les machines, les hommes, l’équipement, les processeurs, les fichiers…

On distingue deux types de ressources renouvelables :
– les ressources disjonctives (ou non partageables) : qui ne peuvent exécuter qu’une tâche à la fois (machine, robot) ;
– les ressources cumulatives (ou partageables) : qui peuvent êtreutilisées par plusieurs tâches simultanément (équipe d’ouvriers).

Les ressources non renouvelables :
Une ressource est non renouvelable (ou consommable), si après avoir été utilisée par une tâche, elle n’est plus disponible pour les autres tâches. La consommation globale en cours du temps est limitée, on dit que la ressource est épuisée en l’utilisant. Exemples de ressources consommables: le capital (ou budget), le carburant, l’énergie dans une batterie, la matière première,… Les ressources non renouvelables sont généralement produites dans un système indépendant de la machine sur laquelle les tâches sollicitant cette ressource sont exécutées. Toutefois, certains problèmes peuvent exister où certaines tâches produisent des ressources qui peuvent être consommées plus tard par d’autres tâches. Les ressources non renouvelables peuvent également être stockées dans un ou plusieurs dépôts (entrepôts, magasins ou warehouses) ayant une capacité de stockage. Les ressources peuvent éventuellement avoir un stock initial dans un ou plusieurs dépôts. Durant la consommation des ressources, la condition générale qui doit toujours être satisfaite est que la quantité totale de la ressource demandée par les tâches ne doit pas dépasser la quantité totale disponible.