Problème d’ordonnancement
Un problème d’ordonnancement se pose lorsqu’il s’agit d’organiser dans le temps, l’exécution de diverses tâches soumises à des contraintes et auxquelles sont attribuées des ressources, de manière à satisfaire un ou plusieurs objectifs donnés .
Une solution au problème d’ordonnancement décrit l’exécution des tâches et l’allocation des ressources au cours du temps : il faut décider, à la fois, quelles ressources réalisent les tâches et quand.
Très fréquemment en ordonnancement de production, les problèmes à résoudre consistent à ne déterminer que le positionnement des tâches dans le temps, le problème d’affectation de ces tâches aux ressources étant résolu en amont. On parle parfois de problème d’ordonnancement «pur». Ce positionnement peut être relatif (on détermine le séquencement des tâches sur les ressources) ou absolu (on fixe les dates de réalisation des tâches). Bien qu’en pratique, il semble difficile de faire abstraction de l’allocation de ressources, l’étude de ce cas a toutefois permis le développement de plusieurs méthodes génériques qui ont été utilisées dans l’étude de problèmes d’ordonnancement avec flexibilité des ressources.
Dans ce mémoire, nous parlons de problème d’ordonnancement flexible lorsqu’il s’agit de déterminer les dates de début et/ou de fin des tâches ainsi que les ressources permettant leur exécution.
Les problèmes d’ordonnancement se rencontrent dans divers domaines. Citons par exemple : les systèmes informatiques, où les tâches représentent les programmes et les ressources sont les processeurs ou la mémoire, la gestion de production, la conception des emplois des temps, etc. Les caractéristiques des problèmes d’ordonnancement peuvent dépendre du contexte ; toutefois, on peut dégager des éléments de base qui sont les tâches, les ressources, les contraintes et les objectifs à réaliser ainsi que les critères d’évaluation, définis tour à tour ci-après.
Les objectifs de l’ordonnancement
L’ordonnancement de tâches tenant compte des ressources disponibles et respectant les divers types de contraintes définis ci-avant n’est en général pas unique. L’objectif de l’ordonnancement vise donc à classer les solutions possibles, voire à guider la méthode d’élaboration de l’ordonnancement utilisée. Il est alors possible de définir un ordonnancement « optimal », c’est-à dire satisfaisant au mieux l’objectif considéré. Des objectifs élémentaires variés, qu’il serait fastidieux d’essayer de tous lister ici, peuvent être assignés à un ordonnancement. Il est néanmoins important de préciser quelques points.
Dans certains cas, on cherche à optimiser plusieurs fonctions objectifs à la fois. Dans ce cas, le problème d’ordonnancement n’est plus un problème d’optimisation simple mais devient un problème multicritère. Autrefois souvent abordé de manière empirique par des pondérations de critères, ce problème est maintenant souvent abordé au moyen de la notion de dominance de Pareto (une solution est dominante au sens de Pareto si aucune autre solution n’améliore la satisfaction d’un critère sans dégrader la satisfaction d’un autre). Il est ainsi possible de définir des ensembles de solutions candidates (front de Pareto) parmi lesquelles le décideur pourra choisir. Une difficulté supplémentaire est que des objectifs apparemment différents peuvent être liés (le lien entre diminution des encours et diminution des temps de cycle en est un exemple flagrant), tandis que d’autres peuvent être antagonistes (diminuer les encours et augmenter le taux d’occupation des ressources est en général difficile).
Problèmes d’atelier sans flexibilité des ressources
Les problèmes d’ordonnancement sans flexibilité des ressources s’intéressent à ordonnancer des tâches interdépendantes. Dans ce genre de problème, seules les contraintes temporelles et les contraintes de capacité des ressources sont considérées : cela revient à supposer que le problème d’affectation est résolu.
Une solution au problème d’ordonnancement sans flexibilité des ressources consiste à associer à chaque tâche une date de début et/ou de fin d’exécution qui respecte les contraintes temporelles et les contraintes de limitation de capacité des ressources du problème.
Ce problème peut être divisé suivant les caractéristiques décrites ci-après en : flow shop, job shop et open shop.
Ordonnancement d’ateliers en flow shop : En flow shop, tous les jobs visitent les machines dans le même ordre, avec des durées opératoires pouvant être différentes. Les machines sont disponibles sur tout l’horizon de planification et elles ne peuvent exécuter qu’une seule opération à la fois. Par ailleurs, une opération ne peut s’exécuter que sur une seule machine à la fois.
En pratique, ce cas est fréquemment rencontré ; citons l’exemple d’une chaîne de fabrication ou de montage.
Ordonnancement d’ateliers en job shop : Dans un job shop, chaque travail passe sur les machines dans un ordre fixé, mais, à la différence du flow shop, cet ordre peut être différent pour chaque travail. Chaque job possède donc une gamme spécifique. Il s’agit ici de déterminer les dates de passage sur différentes ressources des jobs ayant des gammes différentes dans l’atelier. Ces jobs partageant des ressources communes, des conflits sont susceptibles de survenir, résultant des croisements des flux. Dans son expression la plus simple, le problème est donc de gérer ces conflits tout en respectant les contraintes données, et en optimisant les objectifs poursuivis.
Ordonnancement d’ateliers en open shop : C’est un problème sans contrainte d’enchaînement prédéfinie, où chaque produit à fabriquer doit subir diverses opérations sur des machines, mais dans un ordre totalement libre. Cela est rarement généralisé dans un atelier manufacturier, mais peut survenir ponctuellement.
La résolution de ce sous-problème supplémentaire (déterminer la séquence d’opérations de chaque job) complique la production d’un ordonnancement, mais offre des degrés de liberté intéressants.
Il est à noter que la notion de «gamme linéaire», très ancrée au niveau des bureaux des méthodes des entreprises, mais aussi la rigidité des outils de gestion des données techniques, a souvent fait que, lorsque des permutations entre opérations étaient possibles, un choix plus ou moins arbitraire était réalisé lors de l’élaboration de la gamme.
Problèmes d’atelier avec flexibilité des ressources
La nécessité d’être toujours plus réactives a conduit les entreprises à rechercher des nouveaux degrés de liberté. Une partie de ces degrés de liberté réside dans l’élaboration d’alternatives, comme la duplication des exemplaires des machines, pour effectuer une ou plusieurs opérations. Ces problèmes présentent alors une difficulté supplémentaire par rapport aux problèmes sans flexibilité des ressources dans la mesure où les ressources sont en exemplaires multiples. Ainsi, la machine nécessaire pour exécuter une opération n’est pas connue d’avance, mais doit être sélectionnée parmi un ensemble donné. Ces machines peuvent être de trois types à savoir, des machines identiques notées P, des machines uniformes, notées Q, où les durées opératoires dépendent de leurs vitesses, et des machines non-reliées (ou indépendantes) notées R où leurs vitesses varient d’une tâche à une autre.
Dans ce genre de problème, il faut considérer simultanément les contraintes temporelles, les contraintes de limitation de capacité des ressources et les contraintes d’affectation.
Les problèmes avec flexibilité de ressources les plus étudiés dans la littérature sont : les problèmes à machines parallèles, le flow shop hybride et le job shop flexible présentés ci-dessous.
Ordonnancement d’ateliers en machines parallèles : Dans ce cas, on dispose d’un ensemble de machines pour réaliser les travaux. Les travaux se composent d’une seule opération et un travail exige une seule machine. L’ordonnancement s’effectue en deux phases : la première phase consiste à affecter les travaux aux machines et la deuxième phase consiste à établir la séquence de réalisation sur chaque machine.
Ordonnancement d’ateliers en flow shop hybride : Le « flow shop hybride » à k étages est un flow shop pour lequel chaque travail doit subir k opérations différentes telles que chaque opération doit se faire sur une unique machine choisie parmi un ensemble, appelé étage, de machines parallèles dédiées à cette opération. Une machine ne peut appartenir qu’à un seul étage.
Ordonnancement d’ateliers en job shop flexible : Un job shop flexible est un problème à cheminements multiples, mais qui présente une difficulté supplémentaire dans la mesure où chaque opération nécessite une machine pour être réalisée et cette machine doit être choisie dans un ensemble défini a priori.
Complexité des problèmes d’ordonnancement
La théorie de la complexité s’intéresse à l’étude formelle de la difficulté théorique intrinsèque des problèmes en informatique ou d’un problème par rapport à un autre et de l’analyse de la complexité des programmes et des algorithmes. Concrètement, on cherche à savoir si le problème étudié est plutôt «facile» ou plutôt « difficile » à résoudre en se basant sur une estimation (théorique) des temps de calcul et des besoins en mémoire informatique.
Les problèmes d’ordonnancement sont des problèmes d’optimisation combinatoire. Pour résoudre un problème d’ordonnancement, nous devons toujours chercher à établir sa complexité, car cela détermine la nature de l’algorithme à mettre en œuvre. Si le problème étudié appartient à la classe P, nous savons d’avance qu’un algorithme polynomial existe pour le résoudre. Dans le cas contraire, si le problème est NP-difficile, deux approches sont possibles. La première est de proposer un algorithme approché, donc une heuristique, qui calcule en temps polynomial une solution s’approchant au mieux de la solution optimale. Une alternative est de proposer un algorithme qui calcule la solution optimale du problème, mais pour lequel la complexité dans le pire des cas est exponentielle. Dans ce cas, le défi est de concevoir un algorithme qui peut résoudre en temps acceptable les problèmes de la plus grande taille possible.
Les problèmes d’ordonnancement sont spécifiés selon une notation à trois champs α|β|γ [Graham et al., 1979] où α précise l’environnement machines ou le système à ordonnancer, β précise les caractéristiques des opérations ou les contraintes et γ précise le(s) critère(s) à optimiser.
Pour calculer la complexité des problèmes d’ordonnancement, plusieurs résultats traditionnels existent dans la littérature. Ainsi, on rappelle la complexité des problèmes de base de l’ordonnancement de type Z α avec Z un critère donné.
Table des matières
INTRODUCTION GENERALE
CHAPITRE 1. PRESENTATION DES PROBLEMES D’ORDONNANCEMENT
1.1. DEFINITION
1.2. CONCEPTS DE BASE
1.2.1. Les tâches
1.2.2. Les ressources
1.2.3. Variables de décision et contraintes
1.2.4. Les objectifs de l’ordonnancement
1.3. ORDONNANCEMENT D’ATELIER
1.3.1. Problèmes d’atelier sans flexibilité des ressources
1.3.2. Problèmes d’atelier avec flexibilité des ressources
1.4. COMPLEXITE DES PROBLEMES D’ORDONNANCEMENT
1.5. CONCLUSION
CHAPITRE 2. ETAT DE L’ART DES PROBLEMES D’ORDONNANCEMENT D’ATELIER AVEC FLEXIBILITE DE RESSOURCES
2.1. DEFINITION
2.2. PROBLEMES DE FLOW SHOP HYBRIDE
2.2.1. Cas du flow fhop hybride à deux étages
2.2.2. Cas du flow shop hybride général
2.3. PROBLEMES DE JOB SHOP FLEXIBLE
2.4. CONCLUSION
CHAPITRE 3. RECHERCHE A BASE DE DIVERGENCES
3.1. INTRODUCTION
3.2. RECHERCHE A DIVERGENCE LIMITEE (LDS)
3.3. METHODE A DIVERGENCE LIMITEE AMELIOREE (ILDS)
3.4. METHODE A DIVERGENCE LIMITEE PAR LA PROFONDEUR (DDS)
3.5. METHODE DE RECHERCHE PAR PROFONDEUR D’ABORD INTERCALEE (IDFS)
3.6. METHODE A DIVERGENCE LIMITEE PAR PROFONDEUR D’ABORD (DBDFS)
3.7. METHODE A DIVERGENCE LIMITEE INVERSEE (RLDS)
3.8. METHODE A DIVERGENCE PONDEREE PAR SA PROFONDEUR (DWDS)
3.9. METHODE PAR MONTEE DE DIVERGENCES (CDS)
3.10. METHODE A DIVERGENCES LIMITEES PAR APPRENTISSAGE (YIELDS)
3.11. EXEMPLE ILLUSTRATIF DE ILDS, DDS, DDS TRONQUEE ET CDS
3.12. CONCLUSION
CHAPITRE 4. ADAPTATION DES METHODES A BASE DE DIVERGENCES POUR LE FLOW SHOP HYBRIDE
4.1. INTRODUCTION
4.2. UNE NOUVELLE METHODE ARBORESCENTE A BASE DE DIVERGENCES ET SON APPLICATION AU FLOW SHOP HYBRIDE
4.2.1. Méthode proposée : Climbing Depth-bounded Discrepancy Search (CDDS)
4.2.2. Variables de décision du problème de Flow Shop Hybride
4.2.3. Heuristiques sur l’ordre d’instanciation des variables
4.2.4. Notion de divergence pour le Flow Shop Hybride
4.2.5. Stratégies d’exploration
4.2.6. Exemple illustratif
4.3. EXPERIMENTATIONS
4.3.1. Comparaison sur les jeux-tests élaborés par Vignier
4.3.2. Comparaison sur les jeux-tests élaborés par Néron et Carlier
4.4. ADAPTATION DE LA METHODE DEVELOPPEE AUX PROBLEMES DE FLOW SHOP HYBRIDE A DEUX ETAGES
4.4.1. Heuristiques sur l’ordre d’instanciation des variables
4.4.2. Borne inférieure
4.4.3. Expérimentations
4.5. CONCLUSION SUR LE PROBLEME DE FLOW SHOP HYBRIDE
CHAPITRE 5. ADAPTATION DE LA METHODE CDDS POUR LE JOB SHOP FLEXIBLE
5.1. INTRODUCTION
5.2. ADAPTATION DE CDDS POUR LE PROBLEME CONSIDERE
5.2.1. Heuristiques sur l’ordre d’instanciation des variables
5.2.2. Notion de divergence pour le job shop flexible
5.2.3. Stratégies d’exploration
5.3. EXPERIMENTATIONS
5.3.1. Comparaison sur les jeux-test de Brandimarte (1993)
5.3.2. Comparaison sur les jeux-test de Barnes et Chambers (1996)
5.3.3. Comparaison sur les jeux-test de Dauzère-Pérès et Paulli (1997)
5.3.4. Comparaison sur les jeux-test de Hurink (1994)
5.4. CONCLUSION SUR LE PROBLEME DE JOB SHOP FLEXIBLE
CONCLUSIONS ET PERSPECTIVES
BIBLIOGRAPHIE
