Phase expérimentale pour le TLBP/B-P

Dans ce chapitre, nous rapportons les résultats des tests expérimentaux que nous avons effectués pour le problème TLBP/B-P. L’objectif de cette étude est triple, il s’agit d’abord de montrer l’apport des différentes améliorations en particulier celle de la réduction du nombre de variables. Ensuite, nous comparons les différents modèles, et enfin nous étudions l’influence des paramètres du problème. Tous les calculs ont été effectués sur une station de travail de type HP Xeon, avec un processeur de 3,6 GHz et une mémoire vive de 2 Go. Les programmes sont écrits en langage C++ et le compilateur utilisé est Visual Studio version 6.0. Nous utilisons les logiciels ILOG Cplex et ILOG Solver qui sont des librairies programmées en C++ proposées par ILOG pour la résolution de modèles linéaires en nombres entiers, en variables mixte ou encore de modèles quadratiques. Pour résoudre un PLNE, Cplex met en œuvre un algorithme de Branch & Cut, c’est-à-dire une procédure par séparation et évaluation intégrant plusieurs types de coupes telles que les coupes de cliques et les coupes de sac à dos. Quant à Solver c’est une PSE qui intègre des algorithmes de filtrage associés à certaine contraintes du type allDiff pour imposer aux variables de prendre des valeurs distinctes.Nous utilisons les logiciels ILOG Cplex et ILOG Solver qui sont des librairies programmées en C++ proposées par ILOG pour la résolution de modèles linéaires en nombres entiers, en variables mixte ou encore de modèles quadratiques. Pour résoudre un PLNE, Cplex met en œuvre un algorithme de Branch & Cut, c’est-à-dire une procédure par séparation et évaluation intégrant plusieurs types de coupes telles que les coupes de cliques et les coupes de sac à dos. Quant à Solver c’est une PSE qui intègre des algorithmes de filtrage associés à certaine contraintes du type allDiff pour imposer aux variables de prendre des valeurs distinctes.

Pour pouvoir faire des conclusions statistiques, nous générons aléatoirement un grand nombre des jeux de données. Pour générer ces instances, nous fixons les paramètres tels que les densités des graphes de contraintes et les cardinalités des ensembles N et B. Nous y inté- grons l’ensemble des pré-traitements décrits précédemment (voir la sous-section 4.3.1). Nous vérifions également la cohérence des paramètres entre eux. Par exemple, si nous générons un graphe de précédence dont le chemin le plus long est égale à une valeur k + 1, il n’est pas possible d’imposer une borne supérieure sur le nombre de stations m0 qui soit inférieure1 Il est à souligner que nous avons généré chacune des instances de manière à ce que les densité des différents graphes de contraintes ainsi que leur structure soit les plus proches de celles des instances industrielles dont nous disposons. Par exemple, les contraintes de précédence dans l’usinage (contrairement à l’assemblage) ont une forme de graphe série- parallèle, c’est-à-dire plusieurs séquences d’opérations sont en parallèle telles qu’une séquence possible peut être : perçage d’ébauche, filetage et finition. De façon générale, nous testons 7 familles d’instances que nous décrivons dans le tableau 6.2. Pour chaque famille, nous serons amenés à générer différentes sous-familles en fonction de l’étude effectuée que nous décrirons plus en détails aux sous-sections correspondantes.

Il est à souligner que nous avons généré chacune des instances de manière à ce que les densité des différents graphes de contraintes ainsi que leur structure soit les plus proches de celles des instances industrielles dont nous disposons. Par exemple, les contraintes de précédence dans l’usinage (contrairement à l’assemblage) ont une forme de graphe série- parallèle, c’est-à-dire plusieurs séquences d’opérations sont en parallèle telles qu’une séquence possible peut être : perçage d’ébauche, filetage et finition. De façon générale, nous testons 7 familles d’instances que nous décrivons dans le tableau 6.2. Pour chaque famille, nous serons amenés à générer différentes sous-familles en fonction de l’étude effectuée que nous décrirons plus en détails aux sous-sections correspondantes. Nous rapportons les résultats des expérimentations globalement sous deux formes. La première forme est classique, elle correspond à un nuage de points représentant chacun le temps de résolution d’une instance donnée appartenant à une des familles. Nous utilisons cette représentation lorsque le nombre d’instances testées le permet. Pour l’ensemble des 150 instances testées, le modèle linéaire orienté blocs (5.17)-(5.25) est plus performant. En effet, quand le modèle orienté blocs résout l’ensemble des instances en près d’une seconde, le modèle PPC peut aller jusqu’à 350 sec (voir figures 6.2 et 6.3). De plus, le modèle PPC n’a pas permis de résoudre certaines instances ayant plus de 20 opérations (sous la limite de 2h de temps). Nous signalons toutefois les difficultés rencontrées lors de l’implémentation du modèle PPC qui sont essentiellement dues au manque de documentation sur ILOG Solver d’une part et à l’instabilité du logiciel lui-même lors de la résolution de nombreuses instances d’autre part.