Constrained two-dimensional cutting stock problems : the NMVB approach and the duplicate test revisited

Van-Dat Cung*, PRiSM
Mhand Hifi*, CERMSEM et PRiSM
Bertrand Le Cung*, PRiSM

Résumé. Dans cette note, nous proposons une révision de la duplication, notée D3 dans Cung et al.[1], pour la résolution du problème de découpe contraint à deux dimensions. Nous introduisons une relation d'ordre ainsi qu'une symétrie qui permettent d'améliorer sensiblement l'algorithme exact. Finalement, nous testons la validité de l'approche sur des instances prisent de Cung et al.[1].
Mots clés : Problème de découpe, algorithme exact, duplication.

Abstract. In this note, we revisit the duplicate pattern, called Type D3 in Cung et al.[1], in order to solve the constrained two-dimensional cutting stock problem. We use an order-insertion relation and a symetic strategy for enhancing the exact algorithm. Finally, we evaluate the performance of the revised algorithm on some problem instances already used in Cung et al.[1].
Keywords : Cutting problem, exact algorithm, duplicate.

JEL Classification : C44, C61, C63.

*PRiSM, Université de Versailles-Saint-Quentin-en-Yvelines, 45 avenue des Etats-Unis, 78035 Versailles Cedex, France