Le test de circuits est de nos jours un véritable défi industriel. Un ou plusieurs testeurs externes
envoient au composant à tester des données (les vecteurs de test) et analysent sa réponse. Ce processus
pose plusieurs problèmes d'optimisation combinatoire originaux et intéressants. Celui qui nous
intéresse ici est le regroupement des mémoires en lots d'une puissance maximale fixée. Ceux-ci seront
testés de manière séquentielle de sorte à réduire le temps de test global.
Ce problème correspond à une version non classique du Bin-Packing en deux dimensions : le test d'une
mémoire est associé à un rectangle de longueur le temps de test, et de hauteur la puissance développée.
La hauteur d'une Bin est la somme des hauteurs des rectangles qui la composent. Une hauteur maximale
est fixée. La longueur d'une Bin est la longueur maximale d'un rectangle. L'objectif est de minimiser la
somme des longueurs des Bins.
Ce problème inclus le Bin-Packing classique : il est donc NP-difficile. Une borne inférieure simple du
temps de test global est obtenue en utilisant la programmation linéaire. Elle permet de montrer que
l'algorithme Next Fit decreasing (avec l'ordre décroissant sur les longueurs des Bins) a un ratio de
performance de 2.
Dans cet exposé, nous démontrons que la borne inférieure utilisée précédemment pouvait être deux
fois plus petite que l'optimum. Nous introduisons alors une généralisation de la fonction de poids de
Dosa utilisée en Bin-Packing classique. Elle nous permet de montrer un ratio de performance proche de
1.7 pour une extension du First-Fit avec ordre décroissant sur la largeur d'abord, puis la hauteur. Ces
travaux sont complétés par des expérimentations sur plusieurs instances issues à la fois de benchmarks
académiques et industriels.
