The strip cutting/packing problem : incremental substrip algorithms-based heuristics
Mhand Hifi*,
CERMSEM et PRiSM
Résumé.
Le problème de découpe (placement) sur bande consiste à découper un certain nombre de
pièces sur une bande de hauter fixée et de longueur illimitée. Chaque pièce
considérée est limitée par une borne supérieure limitant le nombre d'apparitions de
pièce dans la bande. Dans ce papier, nous proposons différents algorithmes approchés pour la
résolution du problème de découpe sur bande. Ce problème est,
généralement, réduit sous forme d'une série de problèmes de découpe
avec contraintes et résolu par l'utilisation de la programmation dynamique combinée
par une recherche arborescente. Par ailleurs nous utilisons la notion
d'incrémentalité afin d'accélérer le processus de recherche. Les
performances des algorithmes proposés sont évaluées sur un grand nombre d'instances de la
littérature ainsi que d'autres instances de la littérature ainsi que d'autres instances de grande
taille générées aléatoirement. Un des algorithmes donnait des résultats
très encourageants.
Mots clés :
Optimisation combinatoire, problèmes de découpe/placement, programmation dynamique, heuristiques,
"Hill-Climbing".
Abstract.
The strip cutting problem consists of cutting a large strip with a fixed-width and unlimited length into smaller
subrectangles, without violating the demand values imposed on each subrectangle. Computer science, industrial
engineering, logistics, manufacturing, management, production processes are among obvious fields of applications.
In this paper we present some algorithms for solving approximately large-scale strip cutting/packing problems.
The strip cutting problem is reduced to a series of single constrained cutting stock problem and solved
by using dynamic programming techniques and a tree search procedure. The performance of the
proposed algorithms are evaluated on a set of medium and large size problem instances. These algorithms are
parallelizable and this is one of their important feature.
Keywords :
Combinatorial optimization, cutting and packing problems, dynamic programming, heuristics, Hill-Climbing.
*PRiSM, URA 1525, CNRS, Université de Versailles Saint-Quentin-en-Yvelines, 45 Avenue des Etats-Unis, 78035 Versailles Cedex.