ETAT DE L’ART DES PROBLEMES D’ORDONNANCEMENT D’ATELIER AVEC FLEXIBILITE DE RESSOURCE

Télécharger le fichier pdf d’un mémoire de fin d’études

Problèmes d’atelier sans flexibilité des ressources

Les problèmes d’ordonnancement sans flexibilité des ressources s’intéressent à ordonnancer des tâches interdépendantes. Dans ce genre de problème, seules les contraintes temporelles et les contraintes de capacité des ressources sont considérées : cela revient à supposer que le problème d’affectation est résolu.
Une solution au problème d’ordonnancement sans flexibilité des ressources consiste à associer à chaque tâche une date de début et/ou de fin d’exécution qui respecte les contraintes temporelles et les contraintes de limitation de capacité des ressources du problème.
Ce problème peut être divisé suivant les caractéristiques décrites ci-après en : flow shop, job shop et open shop.
Ordonnancement d’ateliers en flow shop:
En flow shop, tous les jobs visitent les machines dans le même ordre, avec des durées opératoires pouvant être différentes. Les machines sont disponibles sur tout l’horizon de planification et elles ne peuvent exécuter qu’une seule opération à la fois. Par ailleurs, une opération ne peut s’exécuter que sur une seule machine à la fois.
En pratique, ce cas est fréquemment rencontré ; citons l’exemple d’une chaîne de fabrication ou de montage.
Ordonnancement d’ateliers en job shop:
Dans un job shop, chaque travail passe sur les machines dans un ordre fixé, mais, à la différence du flow shop, cet ordre peut être différent pour chaque travail. Chaque job possède donc une gamme spécifique.
Il s’agit ici de déterminer les dates de passage sur différentes ressources des jobs ayant des gammes différentes dans l’atelier. Ces jobs partageant des ressources communes, des conflits sont susceptibles de survenir, résultant des croisements des flux. Dans son expression la plus simple, le problème est donc de gérer ces conflits tout en respectant les contraintes données, et en optimisant les objectifs poursuivis.
Ordonnancement d’ateliers en open shop:
C’est un problème sans contrainte d’enchaînement prédéfinie, où chaque produit à fabriquer doit subir diverses opérations sur des machines, mais dans un ordre totalement libre. Cela est rarement généralisé dans un atelier manufacturier, mais peut survenir ponctuellement.
La résolution de ce sous-problème supplémentaire (déterminer la séquence d’opérations de chaque job) complique la production d’un ordonnancement, mais offre des degrés de liberté intéressants.
Il est à noter que la notion de « gamme linéaire », très ancrée au niveau des bureaux des méthodes des entreprises, mais aussi la rigidité des outils de gestion des données techniques, a souvent fait que, lorsque des permutations entre opérations étaient possibles, un choix plus ou moins arbitraire était réalisé lors de l’élaboration de la gamme.

Problèmes d’atelier avec flexibilité des ressources

La nécessité d’être toujours plus réactives a conduit les entreprises à rechercher des nouveaux degrés de liberté. Une partie de ces degrés de liberté réside dans l’élaboration d’alternatives, comme la duplication des exemplaires des machines, pour effectuer une ou plusieurs opérations. Ces problèmes présentent alors une difficulté supplémentaire par rapport aux problèmes sans flexibilité des ressources dans la mesure où les ressources sont en exemplaires multiples. Ainsi, la machine nécessaire pour exécuter une opération n’est pas connue d’avance, mais doit être sélectionnée parmi un ensemble donné. Ces machines peuvent être de trois types à savoir, des machines identiques notées P , des machines uniformes, notées Q, où les durées opératoires dépendent de leurs vitesses, et des machines non-reliées (ou indépendantes) notées R où leurs vitesses varient d’une tâche à une autre.
Dans ce genre de problème, il faut considérer simultanément les contraintes temporelles, les contraintes de limitation de capacité des ressources et les contraintes d’affectation.
Les problèmes avec flexibilité de ressources les plus étudiés dans la littérature sont : les problèmes à machines parallèles, le flow shop hybride et le job shop flexible présentés ci-dessous.
Ordonnancement d’ateliers en machines parallèles:
Dans ce cas, on dispose d’un ensemble de machines pour réaliser les travaux. Les travaux se composent d’une seule opération et un travail exige une seule machine. L’ordonnancement s’effectue en deux phases : la première phase consiste à affecter les travaux aux machines et la deuxième phase consiste à établir la séquence de réalisation sur chaque machine.
Ordonnancement d’ateliers en flow shop hybride:
Le « flow shop hybride » à k étages est un flow shop pour lequel chaque travail doit subir k opérations différentes telles que chaque opération doit se faire sur une unique machine choisie parmi un ensemble, appelé étage, de machines parallèles dédiées à cette opération. Une machine ne peut appartenir qu’à un seul étage.
Ordonnancement d’ateliers en job shop flexible:
Un job shop flexible est un problème à cheminements multiples, mais qui présente une difficulté supplémentaire dans la mesure où chaque opération nécessite une machine pour être réalisée et cette machine doit être choisie dans un ensemble défini a priori.

