Dans plusieurs cas de la vie réelle, les décisions à prendre sont souvent limités par des exigences spécifiques. Plus important encore, ces contraintes sont généralement problématiques dans la nature. Le processus de prise de décision devient de plus en plus compliqué avec l’augmentation du nombre de contraintes. La modélisation et le développement de méthodologies de solution pour ces scénarios, ont été le challenge pour les chercheurs dès le départ. Différents algorithmes, heuristiques et formulations ont été développés pour différentes catégories de problèmes.

L’ordonnancement est le champ de recherche qui étudie ces catégories de problèmes, c’est une activité très courante dans les milieux de l’industrie entre autres. Tous les jours, des réunions sont programmées, des délais sont fixés pour les projets, les périodes de vacances et de travail sont définies, de maintenance et de mise à niveau des opérations sont prévues, les salles d’opération sont réservées et des jeux de sport sont programmées et les arénas réservés, etc. L’ordonnancement adéquate permet à diverses activités, emplois ou tâches à être exécuter d’une manière organisée, tout en évitant les conflits de ressources. Parmi les exemples d’activités on peut citer les tâches d’une machine qui doit effectuer au cours d’une journée de travail, les opérations de fabrication dans une entreprise de semi conducteurs, etc. L’objectif de l’ordonnancement peut-être la réduction au minimum du temps de remplir toutes les activités, la minimisation du retard des activités qui ne peuvent pas être terminé à temps, l’achèvement des activités les plus importantes sur le temps, la maximisation du nombre de clients ou patients servi, etc.

L’ordonnancement est une fonction essentielle dans la gestion de la production, il détermine ce qui va être fait, quand, où et avec quelles ressources. L’ordonnancement de la production est important dans le plan opérationnel et il est un problème difficile en fonction du nombre de calculs et de contraintes. Il cherche la combinaison optimale pour minimiser le temps de fabrication, les délais des stocks, les temps d’attente des machines et donc le temps d’attente du client. Plusieurs solutions algorithmique, heuristiques et d’adaptation ont été proposées pour divers problèmes d’ordonnancement de production. Dans de nombreux systèmes de production, les jobs de production doivent passer par plusieurs étapes, et à chaque étape, il y a plusieurs machines parallèles avec une puissance de traitement différente pour gérer les jobs. Dans ce chapitre nous présentons les problèmes d’ordonnancement déterministes et leur classification et on illustre la représentation graphique d’une solution. Nous focalisons notre intérêt sur les problèmes à machines parallèles identiques et job shop. Ils modélisent plusieurs problèmes pratiques et théoriques.

Préliminaires 

Généralités et définitions

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. Ordonnancer c’est programmer l’exécution d’une réalisation en attribuant des ressources aux tâches et en fixant leur date d’exécution, de sorte qu’une fonction objectif soit optimisée. La réalisation peut être, un programme informatique ou le carnet de commandes d’un atelier. Alors les tâches sont des processus informatiques ou des traitements à appliquer à certaines pièces par des machines. Les ressources sont alors des processus et de la mémoire ou des machines et du personnel. Établir un ordonnancement revient donc à coordonner l’exécution de toutes les tâches, en utilisant au mieux les ressources disponibles [Chrétienne et al 1988]. Les différentes données d’un problème d’ordonnancement sont les tâches, les ressources, et les contraintes. Dans un système de production, un problème d’ordonnancement se définit comme étant la localisation dans le temps de la réalisation d’un ensemble de tâches T = {T1,T2,…,Tn}, compte tenu des contraintes temporelles (une date de début avec une durée ou une date de fin) et de contraintes portant sur l’utilisation et la disponibilité des ressources M = {M1, M2,…, Mm} requises par les tâches. Dans ce cas, une machine est considérée comme une ressource [Boukef 2009]. Une tâche se définit comme un ensemble d’opérations. Une opération est le passage d’une tâche j sur une machine i et elle est notée (i,j) ou Oij. La durée de traitement ou temps d’exécution d’une opération est son temps de passage sur une machine donnée pij ; c’est-à-dire le temps entre le moment où l’opération débute sur une machine et le moment où elle la quitte. Deux types de tâches sont distingués :
• 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 sont exécutées en une seule fois et ne peuvent pas être interrompues avant qu’elles soient complètement terminées.

Une ressource est un moyen technique ou humain utilisé pour réaliser une tâche. Ce moyen technique est donc nécessaire et indispensable pour le bon fonctionnement du cycle de fabrication. Dans un atelier, plusieurs types de ressources sont distingués :
• Les ressources renouvelables, qui, après avoir été allouées à une tâche, redeviennent disponibles et qui peuvent être réutilisées (machines, personnel, etc.), Lorsqu’elle demeure disponible en même quantité
• Les ressources consommables, qui, après avoir été allouées à une tâche, ne sont plus disponibles, et sont donc épuisées (argent, matières premières, etc.),
• Les ressources partageables qui peuvent être partagées entre plusieurs tâches. Ces ressources peuvent être classées d’une autre manière :
• Les ressources de type disjonctif qui ne peuvent exécuter qu’une opération ou une tâche à la fois.
• Les ressources de type cumulatif qui peuvent exécuter plusieurs opérations simultanément.

Une machine est considérée comme un type de ressource qui n’est caractérisé que par son horaire de travail [Pinedo 2008].

De nombreuses contraintes peuvent être imposées. Les contraintes s’agissent des conditions à respecter lors de la construction d’un ordonnancement pour qu’il soit réalisable. Les contraintes des problèmes d’ordonnancement expriment des restrictions sur les valeurs que peuvent prendre simultanément les variables de décision. On distingue les contraintes temporelles et les contraintes des ressources.
➤ Contraintes temporelles : elles sont relatives aux dates limites des tâches (délais de livraisons, disponibilité des approvisionnements) ou à la durée totale d’un projet.
➤ Contraintes de ressources : elles expriment la nature et la quantité des moyens utilisés par les tâches, les caractéristiques d’utilisation de ces moyens, la disponibilité des ressources et la quantité des moyens disponibles au cours du temps.

Dans un problème classique d’ordonnancement, une machine ne peut exécuter qu’une tâche à la fois et une tâche ne peut être exécutée que sur une machine à la fois. Une affectation des tâches qui respecte les contraintes liées à l’environnement des machines et aux caractéristiques des tâches est dite ordonnancement réalisable. Si l’ordonnancement optimise le critère d’optimalité, il est dit optimal.

Système de production 

Un système de production est constitué d’un ensemble de ressources qui répondent à des objectifs de la production, c’est-à-dire la transformation de matières premières et/ou de composants en produits finis. On distingue quatre types de ressources : les équipements, les hommes, les matières et les informations techniques, procédurales ou relatives à l’état et à l’utilisation du système productif.

Giard [Giard 1988] propose deux types de typologie des systèmes de production : la première est basée sur le fait qu’une production peut être réalisée soit pour répondre à une commande, soit pour alimenter un stock et la seconde est liée à la régulation du monde de la production, ce qui varie en fonction de l’importance et de la variété des flux de produits traités par les systèmes productifs.