Complexité des problèmes d’ordonnancement

Ordonnancement : Généralité, spécificités, complexité

Ce premier chapitre est consacré aux connaissances fondamentales sur l’ordonnancement. Nous souhaitons bien que le présent mémoire puisse être parfaitement compris par tout spécialiste d’optimisation combinatoire ou de RO. C’est pourquoi nous avons estimé nécessaire de présenter rapidement dans ce chapitre les définitions et les concepts principaux liés à l’environnement de notre travail. La majorité des problèmes d’ordonnancement se ramènent à des problèmes d’optimisation. C’est pourquoi on s’intéresse aux techniques d’optimisation pour les problèmes d’ordonnancement. L’optimisation est utilisée pour obtenir des performances étendues ou pour rechercher des performances optimales. Elle est également utilisée pour trouver une solution de bonne qualité. Pour les chercheurs, l’ordonnancement a été l’un des problèmes les plus complexes étudiés. Cette dissertation se concentre sur le problème de job-shop qui est un cas particulier des problèmes d’ordonnancement. 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. Dans les systèmes de production, un problème d’ordonnancement se définit comme étant la localisation dans le temps et l’espace la réalisation d’un ensemble de tâches, compte tenu des contraintes temporelles et des contraintes de ressources. Les ateliers de production sont des cellules productrices. Ils exécutent les tâches et assurent la transformation des matières premières en produits finis.

Le problème de Job shop et modes de résolutions

Dans ce chapitre, nous présentons les techniques employées pour la résolution du problème de job shop. Nous y portons un grand intérêt car il est classique et est de plus en plus étudié dans littérature de l’ordonnancement, et de plus en plus d’entreprises optent pour ces types d’ateliers. En effet, le job shop :

– Ces ateliers intègrent en plus du problème d’ordonnancement un problème d’affectation des opérations aux machines ou des gammes aux jobs.

– Il généralise les autres problèmes d’ordonnancement, et donc, un algorithme traitant des problèmes de job shop pourrait résoudre des instances de ces problèmes particuliers.

Un problème d’ordonnancement est défini comme un problème consistant à choisir un séquencement des opérations qui s’exécutent sur un ensemble de machines. Ce choix de séquencement doit comporter l’affectation des ressources aux opérations, ainsi que la minimisation ou la maximisation d’un ou plusieurs critères. Le problème du job shop simple (JSP) s’agit d’un problème NP-difficile ou NP-dur, très difficile à résoudre pratiquement, et pour lequel de nombreuses modélisations existent. Le résoudre consiste à déterminer l’ordre ou le « calendrier » d’exécution de ces opérations en leur attribuant des ressources et des dates de début. Un problème du type job shop est une modélisation d’une unité de production disposant des moyens polyvalents utilisés suivant des séquences différentes en fonction des produits. L’objectif consiste à ordonner la réalisation des produits de manière à optimiser une fonction objective, en respectant un certain nombre de contraintes sur les machines utilisées pour effectuer chaque opération élémentaire entrant dans la fabrication des produits. Dans ce chapitre, nous allons évoquer les principaux problèmes du job shop ainsi que les terminologies associées à ce domaine. Et en second lieu, après avoir défini précisément le problème du job shop, nous étudierons ses principales modélisations, et pour terminer, un état de l’art sur le job shop et le job shop sous contrainte de ressources consommables.

Résolution approchée du job shop :

De nombreuses tentatives de résolution du cas général par un algorithme de liste en utilisant des règles de priorité ont été proposées depuis 1950. Le principe général de ces heuristiques par construction est le suivant : on ordonnance à chaque instant t (où une machine et au moins une tâche sont disponibles) la tâche de priorité maximale conformément à la règle de priorité retenue. Parmi les différentes règles de priorité testées, on peut citer FIFO : sélection de l’opération disponible le plus tôt, SPT : sélection de l’opération de plus petit temps opératoire, MTR : sélection de l’opération ayant le plus grand nombre de tâches restant à exécuter dans sa séquence opératoire et MWKR : sélection de l’opération correspondant à la plus grande quantité de travail restant à exécuter. Parmi les travaux réalisés dans ce sens, on peut citer Lawerence, et une synthèse comparative de Adams, Balas et Zawack, montrant que le dénominateur commun de ces performances en fonction des jeux de données testés.