Complexité des problèmes d’ordonnancement

La théorie de la complexité s’intéresse à l’étude formelle de la difficulté théorique intrinsèque des problèmes en informatique ou d’un problème par rapport à un autre et de l’analyse de la complexité des programmes et des algorithmes. Concrètement, on cherche à savoir si le problème étudié est plutôt « facile » ou plutôt « difficile » à résoudre en se basant sur une estimation (théorique) des temps de calcul et des besoins en mémoire informatique.
Les problèmes d’ordonnancement sont des problèmes d’optimisation combinatoire. Pour résoudre un problème d’ordonnancement, nous devons toujours chercher à établir sa complexité, car cela détermine la nature de l’algorithme à mettre en œuvre. Si le problème étudié appartient à la classe P, nous savons d’avance qu’un algorithme polynomial existe pour le résoudre. Dans le cas contraire, si le problème est NP-difficile, deux approches sont possibles. La première est de proposer un algorithme approché, donc une heuristique, qui calcule en temps polynomial une solution s’approchant au mieux de la solution optimale. Une alternative est de proposer un algorithme qui calcule la solution optimale du problème, mais pour lequel la complexité dans le pire des cas est exponentielle. Dans ce cas, le défi est de concevoir un algorithme qui peut résoudre en temps acceptable les problèmes de la plus grande taille possible.
Les problèmes d’ordonnancement sont spécifiés selon une notation à trois champs α|β|γ [Graham et al., 1979] où α précise l’environnement machines ou le système à ordonnancer, β précise les caractéristiques des opérations ou les contraintes et γ précise le(s) critère(s) à optimiser.
Pour calculer la complexité des problèmes d’ordonnancement, plusieurs résultats traditionnels existent dans la littérature. Ainsi, on rappelle la complexité des problèmes de base de l’ordonnancement de type α Z avec Z un critère donné.
En considérant les problèmes à une seule machine, la minimisation de la fonction fmax = max ( fi (Ci )) (avec fi une fonction croissante de la date de fin i=1,…,n d’exécution) est un problème qui se résout polynomialement. En conséquence, les problèmes de type 1 Z avec Z ∈ {C max , Fmax ,Tmax , Lmax } le sont également. Notons que toute séquence est optimale pour le problème
1 Cmax . Les problèmes de type 1 C w et 1 C peuvent être résolus polynomialement [Lawler et al., 1989] et de même pour le problème 1di U [Pinedo, 1995]. Seuls les problèmes 1di T et 1di U w sont NP-difficiles au sens faible et 1di T w au sens fort [Lawler et al., 1989]. En conséquence, tous les
problèmes de type α di T w sont NP-difficiles au sens fort, quelle que soit la valeur de α .

Problèmes de flow shop hybride

Cas du flow shop hybride à deux étages

