Approximate strip generation algorithms for constrained two-dimensional two-staged
cutting stock problems
Mhand Hifi*,
CERMSEM
et PRiSM
Résumé.
Dans cet article, nous proposons plusieurs approches pour la résolution du problème de découpe
contraint à deux niveaux. Ces approches s'appuient principalement sur une stratégie de
construction de bandes. Une première approche consiste à combiner la résolution de problèmes de
knapsack unidimensionnels bornés et une procédure de placement par le meilleur d'abord. Par la
suite, nous généralisons cette approches pour construire un algorithme plus performant. Finalement,
nous introduisons une nouvelle stratégie, dite Hill-Climbing, pour réduire le temps d'exécution du
deuxième algorithme. La performance de chaque algorithme proposé est évaluée sur un ensemble
d'instances de la littérature.
Mots clés :
Algorithme approché, problème de découpe, programmation dynamique, knapsack unidimensionnel borné,
optimisation.
Abstract.
We given a rectangular stock plate Swith length Land width W, and a set
of nsmall rectangular pieces to cut from S. Each piece's type
i, i = 1,...,n,is characterized by a length li, a width
wi,a profit (or weight) ciand an upper demand value
bi. The upper demand value indicates the maximum number of pieces of type
iwhich can be cut. The Two-Dimensional Cutting(TDC) is the problem of
determining a cutting patternof the stock rectangle maximizing the sum of the profits
of the cut pieces. In this paper, we consider the classical variant of the TDC in which the
maximum number of cuts allowed to obtain each piece, in the final cutting pattern, is fixed to
2. We refer to this problem as two-staged TDC, namely 2TDC. For the 2TDC problem we propose
several approximate algorithms which are mainly based upon strip generation
procedure.The performance of these algorithms is evaluated on problem instances extracted
from the litterature.
Keywords :
Approximate algorithm, cutting problems, dynamic programming, single constrained knapsack problem,
optimization.
JEL Classification :
C44, C61, C63.
*PRiSM-CNRS, Université de Versailles-Saint-Quentin en Yvelines, 45 avenue des Etats-Unis, 78035 Versailles Cedex, France.
