Constructions agrégatives d’ordonnancements pour des jobs-shops statiques, dynamiques et réactifs Bernard Penz To cite this version: Bernard Penz. Constructions agrégatives d’ordonnancements pour des jobs-shops statiques, dynamiques et réactifs. Modélisation et simulation. Université Joseph-Fourier - Grenoble I, 1994. Français. �tel-00005107� HAL Id: tel-00005107 https://tel.archives-ouvertes.fr/tel-00005107 Submitted on 25 Feb 2004 HAL is a multi-disciplinary open access archive for the deposit and dissemination of scientific research documents, whether they are published or not. The documents may come from teaching and research institutions in France or abroad, or from public or private research centers. L’archive ouverte pluridisciplinaire HAL, est destinée au dépôt et à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d’enseignement et de recherche français ou étrangers, des laboratoires publics ou privés. These presentee par Bernard PENZ Pour obtenir le titre de Docteur de l'universite Joseph Fourier - Grenoble 1 (arr^etes ministeriels du 5 juillet 1984 et du 30 mars 1992) Specialite : Mathematiques Appliquees Formation Doctorale : Recherche Operationnelle Constructions agregatives d'ordonnancements pour des job-shops statiques, dynamiques et reactifs soutenue le 5 decembre 1994 devant le jury suivant : MM Pierre Ladet Alain Guinet Marino Widmer Pierre Lopez Lionel Dupont Gerd Finke President Rapporteur Rapporteur Examinateur Directeur Directeur These preparee au sein du laboratoire ARTEMIS-IMAG ii Remerciements Je commencerai par remercier M. Pierre Ladet d'avoir accepte de presider ce jury. J'ai eu l'occasion, dans le cadre du Groupement Scienti que Interdisciplinaire pour la Productique (GSIP), de travailler dans son equipe et d'apprecier son dynamisme. Ma reconnaissance va ensuite aux rapporteurs, M. Alain Guinet et M. Marino Widmer, ainsi qu'a M. Pierre Lopez. Tous trois ont consacre beaucoup de temps a lire mon document. Je les remercie ici pour leurs corrections constructives, leur contact direct et sympathique. A ARTEMIS-IMAG, mes deux codirecteurs, M. Lionel Dupont et M. Gerd Finke, ont taille le cadre administratif de ce travail. Le document a beaucoup gagne en clarte a la suite des nombreuses lectures de M. Lionel Dupont durant ces derniers mois. Je l'en remercie ici, ainsi que pour l'aide qu'il m'a fournie tout au long de ma these. Comme je l'ai deja signale, j'ai eu l'occasion de travailler avec des chercheurs exterieurs au laboratoire ARTEMIS-IMAG, M. Zdeneck Binder, remarquable par la profusion des idees, M. Abderamane Fadil, M. Vladimir Bourgade, et M. Luiz Manoel Aguilera. De ce dernier, j'ai beaucoup apprecie la rigueur, les idees, la generosite qui ont fait un ami autant qu'un collaborateur. iv Toujours dans le m^eme cadre, j'ai encadre M. Alexis Maire pour son DEA de Genie Industriel. Son excellent travail m'a bien pro te puisque la programmation d'une partie des heuristiques est de son fait. Qu'il soit remercie ici pour l'abscence de bugs. Je remercie en bloc toute l'equipe d'ARTEMIS-IMAG et en particulier la joyeuse bande des thesards avec lesquels ces trois ans de theses sont trop vite passes. Aux heures diciles, la famille est toujours la. Je la remercie pour le reconfort qu'elle m'a apporte avant, pendant et apres la soutenance. Resume Dans ce memoire, notre objectif est de presenter une nouvelle approche de resolution pour des problemes d'ordonnancement de type job-shop. Les problemes traites sont de grande taille, ce qui, du fait de la complexite du probleme, ne permet d'envisager que l'utilisation d'heuristiques. Cette approche propose une alternative aux algorithmes bases sur des regles de priorite, generalement utilises. Le principe de l'approche est de construire une succession d'ordonnancements partiels, en agregeant les jobs les uns apres les autres. L'agregation consiste a inserer toutes les operations du job a agreger sans changer l'ordre des operations dans l'ordonnancement partiel precedent. Dans un premier temps, des methodes issues de l'approche sont proposees pour resoudre le probleme classique du job-shop. Ensuite, ces methodes sont etendues pour traiter des problemes de job-shop generalise, ou l'a ectation des operations aux machines n'est pas xee au depart. Pour nir, des problemes de job-shop dynamiques et reactifs sont abordes. Dans ceux-ci, l'arrivee aleatoire de jobs et l'arr^et de machines sont pris en compte. Les methodes agregatives sont particulierement bien adaptees a la resolution de ce type de probleme. vi vii Table des matieres Introduction 1 Le probleme du job-shop 1.1 Le probleme 1.1.1 Les donnees 1.1.2 Les contraintes 1.1.3 Les objectifs 1.1.4 La complexite 1.2 Les modelisations 1.2.1 La modelisation par graphe disjonctif 1.2.2 Les modelisations en programmation mathematique 1.2.2.1 Le modele de A.S. Manne 1.2.2.2 Le modele de E. Pinson 1.2.2.3 Le modele de H.M. Wagner 1.2.2.4 Le modele de E.H Bowman 1.2.3 La modelisation polyedrale 1.2.4 La modelisation algebrique 1.3 Les methodes de resolution 1.3.1 Une classi cation des methodes 1.3.2 Les problemes polyn^omiaux 1.3.2.1 Le probleme a deux machines 1.3.2.2 Le probleme a deux jobs 1.3.3 Les methodes heuristiques 1.3.3.1 Les heuristiques constructives 1.3.3.2 Les heuristiques amelioratrices 1.3.3.3 Les reseaux de neurones : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 1 5 6 6 7 8 8 9 9 11 11 12 12 15 16 17 19 19 20 20 22 23 23 26 33 TABLE DES MATIE RES viii 1.3.3.4 L'intelligence arti cielle 1.3.3.5 Caracterisation des solutions admissibles 1.3.4 Les methodes exactes 1.3.5 Les methodes de relaxation 1.3.6 Les methodes de decomposition : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 2 Une approche par agregation 2.1 Le principe de l'agregation 2.1.1 Ordonnancement partiel sur jobs 2.1.2 L'agregation de deux jobs 2.1.3 L'agregation d'un job et d'un ordonnancement partiel 2.1.4 L'agregation de deux L ordonnancements partiels 2.2 Les algorithmes de type +1 2.2.1 L'algorithme general de resolution 2.2.2 Les procedures de selection des jobs L 2.2.3 Une procedure basee sur l'agregation 1 2 2.2.4 Des procedures d'agregation par decoupage du temps 2.2.4.1 Decoupage du temps et agregation globale 2.2.4.2 Decoupage du temps et insertion iterative 2.2.4.3 Decoupage du temps et insertion relative 2.2.5 Agregation globale par fonction co^ut L 2.3 Les algorithmes de type 2.3.1 L'algorithme general de resolution 2.3.2 Les procedures de groupement des jobs 2.3.2.1 Une methode de decomposition 2.3.2.2 Un regroupement de jobs dissemblables 2.3.2.3 Un regroupement de jobs decales 2.3.3 Les procedures d'agregation 2.4 L'amelioration locale 2.4.1 Amelioration par permutations 2.4.2 La reagregation 2.5 Resultats numeriques 2.5.1 Presentation des jeux de donnees 2.5.2 Resultats et conclusions 2.6 Conclusion : : : : : : : : : : : : : : : : : l : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : Jl Pl : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : J J : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : Pl Pr : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 34 34 35 37 37 39 40 40 42 46 46 47 47 49 49 50 50 56 56 61 66 69 69 69 72 72 73 74 74 76 76 78 78 84 TABLE DES MATIE RES ix 3 Le job-shop generalise 87 3.1 Une presentation du probleme 3.1.1 Description du probleme 3.1.2 Les methodes de resolution connues 3.2 Les modelisations du probleme 3.2.1 La modelisation de H.M. Wagner 3.2.2 Une nouvelle modelisation 3.3 Des methodes de resolution 3.3.1 Heuristiques constructives une-phase 3.3.2 Heuristiques constructives deux-phases 3.3.2.1 L'a ectation lineaire 3.3.2.2 L'a ectation lineaire avec capacites 3.3.2.3 L'a ectation de separation 3.3.2.4 L'a ectation de decomposition 3.3.3 Heuristiques amelioratrices 3.3.3.1 Optimisation par permutations d'operations 3.3.3.2 Optimisation par rea ectations 3.3.3.3 Optimisation par permutations et reaffectations 3.3.3.4 Optimisation par reagregation 3.4 Resultats numeriques 3.4.1 Presentation des jeux de donnees 3.4.2 Resultats et conclusions 3.5 Conclusion : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 4 Le job-shop dynamique et reactif 4.1 Presentation du probleme 4.1.1 Description du probleme 4.1.2 Les methodes de resolution connues 4.1.2.1 Decomposition en job-shop statique 4.1.2.2 Les regles de priorite 4.2 Une approche de resolution 4.2.1 L'algorithme general de resolution 4.2.2 L'arrivee aleatoire des jobs 4.2.3 Les arr^ets machine 4.2.3.1 La rea ectation 88 88 90 90 91 93 95 95 97 97 98 99 100 101 101 101 102 103 103 104 104 107 111 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 112 112 114 114 115 117 117 119 119 121 TABLE DES MATIE RES x 4.2.3.2 La reagregation 4.2.4 La reoptimisation locale 4.3 Resultats numeriques 4.3.1 Presentation des jeux de donnees 4.3.2 Resultats et conclusions 4.3.2.1 Resultats pour l'atelier 1 4.3.2.2 Resultats pour l'atelier 2 4.3.2.3 Resultats pour l'atelier 3 4.3.2.4 Remarques generales 4.4 Conclusion : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : Conclusion 121 123 123 125 126 130 132 135 138 141 143 xi Table des gures 1.1 1.2 1.3 1.4 1.5 2.1 2.2 2.3 2.4 2.5 2.6 2.7 2.8 2.9 2.10 2.11 2.12 2.13 2.14 2.15 2.16 2.17 2.18 2.19 2.20 2.21 2.22 Une classi cation des methodes de resolution Algorithme de liste par regles de priorite Algorithme tabou Algorithme de recuit simule Algorithme genetique Plan avec obstacles Reseau associe au plan Resultat de l'exemple Algorithme general base sur +1 L L Algorithme d'agregation base sur 1 2 Algorithme de decoupage du temps et agregation globale Resultat de l'agregation globale Algorithme de decoupage du temps et insertion iterative Premiere insertion pour l'agregation iterative Deuxieme insertion pour l'agregation iterative Derniere insertion pour l'agregation iterative Algorithme de decoupage du temps et insertion relative Premiere insertion pour l'agregation relative Deuxieme insertion pour l'agregation relative Derniere insertion pour l'agregation relative Algorithme d'agregation a l'aide d'une fonction co^ut Resultat de l'agregation par fonction co^ut L Algorithme general base sur Algorithme d'amelioration locale par permutations Algorithme d'amelioration par reagregations Les types d'instances generees Job-shop, atelier 1 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : Jl Pl : : : : : : : : : : : J J : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : Pl Pr : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 21 24 27 30 31 43 45 45 48 51 54 55 57 58 59 60 62 63 64 65 67 68 70 75 77 79 83 TABLE DES FIGURES xii 2.23 2.24 2.25 3.1 3.2 3.3 3.4 3.5 3.6 3.7 4.1 4.2 4.3 4.4 4.5 4.6 4.7 4.8 4.9 4.10 4.11 4.12 4.13 4.14 4.15 Job-shop, atelier 2 Job-shop, atelier 3 Job-shop, problemes classiques Matrice des temps operatoires pour le job Algorithme d'amelioration par rea ectations Composition des ateliers Les types d'instances generees Job-shop generalise, atelier 1 Job-shop generalise, atelier 2 Job-shop generalise, atelier 3 Algorithme general Algorithme de resolution general Algorithme de rea ectation apres arr^et d'une machine Algorithme de reagregation apres arr^et d'une machine Composition des ateliers Les types d'instances generees Job-shop dynamique, atelier 1 Job-shop reactif, atelier 1 Job-shop dynamique et reactif, atelier 1 Job-shop dynamique, atelier 2 Job-shop reactif, atelier 2 Job-shop dynamique et reactif, atelier 2 Job-shop dynamique, atelier 3 Job-shop reactif, atelier 3 Job-shop dynamique et reactif, atelier 3 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : Ji : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 84 85 86 89 102 104 105 107 108 108 116 120 122 124 125 127 131 132 133 134 135 136 137 138 139 INTRODUCTION 1 Introduction \L'ordonnancement est la distribution des ressources dans le temps pour realiser un ensemble d'activites". Cette de nition tres generale de l'ordonnancement donnee par K.R. Baker [9] ne permet pas de voir le nombre important de problemes que ce domaine comprend. En effet, l'ordonnancement est lie a des secteurs de recherches et d'activites tres varies. En informatique tout d'abord, le partage de la memoire, le choix des t^aches a envoyer aux processeurs se modelisent comme des problemes d'ordonnancement [17]. L'organisation de grands projets de constructions navales ou aeronautiques, de grands chantiers routiers ou ferroviaires et en general les constructions de travaux publics font egalement appel a cette theorie [36]. En n, nous pouvons citer l'organisation de la production dans les entreprises manufacturieres [60]. La theorie de l'ordonnancement est une branche de la recherche operationnelle. Elle consiste en la recherche de modeles mathematiques et la mise au point de methodes de resolution ecaces des problemes poses. Depuis plus de quarante ans, un e ort de recherche important est mene par les informaticiens, les automaticiens et les specialistes de la recherche operationnelle. Les problemes traites par la theorie de l'ordonnancement sont classes en di erentes categories, comme les problemes de machine simple, les problemes de machines paralleles, les problemes de type ow-shop, job-shop, open-shop, et l'ordonnancement de projets. Pour plus de details, de nombreux ouvrages de reference traitent de tous ces problemes [9] [48] [57] [95]. 2 INTRODUCTION Dans ce memoire de these, nous nous interessons plus particulierement aux problemes de type job-shop et a quelques unes de ses generalisations. Avec les problemes de machines simples et paralleles, le job-shop est sans doute le probleme de la theorie de l'ordonnancement le plus traite. Du fait de sa complexite importante, il demeure certainement l'un des problemes de l'optimisation combinatoire le plus dicile. Mettre au point une methode de resolution pour ce probleme n'est pas chose facile. Les criteres a prendre en compte sont nombreux lors de son elaboration, et la connaissance de la structure du probleme n'est pas susante. En e et, il est indispensable de savoir si l'on privilegie la qualite de la solution cherchee ou la rapidite du temps de calcul. Ces criteres etant opposes, il faut choisir l'un ou l'autre, ou trouver un compromis. La deuxieme diculte est la taille des instances traitees par la methode. Il n'est pas possible de traiter de la m^eme facon un probleme de tres petite taille et un probleme de tres grande taille. Ces dicultes seront prises en compte lors de la conception des methodes de resolution proposees plus loin. L'approche que nous allons proposer dans les pages suivantes se veut une alternative aux methodes basees sur des regles de priorite, communement utilisees pour traiter les problemes d'ordonnancement de taille importante. De plus, elle est developpee plus particulierement pour la resolution de problemes faisant intervenir des evenements aleatoires durant le deroulement de l'ordonnancement. C'est ainsi que seront traites les arrivees aleatoires de jobs et les arr^ets momentanes des machines. Le premier chapitre est consacre a un etat de l'art sur le job-shop statique et deterministe. Celui-ci est une des representations les plus simples d'un atelier de fabrication. Apres avoir presente ce probleme, nous faisons un tour d'horizon des di erentes facons de le modeliser. En n, nous proposons une classi cation des methodes de resolution connues en distinguant les di erentes approches. Dans le deuxieme chapitre, nous proposons une nouvelle approche de resolution basee sur un principe d'agregation. Cette nouvelle approche consiste a construire une succession d'ordonnancements partiels INTRODUCTION 3 en ajoutant des jobs les uns apres les autres. L'objectif de cette approche est d'aborder progressivement les dicultes du probleme de maniere a casser sa complexite. Une premiere partie est consacree a l'explication du principe d'agregation. Dans la suite, nous proposons des algorithmes de resolution generaux et donnerons des procedures d'agregation et de selection des jobs utilisees dans ces algorithmes. Pour nir, des tests comparatifs des di erentes heuristiques seront donnes et commentes. Le troisieme chapitre est consacre au probleme du job-shop generalise. La generalisation vient du fait que, contrairement au job-shop statique et deterministe, les operations de chaque job ne sont pas a ectees a une machine unique, mais peuvent ^etre executees par plusieurs machines. En plus des dicultes du job-shop statique et deterministe, le job-shop generalise ajoute le probleme d'a ectation des operations aux machines. Dans ce chapitre, nous decrivons le probleme et di erentes modelisations. Ensuite, nous proposons quelques approches de resolution basees principalement sur l'agregation. Pour nir, nous ferons une etude comparative de ces methodes en les testant sur une bibliotheque de jeux de donnees prealablement creee. Nous abordons, dans le quatrieme chapitre, les aspects dynamiques et reactifs qui peuvent ^etre lies aux problemes de job-shop. Ce type de probleme s'attache a la fois a la creation de l'ordonnancement a partir d'un ensemble de jobs, mais egalement au deroulement de l'ordonnancement au cours du temps. Par aspect dynamique, nous entendons le fait que certains jobs peuvent arriver dans l'atelier a un instant quelconque du deroulement de l'ordonnancement initialement prevu. La reactivite est liee au phenomene d'arr^et des machines, pour cause de pannes, par exemple. Pour cela, nous reprenons le probleme du job-shop generalise et ajoutons des phenomenes aleatoires comme l'arr^et d'une machine ou l'arrivee d'un job supplementaire. Si les problemes traites precedemment (job-shop statique et deterministe et job-shop generalise) etaient \o -line", c'est-a-dire que toutes les donnees sont connues des le commencement de l'optimisation, le job-shop dynamique est un probleme \on-line", c'est-a-dire que des donnees arrivent aleatoirement au cours du temps. Dans un premier temps, nous decrivons le probleme et faisons le tour d'horizon des methodes connues. Ensuite, nous proposons 4 INTRODUCTION une methode de resolution basee sur le principe d'agregation et sur les resultats obtenus pour le job-shop generalise. Pour nir, nous comparerons les heuristiques avec des algorithmes bases sur des regles de priorite, sur une bibliotheque de jeux de donnees creee a cet e et. Pour conclure ce memoire de these, nous reprendrons les grandes lignes du travail e ectue et presente ici. L'approche developpee est trop generale pour que toutes les possibilites de son utilisation puissent ^etre decrites. Pour cela, nous donnerons quelques directions de recherche qu'il nous semble interessant de suivre. 5 Chapitre 1 Le probleme du job-shop Le probleme du job-shop statique et deterministe est un des problemes de la theorie de l'ordonnancement et de l'optimisation combinatoire les plus traites [9] [30] [48] [95]. Il est dit statique car toutes les donnees du probleme sont connues au depart (les aspects dynamiques seront abordes dans le chapitre 4) et deterministe car les temps associes a chaque operation sont parfaitement determines (l'incertitude sur les durees des operations ne sera pas traitee dans cette these). Par la suite, les termes de statique et deterministe seront volontairement omis. Le job-shop propose, du fait de sa structure fortement combinatoire, des dicultes importantes pour la recherche de l'optimalite de ses solutions, et m^eme pour la recherche d'heuristiques performantes. Le but de cet etat de l'art est de presenter le probleme et de repertorier toutes les methodes de resolution envisagees ces dernieres annees. En aucun cas, un jugement de valeur ne sera porte sur l'ecacite des methodes proposees car les approches donnees et les natures m^emes des problemes traites sont extr^emement variables. Dans un premier temps, le job-shop est presente en precisant les donnees, les contraintes et les objectifs du probleme. Quelques modeles classiques et moins classiques tires de la litterature sont ensuite exposes. Certains modeles servent de support a la mise en place de methodes de resolution, d'autres, ne sont interessants que par leur c^ote theorique. Nous proposons une classi cation des methodes de resolution connues CHAPITRE 1. LE PROBLE ME DU JOB-SHOP 6 et a partir de celle-ci, nous repertorions les principales heuristiques et methodes exactes que l'on peut trouver dans la litterature. 1.1 Le probleme Les variations autour du probleme du job-shop sont nombreuses et il n'est pas possible de trouver dans la litterature une formulation unique de celui-ci. Nous donnons ici une formulation la plus generale possible et se rapprochant de l'ensemble de ce que l'on peut trouver sur ce sujet. 1.1.1 Les donnees La terminologie utilisee dans le domaine de l'ordonnancement est issue du contexte industriel et plus precisement des ateliers de fabrication des entreprises manufacturieres. Nous emploierons tout au long de ce memoire les termes de job, operation, machine, gamme operatoire ou encore temps operatoire. Les donnees du probleme sont les suivantes : 1. Un ensemble M de m machines. Chaque machine est specialisee et ne peut e ectuer qu'un seul type d'operation. Une machine est notee M avec k = 1, ..., m. Le nombre total d'operations executees par cette machine est note m . k k 2. Un ensemble J de n jobs. Chaque job est compose d'une gamme operatoire i.e. une suite lineaire xee de n operations. Cette sequence ne depend que du job et peut varier d'un job a l'autre. Un job est note J avec i = 1, ..., n. i i 3. L'operation O est la jeme operation dans la gamme operatoire de J . La date de debut calculee de O sera notee t . i;j i i;j i;j 4. L'operation O necessite l'utilisation de la machine M . Le fait que la machine demandee par l'operation O soit M s'ecrit R(O ) = M . La duree de O sur M , appelee temps operatoire, est notee p . i;j k i;j i;j k i;j i;j k k 5. Au total, no = P ==1 n operations sont a executer dans l'atelier. i i n i 7 1.1. LE PROBLEME Il est frequent de trouver une formulation plus restrictive du probleme de job-shop. Dans celle-ci, chaque job passe sur les m machines de l'atelier une fois et une seule. Tous les jobs sont donc constitues de m operations et chaque machine doit e ectuer n operations. Le nombre total d'operations no est alors n m et le probleme est dit carre si n = m. Une autre restriction de ce probleme amene a un probleme de owshop. Dans ce cas, et pour chaque operation O , R(O ) = M . Ainsi, la jeme operation de chaque job est executee sur la jeme machine. i;j 1.1.2 i;j j Les contraintes Cet atelier de fabrication, introduit precedemment, est soumis a des contraintes technologiques. Ces contraintes touchent a la fois les possibilites d'utilisation des machines et les liens qui peuvent exister entre les operations. Ces contraintes sont les suivantes : 1. Les machines sont independantes les unes des autres (pas d'utilisation d'outil commun, par exemple). 2. Une machine ne peut executer qu'une seule operation a un instant donne. 3. Chaque machine est disponible pendant toute la periode de l'ordonnancement. En particulier, les pannes de machines ne sont pas prises en compte dans le modele du job-shop (ce probleme est traite dans le chapitre 4). 4. Une operation en cours d'execution ne peut pas ^etre interrompue (il n'y a pas de preemption). 5. Les jobs sont independants les uns des autres. En particulier, il n'existe aucun ordre de priorite attache aux jobs. Certaines des methodes presentees plus loin fonctionnent egalement si l'on supprime une ou plusieurs des contraintes donnees ici. 8 CHAPITRE 1. LE PROBLE ME DU JOB-SHOP 1.1.3 Les objectifs Trouver un ordonnancement admissible revient a determiner une sequence de passage des operations sur les machines respectant les contraintes du probleme. Le but est ensuite de minimiser ou maximiser une fonction objectif pour trouver la ou les meilleures solutions. Le resultat d'un ordonnancement, generalement donne sur un diagramme de Gantt, est uniquement fonction des dates de debut calculees des operations. Dans la litterature, nous pouvons trouver un nombre important de fonctions objectif. La plus courante est sans doute la duree totale de l'ordonnancement (makespan) notee Cmax. Nous pouvons egalement citer la moyenne des temps d'achevement de chaque job, le retard maximum des jobs par rapport a une date d'achevement prevue, la moyenne des retards, etc [9] [48]. Dans la suite de ce memoire et pour tous les problemes traites, nous prendrons comme objectif, la duree totale de l'ordonnancement Cmax. 1.1.4 La complexite Le probleme du job-shop est classe par la theorie de la complexite [49] [50] [56] parmi les problemes NP-diciles au sens fort. Nous pouvons trouver la demonstration de ce resultat dans A. H. G. Rinnooy Kan [95]. Le principe de la demonstration repose sur une reduction polyn^omiale d'un probleme de ow-shop vers un probleme de knapsack. Au dela de la complexite theorique, la taille des instances que l'on traite est tres importante pour le choix de la methode de resolution. Pour un temps de calcul donne, il est possible de resoudre optimalement des problemes de petite taille, alors qu'il devient dicile de trouver une bonne solution admissible pour un grand probleme. Nous proposons une classi cation des problemes en fonction de leurs nombre de job, nombre d'operations par job et nombre de machines. Cette classi cation permettra, dans la suite, de reperer facilement les 1.2. LES MODE LISATIONS 9 types de problemes auxquels sont dediees les methodes de resolution. { Problemes de petite taille : Problemes de moins de 20 jobs, moins de 10 machines et moins de 10 operations par jobs. { Problemes de taille moyenne : Problemes entre 20 et 50 jobs, de 5 a 15 machines et de 5 a 15 operations par jobs. { Problemes de grande taille : Problemes de plus de 50 jobs, de plus de 5 machines et de plus 5 operations par machines. 1.2 Les modelisations Traiter un probleme d'une telle complexite necessite toujours une modelisation precise. La formulation la plus classique est sans aucun doute sous forme de graphe disjonctif, mais les modelisations en programmation mathematique sont les plus anciennes. Il existe egalement des modelisations polyedrales et algebriques du probleme. Cette section va t^acher de resumer l'ensemble des modelisations existantes. 1.2.1 La modelisation par graphe disjonctif La modelisation sous forme de graphe disjonctif est tres certainement la plus employee pour representer les problemes d'ordonnancement, et en particulier le probleme du job-shop. Cette formulation est tres souvent utilisee dans la mise au point de methodes de resolution. Presentee pour la premiere fois par B. Roy [98] en 1964, elle fut reprise un peu plus tard par E. Balas [10]. Elle est a l'origine des premieres methodes de resolution ecaces pour traiter le probleme. Le job-shop est represente par un graphe = ( [ ), ou est l'ensemble des sommets du graphe , est l'ensemble des arcs conjonctifs et est l'ensemble des arcs disjonctifs : G G X; C D X C D { L'ensemble des sommets de contient + 2 elements. Parmi ceux-ci, sommets sont associes a chacune des operations . Par la suite, on notera ces sommets . Deux sommets X G no no Oi;j no Oi;j deb CHAPITRE 1. LE PROBLE ME DU JOB-SHOP 10 et sont ajoutes et representent le debut et la n de l'ordonnancement. Le sommet precede tous les sommets du graphe et succede a tous. Tous les sommets correspondant a des operations sont ponderes par leur temps operatoire. { L'ensemble contient les arcs conjonctifs representant les contraintes de precedence entre les operations d'un m^eme job (gamme operatoire). Il existe donc un arc entre les sommets et +1 pour = 1 et = 1 , 1. De plus, il existe des arcs entre et 1 et, entre et pour = 1 . { L'ensemble contient les arcs disjonctifs issus de la contrainte qu'une machine ne peut executer qu'une operation a la fois. Il existe donc un arc et un arc retour entre les operations et pour 6= , utilisant la m^eme machine ( ( ) = ( )). f in deb G f in C Oi;j i ; :::; n deb j Oi;j ; :::; ni Oi; Oi;ni f in i ; :::; n D Oa;b Oc;d a c R Oa;b R Oc;d Pour construire un ordonnancement admissible sur le graphe , il sut d'arbitrer chacune des disjonctions. Cela revient a choisir, pour chaque paire d'arcs, seulement un arc qui determinera l'ordre de passage sur la machine. Pour que l'ordonnancement soit parfaitement de ni, il faut que l'arbitrage soit complet (toutes les disjonctions sont arbitrees) et compatible (le graphe est sans circuit) [98]. G Sur le graphe ainsi obtenu, nous utilisons alors un systeme de potentiels qui respecte les contraintes du probleme. Ces potentiels representent en fait la date de debut calculee de chaque operation. Nous obtenons les equations suivantes : ti;j +1 t 1 i;j + ( =1 pi;j i ; =1 ; :::; n j ; :::; ni , 1) (1.1) tc;d ta;b + pa;b si on a un arc de Oa;b vers Oc;d (1.2) ta;b tc;d + pc;d si on a un arc de Oc;d vers Oa;b (1.3) ti; tdeb tf in ti:ni ( =1 i + pi;ni ) (1.4) ; :::; n ( =1 i ) ; :::; n (1.5) 1.2. LES MODE LISATIONS 11 L'equation 1.1 represente les contraintes de gamme operatoire entre les di erentes operations d'un m^eme job. Les equations 1.2 et 1.3, qui representent une contrainte de disjonction, ne sont pas actives dans les m^emes conditions. L'une seulement sur les deux est active selon que l'arbitrage d'une disjonction donne un arc plut^ot qu'un autre. Les equations 1.4 et 1.5 representent les contraintes de debut et de n d'ordonnancement. La duree totale de l'ordonnancement Cmax est alors donnee par la valeur de tfin. 1.2.2 Les modelisations en programmation mathematique C'est en terme de programmation mathematique [16] qu'ont ete formules les premiers exemples de job-shop [20] [78] [110]. Nous presentons maintenant quelques uns de ces modeles parmi les plus courants. Dans les deux premiers modeles, les contraintes de gamme operatoire et les contraintes de debut et de n sont representees par les m^emes equations que precedemment (cf equations 1.1, 1.4 et 1.5). Le seul probleme reside dans les contraintes de capacite des machines(1.2 et 1.3), une machine ne pouvant executer qu'une seule operation a la fois (cf 1.1.2). Les deux derniers modeles reprennent toutes les contraintes. 1.2.2.1 Le modele de A.S. Manne La programmation lineaire en nombres entiers est un outil tres utilise pour la formulation de nombreux problemes de l'optimisation combinatoire. Pour cette formulation, A.S. Manne [78] de nit une variable nouvelle pour chaque paire ordonnee d'operations utilisant la m^eme a;b pour la paire (O ; O ) si machine. Cette variable en 0 , 1 s'ecrit yc;d a;b c;d (R(Oa;b) = ROc;d ) = Mk : a;b = yc;d ( 0 si Oa;b precede Oc;d sur Mk 1 si Oc;d precede Oa;b sur Mk (1.6) On suppose, de plus, la connaissance d'une borne superieure BS de la duree totale de l'ordonnancement. Cette borne peut simplement ^etre 12 CHAPITRE 1. LE PROBLE ME DU JOB-SHOP la somme de tous les temps operatoires. Les contraintes de disjonction peuvent alors ^etre formulees par les equations suivantes : a;b tc;d ta;b + pa;b , BS yc;d (1.7) a;b) ta;b tc;d + pc;d , BS (1 , yc;d (1.8) Dans ce modele, pour chaque arbitrage d'une paire d'arcs disjonctifs, seule l'une des contraintes 1.7 et 1.8 est active. Ainsi, quand l'ara;b vaut 0. La contrainte 1.8 est alors bitrage donne Oa;b avant Oc;d, yc;d inactive puisque signi ant ta;b ,1, ce qui est toujours vrai, et la contrainte 1.7 est active puisque devenant tc;d ta;b + pa;b. Dans ce modele, en plus des no variables ti;j , nous avons pour chaque machine Mk , mk mk2,1 variables supplementaires correspondant a chaque paire d'operations sur la machine. Aux (no , n) contraintes de gammes operatoires (cf 1.1), s'ajoutent mk (mk , 1) contraintes de disjonctions (1.7 et 1.8). 1.2.2.2 Le modele de E. Pinson E. Pinson [87] propose une formulation en terme de programmation mathematique. Il regroupe en une seule equation quadratique les deux equations disjonctives pour chaque paire d'operations (Oa;b; Oc;d) utilisant la m^eme machine R(Oa;b ) = R(Oc;d ) = Mk . (ta;b , tc;d + pa;b) (tc;d , ta;b + pc;d ) 0 (1.9) Ce modele comporte donc seulement no variables ti;j , (no , n) contraintes de gamme operatoire et mk mk2,1 contraintes de disjonction (1.9). 1.2.2.3 Le modele de H.M. Wagner La modelisation que nous exposons maintenant est due a H.M. Wagner [110]. C'est en fait une restriction d'une modelisation d'un job-shop generalise que nous presenterons dans le chapitre 3. 1.2. LES MODE LISATIONS 13 Dans ce modele, la variable principale est x(i;jl), les autres variables sont exposees ensuite. ( Oi;j passe sur R(Oi;j ) en leme position = 10 sisinon x(i;jl) (1.10) t(kl) : date de debut de la leme operation sur Mk (1.11) s(kl) : duree entre la n de la leme operation et le (1.12) debut de la (l + 1)eme sur Mk (variables d'ecart) s0k : duree entre 0 et la premiere operation sur Mk (1.13) Tx(kl) : temps operatoire de la leme operation sur Mk (1.14) mk : nombre d'operations executees sur Mk (1.15) Les premieres contraintes (1.16) signi ent qu'une operation et une seule est en leme position sur la machine Mk . X O i;j j R(O )=M i;j x(i;jl) = 1 pour k = 1; :::; m; l = 1; :::; mk (1.16) k Les contraintes suivantes (1.17) imposent qu'une operation Oi;j ne soit a ectee qu'a une place et une seule : l=X m k l=1 x(i;jl) = 1 pour i = 1; :::; n; j = 1; :::; ni (1.17) Les contraintes 1.18 determinent le temps operatoire de la leme operation executee sur Mk . Tx(kl) = iX =n i=1 pi;j x(i;jl) pour k = 1; :::; m; l = 1; :::; mk (1.18) CHAPITRE 1. LE PROBLE ME DU JOB-SHOP 14 Les contraintes de gamme operatoire s'expriment pour deux operations Oi;j et Oi;j+1, de la facon suivante : ) ) t(kl11) + pi;j x(i;jl1) t(kl22) + BS (2 , x(i;jl1) , x(i;jl2+1 (1.19) pour l1 = 1; :::; mk1 ; l2 = 1; :::; mk2 Cette contrainte n'est active que si l'operation Oi;j est executee sur la machine R(Oi;j ) = Mk1 en l1eme position et Oi;j+1 en l2eme position sur R(Oi;j+1 ) = Mk2 . Si une de ces deux conditions n'est pas respectee, la contrainte n'est pas active. En n, le calcul des dates de debut au plus t^ot des operations sur les machines se fait par les contraintes suivantes : 0 t(1) k = sk pour k = 1; :::; m t(kr) = l=X r,1 l=1 (1.20) Tx(kl) + s(kl) pour k = 1; :::; m; r = 1; :::; mk (1.21) Les dernieres contraintes (1.22) permettent de calculer le Cmax : tmk k + Txmk k Cmax pour k = 1; :::; m (1.22) Dans ce modele, le nombre de variables et de contraintes est beaucoup plus eleve que pour les modeles precedents. A chaque(l)operation Oi;j telle que R(Oi;j ) = Mk , sont associees mk variables xi;j . Les variables t(kl) sont au nombre de mk sur chaque machine Mk , et les variables d'ecart s(kl) au nombre de mk , 1. A ces variables, s'ajoutent m variables s0k et no variables Tx(kl). Au niveau des contraintes, nous avons (no , n) contraintes de gammes operatoires (1.19), no contraintes d'affectation d'une operation en position l dans la sequence de la machine, no contraintes imposant une seule operation en leme position sur Mk , no contraintes de temps operatoires (1.18) et 2 m + no contraintes de dates au plus t^ot (1.20, 1.21 et 1.22). 1.2. LES MODE LISATIONS 15 1.2.2.4 Le modele de E.H Bowman E.H Bowman [20] utilise, pour sa formulation du probleme sous forme de programme lineaire en nombres entiers, les variables x pour chaque operation O et un decoupage du temps en periode de longueur 1. Il suppose de plus la connaissance d'une borne superieur BS de la valeur de la solution optimale. La variable x a pour signication : ( si O utilise R(O ) = M a l'instant t x = 01 sinon (1.23) i;j;t i;j i;j;t i;j i;j k i;j;t Les contraintes suivantes assurent que l'operation O necessite l'utilisation de la machine M pendant p unite de temps. i;j; k X t=B S x i;j;t t=1 =p i;j (i = 1; :::; n; j = 1; :::; n ) i;j i (1.24) Une machine n'e ectue qu'une operation a la fois. La somme des x , pour un instant t et une machine M donnes, doit ^etre inferieur ou egale a 1. i;j;t k X Oi;j j x i;j;t R(Oi;j )=Mk 1 (k = 1; :::; m; t = 1; :::; BS ) (1.25) Les contraintes de precedences sont alors exprimees par : p x i;j i;j +1;r X,1 t=r x (1.26) i;j;t t=1 (i = 1; :::; n; j = 1; :::; n , 1; t = 1; :::; BS ) i Les contraintes de non preemption sont exprimees par : p (x i;j i;j;t ,x i;j;t+1 )+ X r =B S r =t+2 x i;j;r p i;j (1.27) CHAPITRE 1. LE PROBLE ME DU JOB-SHOP 16 (i = 1; :::; n; j = 1; :::; ni) Pour nir, la fonction objectif Cmax s'ecrit en tenant compte du fait que la duree totale de l'ordonnancement ne peut ^etre inferieure au temps necessaire pour produire le job le plus long : Cmax xi;n ;t t i (i = 1; :::; n; t = 1; :::; BS ) (1.28) Le modele de E.H. Bowman contient encore plus de variables et de contraintes que celui de H.M. Wagner. Les variables xi;j;t sont au nombre de no BS . Nous avons no contraintes de temps operatoires (1.24), m BS contraintes garantissant qu'une seule operation est executee a un instant donne par une machine (1.25), no BS contraintes de gammes operatoires et no (BS , 1) contraintes de non preemption. Nous remarquons directement que la connaissance d'une bonne borne superieure BS permet de limiter considerablement le nombre d'equations. M.L. Fisher [42] [43] a egalement propose un modele faisant intervenir le nombre d'operations sur une machine a un instant donne. 1.2.3 La modelisation polyedrale L'approche polyedrale s'est beaucoup developpee dans le domaine de l'optimisation combinatoire [58]. De nombreux problemes comme le voyageur de commerce font intervenir ce genre de representation pour leur description [71]. Le principe est de trouver les contraintes lineaires de nissant des demi- espaces. L'intersection de ces demi-espaces donne un polyedre dont les sommets representent une solution realisable du probleme. Si l'on se donne une fonction objectif lineaire, l'utilisation d'un programme lineaire permet d'obtenir la solution optimale. Bien entendu, le nombre de contraintes est exponentiel par rapport a la taille du probleme. Le modele polyedral pour des problemes d'ordonnancement a ete introduit par E. Balas [11] en 1985. Il de nit un vecteur solution t dont 1.2. LES MODE LISATIONS 17 les composantes sont les dates de debut calculees de chacune des operations a ordonnancer. est alors l'ensemble de tous les vecteurs veri ant les contraintes du probleme. Il considere le polyedre comme etant l'enveloppe convexe des points de . On a alors : ti;j no T t P T P T = = ( ) (1.29) conv T 8 > < t > : ti;j 2< no ta;b tc;d +1 t + p t 1 0 + i;j i; pc;d _ tc;d 9 > = i;j ta;b + pa;b > ; (1.30) Il en deduit ensuite toute les facettes du polyedre ( ) ou est l'ensemble des operations appartenant a une clique de disjonctions. Il presente pour nir une procedure permettant de couper une solution donnee par un sous-ensemble de contraintes, s'appuyant sur la theorie des polyedres bloquants. Des travaux developpes par M. Queyranne [91] [90] pour des problemes de machines simples peuvent ^etre utilises dans le cadre de la resolution de problemes de job-shop. P K K Malheureusement, pour le probleme du job-shop, cette modelisation ne semble pas ^etre utilisable. Elle n'a ete employee que tres recemment par D. Appelgate et W. Cook [7] pour trouver de bonnes bornes inferieures dans une methode separation et evaluation. Toutefois, il parait tres dicile d'utiliser cette technique pour developper des methodes de resolution ecaces. 1.2.4 La modelisation algebrique Cette modelisation, tres formelle, est sans doute la moins utilisee dans le domaine de l'ordonnancement. Nous presentons ici les structures algebriques du probleme comme elles ont ete donnees dans R.V. Rogers et K.P. White [96]. Soit ( ! ) tel que: { = f j =1 ; =1 operations; O; RI ; RM ; O Oi;j i ;P ; :::; n j ; :::; ni g est l'ensemble de toutes les 18 CHAPITRE 1. LE PROBLE ME DU JOB-SHOP { RI est une relation d'equivalence sur O de nissant les operations communes a un job; { RM est une relation d'equivalence sur O de nissant les operations communes a une machine; { ! est une relation d'ordre non re exive sur O de nissant les precedences entre les operations; { P = fpi;j ji = 1; :::; n; j = 1; :::; ni g est l'ensemble des temps operatoires Chaque job Ji est une classe d'equivalence d'operations determinee par RI . L'espace quotient qui en resulte O=RI = fJ1; :::; Jng est une partition de O. J (Oi;j ) = Ji est alors une surjection de O dans O=RI . De la m^eme facon, chaque machine Mk est une classe d'equivalence d'operations determinee par RM . L'espace quotient qui en resulte O=RM = fM1; :::; Mmg est une partition de O. M (Oi;j ) = Mk est alors une surjection de O dans O=RM . La gamme operatoire pour un job Ji est une relation d'ordre !i de nie par la restriction de ! a Ji. !i=! \(Ji Ji) L'ensemble des contraintes de gamme operatoire pour chaque job est alors donne par f(!i; Ji) jj = 1; :::; n g. De la m^eme facon, la sequence des operations sur une machine est une relation d'ordre !k de nie par la restriction de ! a Mk . !k =! \(Mk Mk ) L'ensemble des contraintes de precedence sur une machine est alors donne par f(!k ; Mk ) jk = 1; :::; m g. Recemment, K.K. Tahboub et N.G. Odrey [102] ont propose une modelisation du probleme de job-shop en utilisant des resultats issus de l'algebre (Max; +) [31]. 1.3. LES METHODES DE RESOLUTION 19 Ces modelisations sont mathematiquement tres interessantes mais ne nous indique pas de direction en ce qui concerne les methodes de resolution. Aucun article a ce jour ne mentionne ces modelisations sinon [96] et [102]. 1.3 Les methodes de resolution Les methodes de resolution proposees au cours de ces quarante dernieres annees sont nombreuses, et sont le re et de l'eventail des methodes dont on dispose pour traiter les problemes de l'optimisation combinatoire [85]. Nous nous proposons, dans cette section, de classi er toutes les approches qui ont servi de support a la creation d'algorithmes d'optimisation. Dans un premier temps, nous decrirons les methodes de resolution exactes pour des classes de problemes polyn^omiaux, puis les methodes heuristiques pour le probleme general. Nous traiterons ensuite les methodes de resolution exactes pour le probleme general. Les methodes de relaxation constitueront la section suivante et pour nir, nous donnerons quelques references sur les methodes de decomposition. Le but de la classi cation n'est pas de comparer les methodes en fonction de leur \performances" pour la resolution du probleme. Le plus souvent, les auteurs ne traitent pas les m^emes problemes de job-shop et n'ont pas les m^emes objectifs. Si certaines methodes sont adaptees aux problemes de grande taille (beaucoup de jobs et/ou beaucoup de machines), d'autres ne traitent que des problemes a environ dix jobs et dix machines. Par ailleurs, des algorithmes sont construits pour ^etre rapide au detriment de la qualite de la solution, alors que d'autres recherchent l'optimalite de la solution. 1.3.1 Une classi cation des methodes Cette section contient une classi cation des approches utilisees pour resoudre le probleme du job-shop statique et deterministe ( gure 1.1). Nous pouvons constater assez rapidement que le job-shop a inspire de nombreux auteurs et que les propositions de methodes de resolution sont extr^emement variees. Les methodes dediees a la resolution du pro- CHAPITRE 1. LE PROBLE ME DU JOB-SHOP 20 bleme c^otoient l'utilisation des methodes classiques de l'optimisation combinatoire. Il est egalement interessant de constater que le probleme du job-shop est un terrain d'essai privilegie pour le test de nouvelles approches de resolution au m^eme titre que le probleme du voyageur de commerce. Dans cette classi cation, apparaissent les principales references pour chaque approche de resolution. Chacune d'elles est plus amplement discutee dans les sections suivantes. 1.3.2 Les problemes polyn^omiaux Comme nous l'avons vu precedemment (cf 1.1.4), le probleme du job-shop est un probleme NP-dicile au sens fort. Toutefois, il existe quelques cas particuliers de ce probleme qui peuvent ^etre resolus en temps polyn^omial. 1.3.2.1 Le probleme a deux machines Le premier de ces problemes faciles est le job-shop a deux machines. Dans celui-ci nous avons quatre types de jobs : { Type 1 : Les jobs n'ayant qu'une operation sur la machine M1 . { Type 2 : Les jobs n'ayant qu'une operation sur la machine M2 . { Type 3 : Les jobs ayant la premiere operation sur xieme sur 2. M1 et la deu- { Type 4 : Les jobs ayant la premiere operation sur xieme sur 1. M2 et la deu- M M La regle de S.M. Johnson [65] dit que pour les jobs de type 3 precede sur les machines 1 et 2 si ( 1 2) ( 2 1). Il en est de m^eme pour les jobs de type 4. On obtient ainsi une sequence des jobs 3 pour les jobs de type 3 et 4 pour les jobs de type 4. On construit une sequence aleatoire 1 avec les jobs de type 1 et 2 avec les jobs de type 2. La regle de J.R. Jackson [64] dit qu'un ordonnancement Ja Jb M M S M in pa; ; pb; M in pa; ; pb; S S S 1.3. LES ME THODES DE RE SOLUTION 21 ! Probleme du job-shop ! Les methodes pour les problemes polyn^omiaux ! Le probleme a deux machines [3] [64] [65] [69] [101] ! Le probleme a deux jobs [6] [22] [23] ! Les methodes de relaxation [46] ! Les methodes de decomposition [35] [74] [88] ! Les methodes exactes ! La programmation dynamique [13] ! Le branch and bound [7] [8] [10] [12] [21] [28] [29] [47] [70] ! Le branch and cut [7] ! Le programmation mathematique [75] ! Les methodes heuristiques ! Les heuristiques constructives ! L'approche par operations [33] [84] [107] [113] [59] ! L'approche par machines [2] ! L'approche par jobs [86] (cf chapitre 2) ! Les heuristiques amelioratrices ! La methode tabou [33] [79] [103] [106] ! Le recuit simule [77] [104] [105] [106] ! Les algorithmes genetiques [32] [34] [41] [83] ! Les methodes dediees [107] [113] ! Les reseaux de neurones [115] [116] ! L'intelligence arti cielle [14] Fig. 1.1 - Une classi cation des methodes de resolution 22 CHAPITRE 1. LE PROBLE ME DU JOB-SHOP est optimal si on adopte sur la machine M1 l'ordre donne par S3, S1,S4 et sur la machine M2, l'ordre donne par S4, S2, S3. Il existe des cas particuliers de job-shop a trois machines pour lesquels on a un algorithme optimal derive du precedant [48]. Une generalisation de ce probleme a ete proposee par Strusevitch [101] dans laquelle il donne un algorithme pour resoudre un super-shop (gamme operatoire non xee) a deux machines. Il existe d'autres problemes polyn^omiaux de type job-shop a deux machines. Parmi ceux-ci nous pouvons citer le probleme a deux machines et temps operatoires unitaires (cas particulier du precedent) [3] [69]. 1.3.2.2 Le probleme a deux jobs Le deuxieme probleme polyn^omial presente est le job-shop a deux jobs J1 et J2. S.B. Akers [6] presente une reduction de ce probleme a un probleme de plus court chemin dans le plan avec obstacles rectangulaires. Les temps operatoires des operations de J1 (resp J2) sont representes par la longueur des intervalles sur l'axe des abscisses (resp sur l'axe des ordonnees) et les obstacles representent l'utilisation d'une m^eme machine. Un ordonnancement realisable correspond alors a un chemin de O a F avec les proprietes suivantes : { Les segments du chemin sont paralleles a l'un des axes (une operation d'un seul job est executee) ou diagonaux (des operations des deux jobs sont executees). { Le chemin ne doit pas passer par l'interieur des obstacles materialisant l'utilisation d'une m^eme machine pour les deux jobs. La duree totale de l'ordonnancement associee a un tel chemin est la somme des longueurs des segments verticaux et horizontaux et de la projection sur un des deux axes des segments diagonaux. Un algorithme de resolution tres performant de ce probleme a ete donne par P. Brucker [22]. Une generalisation a ete proposee plus tard, 1.3. LES METHODES DE RESOLUTION 23 utilisant les m^emes techniques graphiques, par P. Brucker et B. Jurisch [23]. Ces algorithmes seront detailles dans la section 2.1.2. 1.3.3 Les methodes heuristiques Comme pour tous les problemes NP-complets, la recherche d'heuristiques performantes est une des preoccupations des specialistes du domaine. Le principe d'une methode heuristique est de trouver en un temps polyn^omial une solution realisable la meilleure possible [100]. Dans cette recherche, les objectifs poursuivis sont parfois di erents. Certains privilegient la rapidite de calcul au detriment de la qualite de la valeur optimale, d'autres s'interessent plus a la quasi-optimalite du resultat au detriment du temps. Dans la mesure du possible, nous t^acherons dans la suite, de decrire l'ensemble des heuristiques connues a ce jour en precisant leur inter^et. 1.3.3.1 Les heuristiques constructives Le principe de ces methodes est de construire une solution du probleme a partir des donnees initiales. Les methodes proposees dans ce contexte sont nombreuses, mais elles peuvent ^etre regroupees en differentes categories. Nous commencerons par les methodes basees sur les operations. Nous parlerons ensuite des methodes basees sur les machines puis par celles basees sur les jobs. Approche par operations. L'utilisation de regles de priorite est de loin la technique la plus employee pour resoudre les problemes d'ordonnancement. Elle consiste en une approche operation par operation. Le principe de l'algorithme est donne dans la gure 1.2. S.S. Panwalkar et W. Iskander [84] ont repertorie plus d'une centaine de regles de priorite et ont propose une classi cation de celles-ci. Depuis, de nombreux auteurs [107] ont proposes d'autres regles originales ou des evolutions de regles existantes. Les regles de priorite peuvent ^etre utilisees di eremment. En e et, l'algorithme presente precedemment peut ^etre completement inverse et CHAPITRE 1. LE PROBLE ME DU JOB-SHOP 24 1. INITIALISATION Faire la liste de toutes les operations disponibles a l'instant initial, f 1j = 1 g. 2. SELECTION DE L'OPERATION Selectionner l'operation selon la regle de priorite choisie et la placer dans la sequence des operations sur la machine. 3. MISE A JOUR DE LA LISTE Retirer l'operation choisie de la liste et y ajouter la suivante dans la gamme operatoire. ^ 4. CONDITION D'ARRET Recommencer ce processus tant qu'il existe des operations non traitees. oi; i Fig. ; :::; n 1.2 - Algorithme de liste par regles de priorite 1.3. LES METHODES DE RESOLUTION 25 les operations sont traitees par ordre decroissant dans les gammes operatoires. La liste est constituee au depart des operations qui n'ont pas de successeurs. Le choix se fait selon une regle de priorite, l'operation est sortie de la liste et l'operation qui la precede dans la gamme operatoire y est introduite. M. Dell'Amico et M. Trubian [33] proposent une approche bidirectionnelle consistant a ordonnancer les premieres operations des jobs selon la premiere methode et les dernieres operations selon la deuxieme. Cette approche semble donner de meilleurs resultats que les precedentes. En n, F. Werner et A. Winkler [113] proposent une methode basee sur une technique d'insertion d'operation. Les operations sont inserees dans un ordonnancement partiel par ordre decroissant de leur duree operatoire. Dernierement, A. Guinet et M. Legrand [59] ont propose une reduction du probleme de job-shop a un probleme de ow-shop. Ils utilisent ensuite des heuristiques de resolution de problemes de ow-shop. Les principaux atouts de ces techniques sont certainement une grande facilite de mise en uvre informatique et une vitesse de calcul tres importante. Toutefois, les resultats obtenus pour la valeur de la fonction objectif sont parfois assez eloignes de la valeur optimale. Ces techniques sont tres interessantes pour les problemes de grande et tres grande taille. Approche par machine. Le principe de resolution est de trouver un sequencement sur les machines, les unes apres les autres. Cette approche n'a pas ete tres developpee et seule l'heuristique \Shifting Bottleneck" de J. Adams et al. [2] est connue. Dans celle-ci, la premiere etape consiste a determiner la machine goulot (machine posant le plus de probleme pour son sequencement). Lors de la deuxieme etape, un probleme de machine simple avec temps de latences est resolu (cf J. Carlier [26]). Il faut en fait trouver une sequence de passage sur la machine selectionnee sachant que certains jobs ne peuvent commencer avant une 26 CHAPITRE 1. LE PROBLE ME DU JOB-SHOP date xee, somme des temps operatoires des operations qui la precedent dans sa gamme operatoire, et qu'un certain temps doit s'ecouler entre le n d'une operation et la n de l'ordonnancement, somme des temps operatoires des operations qui lui succedent dans sa gamme operatoire. Quand le sequencement est realise sur une machine, on en selectionne une autre et l'on recommence le processus, jusqu'a ce que toutes les machines aient ete traitees. J. Adams et al. proposent, apres le traitement de chaque machine, de reoptimiser le resultat partiel obtenu, toujours en utilisant la procedure de resolution du probleme a une machine de J. Carlier. Cette methode donne de tres bons resultats sur des problemes de petite et moyenne taille. Par contre, la resolution du probleme a une machine necessitant l'utilisation d'un algorithme branch and bound, l'heuristique n'est pas tres adaptee a la resolution de problemes de grande et tres grande taille. Approche par jobs. A ce jour, aucune technique n'a ete developpee sur le principe du traitement job par job. Dans le chapitre 2, nous proposerons un certain nombre d'heuristiques basees sur ce principe. 1.3.3.2 Les heuristiques amelioratrices Le principe de ces methodes n'est plus de construire un ordonnancement a partir des donnees initiales du probleme, mais de modi er le resultat d'un ordonnancement admissible en vue d'ameliorer la valeur de la fonction objectif. La plupart de ces methodes utilise la notion de voisinage de solution. Elle consiste donc a explorer les solutions voisines d'une solution donnee et a en selectionner une, pour ensuite continuer le processus d'exploration. A chaque etape de ce processus, la solution choisie n'ameliore pas forcement la valeur de la fonction objectif ce qui permet de sortir de minima locaux. E. H. L. Aarts et al. [1] ont recemment propose une etude comparative de plusieurs des methodes decrites maintenant. 1.3. LES METHODES DE RESOLUTION 27 1. CALCUL DE LA SOLUTION INITIALE Calculer une solution realisable avec une methode constructive. 2. RECHERCHE DU MOUVEMENT Chercher le meilleur mouvement (permutation de deux operations du chemin critique par exemple) pour obtenir la meilleure solution voisine, hormis par les mouvements places dans la liste tabou. 3. MISE A JOUR DE LA LISTE Stocker le mouvement dans la liste tabou, enlever le mouvement le plus ancien de la liste. ^ 4. CONDITION D'ARRET Recommencer la recherche de solution jusqu'a veri er une condition d'arr^et (nombre limite de mouvement, temps de calcul, etc). Fig. 1.3 - Algorithme tabou La methode tabou. La methode tabou, elaboree par F. Glover [54] [55] est basee sur les notions de voisinage de solution et de mouvements interdits. Le voisinage d'une solution est un ensemble de solutions que l'on peut atteindre a partir de la premiere en e ectuant un mouvement prede ni (permutation de deux operations par exemple). Chaque mouvement est ajoute dans une liste de taille xee (liste tabou) qui contient les mouvements interdits. Le principe de l'algorithme est donne dans la gure 1.3. La notion de voisinage, mais egalement la taille de la liste tabou et les conditions d'arr^et peuvent ^etre tres di erentes. Nous presentons maintenant les voisinages les plus connus : { Une solution voisine s d'une solution s est obtenue en permutant deux operations u et v successives sur la m^eme machine si l'arc 0 CHAPITRE 1. LE PROBLE ME DU JOB-SHOP 28 ( ) est sur le chemin critique. De plus, P.J.M. Van Laarhoven et al. [106] montrent la propriete qu'il existe forcement une sequence de mouvement qui mene a une solution optimale. { Un deuxieme voisinage est donne par H. Matsuo et al. [79]. Ils utilisent la m^eme regle que les precedents avec la restriction que dans les arcs entrant de , au moins un ne soit pas sur le chemin critique (la m^eme chose pour les arcs sortant de ). Dans ce cas, la solution optimale peut ne pas ^etre atteinte par une sequence de mouvements mais cela limite la taille du voisinage etudie. { M. Dell'Amico et M. Trubian [33] proposent une generalisation du premier voisinage. Dans ce cas, plus d'une permutation est possible en m^eme temps. La propriete de P.J.M. Van Laarhoven est veri ee. { M. Dell'Amico et M. Trubian [33] proposent egalement un voisinage par blocs. Un bloc est une sequence d'operations sur une machine telle que les arcs entre deux operations successives sont sur le chemin critique. Si le bloc s'ecrit comme = ( ) ou et sont des blocs et une operation, deux solutions voisines sont donnees par ( ) et ( ). La propriete de P.J.M. Van Laarhoven est encore veri ee. u; v u v b 0 b b 00 b 0 b ; x; b 00 x 0 00 x; b ; b 0 00 b ;b ;x E. Taillard [103] a propose recemment un algorithme parallele pour resoudre le probleme du job-shop. Il utilise le premier voisinage cite pour la mise en uvre informatique de l'algorithme sur un reseau de transputers. La methode tabou est egalement utilisee pour la resolution de job-shop avec contraintes d'outillages [114]. La procedure tabou est particulierement interessante car elle peut ^etre arr^etee soit en fonction de la valeur de la solution courante, soit en fonction du temps de calcul ecoule. Ainsi, il est possible de trouver un compromis entre e ort de calcul et qualite de la solution obtenue. La diculte principale reside dans l'equilibre entre l'e ort de construction d'une solution admissible de depart et l'e ort d'amelioration. En e et, meilleure est la solution de depart et moins l'on a a ameliorer 1.3. LES METHODES DE RESOLUTION 29 celle-ci pour s'approcher de l'optimal. Ce probleme n'a pas encore fait l'objet d'etudes importantes. La methode tabou est d'autant plus ecace que le probleme traite est de petite taille. Dans ce cas, le nombre de solutions voisines reste limite et l'etude complete realisable. Par contre, cette methode est fortement ralentie par l'augmentation de la taille. En e et, plus le probleme est grand et plus le voisinage est important ce qui fait exploser le nombre de solutions voisines. Dans ce dernier cas, il serait interessant de reduire la taille du voisinage. Pour l'instant, il n'existe pas d'articles traitant des problemes de grande et tres grande taille. Le recuit simule. Le recuit simule f^ut developpe par S. Kirkpa- trick [67] [68]. Comme la methode tabou, il est une des approches les plus utilisees pour la resolution des problemes d'optimisation combinatoire. Basee sur un algorithme de simulation de recuit de metaux, elle s'inspire de modeles de la physique statistique. Le principe de voisinage est identique a la methode tabou, seules changent la selection de la solution suivante dans le processus iteratif et la condition d'arr^et ( gure 1.4). P.J.M. Van Laarhoven et E.H.L. Aarts [105], et P.J.M. Van Laarhoven [104] ont fait une etude tres approfondie de cette methode. Le fait d'a ecter aux solutions du voisinage une probabilite de selection permet de ne pas obliger la fonction objectif a decro^tre strictement. Si c'etait le cas, la solution obtenue serait dans un minimum local. Cette technique (comme le tabou) permet de selectionner des solutions voisines faisant augmenter la fonction objectif, avec une certaine probabilite. Des resultats recents sur cette technique sont donnes par P.J.M. Van Laarhoven et al [106]. Un article recent de H.R. Lourenco [77] compare le recuit simule avec d'autres methodes de voisinage comme le tabou. Les remarques faites sur le contr^ole entre le temps de calcul et la qualite de la solution pour la methode tabou restent valables pour le recuit simule. Il en est de m^eme pour les remarques sur la taille des problemes. 30 CHAPITRE 1. LE PROBLE ME DU JOB-SHOP 1. CALCUL DE LA SOLUTION INITIALE Calculer une solution realisable avec une methode constructive. 2. CALCUL DU MOUVEMENT Choisir dans le voisinage de la solution courante, une des solutions a ectees d'une certaine probabilite. ^ 3. CONDITION D'ARRET Recommencer la recherche de solution jusqu'a veri er une condition d'arr^et (valeur d'une fonction energie). Fig. 1.4 - Algorithme de recuit simule Les algorithmes genetiques. Les algorithmes genetiques sont ins- pires de la theorie de l'evolution et datent des travaux de I. Rechenberg [94], J.H. Holland [62] et H.-P. Schwefel [99]. Contrairement aux algorithmes de recherche locale tels que le recuit simule ou le tabou qui manipulent une seule solution realisable, les algorithmes genetiques considerent une population de solutions realisables appelees individus. Le but de la methode est de faire evoluer la population en e ectuant des mutations, des croisements et une selection des individus. La mutation est une operation unaire qui modi e la structure d'un individu (semblable a la mutation genetique). Le croisement est une operation binaire qui a partir de deux individus en produit deux nouveaux (cross-over pour le croisement des genes). La phase de selection consiste a supprimer les individus les moins forts (les solutions les moins interessantes). Le principe des algorithmes genetiques est donne dans la gure 1.5. L'idee de base est que travailler avec une population permet d'identi er et d'explorer les proprietes qu'ont en commun les bonnes solutions. Comme les types de voisinage sont varies pour les methodes tabou ou recuit simule, les types de mutation, de croisement et de selection peuvent ^etre nombreux. De plus, quelques amenagement de l'algorithme 1.3. LES METHODES DE RESOLUTION 31 1. CALCUL DE LA POPULATION INITIALE Construire une population de solutions realisables en utilisant des methodes constructives (cf section 1.3.3.1). 2. CALCUL DES NOUVEAUX INDIVIDUS Accro^tre la population en ajoutant des individus issus de mutations ou de croisements d'individus de la generation precedente. 3. SELECTION DES INDIVIDUS Selectionner les meilleurs individus pour revenir a la taille de la population initiale. ^ 4. CONDITION D'ARRET Recommencer les croisements et les mutations jusqu'a veri er une condition d'arr^et. Fig. 1.5 - Algorithme genetique 32 CHAPITRE 1. LE PROBLE ME DU JOB-SHOP precedent sont possibles comme l'utilisation de methodes amelioratrices (tabou, recuit simule, etc) pour faire evoluer les individus apres la phase de mutation et de croisement en vue d'avoir des solutions dans des minima locaux. De nombreux travaux ont ete realises sur les algorithmes genetiques et le job-shop. Parmi ceux-ci, nous pouvons citer L. Davis [32], E. Falkenauer [41], U. Dorndorf [34] et K. Nakano [83]. Les problemes lies a cette methode sont extr^emement nombreux. Le premier est bien entendu la taille de la population et sa creation. Prendre une population nombreuse ralentirait considerablement la phase de mutation et croisements alors qu'une taille reduite peche par un manque de diversite ce qui est contraire a la philosophie de la methode. Le deuxieme probleme appara^t quand la taille de l'instance traitee devient importante. Dans ce cas, deux solutions tres eloignees au niveau des sequences sur les machines peuvent avoir des valeurs de fonction objectif proches. Il est alors dicile de trouver des proprietes fortes caracterisant les bonnes solutions. Ceci est par contre possible quand le probleme est de petite et moyenne taille. Les methodes amelioratrices dediees. Certaines methodes ame- lioratrices sont completement dediees au probleme du job-shop. Concues specialement pour ce type de probleme, elles utilisent au maximum les structures de celui-ci. Nous pouvons citer, pour commencer, les techniques d'insertion de F. Werner et A. Winkler [113]. A partir d'une solution realisable trouvee par une methode constructive utilisant une technique semblable (cf 1.3.3.1), la procedure iterative selectionne une operation appartenant au chemin critique et tente de l'inserer a un autre endroit dans la sequence des operations sur la machine. Dans cette technique, le voisinage d'insertion peut ^etre plus ou moins grand selon que l'on desire explorer plus ou moins de solution avant d'e ectuer l'insertion. R. Vancheeswaran et M.A. Townsend [107] propose une procedure d'optimisation appelee \critical job perturbation procedure ". Le principe est de traiter les operations du job critique, job dont la n de la 1.3. LES METHODES DE RESOLUTION 33 derniere operation determine la n de l'ordonnancement. Certaines de ses operations sont placees avant les operations des jobs precedents sur les m^emes machines. La procedure recalcule ensuite les dates de debut des operations. Si les changements e ectues n'ameliorent pas la fonction objectif, un autre job est traite. Le choix du job critique peut ^etre fait en fonction d'autres criteres comme le rang, somme des numeros de place dans les sequences d'operations des di erentes machines. Dans ces deux methodes, l'inter^et majeur est la exibilite d'utilisation. En e et, il est possible de contr^oler pour l'une le nombre de positions a explorer pour l'insertion et pour l'autre, le choix ou non d'avancer les operations du job critique dans le sequencement des machines. Ce contr^ole permet donc de tenir compte de la taille du probleme traite et ainsi limiter l'espace de recherche. Toutefois, ne permettant pas de degradation de la solution courante, ces methodes ne permettent pas de sortir de minima locaux. 1.3.3.3 Les reseaux de neurones Depuis quelques annees, la theorie des reseaux de neurones s'est beaucoup developpee. Lancee par W.S. Mc Culloch et W.H. Pitts [80] en 1943, elle a pour but de simuler le fonctionnement du cerveau humain. C'est dans les annees 1960 qu'un premier reseau de neurones est realise : il s'agit du perceptron de F. Rosenblatt [97]. Apres que les limites theoriques du perceptron aient ete montrees, les reseaux de neurones ont retrouve un second soue gr^ace au travaux de J. Hop eld [63]. Cette technique nouvelle a d'abord ete testee sur des problemes traites par l'intelligence arti cielle (reconnaissance de formes, traitement du signal, aide a la decision). Puis, reprise par des specialistes de recherche operationnelle, elle a ete utilisee pour la resolution des problemes du domaine. Le job-shop n'a pas echappe a cette regle, et les recherches sur sa resolution a partir de reseaux de neurones sont actuellement en cours dans de nombreux laboratoires. Nous citerons sur ces travaux, les articles de C.S. Zhang et al. [115], et de D.N. Zhou et al. [116]. 34 CHAPITRE 1. LE PROBLE ME DU JOB-SHOP 1.3.3.4 L'intelligence arti cielle L'intelligence arti cielle est un outil de plus en plus present dans le domaine de l'ordonnancement. Son principe de resolution peut tres bien s'appliquer pour des problemes d'optimisation combinatoire [14]. Le raisonnement temporel, la propagation de contraintes et la recherche combinatoire sont des notions que l'on retrouve a la fois dans la recherche operationnelle et l'intelligence arti cielle. E. Bensana [14] decrit l'impact que peut avoir l'intelligence arti cielle sur des problemes d'ordonnancement. 1.3.3.5 Caracterisation des solutions admissibles Certaines demarches tendent, plut^ot que trouver une solution optimale du probleme, a chercher des classes de solutions admissibles. L'approche retenue est alors de chercher, a partir des conditions initiales du probleme et d'un objectif xe, a exprimer les conditions necessaires que tout ordonnancement admissible devra respecter [39]. Peut intervenir dans ce type de recherche, la notion de dominance, qui permet de dire si une t^ache doit preceder toutes les autres ou succeder a toutes. Dans ce contexte, on peut citer les travaux de J. Erschler et al. [38] [37] et ceux de J. Carlier [25] [26] [27]. Ces travaux concernent essentiellement le probleme d'ordonnancement sur une machine unique, mais une application au probleme du job-shop est propose par J. Carlier et E. Pinson [28] et E. Pinson [87]. L'originalite de l'approche est de developper des regles d'inference qui travaillent uniquement a partir des contraintes du probleme, sans prendre en compte le moindre critere, et qui vont permettre, par des deductions symboliques (du type relations de precedence ou de nonprecedence entre deux operations ou entre une operation et un groupe d'operations par exemple) de reduire l'ensemble initial a une partie des solutions admissibles [76]. Dans le m^eme esprit, F. Roubellat et al. [73] propose une notion de t^aches permutables. Dans ce cas, l'ordonnancement se fait en deux 1.3. LES METHODES DE RESOLUTION 35 temps. Dans une premiere phase on determine des groupes de t^aches de telle sorte que toute permutation dans chacun des groupes peut donner un ordonnancement admissible. Dans la seconde, il ne reste plus qu'a choisir une permutation dans chacun des groupes en fonction de l'objectif que l'on recherche. Cette derniere approche est surtout interessante dans le cas du job-shop reactif (cf chapitre 4) car elle permet de changer de solution en fonction du deroulement de l'ordonnancement previsionnel. 1.3.4 Les methodes exactes Le but des methodes exactes est de trouver, en un temps de calcul le plus court possible, la solution optimale du probleme. Pour tous les problemes de l'optimisation combinatoire classes NP-complet, ceci constitue un de . Si les recherches sur les methodes exactes sont tres nombreuses pour des problemes phare comme le voyageur de commerce, le job-shop a interesse de nombreux auteurs. Parmi les methodes de resolution exactes de problemes d'optimisation combinatoire et en particulier de problemes d'ordonnancement, le branch and bound est la plus utilisee [9] [30] [48] [72] [81]. Le principe de base de cette methode est de separer l'espace des solutions en plusieurs parties (phase de branchement) et evaluer pour chacune de ces branches une borne inferieure de ses solutions. Le but est de couper les branches dont on sait qu'elles ne contiennent pas de solutions d'evaluation inferieures a une solution de reference. Les techniques de branchement et de calcul de bornes inferieures sont tres variees [19] [70], nous ne donnerons ici que quelques references bibliographiques de bases permettant d'avoir plus de details sur ces methodes. A partir de 1965, un certain nombre d'approches de resolution utilisant le principe de generation d'ordonnancements actifs [53] ont ete proposees : S. Ashour et al. [8], G.H. Brooks et C.R. White [21], M. Florian et al. [47]. D'autres algorithmes de ce genre furent developpes par E. Balas [10] en 1969, B.J. Lageweg et al. [70], J.R. Barker et G.B. McMahon [12], J. Carlier et E. Pinson [28], D. Applegate et W. Cook [7], J. Carlier et E. Pinson [29]. 36 CHAPITRE 1. LE PROBLE ME DU JOB-SHOP Comme nous l'avons vu dans la section 1.2.2, la programmation mathematique est un outil de modelisation interessant pour le probleme du job-shop. Recemment, des tests ont ete e ectues sur les modeles classiques presentes dans la section 1.2.2 par C.S. Liao et C.T. You [75]. Une comparaison des temps de calcul est exposee dans leur article, mais les exemples traites sont de petite taille (3 a 5 jobs et 3 a 10 machines). Pour des tailles plus importantes, le temps de calcul semble trop important pour que ces methodes soient directement utilisables. L'approche polyedrale (cf 1.2.3) n'a pas ete tres utilisee en tant que telle pour la mise en uvre de methode de resolution. Cette technique dite de plan de coupe est beaucoup utilisee, avec des resultats probants, pour la resolution du voyageur de commerce par exemple. Le principe d'un tel algorithme est de calculer la solution donnee par la resolution d'un programme lineaire dont les contraintes forment un sous-ensemble des contraintes de nissant le polyedre. La deuxieme phase consiste a analyser la solution trouvee pour determiner les contraintes du probleme non veri ees. Ces contraintes sont introduites dans le programme lineaire et une nouvelle solution est calculee. La diculte reside dans le fait que pour une solution donnee par la resolution du programme lineaire, il est tres dicile de trouver les contraintes non respectees. La structure du polyedre est mathematiquement interessante, mais son exploitation reste trop dicile. D. Applegate et W. Cook [7] ont utilise les contraintes les plus simples pour developper un algorithme branch and bound. La programmation dynamique, developpee par R. Bellman [13] est une des techniques pour la resolution optimale de problemes combinatoires. Tres utilisee pour les problemes a une machine [61], cette technique n'a pas ete utilisee pour la resolution du job-shop. Comme nous le disions plus haut, trouver une solution optimale pour un probleme NP-complet constitue un de . Il n'est donc pas surprenant de voir qu'un probleme de taille 10 jobs, 10 machines propose par M.L. Fischer et G.L. Thompson dans l'ouvrage de J.F. Muth et G.L. Thompson [82] en 1963 ne soit resolu par J. Carlier et E. Pinson [28] qu'en 1989. Pour des tailles petites et quelques fois moyennes 1.3. LES METHODES DE RESOLUTION 37 des problemes, les algorithmes exacts peuvent ^etre performants, mais des que la taille augmente, ces methodes perdent leur ecacite et deviennent inutilisables. 1.3.5 Les methodes de relaxation Les methodes de relaxation ont un double r^ole dans la resolution de problemes d'optimisation combinatoire [52]. D'une part, elles donnent de bonnes bornes inferieures pour augmenter l'ecacite de methodes branch and bound, d'autre part, elles sont a la base de methodes de resolutions comme la relaxation lagrangienne [42] [43] [44] [45]. Le principe de ces methodes et de relaxer un certain nombre de contraintes de facon a rendre plus facile la resolution du probleme. Dans le cas du job-shop, M.L. Fisher et al. [46] propose une approche tres interessante. Dans celle-ci, ils experimentent dans un premier temps la relaxation des contraintes de ressources de machines et ensuite des contraintes de gammes operatoires. Cette methode donne de bonnes solutions pour des problemes de petite taille mais n'a pas ete testee pour des tailles plus importantes. 1.3.6 Les methodes de decomposition Les methodes de decomposition spatiale ne sont pas reellement des methodes de resolution du probleme du job-shop. Le principe d'une telle approche est de casser la complexite du probleme en decomposant le probleme initial en plusieurs sous-problemes plus faciles a resoudre. Le but d'une telle methode est regrouper les jobs utilisant le m^eme ensemble de machines. L'objectif est alors de rendre les plus independant possibles les groupes de jobs. Pour cela, il faut qu'un job n'utilise que des machines lies a son groupe, et qu'une machine ne traite que des jobs d'un m^eme groupe. Pour decomposer un probleme de ce type des methodes comme la technologie de groupe peuvent ^etre utilisees [35]. Nous ne voulons pas detailler ici toutes les methodes de decomposition, mais nous donnons simplement quelques references [35] [88]. Quand le probleme est decompose, deux cas se presentent. La decomposition est dite parfaite (les sous problemes sont completement independants). La 38 CHAPITRE 1. LE PROBLE ME DU JOB-SHOP resolution de chacun des sous-problemes separement donne une solution globale de l'ordonnancement. Si la decomposition n'est pas parfaite (certains jobs passent sur des machines liees a des groupes di erents) la resolution de chaque sous-probleme ne donne pas une solution realisable du probleme global et il faut traiter les problemes de liens residuels. H. Lemonias [74] propose une methode de synchronisation pour ce probleme. 39 Chapitre 2 Une approche par agregation La methode proposee maintenant s'attache a la resolution de probleme de job-shop statique et deterministe. L'objectif des heuristiques qui en decoulent est la minimisation de la longueur maximale de l'ordonnancement (Cmax). Si la plupart des methodes mises en uvre ces dernieres annees (cf 1.3.3.1) utilisent comme elements de base les operations (regles de priorite) [84] [113] ou les machines (Shifting Bottleneck Procedure) [2], notre approche utilise les jobs. Le principe de cette methode est de construire des ordonnancements partiels en agregeant a un ordonnancement deja etabli un job ou un autre ordonnancement partiel. Les algorithmes generaux qui en resultent sont bases sur deux procedures particulieres, les procedures de selection des jobs et d'agregation. L'un des objectifs de cette approche par agregation est de contr^oler d'une part l'e ort d'optimisation en fonction de la taille de l'instance traitee, mais egalement le temps de calcul et la qualite de la solution. Pour cela, un certain nombre d'heuristiques sont proposees, certaines privilegiant la rapidite et sont ainsi adaptees a la resolution de problemes de grande et tres grande taille, d'autres optimisent de facon plus ne et sont plus adaptees a des problemes de petite et moyenne taille. Dans un premier temps, nous allons de nir un ordonnancement partiel sur un ensemble de jobs et le principe d'agregation entre deux jobs. 40 CHAPITRE 2. UNE APPROCHE PAR AGRE GATION Ensuite, cette approche sera generalisee pour les agregations d'un job et d'un ordonnancement partiel et l'agregation de deux ordonnancements partiels. Dans une deuxieme partie, nous proposerons un algorithme general de resolution et des procedures de selection et d'agregation particuliere bases sur le principe d'agregation entre un job et un ordonnancement partiel. Ensuite, un algorithme general et des procedures d'agregation bases sur le principe d'agregation de deux ordonnancements partiels seront decrites. En n, nous parlerons de procedures d'amelioration locale. Pour nir, les heuristiques proposees seront testees sur un ensemble de problemes representatifs. 2.1 Le principe de l'agregation Dans cette nouvelle approche, les jobs sont ordonnances les uns apres les autres et a chaque etape un ou plusieurs ordonnancements partiels realisables sont crees. Ce principe repose sur deux concepts de la theorie de l'ordonnancement : la selection selon des regles de priorite et la creation d'ordonnancements partiels. Les deux etapes cles des algorithmes generaux donnes plus loin sont donc les procedures de selection d'un job (ou d'un ordonnancement partiel) selon un critere prede ni et l'agregation du job (ou de l'ordonnancement partiel) a un ordonnancement partiel courant. Reprenons tout d'abord le modele sous forme de graphe disjonctif que nous avons de ni dans la section 1.2.1. Un probleme de job-shop est represente par un graphe = ( [ ), ou est l'ensemble des sommets du graphe , est l'ensemble des arcs conjonctifs et est l'ensemble des arcs disjonctifs). Dans la suite de ce chapitre, nous travaillerons a partir de ce modele. G G X; C D X C D 2.1.1 Ordonnancement partiel sur jobs l A partir du probleme de job-shop = ( [ ) a jobs, il est possible d'extraire un sous-probleme a jobs avec . Ce sous-probleme est represente par le graphe disjonctif , graphe partiel du graphe . Nous pouvons donc ecrire = ( [ ) ou est G X; C Pl D n l l < n Gl G Gl Xl ; Cl Dl Xl 2.1. LE PRINCIPE DE L'AGRE GATION 41 compose des sommets et et des sommets associes aux operations des jobs de l'ensemble l . Les ensembles d'arcs l et l sont composes des arcs de liant les sommets de l. deb f in P C G D X Le sous-probleme l et son graphe disjonctif associe l etant denis, nous appellerons ordonnancement partiel l une solution de l. Cette solution correspond a un arbitrage complet et compatible des paires d'arcs disjonctifs, selection pour chaque paire d'un des deux arcs (cf 1.2.1). L'ensemble des arcs disjonctifs l est reduit a l'ensemble l. Pour que la solution l soit realisable il est bien sur necessaire que le graphe solution l = ( l l [ l ) soit acyclique. Par la suite, nous noterons la longueur de l'ordonnancement partiel max( l ). Pour une representation simpli ee de la solution sur le graphe, il n'est pas necessaire de conserver la totalite des arcs de l , mais garder pour chaque clique de disjonction un chemin representant l'ordre de passage des operations sur la machine. P G P P D D P G X ;C D C P D Pour chaque solution l du probleme a jobs, nous pouvons de nir deux nouvelles variables par operation. Ces variables seront appelees date de debut au plus t^ot et date de debut au plus tard, et seront respectivement notees i;j et i;j pour une operation i;j . La date au plus t^ot i;j est la date avant laquelle l'operation i;j ne peut commencer, soit parce que l'operation precedente dans sa gamme operatoire n'est pas achevee, soit parce que l'operation precedente sur la machine n'est pas nie. Sur le graphe solution l, i;j represente le plus long chemin (somme des ponderations sur les sommets) du sommet au sommet . Sur le graphe i;j exclu. Nous associons la valeur max au sommet l, i;j represente le plus long chemin du sommet i;j inclus au sommet et represente ainsi une latence de n. Le calcul de i;j se fait donc en enlevant a la valeur max, la somme des temps operatoires du chemin le plus long. Au niveau de l'ordonnancement, ces variables donnent respectivement le temps minimum qui doit s'ecouler avant de pouvoir commencer l'operation i;j , et le temps minimum qui doit s'ecouler apres l'execution de l'operation pour achever l'ordonnancement. P r l q O r O G r deb O G C q f in O f in q C O 42 CHAPITRE 2. UNE APPROCHE PAR AGRE GATION A partir de ces deux variables, nous pouvons introduire la notion de marge associee a une operation. Nous noterons mai;j la marge associee a l'operation Oi;j . Celle-ci est egale a : mai;j = Cmax , (ri;j + qi;j + pi;j ) (2.1) Elle represente, au niveau de l'ordonnancement, la valeur du decalage possible de l'operation sans que le resultat de l'ordonnancement (Cmax) ne soit altere. Dans le graphe solution, nous appellerons chemin critique, un chemin liant deb a fin dont tous les sommets ont une marge nulle. En generalisant, nous appellerons graphe critique, un sous-graphe du graphe solution dont tous les sommets ont une marge nulle. Cela signi e que si l'on decale une operation de ce chemin ou de ce graphe critique, la duree de l'ordonnancement sera augmentee d'autant. 2.1.2 L'agregation de deux jobs L'agregation la plus simple est certainement celle qui a partir de deux jobsLJ1 et J2 genere un ordonnancement. Nous la noterons J1 L J2, le signe representant l'agregation. Ce cas particulier est polyn^omial et constitue un job-shop a deux jobs. Nous donnons maintenant le principe de resolution developpe par S.B. Akers [6] et l'algorithme performant de P. Brucker [22] qui en decoule. La methode est illustree sur un exemple ( gure 2.1). Considerons maintenant l'exemple avec les jobs suivants : J1 est constitue de trois operations. O1;1 a un temps operatoire de 4 unites de temps sur M1, O1;2 de 3 unites de temps sur M2, et O1;2 de 6 unites de temps sur M3. En ce qui concerne J2, les trois operations sont O2;1 qui necessite 5 unites de temps sur M1, O2;2 qui necessite 2 unites de temps sur M3, et O2;3 qui necessite 7 unites de temps sur M2. Comme nous l'avons vu dans la section 1.3.2.2, ce probleme peut ^etre ramene a un probleme de plus court chemin dans le plan avec obstacles rectangulaires ( gure 2.1). P. Brucker [22] propose dans un 2.1. LE PRINCIPE DE L'AGRE GATION 43 J2 6 F 14 =(13,14) , , , , , 2 , , ,, 7 3 5 1 O = (0,0) , ,, ,, 4 Fig. 2.1 - 7 13 Plan avec obstacles - J1 CHAPITRE 2. UNE APPROCHE PAR AGRE GATION 44 premier temps de modeliser le probleme du plan avec obstacles sous la forme d'un reseau. Ce reseau est constitue de deux sommets et dont les coordonnees sont respectivement (0 0) et Pjj==1n2 2;j Pjj==1n1 1;j , et des sommets associes au angles nord-ouest ( ) et sud-est ( ) des obstacles rectangulaires. Il existe un arc : O ; p NO ; F p SE { entre le sommet et les sommets et du premier obstacle rencontre en partant du point et en se deplacant suivant la droite = . O NO SE O y x { entre un sommet d'un obstacle et les sommets du premier obstacle rencontre en partant du point et en se deplacant suivant la direction = . NO NO y x { entre un sommet d'un obstacle et les sommets du premier obstacle rencontre en partant du point et en se deplacant suivant la direction = . SE SE y x { entre un sommet et si a partir de ce sommet et suivant la jX =n2 direction = on arrive sur une des droites = 2;j ou F y x = X j =n1 j =1 x y j =1 p ;j . p1 Les arcs, ainsi construits sur ce reseau ( gure 2.2), sont ponderes par le maximum des longueurs des projections sur les axes de coordonnees. Ce reseau peut ^etre construit en ( A log A) etapes ou A est le nombre d'obstacles dans le plan. O n n n La deuxieme partie de l'algorithme consiste a chercher le plus court chemin dans le reseau. Cette phase necessite ( A ) etapes. Le resultat obtenu donne la duree totale de l'ordonnancement et la sequence des operations sur les di erentes machines ( gure 2.3). O n 2.1. LE PRINCIPE DE L'AGRE GATION 45 : 2 NO S S 7 1 NO Z SS ZZ Z~ 2 SE H S S H H HHSHjSw O * 7 SS 3 NO SS > SS w 1 SE XXXXz 3 SE 9 5 4 7 7 9 1 7 7 F 9 Reseau associe au plan Fig. 2.2 - M 9 O O 1;1 2;1 M O 2 O 1;2 2;3 M O 3 4 Fig. 2.3 - 7 9 2;2 O 11 Resultat de l'exemple 1;3 18 CHAPITRE 2. UNE APPROCHE PAR AGRE GATION 46 2.1.3 L'agregation d'un job et d'un ordonnancement partiel Le principe d'agregation developpe dans la section precedente est polyn^omial L et le resultat obtenu est optimal. Dans le cas de l'agregation +1 , il ne semble pas possible de trouver un algorithme polyn^omial et de faible complexite donnant une solution optimale. Les L algorithmes developpes sur le principe de l'agregation +1 seront de type heuristique. Jl Pl Jl Pl L'agregation +1 L consiste a donner une sequence des operations sur chaque machine en conservant l'ordre des operations donne par l'ordonnancement partiel . Cela revient a creer un ordonnancement partiel +1. Jl Pl Pl Pl Au niveau du graphe disjonctif, cela consiste a reprendre le resultat de l'ordonnancement des premiers jobs = ( [ ) et a ajouter les sommets correspondant au job +1 pour construire le graphe disjonctif +1 , dont certaines des disjonctions sont deja arbitrees (celles de ). Le principe d'agregation utilise sur ce graphe a pour but de selectionner pour chaque paire d'arcs disjonctifs de +1 non arbitree, un unique arc. Pour que l'ordonnancement partiel +1 soit realisable il est bien sur necessaire que le graphe +1 obtenu soit acyclique (cf 1.2.1). l Gl Xl ; Cl Dl Jl Gl Pl Dl Pl Gl 2.1.4 L'agregation de deux ordonnancements partiels L'agregation de deux ordonnancements partiels et est en fait une generalisation du concept decrit dans la section precedente. Comme dans l'agregation d'un job avec un ordonnancement partiel, le principe est de conserver les ordres de passage des operations sur les machines correspondantes dans les deux ordonnancements partiels. L'objectif est alors d'inserer pour chaque machine les operations de (resp. ) utilisant celle-ci dans la sequence donnee pour le passage des operations de (resp. ). Pl Pr Pl Pr Pr Pl Au niveau du graphe disjonctif, cela consiste a reprendre les re- 2.2. LES ALGORITHMES DE TYPE J L+1 L L 47 P sultats des ordonnancements des premiers jobs l = ( l l [ l) et des suivants r = ( r r [ r ) pour creer le graphe disjonctif l+r = ( l [ r l [ r [ l [ r ), dont une partie des disjonctions est arbitree. Ensuite, le but est d'arbitrer les disjonctions pour chaque paire d'arcs disjonctifs de l+r . Pour que l'ordonnancement partiel l+r soit realisable, il est bien sur necessaire que le graphe l+r obtenu soit acyclique (cf 1.2.1). l r G G X X ;C X ;C C D G X ;C D D D D P G 2.2 Les algorithmes de type J +1 L P l l Le type d'agr egation que nous allons maintenant developper est L l'agregation l+1 l . Pour commencer, nous donnons un algorithme general de resolution du job-shop, puis nous detaillerons, dans la suite, les procedures de selection des jobs et les procedures d'agregation. J P 2.2.1 L'algorithme general de resolution L'idee de base de l'algorithme general de resolution base sur l'agregation l+1 L l est de traiter les jobs les uns apres les autres en construisant a chaque etape, un ordonnancement partiel. J P L'algorithme constructif de la gure 2.4 decrit le deroulement de la methode. On constate que cette methode repose sur deux procedures particulieL res, une de selection des jobs (pas 2 et 4) et une d'agregation l+1 l (pas 5). Les procedures de selection ferontLl'objet de la section 2.2.2 alors que des procedures d'agregation l+1 l seront proposees dans les sections 2.2.3 2.2.4 et 2.2.5. J P J P Cet algorithme constructif peut ^etre legerement modi e par l'ajout entre les pas 5 et 6 d'une procedure d'amelioration locale. Ce type de procedure sera discute dans la section 2.4. L'algorithme propose precedemment est sequentiel et ne permet pas d'envisager des calculs en parallele. 48 CHAPITRE 2. UNE APPROCHE PAR AGRE GATION 1. INITIALISATION Faire la liste des jobs a ordonnancer. 2. SELECTION DES DEUX PREMIERS JOBS Utilisation d'une regle de priorite pour la selection des deux premiers jobs (somme des temps operatoires). 3. AGREGATION Utilisation d'une procedure d'agregation pour la creation du premier ordonnancement partiel (algorithme de P. Brucker, cf 2.1.2). 4. SELECTION DU JOB A AGREGER Utilisation d'une regle de priorite pour la selection du job a agreger (somme des temps operatoires). 5. AGREGATION Utilisation d'une procedure d'agregation du type J +1 L P . ^ 6. CONDITION D'ARRET l l (a) Si tous les jobs sont traites, arr^eter. (b) Sinon, retourner en 4. Fig. 2.4 - Algorithme general base sur J +1 L P l l 2.2. LES ALGORITHMES DE TYPE J L+1 L L 49 P 2.2.2 Les procedures de selection des jobs Pour ce qui est des procedures de selection des jobs, nous proposons, le m^eme type de regles de priorite que pour les algorithmes constructifs bases sur ce principe (cf 1.3.3.1), mais appliquees aux jobs au lieu des operations. En premier lieu, il est possible d'envisager des regles de priorite statiques. Ces regles ne dependent que des donnees du probleme et sont independantes du processus de construction des ordonnancements partiels. Nous pouvons donc determiner des l'initialisation un ordre de selection des jobs lie par exemple a la duree totale de ceux-ci ou au nombre d'operations qu'ils contiennent. Dans un deuxieme temps, nous considererons des regles de priorite dynamiques tenant compte cette fois du deroulement du processus de construction des ordonnancements intermediaires. La priorite peut ^etre donnee au job dont l'operation la plus longue utilise une machine goulot (ayant le plus d'operations sur le chemin critique). Ce type de regles est bien entendu plus interessant mais demande des calculs supplementaires lors de la phase de selection. Nous ne voulons pas ici faire un catalogue des regles de priorite possibles pour la selection des jobs. Il est evident que l'on peut creer un nombre important de regles en generalisant celles existantes pour les algorithmes de liste. Pour tous les tests e ectues par la suite, nous ne considererons que la somme des temps operatoires de chaque job. L 2.2.3 Une procedure basee sur l'agregation J1 J2 La premiere methode d'agregation Jl+1 L Pl que nous proposons est iterative et basee sur le principe d'agregation de deux jobs [86]. A une certaine etape de l'algorithme general ( gure 2.4), un nouveau job est selectionne et le probleme Pl+1 Jl+1 L Pl est a resoudre. La procedure d'agregation utilise alors le fait que Pl est un ordonnancement partiel construit sur les jobs S = fJ1; :::; Jlg. Le principe est de selectionner un job Jy de S et de l'agreger avec le job Jl+1. Cette agregation CHAPITRE 2. UNE APPROCHE PAR AGRE GATION 50 permet d'arbitrer les disjonctions entre les operations de ces deux jobs. A l'iteration suivante, un job de S n fJ g est selectionne et agrege avec J +1 en tenant compte de tous les arbitrages determines auparavant et des dates de debut au plus t^ot et au plus tard issues du graphe G associe a l'ordonnancement partiel P . y l l l Cette procedure est basee sur une generalisation de l'algorithme de P. Brucker pour le probleme a deux jobs. P. Brucker et B. Jurisch [23] ont developpe un algorithme permettant de resoudre le probleme de job-shop a deux jobs tenant compte de precedences et de dates au plus t^ot r et au plus tard q . L'algorithme que nous proposons est donne dans la gure 2.5. i;j i;j 2.2.4 Des procedures d'agregation par decoupage du temps Nous proposons maintenant des techniques d'agregation basees sur un decoupage du temps en intervalles, suivi de l'insertion des operations du job a agreger. Dans un premier temps, nous decrirons une methode ou les operations sont reparties dans les intervalles et inserees en une seule fois. La deuxieme procedure insere les operations iterativement et dans l'ordre de la gamme operatoire de facon a tenir compte des decalages possibles a l'issue de chaque insertion. En n, la troisieme procedure insere egalement les operations iterativement mais dans un ordre xe par une regle de priorite. 2.2.4.1 Decoupage du temps et agregation globale Cette procedure repose sur l'idee simple que les premieres operations d'un job J +1 a agreger, doivent ^etre inserees au debut de l'ordonnancement partiel alors que les dernieres doivent plut^ot ^etre inserees a la n. Ceci se justi e aisement par le fait que si la derniere operation O +1 +1 est placee au debut de l'ordonnancement courant, celui-ci est pratiquement decale de la longueur de J +1 (la somme des temps operatoires), car il faut respecter la gamme operatoire et toutes les operations de J +1 seront donc en debut d'ordonnancement. De m^eme, si O +1 1 est placee en n d'ordonnancement, celui-ci sera egalement augmente de l l ;nl l l l ; 2.2. LES ALGORITHMES DE TYPE J +1 L L P L 51 1. INITIALISATION Faire la liste S des jobs de P . 2. SELECTION DU JOB A AGREGER Selectionner un job J de S selon une regle de priorite (somme des temps operatoires). 3. AGREGATION Agreger le job J selectionne avec J +1 en utilisant la procedure de P. Brucker et B. Jurisch (J L J +1). 4. MISES A JOUR Mettre a jour les precedences, les dates de debut au plus t^ot r et au plus tard q dans l'ordonnancement partiel, et supprimer J de S . ^ 5. CONDITION D'ARRET l x x l x l i;j i;j x (a) Si tous les jobs de S sont traites ou si toutes les disjonctions sont arbitrees, arr^eter. (b) Sinon, retourner en 2 Fig. 2.5 - Algorithme d'agregation base sur J1 L J2 CHAPITRE 2. UNE APPROCHE PAR AGRE GATION 52 la longueur de l+1 car toutes les operations de l'ordonnancement. J l+1 J seront a la n de Dans un premier temps, nous allons decouper la duree totale de l'ordonnancement partiel max( l), en autant d'intervalles qu'il y a d'operations dans le nouveau job. Pour cela, nous commencons par calculer la marge relative, notee , disponible pour l'insertion des operations : C P MR MR max , = X j =n +1 l C j =1 (2.2) l+1;j p La marge relative ainsi calculee, nous proposons trois manieres de la repartir sur la duree totale de l. Bien entendu, d'autres repartitions pourraient ^etre envisagees. P { La repartition lineaire : la marge relative sera repartie de facon egale pour chaque operation l+1;j et l'intervalle donne pour l'insertion d'une operation sera de longueur : O l+1;j + p h h (2.3) MR l+1 n i Ainsi, l'operation l+1;1 devra ^etre inseree dans l'intervalle 0 l+1;1 + nMR +1 , l'operation l+1;2 dans MR MR l+1;1 + n +1 l+1;1 + l+1;2 + 2 n +1 et ainsi de suite. { La repartition geometrique : dans ce cas, une plus grande part de la marge relative est a ectee a l'operation l+1;1 et la part de la marge relative decro^t en s'approchant de la derniere operation. Nous obtenons des intervalles pour l+1;j de taille : p O ;p l i O l ;p p l O O l+1;j + (nl+1 + 1 , j ) M R p n 2 l+1 ( l+1 + 1) n (2.4) 2.2. LES ALGORITHMES DE TYPE J +1 L L P L 53 Ce type de decoupage est plus adapte a une agregation iterative comme celle qui sera presentee dans la section 2.2.4.2. { La repartition relative : nous considerons que les operations les plus dures a inserer sont celles dont le temps operatoire est le plus grand. Dans ce cas, les intervalles seront proportionnels au temps operatoire de l'operation. La taille de l'intervalle pour l'operation O +1 sera alors : l p +1 l ;j + ;j p +1 Xp r = r l ni =1 MR ;j +1 l (2.5) ;r Dans chacun des intervalles calcules, il faut maintenant inserer l'operation correspondante. Le principe est de construire la liste des emplacements disponibles pour placer l'operation. Un emplacement est en fait une position dans la sequence d'operations sur une machine. Sa taille ta est calculee en faisant la di erence entre la date de debut au plus tard de l'operation O qui suit et la date de n au plus t^ot de l'operation O qui precede. On a alors : a;b c;d ta = q a;b , (r + p ) c;d c;d (2.6) Ensuite, nous choisirons l'emplacement dont la di erence entre le temps operatoire et la longueur de l'emplacement est minimum. D'autres possibilites sont envisageables comme choisir l'emplacement dont la taille correspond le plus au temps operatoire de l'operation (di erence entre le temps operatoire et la longueur de l'emplacement est proche de zero). Dans cette etape, nous e ectuons une agregation dite globale car des que les intervalles sont xes pour chaque operation, le choix de l'insertion pour une operation est independant des autres. Ainsi, on pourrait commencer par inserer la derniere operation plut^ot que la premiere sans que cela ne change le resultat de la procedure. L'algorithme ainsi obtenu est donne dans la gure 2.6. Un exemple de ce type d'agregation est donne dans la gure 2.7. CHAPITRE 2. UNE APPROCHE PAR AGRE GATION 54 1. CALCUL DE LA MARGE RELATIVE Calcul de la marge relative MR en vue du decoupage en intervalles. 2. CALCUL DES INTERVALLES n +1 l (a) Decoupage lineaire. (b) Ou decoupage geometrique. (c) Ou decoupage relatif. 3. INSERTION DES OPERATIONS Pour chaque operation, insertion dans le meilleur emplacement de l'intervalle considere. 4. MISE A JOUR Calcul des dates au plus t^ot et au plus tard apres agregation. Fig. 2.6 - Algorithme de decoupage du temps et agregation globale 2.2. LES ALGORITHMES DE TYPE J O5 1 +1 L L P 55 L O5 2 ; O5 3 ; ; J5 M1 M2 M3 ? O1 1 ; O3 1 O2 2 ; O2 1 O3 2 ; ; O2 3 ; O1 3 ; M4 O4 3 ; ? O1 2 ; O3 3 ; ; O4 1 O2 4 ; 8 Fig. ? O4 2 ; ; 21 2.7 - Resultat de l'agr egation globale 30 56 CHAPITRE 2. UNE APPROCHE PAR AGRE GATION 2.2.4.2 Decoupage du temps et insertion iterative Le principe de cette procedure d'agregation est sensiblement le m^eme que la procedure de la section 2.2.4.1. Au depart, seul l'intervalle de la premiere operation est calcule, suivant l'un des principes expliques plus haut. Dans cet intervalle, l'operation va ^etre inseree dans l'emplacement le meilleur. Ensuite, les dates de debut au plus t^ot et au plus tard sont recalculees tenant compte des operations inserees. La deuxieme operation du job est ensuite traitee. Un nouvel intervalle de temps est calcule entre la n au plus t^ot de la premiere operation et la n de l'ordonnancement, et l'operation est ensuite inseree. Le processus se poursuit tant qu'il reste des operations non traitees. L'algorithme qui en decoule est donne dans la gure 2.8. Cette methode est moins rapide que la precedente du fait du recalcul des dates au plus t^ot et au plus tard, mais permet un meilleur choix de la zone d'insertion car la marge relative est recalculee apres chaque insertion. Une economie de temps de calcul pourrait ^etre faite si seulement la marge relative etait recalculee sans recalcul des dates au plus t^ot et au plus tard. Dans ce dernier cas, les perturbations apportees par les premieres insertions ne seraient pas repercutees dans la suite et cela reviendrait a une methode directe comme celle de la section 2.2.4.1. Les trois gurent qui suivent (2.9 2.10 2.11) montrent comment sont inserees les operations du job. 2.2.4.3 Decoupage du temps et insertion relative Tout en conservant les principes de decoupage du temps et insertion iteratives, nous proposons maintenant d'inserer les operations dans un ordre qui ne suit plus forcement celui de la gamme operatoire. En e et, certaines operations peuvent poser plus de dicultes que les autres pour ^etre placees dans l'ordonnancement partiel. Ceci peut ^etre d^u a la valeur du temps operatoire ou a un taux d'occupation de la machine deja tres eleve. Pour tenir compte de ce phenomene, l'algorithme de la gure 2.12 accorde un intervalle d'autant plus grand que l'operation est dicile a inserer. 2.2. LES ALGORITHMES DE TYPE JL+1 L PL 57 1. CALCUL DE LA MARGE RELATIVE Calcul de la marge relative pour les operations restant a traiter (calcul de MR sur l'intervalle entre la n de l'operation precedente et Cmax(Pl)). 2. CALCUL DE L'INTERVALLE POUR L'OPERATION COURANTE Calcul de l'intervalle sur un horizon compris entre la n de l'operation precedente et la n de l'ordonnancement. (a) Decoupage lineaire. (b) Ou decoupage geometrique. (c) Ou decoupage relatif. 3. INSERTION DE L'OPERATION COURANTE Pour l'operation courante, insertion dans le meilleur emplacement de l'intervalle considere. 4. MISE A JOUR Calcul des dates au plus t^ot et au plus tard tenant compte des operations deja inserees. 5. SELECTION DE L'OPERATION COURANTE (a) S'il reste des operations non traitees, selectionner l'operation suivante et retourner en 1. (b) Sinon, arr^eter. Fig. 2.8 - Algorithme de decoupage du temps et insertion iterative CHAPITRE 2. UNE APPROCHE PAR AGRE GATION 58 O5 1 O5 2 ; O5 3 ; ; J5 M1 M2 ? O1 1 ; O3 1 ; O1 2 ; M3 O2 2 ; O4 1 ; 8 Fig. 2.9 - O1 3 ; M4 ; ; O3 2 ; O4 3 ; O2 3 ; O2 1 O3 3 O4 2 ; O2 4 ; 30 Premiere insertion pour l'agregation iterative 2.2. LES ALGORITHMES DE TYPE J +1 L L P 59 L O5 2 O5 3 ; ; J5 O5 1 ; M1 M2 M3 O1 1 O2 2 ; O3 1 ; O2 1 O3 2 ; ; ; O4 1 2.10 - O4 2 ; O2 4 ; 7 ; O2 3 O1 3 ; O4 3 ; ? O1 2 ; M4 Fig. O3 3 ; ; 19,5 30 Deuxieme insertion pour l'agregation iterative CHAPITRE 2. UNE APPROCHE PAR AGRE GATION 60 O 5;3 O 5;1 M 1 O M O 2 M 3 O 1;1 O 3;1 2;1 M 3;2 O 1;3 O 4 2;3 O 4;2 ? O 4;1 2;4 18 Fig. 2.11 - 4;3 O 5;2 O O 3;3 O 1;2 O O 2;2 34 Derniere insertion pour l'agregation iterative 2.2. LES ALGORITHMES DE TYPE JL+1 L PL 61 Si l'on considere comme critere de diculte pour l'insertion le temps operatoire de chaque operation, nous pouvons envisager un decoupage semblable a la repartition relative precedemment decrite. Toutefois, si l'on garde strictement la repartition relative, cela n'apporte rien de plus que la methode de la section 2.2.4.2. Pour cela, l'intervalle considere sera augmente de part et d'autre d'un certain pourcentage pour augmenter le nombre de possibilites d'insertion. Dans cette methode, les operations sont traitees iterativement par ordre decroissant de leur diculte d'insertion comme le montrent les gures 2.13 2.14 et 2.15. 2.2.5 Agregation globale par fonction co^ut L'algorithme de la gure 2.16 montre le principe de cette troisieme approche d'agregation. Le but est ici d'agreger le job d'une maniere globale en tenant compte de la totalite de l'ordonnancement partiel et non plus d'un intervalle de temps. Le principe de la methode est de repertorier l'ensemble (ou un sousensemble) des emplacements disponibles pour chacune des operations du job a agreger. Le placement de l'operation dans un des emplacements possibles entra^nera un co^ut dependant a la fois de la place de l'operation dans la gamme operatoire du job, de la marge disponible dans l'emplacement selectionne, etc. La fonction co^ut total pour le job aura alors pour valeur la somme des co^uts entra^nes par le placement de chaque operation dans un emplacement. On realisera l'a ectation dans les emplacements permettant d'obtenir la valeur minimale pour la fonction co^ut total (cf algorithme de la gure 2.16). Nous presentons maintenant un exemple de fonction co^ut a minimiser. Pour cela, on de nit la fonction co^ut total Fjob pour ce job comme etant la somme des fonctions co^ut de chacune de ses operations (Fop). X Fjob = Fop (2.7) Pour le calcul de la valeur de Fop de chaque operation, on choisit de CHAPITRE 2. UNE APPROCHE PAR AGRE GATION 62 1. CALCUL DE LA MARGE RELATIVE Calcul de la marge relative pour les operations restant a traiter (calcul de MR sur l'intervalle entre la n au plus t^ot de l'operation precedente et le debut au plus tard de l'operation suivante). 2. CALCUL DE L'INTERVALLE POUR L'OPERATION COURANTE (a) Calcul de l'intervalle par decoupage relatif (b) Augmentation de l'intervalle en fonction de l'operation courante 3. INSERTION DE L'OPERATION COURANTE Pour l'operation courante, insertion dans le meilleur emplacement de l'intervalle considere. 4. MISE A JOUR Calcul des dates au plus t^ot et au plus tard tenant compte des operations deja inserees. 5. SELECTION DE L'OPERATION COURANTE (a) S'il reste des operations non traitees, selectionner l'operation suivante et retourner en 1. (b) Sinon, arr^eter. Fig. 2.12 - Algorithme de decoupage du temps et insertion relative 2.2. LES ALGORITHMES DE TYPE J O5 1 +1 L L P 63 L O5 2 ; O5 3 ; ; J5 M1 M2 M3 O1 1 O2 2 ; O3 1 ; O2 1 O3 2 ; ; O2 3 ; O1 3 ; O4 3 ; ? O1 2 ; M4 ; O4 2 ; O4 1 O2 4 ; 6 Fig. O3 3 ; 2.13 - ; 23 30 Premiere insertion pour l'agregation relative CHAPITRE 2. UNE APPROCHE PAR AGRE GATION 64 O O 5;1 M 1 O M 3 O 1;1 M O 2 5;3 O 3;1 2;1 M 3;2 O 1;3 O 4 2;3 O 4;2 ? O 4;1 2;4 18 Fig. 2.14 - 4;3 O 5;2 O O 3;3 O 1;2 O O 2;2 34 Deuxieme insertion pour l'agregation relative 2.2. LES ALGORITHMES DE TYPE J +1 L L P 65 L O5 1 ; M1 M2 M3 ? O1 1 ; O3 1 ; ; O4 1 ; 11 Fig. ; O1 3 ; ; O2 3 ; O3 2 O4 3 ; O5 2 ; O2 1 O3 3 ; O1 2 ; M4 O2 2 O4 2 O5 2 ; ; O2 4 ; 34 2.15 - Derniere insertion pour l'agregation relative 66 CHAPITRE 2. UNE APPROCHE PAR AGRE GATION prendre en compte : { La taille du temps mort sur la machine ou A est la valeur de la di erence entre le temps operatoire et le temps mort. Ceci permet d'avantager les temps morts les plus grands. { La position du temps mort dans l'ordonnancement : B = dt , Cnmax j (2.8) l+1 ou dt est le debut du temps mort et j le numero de l'operation. Ceci decoupe l'ordonnancement en intervalle et avantage les temps morts proches de l'intervalle correspondant a l'operation a inserer. La valeur de Fop sera une combinaison lineaire de ces deux parametres. Fop = A + B (2.9) Pour l'a ectation d'une operation sur un temps mort, il faudra faire attention a respecter les precedences. Ceci pourra se faire, soit en ne permettant pas l'a ectation d'une operation au temps mort ne correspondant pas, soit en rajoutant une grande valeur dans les fonctions co^uts correspondant aux temps morts impossibles. Un exemple d'insertion par fonction co^ut est donne dans la gure 2.17. 2.3 Les algorithmes de type Pl Pr L Comme dans la section sur l'agregation Jl+1 Pl , nous proposons ici un algorithme general de resolution du probleme. Dans ce type de resolution, la phase de selection est tres importante car elle determine le type d'agregation que l'on doit utiliser par la suite. L 2.3. LES ALGORITHMES DE TYPE PL L PR 67 1. EMPLACEMENTS DISPONIBLES Faire la liste des emplacements disponibles (en totalite ou partiellement). ^ 2. MINIMISATION DE LA FONCTION COUT Minimisation de la fonction co^ut donnant l'a ectation des operations et la position dans les sequences operatoires des machines. 3. INSERTION DES OPERATIONS Insertion des operations dans les emplacements obtenus a la suite de la minimisation de la fonction co^ut. 4. MISE A JOUR Calcul des dates au plus t^ot et au plus tard apres l'agregation. Fig. 2.16 - Algorithme d'agregation a l'aide d'une fonction co^ut CHAPITRE 2. UNE APPROCHE PAR AGRE GATION 68 O M 1 O ; M 3 O 3;1 O 2;1 M 4 O 5;2 ? O2 2 1;1 M O 2 O 5;1 O O 3;3 4;3 O 1;2 ? 2;3 O 3;2 O 4;1 O 1;3 5;3 O ? 4;2 O 2;4 30 Fig. 2.17 - Resultat de l'agregation par fonction co^ ut 2.3. LES ALGORITHMES DE TYPE PL L PR 69 2.3.1 L'algorithme general de resolution L'algorithme de la gure 2.18 utilise L a la fois le principe d'agregation L Jl+1 Pl et le principe d'agregation Pl Pr . Le but de la methode est de traiter les jobs par groupes pour constituer un certain nombre d'ordonnancements partiels. Ensuite, il faut agreger ces ordonnancements partiels pour construire l'ordonnancement nal. Il est possible d'ajouter apres les pas 3 et 6 une procedure d'amelioration locale (cf 2.4). De plus la structure de cet algorithme permet le calcul en parallele de chaque ordonnancement partiel pour chaque sous groupe de jobs. Dans l'algorithme propose, la deuxieme phase (pas 5 a 7) consiste a agreger sequentiellement les ordonnancements partiels generes dans la premiere phase (pas 1 a 4). Il est bien s^ur possible de regrouper a nouveau ces ordonnancements partiels en di erents sous-groupes pour recreer de nouveaux ordonnancements partiels de taille plus importante. La encore, ces calculs peuvent s'e ectuer en parallele. 2.3.2 Les procedures de groupement des jobs Trois manieres de grouper les jobs sont maintenant envisagees. La premiere repose sur le principe de decomposition. La deuxieme est fondee sur un groupement de jobs di erents, tandis que la troisieme regroupe des jobs dit decales. Bien entendu, ces facons de regrouper les jobs sont tres liees a la nature du probleme traite et a la procedure d'agregation des ordonnancements partiels choisie pour la suite de l'algorithme. 2.3.2.1 Une methode de decomposition La premiere selection que nous proposons est liee a des techniques de decomposition [74] [88]. Elle consiste a regrouper les jobs utilisant les m^emes machines, et de sorte qu'une machine ne travaille que pour executer les operations d'une famille de jobs. Cette selection peut ^etre 70 CHAPITRE 2. UNE APPROCHE PAR AGRE GATION 1. INITIALISATION Faire la liste des jobs a traiter. 2. SELECTION D'UNE FAMILLE DE JOBS Selectionner un sous-ensemble des jobs selon une regle de priorite (cf 2.3.2). 3. AGREGATION (suivant algorithme gure 2.4) Agreger les jobs selectionnes pour creer un ordonnancement partiel. ^ 4. CONDITION D'ARRET Si tous les jobs sont traites, continuer. Sinon, retourner en 2. 5. SELECTION D'UN ORDONNANCEMENT PARTIEL Selectionner un nouvel ordonnancement partiel selon une regle de priorite (longueur des ordonnancements partiels). 6. AGREGATION Utiliser une procedure d'agregation du type P L P pour agreger l'ordonnancement partiel selectionne a l'ordonnancement courant (cf 2.3.3). ^ 7. CONDITION D'ARRET l r (a) Si tous les ordonnancements partiels sont traites, arr^eter. (b) Sinon, retourner en 5. Fig. 2.18 - Algorithme general base sur P L P l r 2.3. LES ALGORITHMES DE TYPE P L L P R 71 faite par l'utilisation d'une methode de technologie de groupes [35] qui permet de minimiser le nombre de machines a ectees a des familles differentes. Le principe de la methode est, dans un premier temps, d'ecrire la matrice d'incidence jobs-machines. Dans cette matrice en 0{1, l'element a vaut 1 si J utilise M et 0 sinon. Ensuite, et par des permutations de lignes et de colonnes, il faut rendre la matrice au maximum bloc-diagonnale, et minimiser la somme des elements hors blocs. Ce probleme est NP-complet mais de nombreuses heuristiques ont deja ete developpees. i;j i j Si la decomposition est parfaite (aucunes machines communes entre les di erentes familles), la resolution independante des sous-problemes permet d'obtenir une solution generale du probleme. Dans ce cas, chaque famille peut ^etre traitee comme un probleme a part entiere et une L des techniques d'agregation J +1 P peut ^etre utilisee. l l Quand la decomposition n'est pas parfaite et que des machines servent a executer des operations de di erentes familles, la resolution des sous-problemes ne sut plus pour donner une solution generale. Une phase d'agregation des blocs est alors necessaire. Cette procedure peut ^etre basee soit sur une technique de decoupage du temps, soit sur l'utilisation d'une fonction co^ut (cf 2.3.3). L'un des avantages de cette methode de decomposition est le fait que l'on regroupe les jobs utilisant les m^emes machines. Ceci permet de traiter un sous-probleme de taille moins importante. De plus, une bonne optimisation de chacun des sous-problemes doit permettre d'obtenir une bonne solution globale, d'autant plus que la decomposition est parfaite. Deux dicultes majeures peuvent se produire. La premiere est que la decomposition n'est pas bonne (trop de liens entre les di erents groupes). Ceci se produit, par exemple, quand le probleme traite est tel que chaque job doit passer sur toutes les machines. Dans ce cas, la procedure d'agregation des ordonnancements partiels devra resoudre les con its que la decomposition n'aura pas traites. Le deuxieme probleme pouvant survenir est que la decomposition, pour ^etre acceptable, genere des groupes de jobs de taille importante. Deux solutions sont 72 CHAPITRE 2. UNE APPROCHE PAR AGRE GATION alors envisageables, soit traiter le groupe de jobs au complet par une des methodes d'agregation precedente, soit le rediviser en utilisant une technique comme celle presentee dans les sections suivantes. 2.3.2.2 Un regroupement de jobs dissemblables Cette methode, a l'inverse de la precedente, constitue des groupes de jobs n'utilisant pas ou peu les m^emes machines. L'avantage de cette methode est de pouvoir realiser des groupes importants de jobs faciles a traiter, car chaque groupe ne genere pas beaucoup de con its. Si nous reprenons la matrice d'incidence jobs-machines, le but est maintenant d'extraire un ensemble de sous-matrices. Pour chacune d'elles, il faut minimiser le nombre maximum de 1 par ligne, ce qui correspond a minimiser le nombre d'operations sur chaque machine pour une famille de jobs. La diculte est en fait repoussee au niveau de l'agregation des ordonnancements partiels. Dans ce cas, agreger les ordonnancements partiels les uns apres les autres permet de resoudre les con its au fur et a mesure sans trop augmenter la complexite du probleme. L'utilisation de la procedure d'optimisation locale permet egalement d'ameliorer les solutions intermediaires. 2.3.2.3 Un regroupement de jobs decales Cette methode de selection constitue des groupes de jobs dont la particularite est d'utiliser les m^emes machines mais pas au m^eme moment dans la gamme operatoire de leur job. En e et, la methode de decomposition regroupait des jobs utilisant le m^eme ensemble de machines sans distinction de la place dans la gamme operatoire. Ici, le principe est de regrouper des jobs dont les operations sur une machine donnee ne sont pas situes au m^eme rang dans la gamme operatoire. Cette approche permet d'arbitrer directement les disjonctions evidentes, dans ces sous-problemes. Ainsi, l'operation O 1 sera placee avant l'operation O sur la machine M . Ces arbitrages etant realises dans chaque famille de jobs, il ne seront pas remis en cause lors des agregations des ordonnancements partiels. a; b;nb k 2.3. LES ALGORITHMES DE TYPE PL L PR 73 L'avantage de cette methode reside dans le fait que la procedure de selection des jobs est moins dicile a mettre en uvre qu'une procedure de decomposition par technologie de groupe. Par contre, la phase d'agregation des blocs est plus technique et necessite une procedure ne d'optimisation et surtout l'emploi d'une methode d'amelioration locale, voire d'une methode tabou (cf 2.4). 2.3.3 Les procedures d'agregation Les methodes que nous proposons maintenant sont basees sur l'agreL gation de type Ph Pl et directement issues des methodes decrites dans les sections 2.2.4.1, 2.2.4.2 et 2.2.5. Elles utilisent soit un decoupage du temps, soit une fonction co^ut. Dans ce type de methodes, le choix des familles de jobs est tres important et determine egalement le choix de la procedure d'agregation qu'il faut mettre en uvre pour une bonne optimisation. Pour ce qui est du decoupage du temps, nous proposons la m^eme approche que pour l'agregation Jl+1 L Pl . La marge relative MR est calculee comme la valeur absolue de la di erence entre les Cmax des deux ordonnancements partiels Pl et Pr (Cmax(Pl) et Cmax(Pr )). MR = jCmax(Pl ) , Cmax(Pr )j (2.10) On prendra donc comme principe d'agreger le plus petit ordonnancement partiel au plus long. Les intervalles sont alors determines de la m^eme facon que precedemment et les insertions d'operations egalement. La premiere etape consiste a repartir la marge relative sur le chemin critique. Cela xe des intervalles pour le debut et la n de chaque operation. Dans une deuxieme etape, on tient compte des precedences dans Pr pour determiner les intervalles des operations hors chemin critique. L'agregation realisee, il est important de mettre en uvre une procedure d'amelioration locale pour optimiser la solution courante. La methode d'agregation bloc par bloc peut egalement ^etre traitee par l'utilisation d'une fonction co^ut. Pour celle-ci, nous reprenons exac- 74 CHAPITRE 2. UNE APPROCHE PAR AGRE GATION tement la m^eme fonction que nous avons proposee dans la section 2.2.5. Dans ce cas, le co^ut total de l'agregation de l'ordonnancement partiel sera la somme des co^uts de chacune des operations de cet ordonnancement partiel. Le choix de la procedure d'agregation est fortement lie a la procedure de groupement des jobs. Une procedure de decomposition regroupera les con its a l'interieur de chaque famille et les con its interfamilles seront peu nombreux. Dans ce cas, l'utilisation d'une procedure de type decoupage du temps et agregation global, ou avec une fonction co^ut simple sera susante. Par contre, pour un groupement de jobs dissemblables, peu de con its seront arbitres dans chaque sous-probleme et la procedure d'agregation devra ^etre plus sophistiquee. 2.4 L'amelioration locale Apres les phases d'agregation, la solution obtenue peut ^etre amelioree rapidement par une procedure d'amelioration locale. Dans ce but, nous proposons une methode d'optimisation locale basee sur des permutations d'operations. En fonction du nombre de con its arbitres par la procedure d'agregation, il est possible d'utiliser une procedure directe (uniquement des permutations qui ameliorent le Cmax), soit une procedure de type tabou. Il est egalement possible d'utiliser un principe de reagregation. Celui-ci consiste a retirer de l'ordonnancement un ou plusieurs jobs critiques, et de les reintroduire a nouveau en les agregeant. 2.4.1 Amelioration par permutations Cette procedure de reoptimisation est classique dans le domaine de l'ordonnancement. Elle consiste a choisir deux operations successives sur une machine et tenter de les permuter pour diminuer la duree totale de l'ordonnancement. Bien entendu, ces operations doivent ^etre sur le chemin critique sans quoi la permutation n'ameliorerait pas la solution. Cette methode est tres utilisee dans les heuristiques de type tabou ou 2.4. L'AME LIORATION LOCALE 75 1. CHOIX DE DEUX OPERATIONS Choix de deux operations successives du graphe critique utilisant la m^eme machine. 2. PERMUTATION DES OPERATIONS (a) Permutation des deux operations selectionnees. (b) Calcul de la duree totale de l'ordonnancement, Cmax, apres permutation. (c) Si le nouveau Cmax est inferieur a l'ancien, valider la permutation, sinon l'annuler. ^ 3. CONDITION D'ARRET (a) Si aucune permutation de deux operations successives du graphe critique n'ameliore le Cmax, arr^eter. (b) Sinon, retourner en 1. Fig. 2.19 - Algorithme d'amelioration locale par permutations recuit simule [33] [79] [105]. Nous presentons, dans l'algorithme de la gure 2.19, la phase de permutation des operations. Cette methode permet de faire converger la solution de l'ordonnancement vers un minimum local. Quelques amenagements de cet algorithme nous permettent de mettre en uvre une methode tabou. Celle-ci demande un temps de calcul plus important, qui ne se justi e pas quand on cherche des solutions intermediaires, surtout au debut de la phase de construction, ou la qualite de la solution n'est pas primordiale. Par contre, lors des dernieres agregations, il peut ^etre interessant d'utiliser une methode tabou. 76 CHAPITRE 2. UNE APPROCHE PAR AGRE GATION 2.4.2 La reagregation L'algorithme de reoptimisation suivant ( gure 2.20) par du principe que dans l'ordonnancement cree, certains jobs sont critiques et determinent ainsi la duree totale Cmax. Le but de la procedure est donc de supprimer de l'ordonnancement calcule, le ou les jobs dont les operations sont sur le graphe critique. La deuxieme phase consiste a les reintroduire dans l'ordonnancement en utilisant une technique d'agregation. Le choix du job critique peut ^etre realise de plusieurs facons. Tout d'abord en considerant que le job qui determine la duree totale est celui dont la derniere operation nit au plus t^ot a la date Cmax. Le deuxieme critere de selection que l'on peut envisager concerne le nombre d'operations sur le graphe critique. Dans ce cas, on retirera de l'ordonnancement le job qui possede le plus d'operations critiques. Une troisieme possibilite pour choisir le job a ^oter est de calculer la somme des temps operatoires des operations critiques pour chaque job, et de selectionner le job dont le temps maximum est critique. Il est possible, apres l'enlevement du job critique, de reoptimiser l'ordonnancement en utilisant la procedure de permutation decrite precedemment. Ceci permet de plus de modi er quelque peu la forme de l'ordonnancement et eviter que la procedure d'agregation ne redonne la m^eme solution. 2.5 Resultats numeriques Les di erents algorithmes presentes dans ce chapitre sont maintenant testes sur des jeux de donnees issus de la litterature, ainsi que sur des instances generees pour l'experimentation. Ceux-ci sont compares avec des algorithmes constructifs bases sur des regles de priorite. Apres une rapide presentation des jeux de donnees crees, les resultats numeriques seront commentes. 2.5. RE SULTATS NUME RIQUES 77 1. CHOIX D'UN JOB CRITIQUE Choix d'un job dont une ou plusieurs operations sont sur le graphe critique. 2. REAGR EGATION DU JOB (a) (b) (c) (d) Enlevement du job selectionne. Calcul du nouvel ordonnancement, apres enlevement du job. Reagregation du job. Si le nouveau Cmax est inferieur a l'ancien, valider la reagregation, sinon l'annuler. ^ 3. CONDITION D'ARRET (a) Si aucune reagregation n'ameliore le Cmax, arr^eter. (b) Sinon, retourner en 1. Fig. 2.20 - Algorithme d'amelioration par reagregations 78 CHAPITRE 2. UNE APPROCHE PAR AGRE GATION 2.5.1 Presentation des jeux de donnees Les methodes developpees ont pour but de trouver, dans un temps le plus court possible, une solution admissible au probleme. L'objectif de celles-ci est de traiter des instances de taille importante, jusqu'a 100 jobs. Pour cela, ont ete generees les instances repertoriees dans la gure 2.21. Les jeux de donnees sont repartis en 3 ateliers possedant respectivement 7 machines, 10 machines et 15 machines. Pour chacun de ces ateliers, deux types de jobs sont envisages, les jobs ayant un faible nombre d'operations dans leur gamme operatoire (4 pour l'atelier 1 par exemple) et les jobs passant sur toutes les machines exactement une fois. Pour les jobs ne passant pas par toutes les machines, le choix de la machine pour une operation donnee est tire selon une loi uniforme sur l'ensemble des machines. Pour les jobs passant sur toutes les machines, la machine utilisee par la premiere operation est tiree selon la loi uniforme sur l'ensemble. Pour l'operation j , la machine est tiree selon la loi uniforme sur l'ensemble des machines non encore utilisees par le job. Tous les temps operatoires sont tires selon la loi uniforme entre 5 et 55. Pour chacun des types proposes, 25 instances sont generees et les resultats presentes sont des moyennes sur ces 25 instances. Des instances issues de la litterature ont egalement ete traitees. Parmi elles, 5 viennent de J. Adams et al. [2], et 3 viennent de M.L. Fischer et G.L. Thompson [82]. 2.5.2 Resultats et conclusions Les regles de priorite choisies pour l'experimentation sont classiques dans le domaine de l'ordonnancement [84] [108] [112]. Dans la le d'attente de chaque machine, sont placees les operations disponibles a la date de liberation de la machine, mais aussi les operations pouvant arriver des la n d'execution de leur predecesseur de gamme. Ceci permet d'anticiper l'arrivee des operations et de pouvoir choisir l'operation a executer avec des connaissances supplementaires. Les regles utilisees sont les suivantes : { RP1 : Pour les operations pouvant commencer au plus t^ot, choisir l'operation ayant le plus petit temps operatoire (Shortest Processing Time, SPT). 2.5. RE SULTATS NUME RIQUES ! Types d'instances ! Atelier 1 (7 machines) ! 4 operations par jobs ! 25, 50 ou 100 jobs ! 7 operations par jobs ! 25, 50 ou 100 jobs ! Atelier 2 (10 machines) ! 7 operations par jobs ! 25, 50 ou 100 jobs ! 10 operations par jobs ! 25, 50 ou 100 jobs ! Atelier 3 (15 machines) ! 11 operations par jobs ! 25, 50 ou 100 jobs ! 15 operations par jobs ! 25, 50 ou 100 jobs Fig. 2.21 - Les types d'instances g enerees 79 80 CHAPITRE 2. UNE APPROCHE PAR AGRE GATION { RP2 : Pour l'ensemble des operations de la le d'attente, choisir l'operation ayant le plus petit temps operatoire (SPT modi e). { RP3 : Pour les operations pouvant commencer au plus t^ot, choisir l'operation appartenant au job ayant le plus grand nombre d'operations a venir (Most Operations Remaining, MOPNR). { RP4 : Pour l'ensemble des operations de la le d'attente, choisir l'operation appartenant au job ayant le plus grand nombre d'operations a venir (MOPNR modi e). { RP5 : Pour les operations pouvant commencer au plus t^ot, choisir l'operation appartenant au job ayant le plus grand temps operatoire a venir (Most Work Remaining, MWKR). { RP6 : Pour l'ensemble des operations de la le d'attente, choisir l'operation appartenant au job ayant le plus grand temps operatoire a venir (MWKR modi e). Pour l'etude des resultats, nous ne conserverons pas l'ensemble des regles de priorite. Pour chaque serie de problemes (25 instances dont on calcule la moyenne), nous garderons la meilleure regle, la plus mauvaise et la moyenne de toutes les regles. Le but n'etant pas de comparer ces regles, nous ne preciserons pas laquelle est la meilleure et laquelle est la plus mauvaise. La borne inferieure presentee dans les tableaux de resultats est le maximum sur toutes les machines de la somme des temps operatoires des operations devant ^etre executees sur la machine. Nous presentons maintenant 6 methodes permettant de tester a la fois les procedures d'agregation et les procedures d'amelioration locale. En ce qui concerne les procedures d'agregation nous testons les agregations globales, iteratives et par fonction co^ut. Pour ce qui est des procedures d'amelioration, nous testons la permutation, et la reagreL gation. Les algorithmes bases sur le principe P P sont en cours de developpement et ne gurent pas dans les resultats. L'algorithme l r 2.5. RE SULTATS NUME RIQUES 81 d'agregation base sur la procedure de P. Brucker a ete teste separement et sans utilisation de methodes d'amelioration locale. Les resultats de cette procedure sont presentes dans [86]. L'integration des methodes d'amelioration locale sont en cours. La methodes utilisees sont : { OPT1 : 1. Amelioration par permutations 2. Agregation globale { OPT2 : 1. Amelioration par permutations 2. Agregation iterative { OPT3 : 1. Amelioration par permutations 2. Agregation par fonction co^ut { OPT4 : 1. Amelioration par permutations et reagregations 2. Agregation globale { OPT5 : 1. Amelioration par permutations et reagregations 2. Agregation iterative { OPT6 : 1. Amelioration par permutations et reagregations 2. Agregation par fonction co^ut 82 CHAPITRE 2. UNE APPROCHE PAR AGRE GATION Pour ne pas multiplier les tests numeriques, nous avons fait une etude prealable sur la repartition de la marge relative dans les procedures d'agregation ainsi que sur le choix de l'emplacement pour inserer l'operation. A l'issue de ces tests nous avons choisi de ne presenter que l'agregation globale avec une repartition lineaire de la marge relative, et l'agregation iterative avec une repartition geometrique de la marge relative. Apres avoir teste plusieurs criteres de choix de l'emplacement d'insertion, ou ta representera la taille de l'emplacement considere et p le temps operatoire de l'operation a inserer, nous avons retenu le critere : i;j Cr = ta , 2 p i;j (2.11) En ce qui concerne la fonction co^ut, nous avons retenu egalement le critere precedent, et la fonction consiste donc a minimiser la somme pour toutes les operations du job, de ce critere. Les resultats obtenus sont donnes dans les tableaux des gures 2.22, 2.23 et 2.24 . Dans ces tableaux, la premiere colonne indique le nombre de jobs a ordonnancer et la deuxieme, le nombre d'operations dans la gamme operatoire de chaque job. Suivent ensuite les resultats des 6 methodes d'optimisation que nous proposons. Pour nir, les quatre dernieres colonnes donnent les resultats des algorithmes bases sur les regles de priorite et le pourcentage d'amelioration entre la meilleure methode OPT et la meilleure regle de priorite. Pour chacun des trois ateliers, les resultats obtenus montrent que les methodes OPT sont tres legerement meilleures que les regles de priorite. En moyenne, l'e ort d'optimisation superieur des methodes agregatives permet une amelioration des durees totales de l'ordonnancement de 1 a 3% selon les ateliers. Toutefois, les methodes agregatives ne garantissent pas une amelioration sensible par rapport aux regles de priorite. En regle generale, les methodes utilisant la reagregation (OPT4, OPT5, OPT6) sont plus performantes que celles utilisant uniquement les permutations (OPT1, OPT2, OPT3). Dans chacun de ces deux groupes, l'agregation par fonction co^ut donne de meilleurs resultats 2.5. RE SULTATS NUME RIQUES n n BI 25 25 50 50 100 4 7 4 7 4 514 886 825 1482 1637 OPT1 520 876 926 1675 1939 OPT2 498 869 914 1648 1924 OPT3 481 884 935 1662 1926 OPT4 485 861 921 1642 1918 OPT5 472 867 902 1637 1905 OPT6 468 847 908 1623 1921 OPT , BI 15,0 14,0 9,3 9,5 16,4 BI Min 479 871 912 1669 1937 Max 587 915 1021 1743 2084 Moy 522 898 986 1706 2015 Min , OPT 2,3 2,8 0,4 2,8 1,7 OPT Fig. 2.22 - Job-shop, atelier 1 i 83 100 7 2896 3197 3172 3212 3196 3204 3149 8,7 3194 3324 3275 1,4 que l'agregation iterative et cette derniere donne de meilleurs resultats que l'agregation globale. Les methodes agregatives sont bien s^ur moins rapides que les regles de priorite, mais les temps de calcul ne sont pas tres important. Sur une station de travail SPARC 10, l'instance de taille la plus importante ne necessite que 5 minutes. Sur les exemples issus de la litterature, nous pouvons faire les m^emes remarques que pour les trois ateliers precedents. Les resultats sont presentes dans la gure 2.25. On constate que les valeurs de la duree totale de l'ordonnancement sont assez eloignees de la valeur optimale. Ceci s'explique par le fait que les methodes developpees ont pour but une optimisation rapide. Le temps de calcul pour chacun des problemes de la gure 2.25 est de l'ordre de la seconde. Dans la ligne BI , les valeurs optimales sont mentionnees par une etoile. 84 CHAPITRE 2. UNE APPROCHE PAR AGRE GATION n n BI 25 25 50 50 100 7 10 7 10 7 538 758 1089 1457 2029 OPT1 658 903 1283 1767 2431 OPT2 645 880 1289 1752 2456 OPT3 618 889 1257 1692 2426 OPT4 623 845 1275 1712 2405 OPT5 621 873 1268 1705 2342 OPT6 604 852 1235 1680 2383 OPT , BI 12,3 11,5 13,4 15,3 15,4 BI Min 624 892 1254 1723 2401 Max 752 993 1321 1867 2657 Moy 702 943 1291 1813 2512 Min , OPT 3,1 5,6 1,5 2,6 2,5 OPT Fig. 2.23 - Job-shop, atelier 2 i 2.6 100 10 2891 3297 3305 3269 3237 3259 3182 10,1 3208 3473 3367 0,8 Conclusion L'approche proposee dans ce chapitre est une alternative aux regles de priorite. Son souci principal est de developper de nouvelles methodes d'optimisation rapides pour traiter des problemes de tailles importantes. A partir de celles-ci, des propositions de methodes d'optimisation ont ete faites. Bien entendu, les possibilites o ertes par cette approche n'ont pas toutes ete investiguees. Les resultats obtenus lors de l'experimentation des quelques methodes presentees plus haut, font appara^tre un reel inter^et a l'utilisation de cette approche. M^eme si pour certaines d'entre elles les resultats sont moins bons que ceux donnes par les regles de priorite, les plus performantes sont interessantes. L'un des atouts remarquables de cette approche est sa exibilite. En e et, le choix des procedures d'agregations et des procedures d'amelio- 2.6. 85 CONCLUSION n n BI 25 25 50 50 100 11 15 11 15 11 561 723 1022 1674 2082 OPT1 706 902 1243 1687 2329 OPT2 672 918 1247 1621 2341 OPT3 681 871 1224 1648 2305 OPT4 669 839 1198 1625 2278 OPT5 643 854 1231 1582 2314 OPT6 658 827 1185 1577 2281 OPT , BI 14,6 14,4 16,0 9,9 9,4 BI Min 666 836 1203 1625 2312 Max 754 987 1326 1721 2423 Moy 703 898 1241 1654 2397 Min , OPT 3,6 1,1 1,5 3,0 1,5 OPT Fig. 2.24 - Job-shop, atelier 3 i 100 15 2867 3254 3247 3197 3145 3205 3120 8,8 3152 3368 3274 1,0 ration locale permet de contr^oler l'e ort d'optimisation. En fonction de la taille de l'instance traitee, il est donc possible de selectionner telles ou telles procedures d'agregation et d'amelioration de facon a limiter le temps de calcul. L'agregation des jobs par fonction co^ut est certainement la methode la plus performante des trois testees. Il parait clair que ce type d'agregation merite d'^etre developpe. Il a l'avantage a chaque agregation d'un job de tenir compte de l'ensemble des emplacements disponibles pour l'insertion des operations. Le choix d'une bonne fonction, necessitant peu de calcul, est sans doute la voie la plus interessante a explorer pour traiter rapidement le probleme de job-shop statique et deterministe. CHAPITRE 2. UNE APPROCHE PAR AGRE GATION 86 n ni BI OPT1 OPT2 OPT3 OPT4 OPT5 OPT6 OPT B I , BI M in M ax M oy M in , OPT OPT 10 10 1234* 1504 1512 1467 1425 1367 1324 10 10 943* 1253 1220 1135 1142 1073 1121 20 15 654 854 865 882 823 831 812 20 15 635 921 903 854 798 825 812 20 15 656 987 1003 957 963 925 908 6 6 55* 68 72 64 63 67 59 10 10 930* 1322 1302 1254 1167 1135 1091 20 5 1165* 1642 1701 1682 1584 1497 1435 7,3 13,8 24,1 25,7 38,4 7,2 17,3 23,2 1348 1606 1464 1089 1249 1135 807 890 831 839 957 887 885 948 909 65 89 71 1160 1396 1279 1429 1739 1599 1,8 1,5 ,0 6 4,4 ,2 5 10,2 6,3 ,0 4 Fig. 2.25 - ; ; Job-shop, problemes classiques ; 87 Chapitre 3 Le job-shop generalise Nous presentons dans ce chapitre une extension du probleme traite jusqu'a present, appele job-shop generalise. La di erence entre les deux problemes reside dans l'a ectation des operations sur les machines. Si dans le job-shop statique et deterministe, une operation est a ectee des le depart a une machine specialisee, dans le job-shop generalise une operation peut ^etre executee par plusieurs des machines mais a ectee a une seule. Ainsi, pour chaque operation, il existe un ensemble de machines utilisables. Ce type d'atelier de production est plus complexe que le precedent, mais sera vu uniquement sur un plan statique. Les donnees sont connues au depart de l'optimisation et seule la construction de l'ordonnancement sera abordee. Les methodes de resolution proposees dans ce chapitre sont basees sur le principe d'agregation et poursuivent les m^emes objectifs que celles proposees dans le chapitre precedent. Ainsi, elles sont concues pour contr^oler l'e ort d'optimisation en privilegiant plus ou moins le temps de calcul par rapport a la qualite de la solution. Ce probleme comprenant a la fois le probleme d'a ectation des operations aux machines et le probleme de l'ordonnancement de celles-ci, des methodes separant ou liant ces deux optimisations seront proposees. Dans une premiere section, nous de nirons le probleme du job-shop generalise, a partir de la de nition du job-shop vue dans le chapitre 1. Puis, nous ferons un tour d'horizon des methodes connues pour le reso- CHAPITRE 3. LE JOB-SHOP GE NE RALISE 88 lution de ce probleme. Les modelisations du probleme feront l'objet de la deuxieme partie. Nous presenterons la modelisation de H.M. Wagner et proposerons une nouvelle formulation du job-shop generalise sous forme de programmation lineaire en nombres entiers. La troisieme section sera consacree a di erentes propositions de methodes de resolution basees sur le principe d'agregation. Nous detaillerons trois types de methodes approchees : les heuristiques constructives une-phase, les heuristiques constructives deux-phases et les heuristiques amelioratrices. Nous nirons ce chapitre par des resultats numeriques. Les jeux de donnees utilises seront expliques et des conclusions sur les tests seront donnees. 3.1 Une presentation du probleme 3.1.1 Description du probleme Le probleme du job-shop generalise contient, du fait de sa structure, deux problemes classiques de l'optimisation combinatoire : le probleme de l'a ectation lineaire et le probleme de l'ordonnancement. Les donnees et les contraintes de ce probleme sont les suivantes : 1. Un ensemble M de m machines. Une machine est notee M avec k = 1; :::; m. k 2. Un ensemble J de n jobs. Chaque job est compose d'une gamme operatoire i.e. une sequence lineaire de n operations xee. Cette sequence ne depend que du job et peut varier d'un job a l'autre. Un job est note J avec i = 1; :::; n. i i 3. Une operation O represente la jeme operation du job J . Cette operation necessite un temps operatoire p qui ne sera xe que lors de l'a ectation de l'operation sur une machine. La date de debut calculee de l'operation O sera toujours notee t . i;j i i;j i;j i;j 4. L'operation O necessite, n pour ^etre realis oee, une des machines de l'ensemble R(O ) = M 1 ; M 2 ; :::; M . Le temps operatoire sur la machine M pour l'operation O sera note p . i;j i;j k k kq k i;j i;j;k 3.1. UNE PRE SENTATION DU PROBLE ME 89 n 1 2 : : : ni 1 pi;1;1 pi;2;1 : : : pi;n ;1 2 pi;1;2 pi;2;2 : : : pi;n ;2 ... ... ... . . . ... m pi;1;m pi;2;m : : : pi;n ;m Fig. 3.1 - Matrice des temps op eratoires pour le job Ji k j i i i La di erence entre le job-shop classique et le job-shop generalise reside dans le fait qu'une operation peut ^etre executee sur plusieurs machines avec des temps operatoires di erents. Pour un job Ji, on obtient donc la matrice des temps operatoires dont les colonnes sont les operations composant le job et les lignes les machines disponibles pour ces operations ( gure 3.1). Le fait, pour une certaine operation Oi;j , que pi;j;k = +1 signi e que la machine Mk ne peut pas executer l'operation Oi;j . Les donnees sont soumises aux contraintes suivantes : 1. Les machines sont independantes les unes des autres. 2. Une machine ne peut executer qu'une seule operation a un instant donne. 3. Chaque machine est disponible pendant toute la periode de l'ordonnancement. En particulier, les pannes de machines ne sont pas prises en compte. 4. Une operation en cours d'execution ne peut ^etre interrompue (il n'y a pas de preemption). 5. Les jobs sont independants les uns des autres. En particulier, il n'existe aucun ordre de priorite attache aux jobs. Le probleme ne consiste plus uniquement a trouver une sequence des operations sur chaque machine mais egalement a determiner une a ectation de chaque operation sur une machine. Le but de l'ordonnancement est de trouver le temps de production minimum pour l'ensemble des jobs (Cmax). 90 CHAPITRE 3. LE JOB-SHOP GE NE RALISE 3.1.2 Les methodes de resolution connues Ce probleme a tres peu ete traite et les articles qui lui font reference sont rares. En fait, les methodes les plus utilisees pour le resoudre sont les regles de priorite. L'algorithme est le m^eme que celui presente dans le premier chapitre. La regle de priorite resout en m^eme temps le probleme d'a ectation et le probleme d'ordonnancement. C'est ce que nous appellerons par la suite une methode une-phase. Une autre approche consiste a separer la phase d'a ectation et la phase de resolution de l'ordonnancement. C'est ce nous appellerons une methode deux-phases. A. Fadil et al. [40] proposent une methode en trois etapes, a ectation, decomposition et resolution. Celle-ci e ectue, dans un premier temps, l'a ectation des operations aux machines. Ensuite, elle met en uvre une methode de decomposition par technologie de groupes [35] pour minimiser le nombre d'operations liees a plusieurs groupes de machines. Si ce nombre est trop important, l'affectation est remise en cause pour ameliorer la decomposition. Quand la decomposition est susante, chaque sous-probleme est resolu par un algorithme exact (J. Carlier et E. Pinson [28]). Si des liens persistent entre les groupes de machines malgre la rea ectation, une methode de synchronisation est mise en uvre. Pour le probleme du job-shop generalise, un cas particulier est polyn^omial. Il s'agit du probleme de job-shop a deux jobs avec plusieurs choix de machines pour chaque operation. P. Brucker et R. Schlie [24] ont propose un algorithme base sur la resolution graphique du job-shop a deux jobs. Ceci constitue une generalisation de la methode de resolution du probleme a deux jobs presentee dans la section 2.1.2. 3.2 Les modelisations du probleme Cette section est consacree a la modelisation du probleme de jobshop generalise. Actuellement, seule la modelisation en programmation mathematique existe. Si pour le job-shop statique et deterministe, le modele sous forme de graphe disjonctif est le plus repandu, il n'existe 3.2. LES MODE LISATIONS DU PROBLE ME 91 pas de modele faisant intervenir les graphes pour le job-shop generalise. Dans un premier temps, une modelisation en programmation lineaire en nombres entiers proposee par H.M. Wagner [110] sera exposee. Ensuite, nous proposons une nouvelle formulation faisant appara^tre a la fois des variables d'a ectation et des variables de precedences. 3.2.1 La modelisation de H.M. Wagner La premiere modelisation sous forme de programme lineaire en nombres entiers est due a H.M. Wagner. Le cas particulier du job-shop statique et deterministe a ete traite dans la section 1.2.2.3 et represente une restriction du modele general que nous presentons maintenant. Les variables utilisees sont les m^emes que pour le cas particulier traite plus haut. ( si Oi;j est la leme operation sur Mk ( l ) xi;j;k = 01 sinon (3.1) t(kl) : est la date de debut de la leme operation sur Mk s(kl) : est la duree entre la n de la leme operation et le debut de la (l + 1)eme sur Mk s0k : est la duree entre 0 et la premiere operation sur Mk mk : est le nombre maximum d'operations pouvant ^etre executees sur Mk Tx(kl) : est le temps operatoire de la leme operation sur Mk (3.2) (3.3) (3.4) (3.5) (3.6) Dans ce modele, une operation Oi;j peut ^etre executee par plusieurs machines Mk1 ; Mk2 ; :::; Mkq . La premiere contrainte signi e que l'operation Oi;j n'est a ectee qu'a une seule machine parmi Mk1 ; Mk2 ; :::; Mkq et a une seule place. l=X mk1 l=1 l) x(i;j;k 1 + l=X mk2 l=1 l) x(i;j;k 2 + ::: + l=X mkq l=1 l) x(i;j;k =1 q (3.7) CHAPITRE 3. LE JOB-SHOP GE NE RALISE 92 (i = 1; :::; n; j = 1; :::; n ) i La deuxieme contrainte signi e que sur la machine M , en position l, pas plus d'une operation n'est a ectee. k X (3.8) l j 2 ( Oi;j Mk x( ) 1 R Oi;j ) i;j;k (k = 1; :::; m; l = 1; :::; m ) k La contrainte 3.9 determine le temps operatoire de la leme operation executees sur M . k X Tx( ) = l k j 2 ( Oi;j Mk R Oi;j x( ) p ) (3.9) l i;j;k i;j;k pour k = 1; :::; m; l = 1; :::; m k Les contraintes de gamme operatoire s'expriment pour deux operations O et O +1 sur les machines M1 et M2 respectivement, de la facon suivante : i;j i;j t( 11) + p l k i;j;k1 x( l1 ) i;j;k1 t( ) + BS (2 , x( l2 l1 k2 ) i;j;k1 , x( ) +1 l2 i;j ;k2 ) (3.10) (l1 = 1; :::; m 1 ; l2 = 1; :::; m 2 ) k k Cette contrainte n'est active que si l'operation O est executee sur la machine M 1 en l1eme position et O +1 en l2eme position sur M 2 . Si une de ces deux conditions n'est pas respectee, la contrainte n'est pas active. i;j k i;j k En n, le calcul des dates de debut au plus t^ot des operations sur les machines se fait par les contraintes suivantes : t(1) = s0 pour k = 1; :::; m k t( ) = s0 + l k (3.11) k r =X ,1 l k r =1 Tx( ) + s( ) r k r k (3.12) 3.2. LES MODE LISATIONS DU PROBLE ME 93 pour k = 1; :::; m; l = 2; :::; mk Les dernieres contraintes permettent de calculer le Cmax : tmk + Txmk Cmax pour k = 1; :::; m k (3.13) k 3.2.2 Une nouvelle modelisation Nous proposons maintenant une formulation du probleme en programmation lineaire en nombres entiers, mettant en evidence l'a ectation des operations aux machines et le sequencement. Tout d'abord, la variable xi;j;k represente l'a ectation de la jeme operation du job Ji sur la machine Mk . ( Oi;j est a ectee Mk xi;j;k = 10 sisinon ) (3.14) a;b represente l'ordre dans lequel sont e ectuees les La variable yc;d operations Oa;b et Oc;d . a;b = yc;d ( 1 si Oa;b est e ectuee avant Oc;d 0 sinon ) (3.15) Les equations 3.16 forment les contraintes d'a ectation. Elles impliquent qu'une operation est a ectee a une seule machine. X M 2R(O ) k xi;j;k = 1 pour i = 1; :::; n et j = 1; :::; ni (3.16) i;j Les equations 3.17 et 3.18 representent les contraintes de gammes operatoires et de n d'ordonnancement. ti;j+1 ti;j + X M 2R(O ) k i;j xi;j;k pi;j;k (3.17) CHAPITRE 3. LE JOB-SHOP GE NE RALISE 94 pour = 1 i max C i,1 et = 1 ; :::; n X j i;n t i + ; :::; n i;ni ) k i;n ;k pi;n ;k x M 2R(O i i pour = 1 i ; :::; n (3.18) En n, les dernieres equations permettent d'arbitrer les disjonctions entre des operations utilisant les m^emes machines. Si pour les operations a;b et c;d l'intersection de ( a;b ) et ( c;d ) n'est pas vide, les contraintes s'ecrivent pour une machine k commune : O O R O R O M y a;b c;d c;d + ya;b c;d t =1 (3.19) a;b c;d a;b + yc;d pa;b;k , B S ya;b t , BS , BS X R O et M X M2 r ( M 2R(O r a;b t a;b ) c;d ) 6 M r= et M 6 a;b;r x k c;d;r x M r= (3.20) k c;d a;b c;d + ya;b pc;d;k , B S yc;d t , BS , BS X R O et M X M2 r ( M 2R(O r a;b ) c;d ) x 6 M r= et M 6 r= (3.21) a;b;r k M x c;d;r k Ces deux dernieres contraintes ne peuvent pas ^etre actives en m^eme temps, et dans la plupart des cas, aucune des deux ne l'est. Pour une machine k donnee et appartenant a ( a;b ) et ( c;d ), les contraintes ne sont pas actives si l'une ou les deux operations ne sont pas a ectees a k . Dans le cas ou les deux operations sont a ectees a k , soit a;b c;d c;d vaut 1 et la contrainte 3.21 est active, soit a;b vaut 1 et alors, la contrainte 3.22 est active. M R O R O M y M y 3.3. DES METHODES DE RESOLUTION 95 3.3 Des methodes de resolution Les methodes de resolution proposees dans cette section utilisent le principe d'agregation. Trois approches di erentes seront developpees. La premiere comprend les methodes constructives une-phase, qui b^atissent l'ordonnancement en m^eme temps qu'elles donnent une a ectation pour les operations. La deuxieme approche permet de developper des methodes constructives deux-phases. Ces methodes separent l'affectation des operations aux machines et l'ordonnancement proprement dit [4] [5]. En n, nous proposons des heuristiques amelioratrices pour ameliorer les solutions donnees par les methodes constructives precedentes. Ces methodes sont basees sur la rea ectation des operations aux machines, sur la permutation des operations du chemin critique et en n sur la reagregation des jobs. 3.3.1 Heuristiques constructives une-phase Le principe des methodes constructives une-phase est de construire, a partir des donnees initiales, un ordonnancement realisable. De plus, la construction se passe en une seule etape ou sont m^eles l'a ectation des operations aux machines et l'ordonnancement. Ce principe est utilise dans les methodes de resolution basees sur des regles de priorite. Dans ces algorithmes, toutes les operations pouvant ^etre executees sur une machine sont placees dans la le d'attente de celle-ci. Une operation peut donc gurer dans plusieurs les d'attente et, au moment ou elle est choisie pour ^etre executee sur une machine, elle doit ^etre ^otee des autres les. Ainsi, le choix de l'operation dans la le resout en m^eme temps le probleme d'a ectation et le probleme de l'ordonnancement. Nous proposons maintenant une generalisation des methodes d'agregation presentees dans la section 2.3. Les algorithmes permettant de traiter le probleme du job-shop generalise sont les m^emes que ceux des gures 2.6, 2.8 et 2.16. La di erence reside dans le fait que la liste des emplacements disponibles ne sont plus sur une seule machine mais sur l'ensemble des machines pouvant executer l'operation a inserer. Cela 96 CHAPITRE 3. LE JOB-SHOP GE NE RALISE donne une marge de manuvre plus grande pour l'insertion de l'operation mais multiplie le nombre de possibilites a explorer. Pour ce qui est des heuristiques par decoupage du temps, le calcul de la marge relative ne peut pas ^etre fait comme pour le probleme du jobshop statique et deterministe, dans la mesure ou le temps operatoire de chaque operation n'est pas xe (l'a ectation n'est pas faite). Ce calcul est donc realise en tenant compte, soit de la moyenne des temps operatoires sur les di erentes machines candidates, soit en utilisant le minimum ou le maximum de ceux-ci. La taille des intervalles etant plut^ot indicative, ce choix n'est pas d'une grande importance. Dans le cas de l'heuristique par decoupage du temps et agregation globale (section 2.2.4.1), la diculte principale est de ne pas trop charger une machine rapide, machine sur laquelle les temps operatoires sont petits. En e et, il serait tentant de placer l'operation sur la machine l'executant le plus rapidement, mais de ce fait, plusieurs operations du m^eme job pourraient se trouver a ectees a la m^eme machine et ainsi la surcharger. La duree de l'ordonnancement s'en trouverait augmentee de facon importante. L'agregation etant globale et les choix des emplacements d'insertion independants, il est necessaire de prevoir ce phenomene. Pour cela, nous proposons de tenir compte de cette surcharge des machines en calculant, pour chaque insertion envisagee, la di erence entre le temps operatoire de l'operation et la longueur de l'emplacement choisi. Ainsi, nous interdisons que deux operations du m^eme job soient executees sur la m^eme machine, si pour ces deux operations la di erence calculee est positive. Pour l'heuristique par decoupage du temps et agregation iterative, le probleme precedent ne se pose pas. Les operations etant inserees les unes apres les autres et les dates de debut au plus t^ot et au plus tard etant recalculees apres chaque insertion, on peut inserer dans le meilleur intervalle possible sans risque de surcharger une machine. Le seul probleme est donc le nombre d'emplacements a considerer. Il en est de m^eme pour l'insertion relative. En n, l'heuristique basee sur une fonction co^ut est confrontee aux 3.3. DES METHODES DE RESOLUTION 97 deux problemes precedents, le nombre d'emplacements et la surcharge des machines. Dans ce cas, il est necessaire de faire intervenir dans la fonction ces deux considerations. Pour le probleme de surcharge d'une machine, le choix de celle-ci sera pondere par rapport a son taux d'utilisation. 3.3.2 Heuristiques constructives deux-phases Les heuristiques constructives deux-phases ont pour but de separer la phase d'a ectation et la phase d'ordonnancement. Ce genre de methodes est deja tres utilise pour la resolution du probleme du \vehicle routing" par exemple [18] , ou les phases d'a ectation et de routage sont separees. Quand l'a ectation est realisee, chaque operation est liee a une machine et l'on se ramene a un probleme de job-shop statique et deterministe. Dans ce genre de methode, la phase d'ordonnancement est tres dependante des choix que l'on fait pour l'a ectation. Quatre processus d'a ectation sont maintenant discutes ainsi que leurs in uences sur le choix de la procedure d'ordonnancement. 3.3.2.1 L'a ectation lineaire L'idee la plus naturelle est bien sur de minimiser le temps total de fonctionnement de l'atelier de production. Pour cela, il sut de choisir pour chaque operation O , le minimum des temps operatoires sur les machines disponibles. On a alors : p = 2min p (3.22) i;j i;j Mk R(Oi;j ) i;j;k La diculte principale vient du fait que certaines machines plus rapides que les autres vont se trouver surchargees. Pour eviter ce phenomene indesirable, une solution est de limiter la capacite des machines. Ainsi, une machine m^eme rapide sera chargee a peu pres autant que les autres. Le probleme peut se modeliser de la facon suivante. Soit x la variable d'a( ectation. O est a ectee a M x = 10 sisinon (3.23) i;j;k i;j i;j;k k CHAPITRE 3. LE JOB-SHOP GE NE RALISE 98 L'objectif est maintenant de minimiser la charge de la machine la plus employee, CHmax. On a alors les equations suivantes : min CHmax X M RO X k 2 ( xi;j;k = 1 k (i = 1; :::; n; j = 1; :::; ni) (3.25) i;j ) O jM 2R(O i;j (3.24) i;j ) xi;j;k pi;j;k CHmax (k = 1; :::; m) (3.26) Les equations 3.25 representent les contraintes de l'a ectation classique. Elles precisent qu'une operation est a ectee a une machine et une seule. Les equations 3.26 (une pour chaque machine) totalisent les temps operatoires des operations qui lui sont a ectees. Ainsi, la minimisation de la charge maximum (CHmax) entra^ne un equilibrage des charges sur les di erentes machines. Cette modelisation est semblable a celle proposee par C.N. Potts [89] pour la resolution de problemes de machines paralleles. Le principe est de relaxer les contraintes d'integrite des variables xi;j;k , puis de resoudre le programme lineaire. Pour les variables fractionnaires, une heuristique permet ensuite de les arrondir pour obtenir une solution en 0{1. Ceci est vrai egalement dans les modeles des paragraphes suivants. 3.3.2.2 L'a ectation lineaire avec capacites Nous proposons maintenant une methode d'a ectation lineaire ou les capacites des machines sont prises en compte. Ces capacites sont estimees en fonction de la somme des temps operatoires sur chaque groupe de machines. Ce type d'a ectation s'adapte particulierement bien aux ateliers dans lesquels les machines appartiennent a des groupes et tels que chaque operation est a ectee a un groupe. Pour un groupe de machines donne Gr , une operation peut passer sur chacune des machines avec des temps operatoires di erents. On peut alors calculer le temps operatoire moyen pour l'execution de l'operation, pi;j . On calcule alors la capacite d'une machine comme etant la somme 3.3. DES METHODES DE RESOLUTION 99 des temps operatoires moyens de toutes les operations liees a ce groupe, divisee par le nombre de machines du groupe. On obtient ainsi pour chaque groupe Gr , une charge maximum CHmax(Gr ). On obtient donc la formulation suivante : X X X xi;j;k pi;j;k i j k X xi;j;k = 1 (i = 1; :::; n; j = 1; :::; ni) M RO X xi;j;k pi;j;k CHmax(Gr) (k = 1; :::; m) min k 2 i=n j =n k=m i =1 ( k =1 (3.27) (3.28) i;j ) O jM 2G i;j =1 (3.29) r Les contraintes de ce probleme sont les m^emes que pour la formulation precedente mais la fonction objectif exprime directement la minimisation de la somme des temps operatoires. 3.3.2.3 L'a ectation de separation Le but de cette a ectation est de repartir l'utilisation des di erentes machines dans les gammes operatoires des jobs. De ce fait, on evite par exemple qu'une machine e ectue la premiere operation de tous les jobs. Ainsi, chaque machine doit realiser un nombre equilibre de premiere operation, de deuxieme operation, etc. L'equilibrage est bien sur le souci principal de cette a ectation, mais il ne doit pas eluder la minimisation de la somme des temps operatoires. C'est pourquoi, le modele suivant tient compte en m^eme temps de l'equilibrage (critere principal d'a ectation), mais egalement de la minimisation de la somme des temps operatoires. Les contraintes 3.26 sont scindees en plusieurs contraintes, une pour chaque position de l'operation dans la gamme operatoire. Ainsi, il existe une contrainte pour chaque machine et chaque position dans la gamme operatoire des jobs. Le probleme s'ecrit : min CHmax (3.30) CHAPITRE 3. LE JOB-SHOP GE NE RALISE 100 i n X xi;j;k pi;j;k CHmax = i=1 i=n (j = 1; :::; max n ; k = 1; :::; m) (3.31) i=1 i Ce type d'a ectation est particulierement adapte pour l'utilisation d'une procedure d'agregation Pl L Pr . Dans ce cas, il est possible de mettre en place une procedure de groupement par une methode de decomposition ou de regroupement de jobs decales (cf 2.3.2). 3.3.2.4 L'a ectation de decomposition Nous proposons, pour nir, une a ectation en deux phases pour la decomposition du probleme. La premiere consiste a regrouper les machines en ^lots. La deuxieme phase est chargee de repartir les jobs a ordonnancer dans ces ^lots. Cette approche a deja ete proposee par L.M. Aguilera [4]. Le principe est de construire autant de famille de jobs qu'il y a d'^lots de machines. Ensuite, les jobs sont repartis dans les di erentes familles en vue d'^etre executes sur les machines de l'^lot. Dans le souci d'equilibrer les charges entre le ^lots, l'utilisation d'un des modeles precedents est indispensable. Il est necessaire que chaque ^lot comporte au moins un exemplaire des machines pouvant executer les operations des jobs. Ainsi, quelque soit le job, toutes ses operations pourront ^etre a ectees a une machine de l'^lot et par la eviter un lien avec un autre ^lot. Quand cette repartition des machines est faite, les jobs sont a ectes a un ^lot. Il est ensuite possible de traiter chaque ^lot comme un jobshop statique et deterministe si une machine de chaque type est presente dans chaque^lot, ou comme un job-shop generalise si plusieurs machines de chaque type gurent dans les ^lots. Chaque sous-probleme peut alors ^etre resolu independamment des autres et la resolution de chacun donne une solution au probleme general. 3.3. DES METHODES DE RESOLUTION 101 3.3.3 Heuristiques amelioratrices Les heuristiques amelioratrices que nous proposons maintenant sont directement issues des methodes exposees dans le chapitre precedent. Toutefois, l'a ectation des operations aux machines ajoute un degre de liberte supplementaire et permet de concevoir une approche de reoptimisation par rea ectation. 3.3.3.1 Optimisation par permutations d'operations La procedure decrite dans la section 2.4 peut ^etre utilisee directement sur les solutions intermediaires ou sur la solution nale. Celle-ci ( gure 2.4) ne joue que sur le placement des di erentes operations dans les sequences des machines mais pas sur l'a ectation. L'inter^et principal de cette methode est son utilisation dans une heuristique deux-phases ou l'a ectation et l'ordonnancement sont separes. Ceci permet de dissocier franchement les deux phases, et ainsi former deux niveaux de decisions tres independants. Ce genre de fonctionnement est utilise dans des systemes de gestion de production [4] [5]. 3.3.3.2 Optimisation par rea ectations La deuxieme maniere d'ameliorer une solution utilise le principe de rea ectation. Celui-ci consiste a choisir une operation du graphe critique et de la rea ecter sur une autre machine moins chargee. De la m^eme facon que pour la procedure decrite precedemment, cette methode peut ^etre integree dans une heuristique de type tabou. L'algorithme de la gure 3.2 montre le fonctionnement d'une procedure simpli ee. En e et, il est possible, en utilisant le principe de rea ectation, de modi er la procedure pour qu'elle prenne en compte la rea ectation de plusieurs operations en m^eme temps. Ceci permet par exemple l'echange des deux operations d'une machine a l'autre. Cette methode est interessante car une a ectation qui pourrait sembler naturelle, par exemple a ecter l'operation a la machine la plus ra- CHAPITRE 3. LE JOB-SHOP GE NE RALISE 102 1. CHOIX D'UNE OPERATION Choix d'une operation du chemin critique. 2. REAFFECTATION (a) Rea ectation de l'operation selectionnee sur une autre machine. (b) Calcul de la duree totale de l'ordonnancement, Cmax, apres rea ectation. (c) Si le nouveau Cmax est inferieur a l'ancien, valider la rea ectation, sinon l'annuler. ^ 3. CONDITION D'ARRET (a) Si aucune rea ectation n'ameliore le Cmax, arr^eter. (b) Sinon, retourner en 1. Fig. 3.2 - Algorithme d'amelioration par rea ectations pide, chargerait sans doute de facon importante quelques machines et en sous-emploierait d'autres. De la m^eme maniere que pour la procedure precedente qui n'agissait que sur l'ordre des operations, cette heuristique n'agit que sur l'a ectation des operations aux machines. Elle est donc tres adaptee aux methodes dissociant les phases d'a ectation et d'ordonnancement. 3.3.3.3 Optimisation par permutations et reaffectations Cette methode utilise les deux procedures decrites precedemment. Plusieurs manieres de les combiner permettent d'ameliorer le rendement de chacune. 3.4. RE SULTATS NUME RIQUES 103 Dans un premier temps, il est possible d'appeler les deux procedures alternativement. A partir d'une solution realisable donnee, la premiere procedure appelee est la permutation. Celle-ci fonctionne tant que des permutations d'operations sont realisees. A l'issue de cette etape, la procedure de rea ectation est appelee et recherche d'eventuelles rea ectations interessantes. Un aller-retour entre ces deux procedures permet une reoptimisation plus importante. Cette approche peut ^etre utilisee dans un contexte ou les deux niveaux de decisions (a ectation et ordonnancement) sont dissocies. Une deuxieme possibilite est d'appeler alternativement ces deux procedures sans attendre que toutes les possibilites de permutation ou de rea ectation ne soient epuisees. Ceci permet entre autres d'eviter les tests signi ant qu'il n'y a plus de permutations (resp. rea ectations) possibles. 3.3.3.4 Optimisation par reagregation Le principe de reagregation est le m^eme que celui de la section 2.4.2. Cette approche resout en m^eme temps les problemes d'a ectation et d'agregation. En e et, quand un job est retire de l'ordonnancement, et reintroduit par une procedure d'agregation, celle-ci gere a la fois le choix de la machine pour les operations a inserer et l'emplacement dans la sequence de la machine. Ceci permet une reoptimisation plus globale et est donc interessante a utiliser en n d'optimisation. Ce type d'optimisation ne tient pas compte d'une eventuelle separation entre les niveaux d'a ectation et d'ordonnancement et ne peut donc pas ^etre utilise dans ce contexte. 3.4 Resultats numeriques Les methodes que nous testons dans cette section sont principalement des generalisations des methodes presentees dans le chapitre precedent. Le probleme de job-shop generalise n'est pas couramment CHAPITRE 3. LE JOB-SHOP GE NE RALISE 104 Atelier 1 Atelier 2 Atelier 3 Nombre de groupes Nombres de machines 3 2-3-2 3 5-4-7 6 2-3-2-4-3-3 Fig. 3.3 - Composition des ateliers traite et il n'existe pas de jeux de donnees dans la litterature. De ce fait, et pour les besoins de l'experimentation, nous avons genere une bibliotheque d'instances de ce probleme. 3.4.1 Presentation des jeux de donnees Dans le but de balayer une large gamme de problemes, nous avons considere 3 types d'atelier resume dans le tableau de la gure 3.3. Chaque atelier est compose de groupes de machines et chaque groupe contient plusieurs machines. Ainsi, une operation qui sera a ectee a un groupe de machines ne pourra ^etre executee que par une des machines de celui-ci. Toutefois, il est possible que certaines machines du groupe ne puissent e ectuer l'operation. L'atelier 1 est de petite taille, 7 machines reparties en 3 groupes. Les ateliers 2 et 3 sont de taille plus importante, respectivement 16 et 17 machines, mais reparties di eremment dans les groupes. Dans l'atelier 2, les machines sont divisees en 3 groupes alors que pour l'atelier 3, elles sont divisees en 6 groupes. Les instances du probleme que nous proposons sont decrites dans la gure 3.4. Pour chacun des ateliers, di erents types de jobs sont envisages ainsi que leurs nombres. Pour chacun des types d'ateliers et chaque type de jobs, 25 instances ont ete generees, cela dans le but de calculer des moyennes sur ces 25 instances. 3.4.2 Resultats et conclusions Les regles de priorite choisies pour l'experimentation sont les m^emes que celles du chapitre precedent. Seulement, la le d'attente d'une machine contient toutes les operations pouvant ^etre executees sur celle-ci. 3.4. RE SULTATS NUME RIQUES ! Types d'instances ! Atelier 1 ! 4 operations par jobs ! 25, 50 ou 100 jobs ! 8 operations par jobs ! 25, 50 ou 100 jobs ! Atelier 2 ! 4 operations par jobs ! 50, 100 ou 150 jobs ! 8 operations par jobs ! 50, 100 ou 150 jobs ! Atelier 3 ! 7 operations par jobs ! 50, 100 ou 150 jobs ! 12 operations par jobs ! 50, 100 ou 150 jobs Fig. 3.4 - Les types d'instances g enerees 105 106 CHAPITRE 3. LE JOB-SHOP GE NE RALISE Une operation pouvant ^etre executee par plusieurs machines, une operation peut gurer dans plusieurs les d'attente. Le choix d'une operation dans une le resoudra a la fois l'a ectation et l'ordonnancement. Une operation choisie sera bien entendu retiree des autres les d'attente ou elle etait presente. De la m^eme facon que pour le job-shop statique et deterministe, nous ne garderons dans les tableaux de resultats que les regles donnant la meilleure et la moins bonne des solutions, ainsi que la moyenne des regles. Les methodes OPT testees sont les generalisations des methodes etudiees dans le chapitre 2. Au niveau des procedures d'amelioration, les deux procedures utilisees sont l'amelioration par permutations et rea ectations d'une part, et l'amelioration par reagregations d'autre part. Les resultats obtenus pour chacun des trois ateliers sont tres semblables (cf gures 3.5, 3.6 et 3.7). On constate que pour le probleme de job-shop generalise, les methodes OPT donnent de tres bons resultats par rapport aux regles de priorite. Selon le type d'atelier, le pourcentage d'amelioration entre la meilleure methode OPT et la meilleure regle de priorite varie entre 7 et 8 %. La deuxieme remarque importante est que dans la plupart des cas, la plus mauvaise methode OPT est meilleure que la meilleure des regles de priorite. En ce qui concerne la comparaison des methodes agregatives, nous arrivons aux m^emes conclusions que pour le job-shop statique et deterministe. Premierement, la methode d'agregation par fonction co^ut domine tres legerement l'agregation iterative, qui elle-m^eme domine l'agregation globale. Deuxiemement, la procedure de reagregation permet d'ameliorer sensiblement les resultats obtenus par une simple application de l'amelioration par permutations et rea ectations. Ces tests ont egalement ete e ectues sur une station de travail SPARC 10. Pour une instance de 150 jobs composes de 15 operations chacun a ordonnancer dans l'atelier 3, le temps de calcul n'excede jamais 30 minutes. Pour l'atelier 1, le temps de calcul varie entre 15 secondes pour 25 jobs de 4 operations sans reagregation, a 12 minutes 3.5. 107 CONCLUSION n n 25 25 50 50 100 4 8 4 8 4 OPT1 475 827 875 1479 1682 OPT2 487 845 851 1422 1651 OPT3 459 802 868 1397 1648 OPT4 473 819 853 1421 1667 OPT5 471 782 857 1389 1626 OPT6 452 789 846 1372 1603 Min 498 835 903 1462 1679 Max 575 971 1072 1708 1897 Moy 534 895 1002 1554 1734 Min , OPT 10,2 6,8 6,7 6,6 4,7 OPT Fig. 3.5 - Job-shop g eneralise, atelier 1 i 100 8 3463 3387 3415 3398 3312 3324 3458 3759 3582 4,0 pour 100 jobs de 8 operations avec reagregation. Les temps pour les ateliers 2 et 3 sont comparables pour des instances et des methodes equivalentes. 3.5 Conclusion Le job-shop generalise se compose des deux problemes diciles que sont l'a ectation des operations aux machines et l'ordonnancement des operations. Les methodes agregatives une-phase que nous avons proposees et testees dans ce chapitre sont particulierement bien adaptees a ce type de problemes. La phase d'agregation proprement dite gere a la fois l'a ectation et l'ordonnancement. L'utilisation d'un critere bien adapte (cf 2.5.2), permet de selectionner une machine rapide pour l'operation consideree, car minimisant le temps operatoire, et de trouver un emplacement interessant pour l'insertion de l'operation dans la sequence de la machine choisie. En ce qui concerne l'amelioration locale, les procedures de rea ec- CHAPITRE 3. LE JOB-SHOP GE NE RALISE 108 n n 25 25 50 50 100 100 4 8 4 8 4 8 OPT1 409 698 737 1367 1189 2148 OPT2 401 681 728 1381 1151 2123 OPT3 382 682 732 1336 1163 2097 OPT4 378 679 744 1342 1170 2121 OPT5 389 654 721 1326 1149 2049 OPT6 369 661 723 1311 1134 2057 413 701 763 1403 1218 2159 514 912 895 1757 1385 2461 462 794 812 1459 1257 2223 11,9 7,2 5,8 7,0 7,4 5,0 i Min Max Moy Min , OPT OPT Fig. 3.6 - Job-shop generalise, atelier 2 n n 25 25 50 50 100 100 7 12 7 12 7 12 OPT1 695 1101 1289 2393 1897 3159 OPT2 659 1049 1257 2261 1812 3106 OPT3 669 1012 1294 2307 1789 3121 OPT4 672 1031 1251 2243 1826 3045 OPT5 631 995 1229 2195 1749 3065 OPT6 644 989 1221 2179 1763 3012 689 1056 1319 2308 1897 3148 802 1397 1598 2639 2103 3493 738 1205 1429 2486 1986 3322 9,2 6,8 8,0 5,9 7,6 4,5 i Min Max Moy Min , OPT OPT Fig. 3.7 - Job-shop generalise, atelier 3 3.5. CONCLUSION 109 tations et de permutations permettent, pour la premiere de corriger une a ectation mauvaise, et pour la deuxieme de corriger l'ordonnancement. En e et, lors de la phase d'agregation, une machine faiblement utilisee peut attirer une operation alors que celle-ci necessite un temps operatoire important. La procedure de rea ectation peut alors modier ceci en faisant passer l'operation sur une machine plus adaptee. De m^eme, la sequence des operations n'etant pas modi ee lors de l'agregation d'un nouveau job, il est possible que l'ordonnancement puisse ^etre ameliore par une simple permutation. L'utilisation en alternance des ces deux procedures permet une amelioration sensible de la solution courante a chaque nouvelle agregation. La reagregation modi e plus profondement la structure de la solution courante. Une utilisation couplee avec les deux procedures precedentes permet une amelioration encore plus importante. Comparees avec les regles de priorite, les methodes agregatives donnent des solutions plus interessantes. Bien entendu, le temps de calcul est tres nettement superieur pour les methodes OPT. Toutefois, le choix du type d'agregation et d'amelioration locale permet de contr^oler ce temps pour qu'il ne devienne pas trop important. 110 CHAPITRE 3. LE JOB-SHOP GE NE RALISE 111 Chapitre 4 Le job-shop dynamique et reactif Le job-shop dynamique et reactif [112] [111] introduit une nouvelle diculte dans la problematique classique de l'ordonnancement tel que nous l'avons traitee dans les chapitres 1 a 3. Le but est de trouver un ordonnancement previsionnel admissible le meilleur possible et de suivre son deroulement dans un atelier de production. Lors de cette execution, deux types d'aleas peuvent se produire : l'arr^et momentane d'une machine et l'arrivee d'un nouveau job. Il est alors necessaire de reagir en temps reel a ces perturbations pour redonner rapidement un nouvel ordonnancement admissible. Ces deux types d'aleas sont generalement traites separement dans la litterature. L'arrivee de nouveaux jobs a des instants quelconques du deroulement des operations dans l'atelier constitue l'ordonnancement dynamique. D'autre part, les arr^ets des machines sont traites dans le cadre de l'ordonnancement reactif. Le job-shop dynamique et reactif fait partie des problemes on-line. Dans ces problemes, a l'inverse des problemes consideres jusqu'a present, les donnees ne sont pas toutes connues au depart de l'optimisation. L'optimisation se fait donc sur l'ensemble des jobs connus a un instant donne. Le but des methodes est donc de tenir compte en temps reel des aleas et de proposer le plus rapidement possible la meilleure solution. 112 CHAPITRE 4. LE JOB-SHOP DYNAMIQUE ET RE ACTIF Apres avoir de ni le probleme, nous ferons un rapide tour d'horizon sur quelques methodes connues pour sa resolution. Nous proposerons ensuite un principe de resolution base sur l'agregation ou nous utiliserons quelques uns des resultats sur le job-shop generalise. Les methodes seront testees sur des jeux de donnees crees pour l'experimentation. 4.1 Presentation du probleme Le probleme de job-shop dynamique et reactif n'est pas reellement associe a un modele d'atelier de production comme le sont le job-shop statique et deterministe et le job-shop generalise. Son inter^et est plut^ot de rendre vivant l'atelier de production considere en abordant les problemes d'arr^ets des machines et d'arrivees aleatoires des jobs. Dans un premier temps, les structures de l'atelier et les contraintes liees aux aspects dynamiques seront exposees. Ensuite, les approches de resolution connues seront decrites. 4.1.1 Description du probleme Le type d'atelier de production considere pour le probleme du jobshop dynamique et reactif est le m^eme que celui du job-shop generalise. Les donnees sont donc les suivantes : 1. Un ensemble M de m machines. Une machine est notee M avec k = 1; :::; m. 2. Un ensemble J de n jobs. Chaque job est compose d'une gamme operatoire i.e. une sequence lineaire de n operations xee. Cette sequence ne depend que du job et peut varier d'un job a l'autre. Un job est note J avec i = 1; :::; n. 3. Une operation O represente la jeme operation du job J . Cette operation necessite un temps operatoire p . La date de debut calculee de l'operation O sera toujours notee t . 4. L'operation O necessite, n pour ^etre realis oee, une des machines de l'ensemble R(O ) = M 1 ; M 2 ; :::; M . Le temps operatoire sur la machine M pour l'operation O sera note p . k i i i;j i i;j i;j i;j i;j i;j k k kq k i;j i;j;k 4.1. PRE SENTATION DU PROBLE ME 113 La di erence entre le job-shop generalise et le job-shop dynamique reside dans les aspects dynamiques. Pour tenir compte de ces aspects dans l'atelier, certaines hypotheses utilisees dans les problemes precedents sont a supprimer. Ainsi, l'hypothese qu'une machine est disponible pour toute la duree de l'ordonnancement est a abandonner. Les contraintes auxquelles est soumis l'atelier sont donc les suivantes : 1. Les machines sont independantes les unes des autres. 2. Une machine ne peut executer qu'une seule operation a un instant donne. 3. Chaque machine peut ^etre arr^etee a un instant quelconque du deroulement de l'ordonnancement. Au moment ou l'arr^et se produit, la date de remise en route est xee (on considere ici que l'estimation de la duree des pannes ou de la maintenance est correcte). 4. Une operation en cours d'execution ne peut ^etre interrompue (il n'y a pas de preemption) sauf si la machine s'arr^ete avant que l'operation ne soit nie. Dans ce cas, le reste de l'operation sera poursuivi soit sur la m^eme machine au moment de son redemarrage soit sur une autre. Le temps operatoire restant sera recalcule en fonction de la rapidite de la machine choisie pour nir l'operation. 5. Les jobs sont independants les uns des autres. En particulier, il n'existe aucun ordre de priorite attache aux jobs. 6. Les jobs ne sont pas tous connus au depart, certains peuvent arriver a un instant quelconque de l'ordonnancement. A cet instant, le job est parfaitement de ni (gamme operatoire, machines utilisables pour chaque operation et temps operatoires). Le probleme consiste non seulement a determiner une a ectation de chaque operation sur une machine et a trouver une sequence des operations, mais egalement a tenir compte au cours du temps des evenements aleatoires pouvant se produire. Dans notre etude, et comme 114 CHAPITRE 4. LE JOB-SHOP DYNAMIQUE ET RE ACTIF pour les problemes precedents, le but de l'ordonnancement est de trouver le temps de production pour la totalite des jobs le plus court possible (minimisation de Cmax). 4.1.2 Les methodes de resolution connues Pour la resolution des problemes de job-shop dynamique et reactif, deux grandes idees ont deja ete developpees. La premiere privilegie l'optimisation de l'ordonnancement propose aux depens du temps de calcul et e ectue une decomposition du probleme en une serie de problemes de job-shop statique. La seconde methode est basee sur l'utilisation de regles de priorite, ce qui necessite un temps de calcul tres court et permet de repondre rapidement a un alea. 4.1.2.1 Decomposition en job-shop statique Cette methode ne s'applique pas directement au probleme que nous traitons, mais a un probleme voisin, le job-shop dynamique avec minimisation de la somme des retards. Une adaptation de la methode permettrait de traiter un probleme dynamique et reactif. Cette approche presentee par N. Raman et F.B. Talbot [92] a pour but de decomposer un job shop dynamique en une serie de job-shops statiques. Cette approche est bien s^ur adaptable au probleme que nous traitons maintenant. Le principe de cette approche consiste en un recalcul complet de l'ordonnancement a l'arrivee de chaque nouvel alea. Des qu'un nouveau job arrive ou qu'une machine s'arr^ete, l'ordonnancement prevu est alors annule et les donnees sont entierement reprises pour un nouveau calcul de l'ordonnancement previsionnel (algorithme de la gure 4.1). La m^eme demarche peut s'appliquer au probleme qui nous interesse dans ce memoire. A la date ou un alea survient, on prend les donnees du probleme, sans tenir compte de l'ordonnancement previsionnel precedent, et l'on recalcul un nouvel ordonnancement a partir des donnees. Les jobs dont toutes les operations ont ete executees ne gureront plus dans la liste. Les jobs dont seulement une partie des operations a ete executee seront introduits dans la liste, en les restreignant aux operations restantes. Les jobs dont aucune des operations ne sera traitee 4.1. PRE SENTATION DU PROBLE ME 115 seront mis completement dans la liste. L'ensemble des donnees ainsi reconstitue, il faut mettre en uvre une methode exacte (branch and bound par exemple) pour redonner un ordonnancement previsionnel optimal, au sens de la minimisation de la longueur totale. L'avantage de cette methode est sans aucun doute la qualite des solutions trouvees. En e et, pour chaque alea, un nouvel ordonnancement tenant compte de la totalite des donnees est calcule. Par contre, le temps de calcul est important et cette methode perd de son inter^et lors d'arr^et machines ou d'arrivees de job frequents. On peut donc l'envisager dans des systemes de tres petite taille avec de rares aleas. 4.1.2.2 Les regles de priorite L'utilisation de regles de priorite [15] [51] [84] est de loin la technique la plus employee pour resoudre les problemes d'ordonnancement dynamique et reactif. Dans cette approche, l'ordonnancement est construit au fur et a mesure des besoins. A chaque fois qu'une machine se libere, une regle de priorite determine l'operation qui va ^etre executee sur cette machine, parmi la liste des operations candidates. Cette methode assure a la fois l'a ectation des operations aux machines et l'ordonnancement. Les nombreuses regles etudiees [15] [51] [66] [108] [109] peuvent ^etres classees suivant leurs caracteristiques. Tout d'abord, ces regles peuvent ^etre locales ou globales, statiques ou dynamiques. Une regle est dite locale si elle n'utilise que les informations contenues dans la le ou elle est utilisee, elle est globale si elle utilise des informations de l'ensemble du systeme. Une regle statique a ecte a une piece une priorite constante durant tout l'ordonnancement, elle est dynamique si la valeur de cette priorite peut evoluer au cours du temps ou de l'avancement dans l'ordonnancement. Nous pouvons par exemple citer quelques une des regles les plus classiques tel que FIFO (First In First Out) qui realise en priorite l'operation arrivee la premiere, SPT (Shortest Processing Time) qui choisit l'operation ayant le temps operatoire le plus court. La caracteristique de cette approche est de ne pas construire l'or- 116 CHAPITRE 4. LE JOB-SHOP DYNAMIQUE ET RE ACTIF 1. INITIALISATION Faire la liste des jobs a ordonnancer. 2. CALCUL D'UNE SOLUTION Calculer un ordonnancement avec les jobs presents dans la liste par une methode optimale minimisant la dure totale (Cmax). D'UN JOB 3. ARRIVEE (a) Supprimer de l'ordonnancement les operations deja realisees. (b) Reconstruire la liste des jobs a ordonnancer. (c) Retourner en 2. ^ D'UNE MACHINE 4. ARRET (a) Supprimer de l'ordonnancement les operations deja realisees. (b) Reconstruire la liste des jobs a ordonnancer en tenant compte de la panne. (c) Retourner en 2. 5. FIN DE L'ORDONNANCEMENT L'ordonnancement se termine quand toutes les operations sont achevees. Fig. 4.1 - Algorithme general 4.2. UNE APPROCHE DE RE SOLUTION 117 donnancement previsionnel et de ne pas anticiper sur le deroulement de l'ordonnancement. L'utilisation d'une telle methode se justi e quand le systeme est complexe et que les arrivees des aleas sont frequentes. 4.2 Une approche de resolution L'approche proposee maintenant est basee sur le principe d'agregation, developpe dans les chapitres precedents. L'idee de base de cette approche est de construire un ordonnancement previsionnel qui sera suivi tant qu'il n'y a pas d'aleas. Des qu'un alea survient, le but et de reagir pour proposer a nouveau un ordonnancement previsionnel. L'objectif est de conserver a tout instant du deroulement de l'ordonnancement, un ordonnancement previsionnel complet et optimise. Ceci permet d'avoir une vue globale de l'ordonnancement a venir, a l'inverse des regles de priorite qui construisent l'ordonnancement au fur et a mesure des liberations des machines ou des arrivees des aleas. A chaque arrivee d'un job, la structure de l'ordonnancement previsionnel n'est pas modi e et le nouveau job est agrege a l'ordonnancement existant. Lors d'un arr^et machine, une procedure de rea ectation des operations aux machines ou une procedure de reagregation est mise en uvre pour repondre a la perturbation. Cette methode tente non seulement de trouver un compromis entre le temps de calcul pour la resolution du probleme (regle de priorite) et la recherche de la meilleure solution (decomposition en job-shop statique), mais egalement de repondre rapidement aux aleas en proposant un nouvel ordonnancement partiel. 4.2.1 L'algorithme general de resolution Avant de donner l'algorithme general de resolution du job-shop dynamique et reactif, nous allons detailler les points essentiels du deroulement du probleme. A l'instant initial, nous connaissons l'ensemble M des machines disponibles ainsi qu'un sous-ensemble des jobs a ordonnancer. De ce fait, nous sommes confrontes a un probleme de job-shop generalise. Le but est alors de construire un ordonnancement prevision- 118 CHAPITRE 4. LE JOB-SHOP DYNAMIQUE ET RE ACTIF nel en minimisant la duree totale (Cmax). Celui-ci peut ^etre construit par n'importe quel algorithme de resolution du job-shop generalise. En particulier, tous les algorithmes developpes dans le chapitre 3 sont utilisables. Cet ordonnancement previsionnel se deroulera tant qu'il n'y a pas d'aleas (arr^ets de machines ou arrivee de nouveaux jobs). A l'arrivee d'un nouveau job, nous nous xons comme objectif de garder un maximum d'informations issues de l'ordonnancement previsionnel qui est deja optimise, plut^ot que de recalculer un ordonnancement complet comme le proposent N. Raman et F.B. Talbot [92]. Pour cela, les di erentes operations du nouveau job sont inserees dans l'ordonnancement precedent. La description precise de cette agregation sera presentee dans la section 4.2.2. Le deuxieme type d'aleas pouvant se produire est l'arr^et d'une machine. Lorsque cet arr^et est de courte duree cela ne change pas de facon signi cative l'ordonnancement prevu et un simple decalage dans le temps des operations concernees sut pour absorber l'alea. Pour cela, il sut de decaler les dates de debut de chaque operation sur la machine de la duree de l'arr^et et eventuellement leurs successeurs de gamme. Par contre, si cet arr^et est d'une duree plus importante, une rea ectation des operations que la machine en panne devait realiser sera e ectuee. Chaque operation sera alors dirigee vers une autre machine en fonctionnement. Cette rea ectation sera realisee de la m^eme facon que pour l'agregation de nouvelles operations, a savoir par insertion entre deux operations de l'ordonnancement previsionnel et pendant les temps morts machine. Le comportement detaille de la methode lors de l'arr^et d'une machine sera explique dans la section 4.2.3. Une autre possibilite serait de retirer de l'ordonnancement previsionnel, les jobs touches par l'arr^et de la machine et de les reagreger. Apres chaque modi cation de l'ordonnancement pour une des deux raisons precedentes, une amelioration locale sera e ectuee si le Cmax est fortement augmente. Cette optimisation s'appuie sur trois procedures particulieres utilisant respectivement des permutations d'operations, des rea ectations ou des reagregations de jobs. La procedure de permutation agit sur deux operations successives sur la m^eme machine 4.2. UNE APPROCHE DE RE SOLUTION 119 et tente de les intervertir pour ameliorer la solution courante. La procedure de rea ectation e ectue la rea ectation d'une operation sur une autre machine plus disponible et ceci toujours dans le but d'optimiser la solution courante. Bien entendu, une combinaison de ces deux procedures est envisageable. En n, il est possible d'enlever de l'ordonnancement, des jobs critiques et de les reagreger. Ces procedures seront presentees dans la section 4.2.4. Chacun des points abordes dans les paragraphes precedents permettent de construire l'algorithme general presente dans la gure 4.2. 4.2.2 L'arrivee aleatoire des jobs Comme nous l'avons vu dans la section 4.2.1, l'arrivee d'un job J compose de n operations perturbe le deroulement de l'ordonnancement previsionnel. Notre objectif est ici de faire face a cette perturbation en veillant a conserver une bonne solution sans calculs excessifs. Pour cela, nous utilisons le principe d'agregation qui permet de conserver l'a ectation et l'ordre precedent de passage des operations sur les machines et d'inserer les nouvelles operations dans l'ordonnancement precedent. i i Pour realiser cette agregation, il est possible d'utiliser les methodes d'agregation une-phase developpees dans le chapitre precedent. L'agregation etant faite, il est ensuite possible d'ameliorer la solution donnee par une methode d'optimisation locale. 4.2.3 Les arr^ets machine Dans un probleme de job-shop dynamique, un des aleas possibles est l'arr^et d'une machine M a un instant quelconque t du deroulement de l'ordonnancement [93] et pendant une duree xee au moment de l'arr^et t . Ceci entra^ne une perturbation a laquelle il faut faire face pour redonner un ordonnancement admissible en vue de poursuivre la production. k k Dans ce but, nous proposons deux procedures comportant deux alternatives possibles en fonction de la duree de l'arr^et (algorithmes de 120 CHAPITRE 4. LE JOB-SHOP DYNAMIQUE ET RE ACTIF 1. INITIALISATION Calculer un ordonnancement avec les jobs presents a la date t = 0 par une methode constructive minimisant la dure totale (Cmax). 2. AMELIORATION LOCALE Optimisation de l'ordonnancement par permutations, rea ectations ou reagregations (cf 4.2.4). D'UN JOB 3. ARRIVEE (a) Supprimer de l'ordonnancement les operations deja realisees. (b) Agreger le nouveau job (cf 4.2.2). (c) Retourner en 2. ^ D'UNE MACHINE 4. ARRET (a) Supprimer de l'ordonnancement les operations deja realisees. (b) Si l'arr^et est court, decaler les operations de la duree de l'arr^et. (c) Sinon rea ecter les operations sur une autre machine ou reagreger les jobs touches (cf 4.2.3). (d) Retourner en 2. 5. FIN DE L'ORDONNANCEMENT L'ordonnancement se termine quand toutes les operations sont achevees. Fig. 4.2 - Algorithme de resolution general 4.2. UNE APPROCHE DE RE SOLUTION 121 la gure 4.3 et 4.4). Si la duree de la panne k est petite, environ de la duree moyenne d'une operation sur cette machine, la procedure opere un simple decalage des operations sur cette machine. Ceci pouvant entra^ner un decalage des operations suivantes, il est alors necessaire de recalculer les dates au plus t^ot et au plus tard. Dans le deuxieme cas, si la duree k est grande, superieure a la duree moyenne d'une operation sur la machine, un decalage peut augmenter la duree totale de l'ordonnancement de facon trop importante. Il est alors necessaire de mettre en uvre une procedure de calcul plus importante. t t 4.2.3.1 La rea ectation Une premiere solution est de mettre en uvre une rea ectation des operations concernees par l'arr^et de la machine. Dans ce cas, la procedure determine les operations qui etaient prevues sur la machine defaillante dans l'intervalle de temps [ + k ] et tente de les inserer dans les sequences operatoires des autres machines. La derniere operation pourra eventuellement ^etre simplement decalee. Le principe de cette methode et, dans un premier temps, de trouver pour l'operation a rea ecter, l'intervalle entre et la date de debut au plus tard de l'operation qui suit dans la gamme operatoire du job. Ensuite, il faut chercher les temps-morts sur les machines disponibles dans l'intervalle considere (cf 2.2.4). Il est bien sur obligatoire de veri er la validite de la solution en n'inserant pas d'operations avant leurs predecesseurs de gamme operatoire. Apres avoir e ectue ces rea ectations, il faut a nouveau mettre a jour les dates au plus t^ot et au plus tard. L'insertion se fait comme les insertions precedentes (cf 2.2.4), dans les emplacements les plus grands ou les plus proches de la duree operatoire de l'operation. t; t t t 4.2.3.2 La reagregation Une deuxieme possibilite pour traiter le probleme des arr^ets est la reagregation. Le principe est de supprimer de l'ordonnancement previsionnel, les jobs dont une au moins des operations est touchee par l'arr^et de la machine. Ensuite, il est possible d'ameliorer le nouvel ordonnancement obtenu avant de reagreger les jobs. Ceci est interessant dans le cas ou beaucoup de jobs sont concernes par l'arr^et de la ma- 122 CHAPITRE 4. LE JOB-SHOP DYNAMIQUE ET RE ACTIF ^ D'UNE MACHINE 1. ARRET Arr^et de la machine k pour une duree de k a l'instant . 2. MISE A JOUR DE L'ORDONNANCEMENT PREVISIONNEL Suppression des operations achevees avant la date . ^ 3. IMPORTANCE DE L'ARRET M t t t (a) Si k est petit, decalage des operations sur la machine et retourner en 5. (b) Si k est grand, aller en 4. 4. REAFFECTATION Rea ectation des operations de la machine k initialement prevues dans l'intervalle de temps [ + k ], sur d'autres machines disponibles. 5. CALCUL DU PERT Calcul des dates au plus t^ot et au plus tard. t t M t; t Fig. t 4.3 - Algorithme de rea ectation apres arr^et d'une machine 4.3. RE SULTATS NUME RIQUES 123 chine. La derniere phase consiste a reagreger les jobs enleves. Pour cela, nous pouvons utiliser une des procedures d'agregation proposees avant. L'ordre dans lequel les jobs sont reintroduits est dependant du choix de la procedure de selection. 4.2.4 La reoptimisation locale Le principe de reoptimisation des solutions n'est bien s^ur pas different des principes expliques dans les chapitres 2 et 3. Le choix des methodes est surtout lie au temps dont on dispose pour l'amelioration par rapport au deroulement de l'ordonnancement previsionnel. Dans le cas ou l'atelier est peu perturbe, calculer une bonne solution est interessant. Cela permet une bonne optimisation et d'obtenir un ordonnancement quasi-optimal qui sera suivi sur une longue periode. Par contre, si l'atelier est fortement perturbe, l'inter^et est plut^ot de reagir vite aux aleas et limiter les phases de reoptimisation locale. En e et, il n'est pas necessaire de calculer de tres bonnes solutions si elles doivent ^etre remises en cause peu de temps apres. 4.3 Resultats numeriques Dans le but de valider notre approche par agregation pour le jobshop dynamique et reactif, nous avons compare nos resultats avec ceux obtenus par des algorithmes bases sur des regles de priorite. Dans un premier temps, et comme il n'existe pas d'exemples classiques pour le job-shop dynamique dans la litterature, nous avons cree une bibliotheque de jeux de donnees. Ces jeux de donnees regroupent plusieurs types d'atelier de production et des problemes de tailles di erentes. Ensuite, quelques methodes de resolution issues de notre approche sont testees sur cette bibliotheque et comparees avec des algorithmes classiques. Pour nir, les resultats obtenus sont commentes. 124 CHAPITRE 4. LE JOB-SHOP DYNAMIQUE ET RE ACTIF ^ D'UNE MACHINE 1. ARRET Arr^et de la machine Mk pour une duree de tk a l'instant t. 2. MISE A JOUR DE L'ORDONNANCEMENT PREVISIONNEL Suppression des operations achevees avant la date t. ^ 3. IMPORTANCE DE L'ARRET (a) Si tk est petit, decalage des operations sur la machine et retourner en 5. (b) Si tk est grand, aller en 4. 4. ENLEVEMENT DES JOBS Enlevement des jobs dont les operations sont touchees par l'arr^et de la machine. 5. REAGR EGATION Reagregation des jobs enleves. 6. CALCUL DU PERT Calcul des dates au plus t^ot et au plus tard. Fig. 4.4 - Algorithme de reagregation apres arr^et d'une machine 4.3. RE SULTATS NUME RIQUES Atelier 1 Atelier 2 Atelier 3 125 Nombre de groupes Nombre de machines 3 2-3-2 3 5-4-7 6 2-3-2-4-3-3 Fig. 4.5 - Composition des ateliers 4.3.1 Presentation des jeux de donnees Le probleme de job-shop dynamique que nous avons decrit dans ce chapitre est rarement traite avec les m^emes contraintes et les m^emes objectifs dans la litterature [9] [17] [48]. Le plus souvent, les deux problemes que constituent l'ordonnancement dynamique et l'ordonnancement reactif sont separes. Le premier ne traite que les aspects dynamiques representes par l'arrivee aleatoire de jobs et pour le second, seule la reaction a un arr^et machine est prise en compte. C'est pour cela que nous proposons la creation d'une bibliotheque de jeux de donnees correspondant au probleme que nous avons de ni dans ce chapitre. Pour cela, plusieurs types d'ateliers sont proposes et pour chacun d'eux plusieurs types de production. Le nombre de jobs, d'operations par jobs ainsi que le type et le nombre des aleas peuvent varier. En ce qui concerne les ateliers, 3 types sont proposes (tableau de la gure 4.5). Ces ateliers sont les m^emes que ceux qui nous ont servis dans le chapitre precedent pour generer les instances du job-shop generalise. Le nombre de jobs presents a l'instant initial est d'environ 25 pour l'atelier 1, 50 pour l'atelier 2 et 60 pour l'atelier 3. Ces jobs peuvent avoir des caracteristiques di erentes. Ainsi, nous avons cree des jeux de donnees pour l'atelier 1 ou les jobs sont composes de 4 operations, puis des jeux de donnees ou les jobs sont composes de 8 operations. Les details pour les autres ateliers sont consignes dans la gure 4.6. Pour chacun des ateliers et des types de jobs, nous avons genere 3 types d'aleas, seulement des arr^ets machines (ordonnancement reactif), seulement des arrivees de jobs (ordonnancement dynamique) et les deux 126 CHAPITRE 4. LE JOB-SHOP DYNAMIQUE ET RE ACTIF ensemble. Pour nir, pour chacun des cas precedents, deux instances ont ete creees, l'une avec un faible nombre d'aleas, et l'autres avec un nombre plus important. Pour chacun des cas precedents, nous avons realise 25 instances avec les m^emes valeurs (nombre de jobs au depart, nombre d'operations par jobs, etc). Ceci nous permettra de donner des resultats sur la moyenne des 25 instances et ainsi mieux juger de la qualite des methodes mises en uvre. La diversite des problemes que nous proposons a pour but d'etudier l'in uence des di erents parametres sur les resultats obtenus. Ainsi, on pourra etudier le comportement des methodes sur des tailles d'ateliers di erentes, des nombres d'operations variables et aussi sur les aspects reactifs et dynamiques des ordonnancements. 4.3.2 Resultats et conclusions Les regles de priorite choisies pour l'experimentation sont les m^emes que celles des chapitres precedents. A l'arrivee d'un nouveau job dans l'atelier, la premiere operation est placee dans les les d'attente des machines pouvant executer celle-ci. Dans le cas d'un arr^et d'une machine, l'operation en cours est stoppee et remise dans les les d'attente sur les machines disponibles. De la m^eme facon que pour les problemes precedents, nous ne garderons dans les tableaux de resultats que les regles donnant la meilleure et la moins bonne des solutions, ainsi que la moyenne des regles. Nous presentons maintenant 12 methodes permettant de tester a la fois les procedures d'agregation, les procedures de reoptimisation et les reactions aux aleas. L'agregation globale sera testee ainsi que les agregations iterative et par fonction co^ut. Pour ce qui est des procedures de reoptimisation, nous utiliserons la permutation, la rea ectation et la reagregation. En n nous regarderons la reaction aux arr^ets machines par rea ectation de l'operation en cours et par reagregation des jobs concernes. 4.3. RE SULTATS NUME RIQUES ! Types d'instances 127 ! Atelier 1 (25 jobs au depart) ! 4 operations par jobs ! Arr^ets de machines (15 ou 50) ! Arrivees de jobs (15 ou 50) ! Arr^ets de machines (8 ou 25) et arrivees de jobs (8 ou 25) ! 8 operations par jobs ! Arr^ets de machines (25 ou 100) ! Arrivees de jobs (25 ou 100) ! Arr^ets de machines (13 ou 50) et arrivees de jobs (13 ou 50) ! Atelier 2 (50 jobs au depart) ! 4 operations par jobs ! Arr^ets de machines (15 ou 50) ! Arrivees de jobs (15 ou 50) ! Arr^ets de machines (8 ou 25) et arrivees de jobs (8 ou 25) ! 8 operations par jobs ! Arr^ets de machines (30 ou 120) ! Arrivees de jobs (30 ou 120) ! Arr^ets de machines (15 ou 60) et arrivees de jobs(15 ou 60) ! Atelier 3 (60 jobs au depart) ! 7 operations par jobs ! Arr^ets de machines (25 ou 100) ! Arrivees de jobs (25 ou 100) ! Arr^ets de machines (13 ou 50) et arrivees de jobs (13 ou 50) ! 12 operations par jobs ! Arr^ets de machines (40 ou 160) ! Arrivees de jobs (40 ou 160) ! Arr^ets de machines (20 ou 80) et arrivees de jobs (20 ou 80) Fig. 4.6 - Les types d'instances g enerees 128 CHAPITRE 4. LE JOB-SHOP DYNAMIQUE ET RE ACTIF Les methodes sont presentees en fonction de la methode d'agregation, puis de la methode d'amelioration et en n de la maniere de reagir aux arr^ets de machines : { OPT1 : 1. Agregation globale 2. Amelioration par permutations et rea ectations 3. Rea ectation des operations { OPT2 : 1. Agregation globale 2. Amelioration par permutations et rea ectations 3. Reagregation des jobs { OPT3 : 1. Agregation globale 2. Amelioration par permutations, rea ectations et reagregations 3. Rea ectation des operations { OPT4 : 1. Agregation globale 2. Amelioration par permutations, rea ectations et reagregations 3. Reagregation des jobs { OPT5 : 1. Agregation iterative 2. Amelioration par permutations et rea ectations 3. Rea ectation des operations 4.3. RE SULTATS NUME RIQUES 129 { OPT6 : 1. Agregation iterative 2. Amelioration par permutations et rea ectations 3. Reagregation des jobs { OPT7 : 1. Agregation iterative 2. Amelioration par permutations, rea ectations et reagregations 3. Rea ectation des operations { OPT8 : 1. Agregation iterative 2. Amelioration par permutations, rea ectations et reagregations 3. Reagregation des jobs { OPT9 : 1. Agregation par fonction co^ut 2. Amelioration par permutations et rea ectations 3. Rea ectation des operations { OPT10 : 1. Agregation par fonction co^ut 2. Amelioration par permutations et rea ectations 3. Reagregation des jobs { OPT11 : 1. Agregation par fonction co^ut 2. Amelioration par permutations, rea ectations et reagregations 130 CHAPITRE 4. LE JOB-SHOP DYNAMIQUE ET RE ACTIF 3. Rea ectation des operations { OPT12 : 1. Agregation par fonction co^ut 2. Amelioration par permutations, rea ectations et reagregations 3. Reagregation des jobs On peut remarquer que dans le cas ou il n'y a pas d'arr^ets machines dans les aleas, les calculs OPT1 et OPT2, OPT3 et OPT4, OPT5 et OPT6, OPT7 et OPT8, OPT9 et OPT10, OPT11 et OPT12 sont identiques, car la di erence entre ces calculs provient uniquement du type de reponses a un arr^et. Les resultats des tests numeriques sont presentes pour chaque atelier. Pour un atelier donne, un tableau presente un des types d'aleas consideres dans cette etude, job-shop dynamique pour les arrivees de jobs uniquement, job-shop reactif pour les arr^ets machines et job-shop dynamique et reactif pour les deux en m^eme temps. La premiere colonne du tableau (n ) donne le nombre d'operations dans la gamme des jobs, la deuxieme donne la quantite d'aleas arrivant dans l'atelier (P pour peu et B pour beaucoup) (se reporter a la gure 4.6). Les 3 colonnes suivantes donnent les resultats des methodes d'optimisation OPT. Pour ne pas compliquer l'analyse des resultats, nous donnons uniquement la valeur de la meilleure methode, la valeur de la plus mauvaise et la moyenne des 12 (ou des 6 dans le cas du job-shop dynamique). Dans les 3 colonnes suivantes gurent les resultats des regles de priorite. La derniere colonne contient le pourcentage d'amelioration entre la meilleure methode d'optimisation et la meilleure regle de priorite. i 4.3.2.1 Resultats pour l'atelier 1 Le tableau 4.7 presente les resultats obtenus avec des aleas de type arrivee de jobs. Mis a part pour la premiere serie de donnees ou les 4.3. RE SULTATS NUME RIQUES 131 n qa 4 8 4 8 P P B B OPT1 881 1534 1341 4803 OPT2 869 1542 1322 4822 OPT3 841 1491 1361 4791 OPT4 842 1502 1354 4788 OPT5 853 1448 1382 4742 OPT6 812 1463 1219 4738 OPT7 791 1442 1228 4699 OPT8 802 1419 1197 4684 OPT9 804 1412 1203 4720 OPT10 741 1399 1198 4610 OPT11 722 1396 1182 4682 OPT12 715 1421 1145 4634 Min 782 1435 1203 4781 Max 905 1698 1411 5428 Moy 842 1582 1341 5154 Min , OPT 9,4 2,8 5,1 3,2 OPT Fig. 4.7 - Job-shop dynamique, atelier 1 i meilleures methodes OPT sont performantes, dans les autres cas, la meilleure regle de priorite n'est que tres legerement moins bonne. Le tableau 4.8 presente les resultats obtenus avec des aleas de type arr^ets machines. On constate que les methodes par agregation donnent des resultats de 5 a 10 % meilleurs que les regles de priorite. Ces resultats sont d'autant meilleurs que le nombre d'operations par jobs est faible (4 au lieu de 8). Dans le cas du job-shop dynamique et reactif (tableau de la gure 4.9), ou les aleas sont repartis entre arrivees de jobs et arr^ets machines, les resultats obtenus sont comparables a ceux obtenus pour le job-shop reactif. La valeur de la meilleure methode agregative est de 3 a 6 % inferieure a celle donnee par la meilleure regle de priorite. 132 CHAPITRE 4. LE JOB-SHOP DYNAMIQUE ET RE ACTIF n qa 4 8 4 8 P P B B OPT1 524 903 728 1212 OPT3 532 848 741 1221 OPT5 494 862 754 1203 OPT7 482 821 692 1170 OPT9 481 834 649 1182 OPT11 465 808 688 1145 Min 512 860 688 1145 Max 603 992 873 1392 Moy 545 922 769 1244 Min , OPT 10,2 6,4 9,3 5,2 OPT Fig. 4.8 - Job-shop r eactif, atelier 1 i Pour l'atelier 1, les resultats obtenus par les methodes agregatives sont meilleurs que ceux obtenus par les regles de priorite. Il est toutefois interessant de constater que les methodes OPT obtiennent de meilleurs resultats dans la resolution de problemes reactifs. 4.3.2.2 Resultats pour l'atelier 2 Le tableau 4.10 contient les resultats obtenus sur l'atelier 2 dans le cas du job-shop dynamique. On peut remarquer que les methodes agregatives donnent globalement de meilleurs resultats que les regles de priorite (de 5 a 11 %). De plus on peut constater que l'on obtient de meilleurs resultats pour les instances dont le nombre d'aleas est le plus faible (cf gure 4.6). D'apres les resultats du tableau 4.11, on peut constater, comme pour l'atelier 1, que dans le cas d'un job-shop reactif, on obtient les meilleurs resultats pour les methodes agregatives. Les resultats obtenus dans le cas d'un job-shop dynamique et reactif sont comparable a ceux de l'atelier 1. Ils sont presentes dans le tableau 4.3. RE SULTATS NUME RIQUES n qa 133 4 8 4 8 P P B B OPT1 643 1291 1143 2853 OPT2 651 1298 1138 2812 OPT3 650 1302 1108 2821 OPT4 639 1281 1121 2842 OPT5 642 1253 1141 2824 OPT6 621 1248 1122 2831 OPT7 638 1261 1106 2803 OPT8 626 1268 1121 2742 i OPT9 631 1241 1092 2803 OPT10 623 1234 1097 2752 OPT11 604 1241 1112 2764 OPT12 612 1236 1080 2724 642 1297 1121 2841 748 1402 1262 3287 691 1351 1135 3012 6,2 5,1 3,8 4,3 Min Max Moy Min , OPT OPT Fig. 4.9 - Job-shop dynamique et reactif, atelier 1 134 CHAPITRE 4. LE JOB-SHOP DYNAMIQUE ET RE ACTIF n qa 4 8 4 8 P P B B OPT1 612 1272 992 2198 OPT2 608 1285 978 2213 OPT3 621 1279 980 2212 OPT4 604 1221 982 2212 OPT5 618 1238 961 2239 OPT6 612 1248 955 2213 OPT7 598 1254 953 2164 OPT8 612 1163 947 2203 i OPT9 604 1204 968 2164 OPT10 582 1173 936 2158 OPT11 591 1198 963 2192 OPT12 563 1204 945 2133 618 1292 986 2242 742 1503 1104 2692 663 1204 1023 2453 9,8 11,1 5,4 5,1 Min Max Moy Min , OPT OPT Fig. 4.10 - Job-shop dynamique, atelier 2 4.3. RE SULTATS NUME RIQUES 135 n qa 4 8 4 8 P P B B OPT1 489 908 672 1021 OPT3 509 887 651 1014 OPT5 501 872 683 982 OPT7 468 857 642 957 OPT9 460 845 623 964 OPT11 482 839 608 943 Min 514 912 672 1032 Max 682 1098 782 1291 Moy 569 973 687 1129 Min , OPT 11,9 8,7 10,5 9,4 OPT Fig. 4.11 - Job-shop r eactif, atelier 2 i de la gure 4.12. Dans cet atelier ou le nombre de machines par groupes et plus important (cf 4.5), les methodes agregatives donnent de meilleurs resultats que pour l'atelier precedent. En e et, le pourcentage d'amelioration entre la meilleure methode OPT et la meilleure regle de priorite est plus eleve. 4.3.2.3 Resultats pour l'atelier 3 En ce qui concerne l'atelier 3, le tableau de resultat 4.13 sur le job-shop dynamique con rme les resultats enregistres pour le job-shop dynamique de l'atelier 1. Les methodes agregatives, bien que meilleures, ne dominent pas franchement les regles de priorite. Comme nous l'avons deja constate pour les ateliers precedents, c'est pour le job-shop reactif que les methodes OPT donnent les resultats les meilleurs. Dans ce cas, le pourcentage d'amelioration varie entre 6 et 9 %. Les resultats sont consignes dans le tableau de la gure 4.14. 136 CHAPITRE 4. LE JOB-SHOP DYNAMIQUE ET RE ACTIF n qa 4 8 4 8 P P B B OPT1 535 1038 742 1769 OPT2 552 1021 754 1781 OPT3 524 997 743 1792 OPT4 551 1005 738 1779 OPT5 523 1024 755 1748 OPT6 534 1032 731 1712 OPT7 542 988 725 1721 OPT8 521 987 706 1705 i OPT9 511 972 714 1698 OPT10 498 948 712 1672 OPT11 502 930 709 1682 OPT12 491 954 721 1655 543 1021 759 1789 639 1282 903 2024 591 1132 824 1941 10,5 9,8 7,5 8,1 Min Max Moy Min , OPT OPT Fig. 4.12 - Job-shop dynamique et reactif, atelier 2 4.3. RE SULTATS NUME RIQUES n qa 137 4 8 4 8 P P B B OPT1 1082 1928 1748 4592 OPT2 1098 1898 1753 4578 OPT3 1102 1904 1751 4524 OPT4 1089 1904 1737 4548 OPT5 1101 1891 1724 4523 OPT6 1101 1879 1742 4492 OPT7 1086 1879 1721 4512 OPT8 1078 1901 1711 4503 i OPT9 1051 1888 1724 4482 OPT10 1068 1862 1709 4491 OPT11 1053 1881 1712 4459 OPT12 1046 1871 1706 4461 1092 1935 1742 4602 1305 2218 2105 5328 1154 2031 1904 4948 4,4 3,9 2,1 3,2 Min Max Moy Min , OPT OPT Fig. 4.13 - Job-shop dynamique, atelier 3 138 CHAPITRE 4. LE JOB-SHOP DYNAMIQUE ET RE ACTIF n qa 4 8 4 8 P P B B OPT1 755 1403 988 1712 OPT3 725 1423 975 1663 OPT5 742 1381 962 1705 OPT7 714 1372 932 1634 OPT9 710 1308 945 1651 OPT11 698 1321 924 1622 Min 762 1421 992 1721 Max 912 1552 1148 2086 Moy 834 1493 1082 1921 Min , OPT 9,1 8,6 7,4 6,1 OPT Fig. 4.14 - Job-shop r eactif, atelier 3 i Pour nir, le tableau 4.15 con rme a nouveau les resultats sur l'atelier 1. Les resultats obtenus pour cet atelier semble con rmer les resultats obtenus pour l'atelier 1. Des remarques generales sont faites dans la section suivante ou les grandes lignes de l'experimentation sont precisees. 4.3.2.4 Remarques generales En ce qui concerne les types d'agregation, les resultats obtenus aux chapitres 2 et 3 sont con rmes par les tests presentes plus haut. L'agregation globale, plus rapide que les deux autres, est la moins performante des trois (de 5 a 10 %). L'agregation iterative est plus rapide que l'agregation par fonction co^ut mais donne des resultats legerement moins bons (de l'ordre de 2 %). Pour ce qui est des methodes d'amelioration locale, l'utilisation combinee de la reagregation avec les permutations et les rea ectations ameliore sensiblement les performances des methodes. Ceci etait deja vrai 4.3. RE SULTATS NUME RIQUES n qa 139 4 8 4 8 P P B B 1012 1923 1451 3095 OPT2 998 1934 1412 3107 OPT3 1005 1892 1438 3098 OPT4 1022 1872 1423 3056 OPT5 978 1905 1442 3063 OPT6 964 1912 1423 3092 OPT7 982 1864 1421 3087 OPT8 1005 1872 1399 3052 i OPT1 OPT9 942 1845 1376 3038 OPT10 954 1832 1402 3043 OPT11 963 1824 1398 2962 OPT12 939 1808 1381 3082 1031 1942 1443 3122 1221 2203 1612 3587 1123 2104 1491 3348 9,8 7,4 4,9 5,4 Min Max Moy Min , OPT OPT Fig. 4.15 - Job-shop dynamique et reactif, atelier 3 140 CHAPITRE 4. LE JOB-SHOP DYNAMIQUE ET RE ACTIF pour les problemes de job-shop statique et deterministe et pour le jobshop generalise. Pour l'experimentation, nous avons teste deux types de reponses a l'arr^et d'une machine, la rea ectation des operations concernees par l'arr^et et la reagregation des jobs. La reagregation donne de meilleurs resultats que la rea ectation sans toutefois que cela soit signi catif (de l'ordre de 2 %). Les resultats obtenus sur les trois types de problemes etudies (jobshop dynamique, reactif et, dynamique et reactif) font appara^tre que toutes les methodes OPT donnent de meilleurs resultats sur les problemes de type reactif. C'est en e et sur le job-shop reactif que l'ecart des durees de l'ordonnancement entre les methodes agregatives et les regles de priorite est le plus important (entre 8 et 10 % selon les ateliers). Par contre, dans le cas du job-shop dynamique, le pourcentage d'amelioration varie entre 4 et 7 %. Lorsque les aleas sont des deux types (job-shop dynamique et reactif), le pourcentage varie entre 5 et 10 %. Pour tester l'in uence de la frequence d'arrivees des aleas, deux nombres d'aleas ont ete proposes pour chaque type d'instances. On constate que quand la frequence d'arrivees des aleas est elevee, les methodes OPT sont moins performantes. L'ecart entre les methodes agregatives et les regles de priorite se resserre. L'in uence du nombre d'operations dans les gammes operatoires des jobs ne semblent pas ^etre tres importante. Les di erences constatees pour un job-shop reactif de l'atelier 1 (cf tableau 4.8) ne se con rme pas pour les autres problemes et les autres ateliers. Pour nir, les methodes agregatives donnent de tres bons resultats quand le nombre de machines par groupes est le plus eleve (cf 4.10, 4.11 et 4.12). Ceci se voit en comparant les resultats donnes sur les ateliers 1 et 2. Par contre, le nombre de groupes ne semble pas in uer sur les resultats des methodes OPT (comparaison entre les ateliers 1 et 3). 4.4. 4.4 CONCLUSION 141 Conclusion L'approche par agregation a ete concue plus particulierement pour traiter des problemes de job-shop dynamique et reactif. Les methodes qui en sont issues et qui ont ete presentees dans ce chapitre et les precedents permettent, dans un premier temps, de trouver des solutions previsionnelles pour l'ordonnancement de production dans un atelier. Ce probleme, de type job-shop generalise, est resolu de facon rapide. Mais l'inter^et principal de l'approche est de reagir rapidement aux aleas de production pouvant survenir. La reaction a un alea par les methodes les plus complexes et sur les instances les plus grandes ne prend pas plus de deux minutes sur une station de travail de type SPARC 10. Les resultats obtenus sont donc conformes a ce que l'on attend de ce genre de methodes. Les methodes proposees jouent beaucoup sur l'a ectation des operations aux machines. Ceci explique tres certainement les bons resultats obtenus sur l'atelier 2. Les methodes fonctionnent d'autant mieux que le nombre de machines dans les groupes est important. Il faudrait donc adapter les methodes pour traiter des problemes ou les possibilites d'a ectation sont plus restreintes. Dans ce cas, l'e ort de calcul pour l'ordonnancement proprement dit devrait ^etre beaucoup plus important, en utilisant des procedures de type tabou pour les permutations d'operations par exemple. Ceci serait possible en reduisant le temps de calcul concernant l'a ectation et la rea ectation. 142 CHAPITRE 4. LE JOB-SHOP DYNAMIQUE ET RE ACTIF CONCLUSION 143 Conclusion Prevoir pour une periode donnee l'organisation et la gestion d'un atelier de production n'est pas chose facile. Parmi toutes les dicultes rencontrees, l'ordonnancement des jobs sur les di erentes machines de l'atelier pose un probleme extr^emement complexe. Les algorithmes developpes ces dernieres annees permettent de resoudre de facon tres ecace des problemes de petite taille (dix jobs, dix machines). Mais, des que le nombre de jobs devient trop important (de l'ordre de cent), l'utilisation de regles de priorite prend le pas sur les autres methodes. L'approche que nous avons developpee dans cette these a pour but de proposer une alternative a l'utilisation des regles de priorite. L'objectif de cette approche est le calcul dans un temps le plus court possible d'une solution de qualite superieure a celle donnee par les regles. Quelques methodes de resolution ont ete presentees, mais d'autres methodes pourront ^etre developpees a partir de cette approche. L'utilisation d'autres fonctions co^ut dans les procedures d'agregation permettrait de mieux tenir compte de la nature du probleme et de l'objectif poursuivi (rapidite ou optimisation par exemple). Bien qu'en partie developpe sur des problemes statiques (job-shop statique et deterministe et job-shop generalise), le principe d'agregation trouve sa pleine justi cation sur les problemes dynamiques et reactifs. Les machines actuelles sont de plus en plus polyvalentes et peu- 144 CONCLUSION vent realiser, gr^ace a un ensemble d'outils, plusieurs types d'operations qui etaient autrefois dediees a une seule. De ce fait, la tendance, pour les ateliers de production modernes, va vers une reduction du nombre des types de machines. La polyvalence de ces machines genere des problemes d'a ectation supplementaires. L'approche par agregation permet de gerer ces problemes d'a ectation et, le developpement de methodes de rea ectations multiples (plusieurs operations echangees entre di erentes machines) permettrait d'ameliorer encore les methodes proposees. Prevoir l'ordonnancement des operations dans un atelier de production est une chose, la realite de l'atelier en est souvent une autre. Le deroulement de l'ordonnancement prevu est souvent dicile car assujetti a de nombreux aleas. Dans le modele de job-shop dynamique et reactif que nous avons traite, deux types d'aleas etaient pris en compte : l'arrivee aleatoire de jobs et l'arr^et momentanee de machines. Ce suivi de production est gere par les methodes agregatives dont le but est de conserver le maximum d'informations de l'ordonnancement previsionnel, tout en prenant en compte les contraintes induites par l'evenement imprevu. La reaction est rapide et redonne immediatement un ordonnancement previsionnel optimise. Ce souci de vision a long terme de l'ordonnancement previsionnel a permis une meilleure optimisation que celle donnee par les regles de priorite utilisees. Les di erents modeles d'ateliers qui ont servi de support au developpement de l'approche par agregation sont bien s^ur tres simpli es. Un objectif interessant serait d'adapter les methodes sur des modeles d'ateliers de production plus complexes tenant compte, par exemple, de l'outillage des machines, des temps de changements de production, etc. En n, l'adaptation du principe d'agregation pour gerer un atelier de production industriel permettrait une reelle evaluation de l'approche proposee. 145 Bibliographie [1] Aarts (E. H. L.), Van Laarhoven (P. J. M.), Lenstra (J. K.) et Ulder (N. L. J.). { A computational study of local search algorithms for job shop scheduling. ORSA Journal on Computing, vol. 6, n 2, 1994. [2] Adams (J.), Balas (E.) et Zawack (D.). { The shifting bottleneck procedure for the job-shop scheduling. Management Science, vol. 34, n 3, 1988. [3] Adiri (I.) et Hefetz (N.). { An ecient algorithm for the twomachine, unit-time, job-shop schedule length problem. Mathematics of Operations Research, vol. 7, 1982. [4] Aguilera (L. M.). { Ordonnancement de Production avec Co^uts de Changements. { These de PhD, Institut National Polytechnique de Grenoble, INPG, 1993. [5] Aguilera (L. M.), Penz (B.), Song (H.) et Binder (Z.). { Design and implementation of a scheduling software system. In : System, Man and Cybernetics Conference, IEEE/SMC. Le Touquet, France, 1993. [6] Akers (S. B.). { A graphical approach to production scheduling problems. Operations Research, vol. 4, 1956. [7] Appelgate (D.) et Cook (W.). { A computational study of jobshop scheduling. ORSA Journal on Computing, vol. 3, 1991. [8] Ashour (S.), Chiu (K. Y.) et Moore (T. E.). { An optimal schedule time of a job-shop like disjunctive graph. Networks, vol. 3, 1973. 146 BIBLIOGRAPHIE [9] Baker (K. R.). { Introduction to Sequencing and Scheduling. { Wiley, 1974. [10] Balas (E.). { Machine sequencing via disjunctive graphs : An implicit enumeration algorithm. Operations Research, vol. 17, n 6, 1969. [11] Balas (E.). { On the facial structure of scheduling polyhedra. Mathematical Programming Studies, vol. 24, 1985. [12] Barker (J. R.) et McMahon (G. B.). { Scheduling the general job-shop. Management Science, vol. 31, n 5, 1985. [13] Bellman (R.). { Dynamic Programming. { Princeton University Press, 1957. [14] Bensana (E.). { Utilisation de Techniques d'Intelligence Arti cielle pour l'Ordonnancement d'Atelier. { These de PhD, Ecole Nationale Superieure de l'Aeronautique et de l'Espace, 1987. [15] Blackstone (J.), Phillips (D.) et Hogg (G.). { A state-of-theart survey of dispatching rules for manufacturing job-shop operations. International Journal of Production Research, vol. 20, n 1, 1982. [16] Blazewicz (J.), Dror (M.) et Weglarz (J.). { Mathematical programming formulations for machine scheduling: A survey. European Journal of Operational Research, vol. 51, 1991. [17] Blazewicz (J.), Ecker (K.), Schmidt (G.) et Weglarz (J.). { Scheduling in exible manufacturing systems. { Springer-Verlag, 1993. [18] Blazewicz (J.), Eiselt (H.), Finke (G.), Laporte (G.) et Weglarz (J.). { Scheduling tasks and vehicles in a exible manufacturing system. International Journal of exible manufacturing systems, vol. 4, n 1, 1991. [19] Bouma (R. W.). { Job-Shop Scheduling : A Comparison of three Enumeration Schemes in a Branch and Bound Approach. { These de PhD, Faculty of Econometrics and Operations Research, Erasmus University, Rotterdam, 1982. BIBLIOGRAPHIE 147 [20] Bowman (E. H.). { The schedule sequencing problem. Operations Research, vol. 7, 1959. [21] Brooks (G. H.) et White (C. R.). { An algorithm for nding optimal or near optimal solution to the production scheduling problem. Journal of Industrial Ingineering, vol. 16, n 1, 1965. [22] Brucker (P.). { An ecient algorithm for the job-shop problem with two jobs. Computing, vol. 40, 1988. [23] Brucker (P.) et Jurisch (B.). { A new lower bound for the job-shop scheduling problem. In : Second International Workshop on Project Management and Scheduling, EURO WG-PMS, Compiegne, 1990. [24] Brucker (P.) et Schlie (R.). { Job-shop scheduling with multipropose machine. Computing, vol. 45, 1990. [25] Carlier (J.). { Disjonctions dans les ordonnancements. RAIRO Recherche Operationnelle, vol. 9, n 2, 1975. [26] Carlier (J.). { One machine problem. European Journal of Operational Research, vol. 11, 1982. [27] Carlier (J.). { Problemes d'Ordonnancements a contraintes de Ressources : Algorithmes et Complexite. { These d'etat, Paris 6, 1984. [28] Carlier (J.) et Pinson (E.). { An algorithm for solving the jobshop problem. Management Science, vol. 35, 1989. [29] Carlier (J.) et Pinson (E.). { A practical use of jackson's preemptive schedule for solving the job-shop problem. Annals of Operations Research, vol. 26, 1990. [30] Conway (R. W.), Maxwell (W. L.) et Miller (L. W.). { Theory of scheduling. { Addison-Wesley, Reading, Mass, 1967. [31] Cuninghame Green (R.). { Minimax Algebra. { Springer-Verlag, Berlin, 1979. 148 BIBLIOGRAPHIE [32] Davis (L.). { Job-shop scheduling with genetic algorithms. In : International conference on Genetic Algorithms and their Applications, ed. par Grefenstette (J.). Carnegie Mellon University, 1985. [33] Dell'Amico (M.) et Trubian (M.). { Applying tabu-search to the job-shop scheduling problem. Annals of Operations Research, vol. 41, 1993. [34] Dorndorf (U.) et Pesch (E.). { Evolution based learning in a job-shop scheduling environment. { avr 1992. Communication Personnelle. [35] Dridi (N.) et Proth (J. M.). { Ordonnancement des t^aches : une methode basee sur la technologie de groupe. In : Proceedings of the second international conference on production systems. 1987. [36] Durand (A.). { Une methode optimale de traitement des contraintes disjonctives dans les problemes d'ordonnancement, application a la construction d'un barrage. R.I.R.O, vol. 1, n 3, 1967. [37] Erschler (J.) et Esquirol (P.). { Decision-aid in job-shop scheduling : A knowledge based approach. In : IEEE Conference on Robotics and Automation. San Fransisco, 1986. [38] Erschler (J.), Fontan (G.) et Merce (C.). { Un nouveau concept de dominance pour l'ordonnancement de travaux sur une machine. RAIRO Recherche Operationnelle, vol. 19, n 1, 1985. [39] Erschler (J.), Roubellat (F.) et Vernhes (J. P.). { Finding some essential characteristics of the feasible solution for a scheduling problem. Operations Research, vol. 24, 1976. [40] Fadil (A.), Aguilera (L. M.), Binder (Z.) et Lemonias (H.). { Jobshop scheduling and production planning assignment. In : International Conference on Industrial Engineering and Production Management. Mons, Belgique, 1993. BIBLIOGRAPHIE 149 [41] Falkenauer (E.) et Bou ouix (S.). { A genetic algorithm for jobshop. In : IEEE International Conference on Robotics and Automation. Sacramento, California, 1991. [42] Fisher (M. L.). { Optimal solution of scheduling problems using lagrange multipliers : Part 1. Operations Research, vol. 21, 1973. [43] Fisher (M. L.). { Optimal solution of scheduling problems using lagrange multipliers : Part 2. In : Symposium on the Theory of Scheduling and its Applications. { Springer, Berlin, 1973. [44] Fisher (M. L.). { A dual algorithm for the one-machine scheduling problem. Mathematical Programming, vol. 11, 1976. [45] Fisher (M. L.). { The lagrangian relaxation method for solving integer programming problems. Management Science, vol. 27, 1981. [46] Fisher (M. L.), Lageweg (B. J.), Lenstra (J. K.) et Rinnooy Kan (A. H. G.). { Surrogate duality relaxation for job-shop scheduling. Discrete Applied Mathematics, vol. 5, 1983. [47] Florian (M.), McMahon (G.) et Trepant (P.). { An implicit enumeration algorithm for the machine sequencing problem. Management Science, vol. 17, n 12, 1971. [48] French (S.). { Sequencing and Scheduling : An Introduction to the Mathematics of the Job-Shop. { Ellis Horwood Limited, 1982. [49] Garey (M. R.) et Johnson (D. S.). { Computers and Intractability : A Guide to the Theory of NP-Completeness. { W. H. Freeman, 1979. [50] Garey (M. R.), Johnson (D. S.) et Sethi (R.). { The complexity of ow-shop and job-shop scheduling. Mathematics of Operations Research, vol. 1, 1976. [51] Gee (E. S.) et Smith (C. H.). { Selecting allowance policies for improved job shop performance. International Journal of Production Research, vol. 31, n 8, 1993. 150 BIBLIOGRAPHIE [52] Geo rion (A. M.). { Lagrangean relaxation for integer programming. Mathematical Programming Studies, vol. 3, 1974. [53] Gier (R.) et Thompson (G. L.). { Algorithms for solving production scheduling problems. Operations Research, vol. 8, n 4, 1960. [54] Glover (F.). { Tabu search, part 1. ORSA Journal on Computing, vol. 1, n 3, 1989. [55] Glover (F.). { Tabu search, part 2. ORSA Journal on Computing, vol. 2, n 1, 1990. [56] Gonzalez (T.) et Sahni (S.). { Flow-shop and job-shop scheduling : Complexity and approximation. Operations Research, vol. 26, 1978. [57] GOThA. { Les problemes d'ordonnancement. RAIRO-RO, vol. 27, n 1, 1993. [58] Grotschel (M.), Lovasz (L.) et Schrijver (A.). { Geometric Algorithms and Combinatorial Optimization. { Springer-Verlag, Berlin Heidelberg, 1988. [59] Guinet (A.) et Legrand (M.). { Reduction of job-shop problems to ow-shop problems with precedence constraints. { 1994. Communication personnelle. [60] Hax (A. C.) et Candea (D.). { Production and inventory management. { Englewood Cli s, New Jersey, Practice-Hall, Inc, 1984. [61] Held (M.) et Karp (R. M.). { A dynamic programming approach to sequencing problems. Journal of SIAM, 1962. [62] Holland (J. H.). { Adaptation in Natural and Arti cial Systems. { The University of Michigan Press, Ann Arbor, 1975. [63] Hop eld (J.). { Neural networks and physical systems with emergent collective computational abilities. In : Proceeding of the National Academy of Science. 1969. BIBLIOGRAPHIE 151 [64] Jackson (J. R.). { An extension of Johnson's results on job lot scheduling. Naval Research Logistic Quarterly, vol. 3, n 3, 1956. [65] Johnson (S. M.). { Optimal two and three stage production schedules. Naval research Logistic Quarterly, vol. 1, n 1, 1954. [66] Karsiti (M. N.), Cruz (J. B.) et Mulligan (J. H.). { Simulation studies of multilevel dynamic job shop scheduling using heuristic dispatching rules. Journal of Manufacturing Systems, vol. 11, n 5, 1992. [67] Kirkpatrick (S.). { Optimization by simulated annealing: Quantitative studies. Journal of Statistical Physics, vol. 34, n 5, 1984. [68] Kirkpatrick (S.), Gelatt (C. D.) et Vecchi (M. P.). { Optimization by simulated annealing. Science, no220, 1983. [69] Kubiak (W.), Sethi (S.) et Sriskandarajah (C.). { An ecient algorithm for a job-shop problem. { 1993. Communication Personnelle. [70] Lageweg (B. J.), Lenstra (J. K.) et Rinnooy Kan (A. H. G.). { Job-shop scheduling by implicit enumeration. Management Science, vol. 24, n 4, 1977. [71] Lawler (E. L.), Lenstra (J. K.), Rinnooy Kan (A. H. G.) et Shmoys (D.) (edite par). { The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization. { John Wiley & Sons, 1987. [72] Lawler (E. L.) et Wood (D. E.). { Branch and bound methods : A survey. Operations Research, vol. 14, 1966. [73] Le Gall (A.) et Roubellat (F.). { Caracterisation d'un ensemble d'ordonnancements avec contraintes de ressources de type cumulatif. APII, vol. 26, 1992. [74] Lemonias (H.). { Ordonnancement d'Atelier a T^aches : Une Approche par Decomposition. { These de PhD, Institut National Polytechnique de Grenoble, 1991. 152 BIBLIOGRAPHIE [75] Liao (C. J.) et You (C. T.). { An improved formulation for the job-shop scheduling problem. Journal of Operational Research Society, vol. 43, n 11, 1992. [76] Lopez (P.), Erschler (J.) et Esquirol (P.). { Ordonnancement de t^aches sous contraintes : une approche energetique. APII, vol. 26, 1992. [77] Lourenco (H. R.). { Local optimization and the job-shop scheduling problem. { 1994. Communication personnelle. [78] Manne (A. S.). { On the job-shop scheduling problem. Operations Research, vol. 8, 1960. [79] Matsuo (H.), Suh (C. J.) et Sullivan (R. S.). { A Controlled Search Simulated Annealing Method for the General Job-Shop Scheduling Problem. { Rapport technique n 03-44-88, Graduate School of Business, University of Texas, Austin, 1988. [80] Mc Culloch (W. S.) et Pitts (W. H.). { A logical calculus of ideas immanent in nervous activity. Bulletin of Mathematical Biophysics, vol. 3, 1943. [81] Mitten (L. G.). { Branch and bound methods : General formulation and properties. Operations Research, vol. 18, 1970. [82] Muth (J. F.) et Thompson (G. L.). { Industrial Scheduling. { Prentice Hall, Englewood Cli s, New Jersey, 1963. [83] Nakano (R.) et Yamada (T.). { Conventional genetic algorithm for job-shop problems. In : Conference on Genetic Algorithms. San Diego, California, 1991. [84] Panwalkar (S. S.) et Iskander (W.). { A survey of scheduling rules. Operations Research, vol. 25, n 1, 1977. [85] Papadimitriou (C. H.) et Steiglitz (K.). { Combinatorial Optimization : Algorithms and Complexity. { Prentice Hall, Englewood Cli s, N.J., 1982. BIBLIOGRAPHIE 153 [86] Penz (B.) et Dupont (L.). { New heuristics for the job-shop problem. In : International Conference on industrial Engineering and Production Management. Mons, Belgique, 1993. [87] Pinson (E.). { Le Probleme de Job-Shop. { These de PhD, Universite Pierre et Marie Curie, 1988. [88] Portmann (M.-C.). { Methodes de decomposition spatiale et temporelle en ordonnancement de la production. APII, vol. 22, 1988. [89] Potts (C. N.). { Analysis of a linear programming heuristic for scheduling unrelated parallel machines. Discrete Applied Mathematics, vol. 10, 1985. [90] Queyranne (M.). { Structure of a simple scheduling polyhedron. Mathematical Programming, vol. 58, 1993. [91] Queyranne (M.) et Wang (Y.). { Single-machine scheduling polyhedra with precedence constraints. Mathematics of Operations Research, vol. 16, n 1, 1991. [92] Raman (N.) et Talbot (F. B.). { The job-shop tardiness problem : A decomposition approach. European Journal of Operational Research, vol. 69, 1993. [93] Ramasesh (R.). { Dynamic job-shop scheduling : A survey of simulation research. International Journal of Management Science, vol. 18, n 1, 1990. [94] Rechenberg (I.). { Optimierung technischer Systeme nach Prinzipien der biologischen Evolution. { Problemata, 1973, FrommannHolzboog edition. [95] Rinnooy Kan (A. H. G.). { Machine Scheduling Problem : Classi cation, Complexity and Computations. { Nyho , 1976. [96] Rogers (R. V.) et White (K. P.). { Algebraic, mathematical programming and network models of the deterministic job-shop scheduling problem. IEEE Transactions on Systems, Man, and Cybernetics, vol. 21, n 3, 1991. 154 BIBLIOGRAPHIE [97] Rosenblatt (F.). { Perceptron simulation experiment. In : Proceeding of the IRE. 1960. [98] Roy (B.) et Sussman (B.). { Les Problemes d'ordonnancement avec contraintes disjonctives. { Rapport technique n D. S. 9, SEMA, Paris, France, 1964. [99] Schwefel (H.-P.). { Numerische Optimierung von ComputerModellen mittels der Evolutionsstrategie. { Birkhauser Verlag, 1977. [100] Silver (E. A.), Vidal (V. V.) et de Werra (D.). { A tutorial on heuristic methods. European Journal of Operational Research, vol. 5, 1980. [101] Strusevitch (V. A.). { Two machine super-shop scheduling problem. Journal of Operational Research Society, vol. 42, n 6, 1991. [102] Tahboub (K. K.) et Odrey (N. G.). { A dioid algebra approach for modeling the job-shop scheduling problem. { 1994. Communication Personnelle. [103] Taillard (E.). { Parallel taboo search techniques for the job-shop scheduling problem. ORSA Journal on Computing, vol. 6, n 2, 1994. [104] Van Laarhoven (P. J. M.). { Theoretical and Computational Aspects of Simulated Annealing. { These de PhD, Erasmus University, Rotterdam, 1988. [105] Van Laarhoven (P. J. M.) et Aarts (E. H. L.). { Simulated Annealing : Theory and Applications. { Reidel, Dordrecht, The Netherlands, 1987. [106] Van Laarhoven (P. J. M.), Aarts (E. H. L.) et Lenstra (J. K.). { Job-shop scheduling by simulated annealing. Operations Research, vol. 40, n 1, 1992. [107] Vancheeswaran (R.) et Townsend (M. A.). { Two-stage heuristic procedure for scheduling job-shops. Journal of Manufacturing Systems, vol. 12, n 4, 1993. BIBLIOGRAPHIE 155 [108] Vepsalainen (A. P. J.) et Morton (T. E.). { Priority rules for job shops with weighted tardiness costs. Management Science, vol. 33, n 8, 1987. [109] Vig (M. M.) et Dooley (K. J.). { Dynamic rules for due-date assignment. International Journal of Production Research, vol. 29, n 7, 1991. [110] Wagner (H. M.). { An integer linear programming model for machine scheduling. Naval Research Logistic Quarterly, vol. 6, 1959. [111] Wein (L. M.) et B. (C. P.). { A broader view of the job-shop scheduling problem. Management Science, vol. 38, n 7, 1992. [112] Wein (L. M.) et Ou (J.). { The impact of processing time knowledge on dynamic job-shop scheduling. Management Science, vol. 37, n 8, 1991. [113] Werner (F.) et Winkler (A.). { Insertion techniques for the heuristic solution of the job-shop problem. { 1991. Communication Personnelle. [114] Widmer (M.). { Job shop scheduling with tooling constraints: a tabu search approach. Journal of the Operational Research Society, vol. 42, n 1, 1991. [115] Zhang (C. S.), Yan (P. F.) et Chang (T.). { Solving job-shop scheduling problem with priority using neural network. { 1991. Communication personnelle. [116] Zhou (D. N.), Cherkassky (V.), Baldwin (T. R.) et Olson (D. E.). { A neural network approach to job-shop scheduling. IEEE Transactions on Neural Networks, vol. 2, n 1, 1991.
© Copyright 2021 DropDoc