Le problème de flow shop hybride à deux étages est un cas particulier du problème de flow shop hybride. Il peut être décrit comme suit. Soient un ensemble J = {1,2,…, n} de n jobs, un ensemble M = {M1, M 2 ,…, M m } de m machines, deux étages E1 et E2 dans lesquels chaque étage i contient mi (i = 1,2) machines parallèles { M i,1 , M i,2 ,…, M i,m } (voir Fig.3). Chaque job j ∈ J doit passer sur une machine du premier étage, sans interruption, durant une durée p1, j . Ensuite, le job j passe sur une machine du deuxième étage, sans interruption, pendant une durée p2, j . Le but est de trouver un ordonnancement admissible minimisant la date de fin d’exécution totale (makespan) de l’ensemble des opérations.
En se basant sur la notation à trois champs proposée dans [Hoogeveen et al., 1996], le problème est noté F2(P)||Cmax. Comme cela a été vu au chapitre précédent, ce problème est NP-difficile au sens fort dans le cas où max(m1, m2)>1 [Gupta, 1988]. Notons que dans les travaux dont nous avons connaissance, aucun auteur ne traite du problème de Flow Shop Hybride à étages avec machines quelconques F2(R)||Cmax.

Problèmes de job shop flexible

Un job shop flexible est une extension du problème à cheminements multiples classique. En effet, la résolution de ce problème présente une difficulté supplémentaire dans la mesure où chaque opération nécessite une machine pour être réalisée et cette machine doit être choisie dans un ensemble défini a priori.
Deux cas sont traités dans la littérature : le cas où les machines sont identiques (les durées opératoires sont les mêmes pour toutes les machines pouvant exécuter un job donné) et le cas où les ressources sont non-reliées ; les durées opératoires dépendent de la ressource choisie.
Ce problème peut être décrit comme suit. On dispose d’un ensemble J = {1,2,…,n} de n jobs et un ensemble M = {1,2,…,m} de m machines. Chaque job i est composé de ni opérations{Oi,1,Oi,2,…,Oi,ni }. L’opération j du job i est notée Oi, j . Chaque opération Oi, j doit passer sur une unique machine k ni sélectionnée parmi un ensemble Mi, j ⊆ M ( ∀i, I M i, j peut être différente de j=1 l’ensemble vide) pendant une durée pik, j de temps et ce, sans interruption.
Une machine ne peut exécuter qu’une seule opération à la fois. Pour une opération Oi, j , sa date de début est notée Si, j , sa date de fin Ci, j et sa date de début au plus tôt est ri, j . Une date de début au plus tôt d’un job est notée ri et sa date de fin est Ci . Ce problème est noté JMPM||Cmax. Plusieurs méthodes ont été développées pour résoudre ce type de problème mono- et/ou multi-critère, à savoir des méthodes heuristiques ou exactes. Ces dernières approches ont été proposées pour la résolution des instances de petite taille ou pour des cas particuliers.
La première étude de ce type de problème est celle proposée dans [Brucker et Schlie, 1990]. Les auteurs se sont basés sur une approche géométrique pour développer un algorithme polynomial pour la résolution optimale de ce problème dans le cas de deux jobs JMPM n = 2 C max .
On trouve dans [Jurisch, 1992] une procédure par séparation et évaluation ainsi que des heuristiques pour les problèmes d’ordonnancement d’atelier avec machines multi-usages (plus connue sous le nom « shop scheduling problems with multi-purpose machine »). Les ressources considérées ont une durée identique quelle que soit la ressource. L’auteur a également proposé des bornes inférieures pour le problème.
Dans [Brandimarte, 1993], l’auteur a utilisé une approche hiérarchique pour la résolution du job shop flexible. Il a commencé par la résolution du sous-problème d’affectation de ressources en utilisant des règles de priorité. Les durées opératoires sont variables en fonction des ressources. Une fois ce problème d’affectation résolu, le problème devient un job shop classique. Pour le résoudre, Brandimarte a utilisé une méthode de recherche Tabou. Les expérimentations ont été menées sur des exemples générés aléatoirement. L’heuristique a de plus été appliquée à des problèmes de job shop flexible avec minimisation des retards pondérés.
Dans [Hurink et al., 1994], les auteurs ont proposé une extension du graphe disjonctif pour développer une heuristique de recherche tabou ainsi que deux voisinages permettant de générer une solution voisine basés sur la notion de bloc. Un bloc est une succession (au moins deux) d’opérations critiques sur une même ressource. En conservant l’admissibilité de l’ordonnancement, le premier voisinage consiste à déplacer une opération d’un bloc avant (ou après) toutes les opérations du bloc. Le second voisinage consiste à changer l’affectation d’une opération du bloc. Il a été démontré que le deuxième voisinage était connexe, ce qui est une propriété importante pour la convergence des méthodes de recherche locale. Les auteurs proposent, dans le même cadre, une heuristique basée sur les techniques d’insertion afin de construire un ordonnancement.
Des benchmarks ont été générés aléatoirement et les solutions trouvées ont été comparées avec les bornes inférieures proposées dans [Jurisch, 1992]. Les machines considérées sont identiques. Cette approche est caractérisée par le fait que l’affectation des machines aux opérations et le séquencement sur les machines sont traités séparément.
Dans [Dauzère-Pérès et Paulli, 1994], les auteurs se sont intéressés au problème de job shop flexible avec minimisation du makespan et ont proposé des conditions suffisantes permettant d’assurer que le déplacement des opérations n’augmente pas la valeur du makespan. Basée sur ces conditions, une méthode tabou a été développée pour résoudre le problème du job shop une fois l’affectation des machines aux opérations fixée. Les machines considérées sont identiques. Les résultats trouvés par leur méthode sont comparables à ceux présentés dans [Hurink et al., 1994].
Une approche en deux phases a été proposée dans [Paulli, 1995] pour ordonnancer un système de production manufacturier dans lequel le nombre de jobs pouvant être exécutés simultanément est limité. Ainsi, si l’atelier est plein, un nouveau job ne peut être commencé que si l’un des jobs en cours dans l’atelier est terminé. L’objectif est de minimiser le makespan. Les machines considérées sont identiques. Dans la première phase, les machines sont affectées aux opérations en utilisant des règles de priorité, et le problème devient alors un job shop classique. La deuxième phase consiste à représenter le problème résultant par un graphe disjonctif utilisé pour développer une heuristique de recherche tabou permettant de trouver les meilleures séquences d’entrée. Les deux phases sont répétées et une opération appartenant au chemin critique est à chaque fois réaffectée.
Une autre méthode de recherche tabou a été proposée dans [Barnes et Chambers, 1996]. Les auteurs considèrent deux types de voisinages. Le premier consiste à permuter deux opérations critiques adjacentes et le deuxième consiste à réaffecter une opération critique sur toutes les machines pouvant l’exécuter. Ils ont considéré trois exemples de problème de type job shop classique FT10 de [Fisher et Thompson, 1963], LA24 et LA40 de [Lawrence, 1984] et ils ont fait une extension de ces derniers afin d’avoir des problèmes flexibles. Les machines considérées sont identiques. Les résultatsdonnent une amélioration du makespan d’environ 10% par rapport aux résultats donnés dans [Chambers et al., 1996].
La méthode proposée dans [Dauzère-Pérès et Paulli, 1997] repose sur une résolution intégrée du problème d’affectation et de séquencement. Basé sur une extension du graphe disjonctif, le voisinage ainsi construit est intégré pour l’exploration de l’espace des solutions dans la recherche tabou. Les résultats obtenus sont meilleurs que ceux donnés dans [Hurink et al., 1994] et dans [Dauzère-Pérès et Paulli, 1994].
Dans [Mastrolilli et Gambardella, 2000], les auteurs proposent une autre approche intégrée basée sur une recherche tabou. Les machines considérées sont identiques. Cette approche utilise le graphe disjonctif pour la représentation des solutions, ainsi que deux types de voisinages (V1 et V2). Ces voisinages sont basés sur le déplacement d’une opération dans le graphe disjonctif. Les auteurs ont démontré la connexité d’un seul type de voisinage développé (V2). La contribution de cette étude est la diminution de la taille du voisinage. Cette approche améliore les solutions proposées dans les études précédentes. Les expérimentations ont montré que, malgré l’absence de connexité du voisinage V1, ce dernier donne de meilleurs résultats que V2 grâce à sa vitesse d’exécution. Cette méthode Tabou est parmi celles fournissant actuellement les meilleurs résultats sur les instances connues de job shop flexible.
Un algorithme génétique a été également proposé pour résoudre le problème de job shop flexible dans [Kacem et al. , 2002]. Cet algorithme a été testé pour la résolution du problème mono et multicritère. L’objectif de cette méthode est d’optimiser conjointement deux critères classiques : le makespan et la charge des ressources. La première étape de cette approche permet de résoudre le problème d’affectation de ressources et de construire un schéma d’affectation. La deuxième étape est une approche évolutionnaire contrôlée par le modèle des affectations généré dans la première étape. Dans cette approche, les auteurs appliquent des manipulations génétiques avancées pour améliorer la qualité des solutions.
Dans sa thèse, Mati (2002) s’est intéressé à l’étude de la complexité des problèmes d’ordonnancement d’un job shop flexible à deux jobs. Il a montré que le problème de minimisation de toute fonction objectif régulière est NP-difficile au sens faible. Il a ensuite proposé un algorithme polynomial basé sur une approche géométrique pour résoudre le problème et ceci pour n’importe quelle fonction objectif régulière.
Une approche multi-agents a été introduite dans [Ennigrou et Ghedira, 2005] pour la résolution du job shop flexible en se basant également sur une méthode de recherche Tabou. Le modèle proposé est composé de trois classes d’agents : les agents Job, les agents Ressource responsables de la satisfaction des contraintes et l’agent Interface contenant le noyau de la recherche tabou. Les auteurs ont utilisé deux types de voisinage : la permutation de deux opérations critiques adjacentes exécutées par la même ressource et la réaffectation d’une opération critique sur une autre ressource. Les expérimentations ont été menées sur les problèmes donnés dans [Brandimarte, 1993 ; Hurink et al., 1994].
Xia et Wu (2005) ont développé une autre approche hiérarchique pour la résolution des problèmes de type job shop flexible multicritères. Ils ont utilisé une méthode SPO (Swarm Particle Optimization) pour la résolution du sous-problème d’affectation et le recuit simulé pour la résolution du sous-problème d’ordonnancement. L’objectif de cette méthode hybride est de minimiser le makespan, la charge des ressources et la charge des ressources critiques. Les résultats obtenus par cette approche ont montré que l’algorithme proposé est une approche viable et efficace pour le FJSP multi-critère, particulièrement pour des problèmes de grande taille.
Dans leur travail, Zhang et Gen (2005) ont proposé un algorithme génétique pour la résolution du job shop flexible multicritère. L’objectif est de minimiser le makespan, la charge maximale et la somme des charges de ressources. La méthode a été évaluée via les instances utilisées dans [Kacem et al., 2002] et a donné de meilleures solutions.
Fattahi et al. (2007) ont proposé un modèle mathématique pour le problème de job shop flexible et une hybridation de deux méthodes : une méthode de recherche tabou (TS) et un recuit simulé (SA). Sur la base de ces deux méthodes, les auteurs ont développé six algorithmes différents basés sur la combinaison des deux méthodes et des deux approches: intégrée et hiérarchique. Les expérimentations ont permis de comparer les algorithmes entre eux. Il en résulte qu’en général, l’approche hiérarchique donne les meilleures solutions et ce en appliquant la méthode de recherche tabou pour le problème d’affectation et le recuit simulé pour le problème de séquencement.

