A simulation-optimization approach for the 2D irregular cutting stock problem with free rotation

This paper focuses on the study of the two-dimensional cutting or packing problem of irregular polygons with free rotation that must be organized within a set of identical plates with fixed dimensions. The main objective is to minimize the number of plates that can fit a specific demand of objects. Given the constraint of non-overlapping, the possibility of free rotations and the irregular shape of the objects, this is a combinatorial problem with NP-Hard complexity. A column generation procedure was proposed, in which the master problem will be in charge of selecting the subset of plates that will compose the solution, while the auxiliary problem will create each of the proposed plates to be given to the master problem as columns. For this, the auxiliary problem will use a two phased procedure with a constructive algorithm and a local search enhanced with swapping and insertion operators, made using Unity engine. To test the proposed algorithms, known instances for the cutting stock problem were selected. The solutions and computational times achieved were compared by benchmarking with the available work in the literature, obtaining satisfactory results. Further work will include the sequential use of the shown algorithms that produce good performance in order to produce a more specialized algorithm.

• Autores: Casas Cortés, Andrés Gabriel de las
• Fecha de publicación: 2020
• Institución: Universidad de los Andes
• Repositorio: Séneca: repositorio Uniandes
• Idioma: eng
• OAI Identifier: oai:repositorio.uniandes.edu.co:1992/43972
• Acceso en línea: http://hdl.handle.net/1992/43972
• Palabra clave: Programación de la producción - Investigaciones; Optimización combinatoria - Investigaciones; Métodos de simulación - Investigaciones; Sistemas integrados de fabricación por computador - Investigaciones; Ingeniería
• Rights: openAccess
• License: https://repositorio.uniandes.edu.co/static/pdf/aceptacion_uso_es.pdf