La réussite de la méthode de B&B

REVUE DE LA LITTÉRATURE

Le problème d’aménagement d’usines a été étudié intensivement dans la littérature. Pour les aperçus les plus récents, le lecteur est référé à Kusiak et Heragu et Mel/er et Gau. Nous rappelons que le problème d’aménagement d’usines est un problème d’optimisation combinatoire difficile, et que le problème d’affectation quadratique, où l’optimisation est reportée à un ensemble d’endroits possibles de département, est NP-difficile aussi. Donc, des méthodes exactes de solution sont seulement faisables pour des petits problèmes ou des problèmes considérablement limités.

Pour cette raison, la plupart des méthodologies de solution dans la littérature sont basées sur des heuristiques. En général, les problèmes de disposition de service sont trouvés dans la littérature avec l’arrangement des départements rectangulaires. Cependant, il y a des applications dans lesquelles un arrangement orthogonal des départements n’est pas nécessairement une condition (par exemple : la planification du tableau de bord d’un avion, une ville ou un voisinage, une disposition des bâtiments de bureau et les circuits intégrés). D’autre part, le problème statique de 1′ aménagement « SFLP : static facility laya ut problem » est un problème bien étudié et la littérature remonte à presque cinq décennies. Récemment, une emphase particulière a été remise sur l’utilisation des heuristiques pour la résolution de ce problème d’optimisation combinatoire. D’autre part, cette littérature est aussi la base pour résoudre le problème dynamique d’aménagement d’usines qui a commencé au milieu des années 80. Ainsi, la littérature de  » SFLP  » fut d’abord publiée et quelques années plus tard, ce fut la littérature de  » DFLP  » qui fut passée en revue.

Généralement, les méthodologies pour le problème statique d’aménagement d’usines « SFLP » peuvent être classifiées en algorithmes Exacts, donnent des solutions optimales et algorithmes heuristiques. Des algorithmes l’algorithme par séparation et évaluation (Branch and Bound) et les plants sécants sont employés pour résoudre le SFLP. Les algorithmes par séparation et évaluation ont été développés et mis en application par Gilmore (1962), Lawler (1963), et Kaku et Thompson (1986), pour ne mentionner que quelques-uns. Bazaraa et Sherali (1980) ont développé un algorithme utilisant des plans sécants (Cutting plane) et, plus tard, Burkard et Bonninger (1983) ont également développé des algorithmes (Cutting plane). Pour un examen des algorithmes exacts pour le « SFLP « , voir Kusiak et le Heragu (1987). Montreuil (1990) a présenté une formulation de programmation de nombre entier pour le « SFLP ». De même, Heragu et Kusiak (1991) ont présenté deux nouveaux modèles pour le  » SFLP » :

o Modèle continu ;

o Modèle linéaire en nombres entiers.

Les algorithmes par séparation et évaluation Branch and Bound Selon le terme anglo-saxon, un algorithme par séparation et évaluation est également appelé Branch et Bound (B&B). C’est une méthode générique de résolution de problèmes d’optimisation et plus particulièrement d’optimisation combinatoire ou discrète. Elle a été introduite pour la première fois par A. H Land et A. G. Drigo (1960) qui l’avaient décrite comme une méthode de construction d’un arbre de décision. Elle permet de résoudre les problèmes en nombres entiers dans plusieurs logiciels commerciaux.

Dans les méthodes par séparation et évaluation, la séparation permet d’obtenir une méthode générique pour énumérer toutes les solutions tandis que l’évaluation évite l’énumération systématique de toutes les solutions. Si tout le nombre de solutions faisables pour le problème à résoudre est petit, nous pouvons étudier chaque solution faisable individuellement et choisir l’optimum en les comparant l’un par rapport à l’autre. Cependant, dans la plupart des situations réelles, une telle méthode d’énumération totale est impraticable, car le nombre de solutions s’avère être très grand.