Recherche à divergence limitée (LDS)

La méthode LDS s’appuie sur des heuristiques de parcours d’une arborescence. L’objectif principal de cette méthode est d’explorer uniquement une partie de l’espace de recherche en se basant sur des heuristiques pour l’ordre de sélection des variables et pour leur instanciation. Ces heuristiques sont mises au point en vue de guider la recherche vers des régions prometteuses en se basant sur les caractéristiques des problèmes à résoudre ; en ordonnancement, on considère notamment : les dates de disponibilité des tâches, les dates de disponibilité des machines, les durées opératoires au cours de la recherche, etc.
L’idée de la méthode est de calculer, en premier lieu, le chemin de l’arborescence recommandé par l’heuristique, ce qui constitue le chemin à 0 divergence, suivi de tous les chemins qui divergent de l’heuristique en un seul point de décision, ce qui constitue les chemins à une seule divergence, suivi de tous les chemins qui ont 2 divergences et ainsi de suite. Cela revient à dégrader peu à peu les choix des heuristiques dans le but d’améliorer à chaque itération la qualité de l’instanciation pour la rendre admissible (dans le cadre de la résolution des CSP). En autorisant suffisamment de divergences par rapport aux heuristiques de parcours, cette méthode est complète dans le sens où elle revient à parcourir toute l’arborescence.
Une telle stratégie d’exploration se justifie par le fait que les chemins à une seule divergence d’une bonne heuristique sont les plus susceptibles de contenir une solution par rapport à ceux ayant deux divergences. Elle considère alors les chemins de l’arborescence variant peu par rapport au chemin recommandé par l’heuristique, ceux-ci étant les plus probables de contenir des solutions admissibles.
De ce fait, la méthode LDS exprime l’idée d’un parcours incrémental de l’arborescence avec un nombre limité de divergences. Si elle ne trouve pas de solution pour k divergences, le nombre de divergences augmente et la recherche est alors recommencée avec un nombre de divergences égal à k +1. Si k atteint le nombre maximal de divergences possible, alors tous les chemins de l’arborescence sont explorés, ce qui prouve l’absence de solution et rend la méthode complète. LDS peut aussi produire un algorithme incomplet en fixant k < kmax , ce qui permet un développement partiel de l’arbre, restreint aux zones que l’heuristique estime les plus prometteuses. En pratique, la méthode LDS sera d’un très grand intérêt si elle réussit à trouver une solution de bonne qualité avec un nombre minimum de divergences.
Les premiers travaux sur LDS ont uniquement considéré des problèmes à variables binaires. Par convention, les auteurs supposent que l’heuristique privilégie l’exploration du nœud fils gauche. À tout nœud fils gauche correspond alors une valeur de divergence de 0 et à tout nœud fils droit correspond une divergence de valeur 1 de l’heuristique. Le nombre maximum de divergences nécessaires pour l’exploration complète de cette arborescence binaire est égal au nombre de variables du problème.
Considérons une arborescence binaire à trois variables. La trace de la méthode LDS après 4 itérations est donnée par la figure 5. Cette illustration est issue de [Harvey et Ginsberg, 1995]. Sur cette figure, le nombre indiqué en dessous de chaque feuille, à la première ligne, correspond au nombre de divergences qui ont permis d’atteindre cette feuille et à la deuxième ligne, le nombre correspond à l’ordre de visite des feuilles de l’arbre.