Plus récemment, ces derniers proposèrent une méthode de résolution approchée de ce même problème, « The Shifting Bottleneck Procedure » dont les résultats sont très satisfaisants même sur des problèmes de taille importante. Le principe de cette méthode est le suivant : partant du problème global, ils ordonnancent localement les machines une à une, chacune de manière optimale (en utilisant la méthode arborescente proposée par Carlier [11] en 1982). Ils propagent pour chaque nouveau séquencement les contraintes résultantes à l’aide du graphe conjonctif associé au problème global. L’ordre dans lequel les machines seront séquencées dépend d’une évaluation des goulets d’étranglement associés à chacune d’entre elles. Chaque fois qu’une nouvelle machine est ordonnancée, ils réoptimisent le séquencement de toute machine déjà ordonnancée dont l’ordre induit peut-être améliorer. Dans la méthode arborescente associée, chaque noeud correspond donc à un sous-ensemble de machines ordonnancées. Dans le but de limiter la taille de l’arborescente générée, une fonction de pénalité, calculé en chaque noeud, mesurant sa déviation par rapport au goulet d’étranglement, et pondérée en fonction de son niveau dans l’arbre de recherche, est utilisé.

Le job shop avec ressources consommable :

Dans ce qui va suivre, nous allons présenter quelques travaux qui ont traité les problèmes d’ordonnancement avec la contrainte de ressource consommable. A.Janiak, C.N.Potts et T.Tautenhahn [30] ont travailler sur un problème d’ordonnancement pour la minimisation de Cmax, où les contraintes de précédences sont imposées, ainsi que les dates de disponibilités de tâches, et qui dépendent d’une ressource additionnelle. Or, la date de disponibilité de chaque tâche est en fonction de la ressource qui lui est allouée avec une quantité déterminée. On rencontre ce genre de problème dans les ateliers de production des feuilles métalliques, l’étape principale est le laminage à chaud, où les tâches sont préchauffées par un gaz durant un certain moment dépendant de l’intensité du flux du gaz avant de passer au laminage. Si les quantités allouées aux tâches sont fixes et déterminées, le problème particulier est équivalant au 1| prec,r |C et, il est résolu par la règle de Jackson O(n²). Les auteurs ont développé différentes heuristiques à ce problème, en fixant un ensemble de valeurs possibles des dates de disponibilités. Le cas le plus simple est lorsque toutes les tâches ont des dates de disponibilités égales. Dans le cas où 2 valeurs sont allouées, le programme est à valeurs et devient un problème de knapsack (sac à dos).

Dans le cas général où k valeurs sont allouées et où les contraintes de précédence sont supprimées ; les auteurs ont montré qu’une LP-relaxation du programme à valeurs entière peut être utilisée pour ordonnancer (n-k) tâches de façon optimale. K.De Bontridder [31] a utilisé des méthodes de recherche locales pour la résolution de problème d’approvisionnement et de planification de la production en présence d’une ressource non renouvelable, dans le problème job shop proposé, les dates de disponibilités, les règles de précédence, les dates de début et de fin des tâches, ainsi que la contrainte de ressource non renouvelable sont imposées, afin de trouver un ordonnancement qui minimise la somme des retards. Dans ce contexte, la ressource est livrée avant l’exécution des tâches, ou est produite par d’autres tâches dans le même système, l’auteur propose une heuristique basée sur « list scheduling » pour ordonnancer et respecter les contraintes de précédence, ensuite il a utilisé une approche de recherche tabou pour trouver un ordonnancement de meilleure qualité. A.Grigiriev, M.Holthuijsen et J.V. De Klundert [28] dans leur article publié en 2005, ont étudié un ensemble de problèmes d’ordonnancement sur une machine en présence des matières premières. Les auteurs ont étudié plusieurs problèmes particuliers à contrainte de matières premières où les temps d’exécution sont unitaires ou égaux.

Deux grandes classes de problèmes sont étudiées, une première a pour objectif la minimisation du plus grand retard Lmax, une deuxième classe a été abordée pour la minimisation du makespan ; Le tableau suivant résume l’ensemble de ces travaux : Les travaux de Carlier et Rinnooy Kan [11] et Carlier [12] associent les ressources consommables aux ressources financières en raison des similarités observées dans les contraintes de disponibilité que ces deux types de ressources induisent. Carlier prouve par la suite que le problème d’ordonnancement de projet (RCPSP) avec des ressources financières et avec des contraintes de précédence arbitraire est polynomial si l’on ne considère pas de machine (ou autre ressource renouvelable) ; Carlier démontre aussi que ce problème devient NP-difficile si l’on admet la production et la consommation de ressources. Patterson et al [41] proposent une procédure exacte pour résoudre le problème d’ordonnancement de projet avec des hypothèses d’interruption des opérations, des contraintes de précédence et de ressources qui peuvent être produites et consommées. Carlier et al [13] ont étudié le problème d’ordonnancement de projet où des unités de ressource peuvent être produites et consommées lors de l’exécution de certains événements. Les autres proposent un algorithme de liste pour minimiser la durée totale d’ordonnancement (makespan).