A best-local position procedure-based heuristic for the two-dimensional layout problem

Mhand Hifi*, CERMSEM
Rym M'Hallah**, Institut Supérieur de Gestion de Sousse

Résumé. Nous étudions dans cet article, le problème de placement de pièces de forme (ir)régulière. Etant donné une bande de hauteur limitée et un ensemble de pièces de forme (ir)régulière. Le but est de trouver le meilleur placement de l'ensemble de ces pièces de sorte à minimiser la longueur à utiliser. Nous proposons une nouvelle méthode approchée qui s'appuie principalement sur une recherche locale. Nous commençons par présenter la première approche dite constructive en s'appuyant sur le balayage d'un meilleur voisinage. Par la suite, nous proposons une hybridation combinant l'approche constructive et la stratégie réactive. L'algorithme qui en résulte produit des résultats très satisfaisants en utilisant un temps d'exécution très satisfaisant. Les deux approches ont été testées sur un ensemble d'instances de la littérature, et montraient qu'elles produisaient des résultats meilleurs que les résultats publiés dans la littérature.
Mots clés : Problème de découpe et du placement, recherche locale, optimisation, heuristiques.

Abstract. The two-dimensional layout (TDL) optimization problem consists of finding the minimal length layout of a set of shapes or pieces on a stock sheet of finite width and infinite length. In this paper, we solve the TDL problem using a new approximate solution method. First, we describe a constructive method based mainly upon the best-local position search (called BLP). Next, we enhance the BLP method by introducing a dynamic re-ordering procedurefor re-starting the BLP approach. The resulting algorithm (called RBLP) yields satisfactory results within reasonable computational time. Extensive computational testing on problem instances taken from the literature shows the effectiveness of the proposed approach.
Keywords : Cutting and packing, best-local position, optimization, heuristics.

JEL Classification : C44, C61, C63.

*Membre extérieur du PRiSM-CNRS UMR 8636, Université de Versailles Saint Quentin en Yvelines, 45 Avenue des Etats-Unis, 78035 Versailles cedex, France.
**Department of Qualitative Methods, Institut Supérieur de Gestion de Sousse, B.P. 763, Sousse 4000, Tunisia and Research Institution for Computer Science and Telecommunications, Parc Technologique des Communications, Route de Raoued km 3.5, 2083 Ariana, Tunisia