Méthode de recherche par profondeur d’abord intercalée (IDFS)

Messeguer et Walsh (1998) ont proposé la méthode Interleaved Depth-First Search (IDFS) qui cherche à explorer des niveaux parallèles le plus haut dans l’arborescence.
En effet, elle parcourt plusieurs sous-arborescences en parallèle (dites actives) sur certains niveaux de l’arbre (dit parallèle). Elle peut être vue comme un parcours en parallèle d’une arborescence en profondeur d’abord (DFS).
IDFS traverse le sous-arbre courant en profondeur jusqu’à ce qu’il atteigne une feuille non encore explorée. S’il atteint une solution optimale, la recherche s’arrête, sinon l’état du sous-arbre courant est sauvegardé pour être réutilisé par la suite.

Méthode à divergence limitée par profondeur d’abord (DBDFS)

La méthode à divergence limitée par profondeur d’abord (Discrepancy-Bounded Depth First Search, DBDFS) est une autre amélioration de LDS introduite dans [Beck et al., 2000]. Cette méthode, comme son nom l’indique, donne la priorité à la profondeur par rapport à la divergence. Elle peut être considérée comme une combinaison entre DDS et la méthode classique de recherche en profondeur (DFS : Depth First Search).
Ainsi, au lieu de se restreindre à la visite de branches ayant exactement le même nombre de divergences lors de chaque itération de LDS, on examinera les branches ayant leur nombre de divergences appartenant à un intervalle donné qui dépend du numéro de l’itération. Le but est de limiter la redondance dans l’ordre de visite des branches.
Ainsi, la stratégie d’exploration de l’espace de recherche est un peu différente de celle donnée par DDS et par LDS. La figure 11 montre la différence. Le nombre noté en dessous de chaque feuille correspond à l’ordre d’exploration.

