This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via HighWire Citing Articles via Google Scholar Google Scholar Articles by Alvarez-Valdes, R. Articles by Parajón, A. Search for Related Content

GRASP and Path Relinking for the Two-Dimensional Two-Stage Cutting-Stock Problem

Departamento de Estadística e I.O., Universidad de Valencia, Dr. Moliner, 50, 46100 Burjassot, Valencia, Spain
Departamento de Estadística e I.O., Universidad de Valencia, Dr. Moliner, 50, 46100 Burjassot, Valencia, Spain
Departamento de Estadística e I.O., Universidad de Valencia, Dr. Moliner, 50, 46100 Burjassot, Valencia, Spain
Departamento de Matemáticas, Universidad Nacional Autónoma de Nicaragua, UNAN-Managua, ENEL Central 2 Km Sur, Managua, Nicaragua
ramon.alvarez{at}uv.es
rafael.marti{at}uv.es
jose.tamarit{at}uv.es
ramon.a.parajon{at}uv.es

We develop a greedy randomized adaptive search procedure (GRASP) for the constrained two-dimensional two-stage cutting-stock problem. This is a special cutting problem in which the cut is performed in two phases. In the first phase, the stock rectangle is slit down its width into different vertical strips and in the second phase, each of these strips is processed to obtain the final pieces. We propose two different algorithms based on GRASP methodology. One is "piece-oriented" while the other is "strip-oriented." Both procedures are fast and provide solutions of different structures to this cutting problem. We also propose a path-relinking algorithm, which operates on a set of elite solutions obtained with both GRASP methods, to search for improved outcomes. We perform extensive computational experiments with a wide range of instances, first to study the effect of changes in critical search parameters, and then to compare the efficiency of alternative solution procedures. The experiments establish the effectiveness of our procedure in relation to approaches previously identified as best, especially in large-scale instances.

Key words: cutting; packing; heuristics; GRASP; path relinking
History: received June 2004; revised July 2005; accepted November 2005.

This article has been cited by other articles:

				M. Hifi, R. M'Hallah, and T. Saadi Algorithms for the Constrained Two-Staged Two-Dimensional Cutting Problem INFORMS Journal on Computing, January 1, 2008; 20(2): 212 - 221. [Abstract] [PDF]