Modélisation et résolution du TLBP/B-P

Modélisation et résolution du TLBP/B-P

Dans ce chapitre, nous proposons d’abord une formulation générique. Puis, nous décri- vons le schéma global adopté pour une approche basée sur la programmation par contraintes (PPC) en décrivant les règles de propagation qui sont appliquées ainsi que les règles de dominance. Ensuite, deux bornes inférieures sont fournies, l’une est basée sur une relaxa- tion linéaire et la seconde sur une relaxation à un problème particulier de set partitioning. Nous proposons également un modèle basé sur la programmation linéaire en nombres entiers que nous améliorons par la suite en reformulant certaines contraintes. Enfin, nous suggé- rons des techniques efficaces pour réduire le nombre de variables binaires et augmenter les performances du modèle linéaire. Dans cette partie du travail, nous proposons deux bornes inférieures pour le TLBP/B-P : la première est une relaxation à un problème particulier de set partitioning [BDG+04], quant à la seconde, elle est obtenue grâce à une relaxation linéaire d’un des modèles linéaires en nombres entiers que nous proposons dans la suite. Nous décrivons ensuite le schéma global de l’approche PPC, celui-ci est basée essentielle- ment sur une méthode de type séparation et évaluation combinée à une règle de dominance. Nous décrivons le modèle utilisé pour cette approche, ensuite nous indiquons la politique de branchement utilisée pour la séparation et l’évaluation.

Dans cette section, nous proposons une borne inférieure basée sur une relaxation du TLBP/B-P à un problème de set partitioning [BDG+04]. Pour ce faire, nous calculons d’abord une borne inférieure sur le nombre des stations et ensuite une estimation du coût engendré par les blocs sélectionnés. inférieure sur le nombre de stations. Ensuite, nous proposons une relaxation à un problème de partitionnement particulier afin de déduire une borne sur le second terme de l’objectif, à savoir : le coût des blocs sélectionnés. Cette borne est une adaptation de celle proposée dans les travaux de [DI05] où les auteurs se sont intéressés au problème mixte (de type TLBP/B-M, voir la classification dans la figure 3.1). Pour obtenir une borne inférieure sur le nombre de stations nous exploitons d’abord les contraintes d’exclusion entre les blocs avec les contraintes de précédence entre les opérations. Puis, nous renforçons la valeur de la borne en prenant en compte également les contraintes sur le nombre maximum de blocs par station. Dans un premier temps, nous construisons un graphe non orienté pour les blocs à partir du graphe de précédence Gor. Nous notons ce graphe Gbr = (B, Ebr). Plus précisément, le graphe Gbr est obtenu après une transformation de Gor, en déduisant les contraintes de précédence entre les blocs à partir de celles qui existent entre les opérations. En particulier, chaque arc qui lie deux opérations est transformé en une ou plusieurs arêtes qui lient les blocs qui les contiennent. Ainsi, s’il existe un arc entre les sommets i et j dans Gor, sa correspondance, dans Gbr, est telle que, tout bloc qui contient l’opération i est lié par une arête à tout bloc qui contient l’opération j. De plus, nous appliquons la fermeture transitive du graphe Gbr ainsi obtenu1. Ainsi, si ∃(b, b′) ∈ Ebr et ∃(b′, b′′) ∈ Ebr alors nous ajoutons l’arête (b, b′′) dans Ebr.

Ensuite, nous fusionnons les deux graphes Gex et Gbr pour obtenir le graphe GB. Ce graphe contient ainsi l’ensemble des contraintes d’exclusion et toutes les précédences reliant les blocs. Puis, nous construisons le complément de ce graphe que nous notons GB, tel que GB contient toutes les arêtes qui existent dans le graphe complet2 et qui n’existe pas dans le graphe GB. Nous notons GB ), k = 1, . . . , l, toute composante connexe du graphe GB. Il est clair que deux blocs qui appartiennent à deux composantes distinctes ne peuvent pas être affectés à la même station. Ainsi, le nombre de composantes connexes de GB fournit une borne inférieure sur le nombre de stations. De plus, le nombre de stations nécessaires pour les blocs de chaque composante connexe ne peut pas être inférieure à la cardinalité de l’ensemble indépendant maximum de la composante [Aig95]. Pour obtenir une borne inférieure sur le coût des blocs, il faut résoudre à l’optimum le problème de set partitioning. Pour ce faire, il est nécessaire de trouver le meilleur sous- ensemble β ⊆ B pour exécuter les opérations non encore affectées, c’est-à-dire N′ = N − {i | i ∈ b, b ∈ B}, tel que B ⊂ B est l’ensemble des blocs qui ont déjà été affectés.