Méthode par montée de divergences (CDS)

Contrairement aux méthodes à base de divergences que l’on vient de présenter et qui ont été conçues pour la recherche de solutions admissibles, la méthode par montée de divergences (Climbing Discrepancy Search, CDS) est une méthode d’optimisation. La méthode CDS est définie comme une méthode de recherche locale basée sur une adaptation de la notion de divergence afin de trouver une bonne solution pour les problèmes d’optimisation combinatoire [Milano et Roli, 2002].
CDS commence l’exploration à partir d’une solution initiale suggérée par une heuristique donnée. Les nœuds ayant une divergence égale à 1 sont explorés d’abord, puis ceux ayant la divergence 2, et ainsi de suite. Quand une feuille améliorant la fonction objectif est obtenue, la solution de référence est mise à jour, le nombre de divergences est remis à zéro et le processus d’exploration se déclenche de nouveau (voir algorithme 8).

Exemple illustratif de ILDS, DDS, DDS tronquée et CDS

Les méthodes ILDS, DDS, DDS tronquée et CDS étant importantes pour la lecture de la suite de ce document, nous illustrons leurs stratégies d’exploration plus en détail.
Considérons un problème se composant de trois variables de décision x1 , x2 et x3 . Nous donnons la priorité au nœud fils gauche et nous adoptons un mode de comptage binaire des divergences. Une instanciation complète est obtenue après l’instanciation des trois variables. Initialement, l’instanciation de référence S ref est obtenue sans aucune divergence ; on notera par la suite le nombre de divergences pour une instanciation donnée de la manière suivante : [ x1 , x2 , x3 ] = [0,0,0]. Les instanciations à une divergence par rapport à la solution S ref sont celles ayant un des chiffres [ x1 , x2 , x3 ] égal à 1 (ex. [0,0,1]). Pour représenter les divergences graphiquement, nous associons à une instanciation définie par l’heuristique un cercle noir et à une divergence un cercle creux. Ainsi, S ref sera représenté par ●●● et une instanciation présentant une divergence au niveau de la troisième variable par ●●○.
La figure 13 illustre les arbres de recherche obtenus en utilisant ILDS (a), DDS (b), DDS tronquée (c) et CDS (d). Pour les trois méthodes, la recherche commence à partir d’une instanciation de référence S ref obtenue avec [ x1 , x2 , x3 ] = [0,0,0] ou plutôt ●●●.
La figure 13(a) montre toutes les branches générées par la méthode LDS et qui correspondent aux instanciations obtenues à partir de ●●●. Les numéros en dessous des feuilles indiquent le numéro de l’itération de la méthode LDS ayant permis de découvrir cette instanciation.
Dans la figure 13(b), les feuilles obtenues par la méthode DDS sont les mêmes que celles obtenues par la méthode LDS mais elles sont découvertes dans un ordre différent puisqu’à chaque itération de la méthode, la profondeur à laquelle on peut effectuer des divergences est limitée. La figures 13(c) montre la différence entre la méthode DDS et la méthode DDS tronquée à la profondeur d=1 (seules les variables de profondeur inférieur ou égale à 1 sont considérées).
La figure 13(d) explique la stratégie de recherche de la méthode CDS et exprime l’ordre de génération des branches. Pour cette méthode d’optimisation, l’instanciation initiale S ref est une solution et l’on peut évaluer
la fonction objectif associée à cette solution. On note f ref cette valeur de la fonction objectif. La première solution à 1 divergence de S ref a une valeur f1 . Puisque f1 est plus grande que f ref , une deuxième solution d’une valeur f2 est générée. Son coût est comparé par rapport à f ref et ce processus est répété jusqu’à ce qu’une solution d’une valeur f 4 ≤ fref soit obtenue. Ainsi, cette solution devient la nouvelle solution de référence, f 4 la nouvelle valeur de la fonction objectif et le nombre de divergences est remis à zéro. Par conséquent, la prochaine solution (ayant la valeur f5 ) est seulement à une divergence de cette nouvelle solution de référence.