L’algorithme B&B fournit une méthode pour rechercher une solution optimale en conduisant une énumération qui n’est pas une énumération totale. L’ensemble de solutions faisables est divisé en plusieurs sous-ensembles simples. Dans chaque étape, un sous-ensemble prometteur est choisi et un effort est fait pour trouver la meilleure solution pour lui. Si la solution obtenue est la meilleure jusqu’ici, alors nous mettons à jour la limite. Autrement, nous devons encore diviser ce sous-ensemble en deux sous-ensembles simples ou plus et que le même processus soit répété jusqu’à ce que la meilleure solution soit obtenue. L’exécution de la branche et de la méthode attachée est facilitée par le calcul d’une limite dans chaque sous-ensemble de la partition produite.

Ces limites sont employées en choisissant les sous-ensembles prometteurs dans la recherche pour l’optimum et pour éliminer quelques sous-ensembles qui ne peuvent probablement pas contenir la solution faisable optimale. Dans les problèmes de minimisation, des limites inférieures peuvent être employées pour décider si nous exécutons l’embranchement à un certain noeud dans l’arbre de recherche. Si nous avons une limite inférieure pour un sous-ensemble qui est supérieur ou égal à la limite supérieure courante, il n’y a pas d’avantage à l’embranchement dans ce noeud.

La réussite de la méthode de B&B dépend de la stratégie d’embranchement, de la stratégie de recherche et de la qualité de la limite inférieure (dans la maximisation) ou des limites supérieures (dans la minimisation) produites. Dans cette technique de recherche, un sous-ensemble choisi parmi la liste active est exploré jusqu’à ce qu’une solution faisable améliorée ou une violation de la limite inférieure soit trouvée. Un autre sous-ensemble est choisi si la solution n’est pas faisable. Nous relions alors le noeud parent dans la branche où l’exploration n’a pas été faite. Des limites inférieures peuvent être obtenues à chaque noeud en employant une méthode heuristique. Dans la méthode de B&B, une recherche alternative dans laquelle le sous-ensemble avec la plus basse limite (LB) choisie pour s’embrancher est la meilleure. Des algorithmes de B&B ont été développés la première fois par Gilmore (1962) et Lawler (1963) pour résoudre le QAP. Ces deux algorithmes affectent un service simple à un endroit simple et calculent toutes les solutions potentielles ainsi que les limites inférieures.

Différent de Gilmore (1962) et de Lawler (1963); Land (1963), Cravett et Plyter (1966) ont proposé l’algorithme par séparation et évaluation pour affecter des paires d’équipements aux paires d’endroits. Pierce et Crowston (1971) ont proposé un algorithme qui procède sur la base de l’exclusion étape par étape des paires de tâches d’une solution aux problèmes basés sur le concept de la réduction carrée de forces. Burkard (1973) a développé un algorithme exact pour résoudre le QAP. Dans cet algorithme, une matrice est transformée en une autre matrice de sorte que la matrice résultante ait seulement les éléments non négatifs, et que dans chaque rangée et colonne, il y ait au moins un élément zéro. Dans l’algorithme de Branch and Bound développé par Bazaraa (1975), un arrangement partiel à chaque étape est construit et une limite pour tous les accomplissements possibles de cet arrangement partiel existant est calculée. La disposition partielle existante est alors développée en assignant un nouveau service à condition que la tâche choisie ait un meilleur avantage comparé à la limite courante. Si la tâche a pour conséquence un avantage inférieur, une autre recherche est considérée. Si c’est le cas, une nouvelle tâche différente doit être trouvée.

Le processus est suivi jusqu’à ce que l’arrangement complet soit obtenu. Bazzara et Elshafei (1979) ont proposé l’algorithme par séparation et évaluation (Branch and Bound) basé sur l’attribution étape par étape des équipements simples aux endroits inoccupés pour le QAP.

Le recuit simulé

