An exact algorithm for constrained two-dimensional two-staged cutting stock problems

Mhand Hifi*, LaRIA et CERMSEM
Rym M'Hallah**, ISG - Sousse

Résumé. Une instance du problème de découpe à deux dimensions est caractérisée par une plaque rectangulaire S de dimensions L x W, d'un ensemble de n types de pièces rectangulaires de dimensions l_i x w_i , i = 1,..., n. A chaque type de pièce i est associé un profit c_i (ou poids) et une borne supérieure b_i (la demande). Dans cet article, nous étudions le problème de découpe contraint à deux niveaux. Il s'agit d'une variante classique du problème de découpe, où chaque pièce appartenant à un plan de découpe est obtenue en utilisant au plus une découpe verticale/horizontale et une autre découpe horizontale/verticale. Nous proposons un algorithme exact du type "construction-rassemblement". Nous introduisons des nouvelles bornes inférieures et supérieures pour le problème, et nous donnons une nouvelle stratégie d'élagage pour l'élimination des constructions symétriques. L'algorithme proposé est évalué sur un ensemble d'instances et comparé aux meilleurs algorithmes de la littérature.
Mots-clés : Algorithme approché, problème de découpe, programmation dynamique, knapsack uni-dimensionnel, optimisation.

Abstract. The Constrained Two-Dimensional Cutting (C_TDC) problem consists of determining a cutting pattern of a set of n small rectangular piece types on a rectangular stock plate S with length L and width W, as to maximize the sum of the profits of the pieces to be cut. Each piece type i = 1,..., n, is characterized by a length l_i, a width w_i, a profit (or weight) c_i and an upper demand value b_i. The upper demand value is the maximum number of pieces of type i wich can be cut on S. In this paper, we study the two-staged C_TDC problem, noted C_2TDC. It is a classical variant of the C_TDC where each piece is produced, in the final cutting pattern, by at most two cuts. We solve the C_2TDC problem using an exact algorithm that is mainly based upon a bottom-up strategy. We introduce new lower and upper bounds and propose new strategies that eliminate several duplicate patterns. We evaluate the performance of the proposed exact algorithm on problem instances extracted from the literature, and compare it to an existing exact algorithm.
Keywords : Approximate algorithm, cutting problems, dynamic programming, single constrained knapsack problem, optimization.

JEL Classification : C44, C61, C63.

*LaRIA, Laboratoire de Recherche en Informatique d'Amiens, 5 rue du Moulin Neuf, 80000 Amiens.
**Department of Quantitative Methods, ISG de Sousse, B.P. 763, Sousse 4000, Tunisia