Table des matières

CHAPITRE 1. PRESENTATION DES PROBLEMES D’ORDONNANCEMENT
1.1. DEFINITION
1.2. CONCEPTS DE BASE
1.2.1. Les tâches
1.2.2. Les ressources
1.2.3. Variables de décision et contraintes
1.2.4. Les objectifs de l’ordonnancement
1.3. ORDONNANCEMENT D’ATELIER
1.3.1. Problèmes d’atelier sans flexibilité des ressources
1.3.2. Problèmes d’atelier avec flexibilité des ressources
1.4. COMPLEXITE DES PROBLEMES D’ORDONNANCEMENT
1.5. CONCLUSION
CHAPITRE 2. ETAT DE L’ART DES PROBLEMES D’ORDONNANCEMENT D’ATELIER AVEC FLEXIBILITE DE RESSOURCES
2.1. DEFINITION
2.2. PROBLEMES DE FLOW SHOP HYBRIDE
2.2.1. Cas du flow fhop hybride à deux étages
2.2.2. Cas du flow shop hybride général
2.3. PROBLEMES DE JOB SHOP FLEXIBLE
2.4. CONCLUSION
CHAPITRE 3. RECHERCHE A BASE DE DIVERGENCES
3.1. INTRODUCTION
3.2. RECHERCHE A DIVERGENCE LIMITEE (LDS)
3.3. METHODE A DIVERGENCE LIMITEE AMELIOREE (ILDS)
3.4. METHODE A DIVERGENCE LIMITEE PAR LA PROFONDEUR (DDS)
3.5. METHODE DE RECHERCHE PAR PROFONDEUR D’ABORD INTERCALEE (IDFS)
3.6. METHODE A DIVERGENCE LIMITEE PAR PROFONDEUR D’ABORD (DBDFS)
3.7. METHODE A DIVERGENCE LIMITEE INVERSEE (RLDS)
3.8. METHODE A DIVERGENCE PONDEREE PAR SA PROFONDEUR (DWDS)
3.9. METHODE PAR MONTEE DE DIVERGENCES (CDS)
3.10. METHODE A DIVERGENCES LIMITEES PAR APPRENTISSAGE (YIELDS)
3.11. EXEMPLE ILLUSTRATIF DE ILDS, DDS, DDS TRONQUEE ET CDS
3.12. CONCLUSION
CHAPITRE 4. ADAPTATION DES METHODES A BASE DE DIVERGENCES POUR LE FLOW SHOP HYBRIDE
4.1. INTRODUCTION
4.2. UNE NOUVELLE METHODE ARBORESCENTE A BASE DE DIVERGENCES ET SON APPLICATION AU FLOW SHOP HYBRIDE
4.2.1. Méthode proposée : Climbing Depth-bounded Discrepancy Search (CDDS)
4.2.2. Variables de décision du problème de Flow Shop Hybride
4.2.3. Heuristiques sur l’ordre d’instanciation des variables
4.2.4. Notion de divergence pour le Flow Shop Hybride
4.2.5. Stratégies d’exploration
4.2.6. Exemple illustratif
4.3. EXPERIMENTATIONS
4.3.1. Comparaison sur les jeux-tests élaborés par Vignier
4.3.2. Comparaison sur les jeux-tests élaborés par Néron et Carlier
4.4. ADAPTATION DE LA METHODE DEVELOPPEE AUX PROBLEMES DE FLOW SHOP HYBRIDE A DEUX ETAGES
4.4.1. Heuristiques sur l’ordre d’instanciation des variables
4.4.2. Borne inférieure
4.4.3. Expérimentations
4.5. CONCLUSION SUR LE PROBLEME DE FLOW SHOP HYBRIDE
CHAPITRE 5. ADAPTATION DE LA METHODE CDDS POUR LE JOB SHOP FLEXIBLE…
5.1. INTRODUCTION
5.2. ADAPTATION DE CDDS POUR LE PROBLEME CONSIDERE
5.2.1. Heuristiques sur l’ordre d’instanciation des variables
5.2.2. Notion de divergence pour le job shop flexible
5.2.3. Stratégies d’exploration
5.3. EXPERIMENTATIONS
5.3.1. Comparaison sur les jeux-test de Brandimarte (1993)
5.3.2. Comparaison sur les jeux-test de Barnes et Chambers (1996)
5.3.3. Comparaison sur les jeux-test de Dauzère-Pérès et Paulli (1997)
5.3.4. Comparaison sur les jeux-test de Hurink (1994)
5.4. CONCLUSION SUR LE PROBLEME DE JOB SHOP FLEXIBLE
CONCLUSIONS ET PERSPECTIVES
BIBLIOGRAPHIE

Télécharger le rapport complet