Le recuit simulé est une méta-heuristique inspirée d’un processus utilisé en métallurgie. Ce processus alterne des cycles de refroidissement lent et de réchauffage (recuit) qui tendent à minimiser l’énergie du matériau. Elle est aujourd’hui utilisée en optimisation pour trouver les extrema d’une fonction. Elle a été mise au point par trois chercheurs de la société IBM S. Kirkpatrick, C.D. Gelatt et MP. Vecchi, en 1983, et indépendamment par V Cerny en 1985. Afin de transposer les propriétés physiques aux problèmes d’optimisation, on établit l’analogie présentée dans le Tableau 2.1. L’algorithme du recuit simulé s’appuie sur deux résultats de la physique statistique.

D’une part, lorsque l’équilibre thermodynamique est atteint à une température donnée (T), la probabilité pour un système physique de posséder une énergie donnée (E) est proportionnelle au facteur de Boltzmann : e D’autre part, pour simuler l’évolution d’un système physique vers son équilibre thermodynamique à une température donnée (T), on peut utiliser l’ algorithme de Metropolis partant d’une configuration donnée (dans notre cas un placement), on fait subir au système une modification élémentaire (échange deux composants). Si cette transformation a pour effet de diminuer la fonction objective (ou énergie ) du système, elle est acceptée; si elle provoque, au contraire, une augmentation !::.E de la fonction -DE objective, elle est tout de même acceptée, mais avec la probabilité de e r (en pratique cette condition est réalisée de la manière suivante : on tire au hasard un nombre réel compris entre 0 et 1, et on accepte la configuration dégradant de ilE la fonction – DE objective, si le nombre tiré est inférieur ou égal à e T ). L’itération se poursuit tant que l’énergie du système diminue. Lorsque l’énergie reste stationnaire, on diminue un peu la température et l’on reprend le processus de décroissance de l’énergie. On arrête lorsque les diminutions de température restent inefficaces.

Table des matières

RÉSUMÉ
REMERCIEMENTS
TABLE DES MATIÉRES
LISTE DES FIGURES
LISTE DES TABLEAUX
INTRODUCTION GÉNÉRALE
Chapitre 1 Généralités sur l’aménagement
1.1 INTRODUCTION
1.2 PROBLÈME DE L’AMÉNAGEMENT
1.3 CLASSIFICATION DE PROBLÈMES D’ AMÈNAGEMENT
1.4 LES PARAMÈTRES DE L’AMÈNAAGEMENT
1.4 .1 Calcul des distances
1.4.2 Le flux et le modèle d’acheminement
1.5 LE PROBLÈME D’ AMÈNAGEMENT STATIQUE
1.5.1 Modélisation comme un probléme d’affectation quadratique
1.5.2 Présentation du problème d’affectation quadratique
1.5.3 Application principales
1.6 CONCLUSION
Chapitre 2 Revue de la littérature
2.1 INTRODUCTION
2.2 ALGORITHMES EXACTES
2.2.1 les algorithmes par séparation et évolution
2.2.2 Les plants sécants
2.2.3 Algorithmes grapiques
2.2.4 Algorithmes de construction
2.3 LES DIFFÉRENTS TYPES DE MÉT AHEURISTIQUES
2.3.1 Les approches de recherche locale
2.3 .1.1 Le ricuit simulé
2.3.1.2 La recherhce avec tabous
2.3.1.3 Plafond dégradé
2.3.2 Les approches évolutives
2.3.2.1 Les algorithmes génètiques
2.3 .2.2 Algorithme à colonies de fourmis
2.4 CONCLUSION
Chapitre 3 Méthodologie
3.1 INTRODUCTION
3.2 IDÉES DE BASE
3.3 MÉTHODE DE RÉSOLUTION
3.4 FONCTIONNEMENT DE L’ALGORITHME PROPOSÉ
3.5 EXEMPLE DE DÉROULEMENT DE L’ALGORITHME
3.6 CONCLUSION
Chapitre 4 Expérimentation et Résultats
4.1 INTRODUCTION
4.2 INSTANCES CONSIDÉRÉES
4.3 RÉGLAGE DES PARAMÉTRES
4.4 RÉSULTATS NUMÉRIQUES
4.5 CONCLUSION
Chapitre 5 Conclusion
BIBLIOGRAPHIE
ANNEXE

Télécharger le rapport complet