A column generation based heuristic for two-dimensional cutting stock problems with variable dimensions

In the Two-Dimensional Multiple Stock Size Cutting Stock Problem with Variable Dimensions (2D MSSCSP-VD) one wishes to fulfill the demand for a set of two-dimensional items out of a set of stock sheets, each of which has dimensions that may vary in some given range, at minimum cost. Research is scarce on Cutting Stock problems involving variable dimensions so we propose a heuristic to tackle this problem based on existing column generation and dynamic programming strategies. To evaluate its flexibility and the quality of its solutions we test it on a wide range of instances both from the literature and designed by us. The computational experiments show that not only does the approach produce solutions of excellent quality, but also that it is flexible and outperforms other heuristics for related problems that can be reduced to the 2D MSSCSP-VD, such as the 2D MSSCSP and 2D SSSCSP.

• Autores: Ramírez Ramos, Mauricio Adolfo
• Fecha de publicación: 2010
• Institución: Universidad de los Andes
• Repositorio: Séneca: repositorio Uniandes
• Idioma: eng
• OAI Identifier: oai:repositorio.uniandes.edu.co:1992/11284
• Acceso en línea: http://hdl.handle.net/1992/11284
• Palabra clave: Administración de la producción; Control de la producción; Programación dinámica; Ingeniería
• Rights: openAccess
• License: https://repositorio.uniandes.edu.co/static/pdf/aceptacion_uso_es.pdf