Evaluación del rendimiento computacional de la generación de columnas y técnicas de generar y resolver para el problema de corte unidimensional de stock
Autores: Sá Santos, José Victor; Nepomuceno, Napoleão
Idioma: Inglés
Editor: MDPI
Año: 2022
Acceso abierto
Artículo científico
2022
Evaluación del rendimiento computacional de la generación de columnas y técnicas de generar y resolver para el problema de corte unidimensional de stock
Categoría
Ingeniería y Tecnología
Subcategoría
Ingeniería de Software
Palabras clave
Problema de corte de stock
Optimización
Patrones de corte
Unidimensional
Programación lineal entera
Generación de columnas
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 32
Citaciones: Sin citaciones
El Problema de Corte Óptimo (CSP) es un problema de optimización que consiste en cortar objetos grandes para producir artículos pequeños. El esfuerzo computacional para resolver este problema se ve afectado en gran medida por la cantidad de patrones de corte. En este artículo, para hacer frente a instancias grandes del Problema de Corte Unidimensional (1D-CSP), recurrimos a un procedimiento generador de patrones y proponemos una estrategia para restringir la cantidad de patrones generados. Se utilizaron modelos de Programación Lineal Entera (ILP), una implementación de la técnica de Generación de Columnas (CG) y una aplicación del marco Generar y Resolver (G&S) para obtener soluciones para instancias de referencia de la literatura. El método exacto fue capaz de resolver instancias pequeñas y de tamaño mediano del problema. Para instancias de tamaño grande, el método exacto no era aplicable, mientras que la efectividad de los otros métodos dependía de las características de las instancias. En general, el método G&S presentó resultados exitosos, obteniendo soluciones cuasióptimas para la mayoría de las instancias, empleando la estrategia de reducir artificialmente la cantidad de patrones de corte y explotándolos en un marco heurístico.
Descripción
El Problema de Corte Óptimo (CSP) es un problema de optimización que consiste en cortar objetos grandes para producir artículos pequeños. El esfuerzo computacional para resolver este problema se ve afectado en gran medida por la cantidad de patrones de corte. En este artículo, para hacer frente a instancias grandes del Problema de Corte Unidimensional (1D-CSP), recurrimos a un procedimiento generador de patrones y proponemos una estrategia para restringir la cantidad de patrones generados. Se utilizaron modelos de Programación Lineal Entera (ILP), una implementación de la técnica de Generación de Columnas (CG) y una aplicación del marco Generar y Resolver (G&S) para obtener soluciones para instancias de referencia de la literatura. El método exacto fue capaz de resolver instancias pequeñas y de tamaño mediano del problema. Para instancias de tamaño grande, el método exacto no era aplicable, mientras que la efectividad de los otros métodos dependía de las características de las instancias. En general, el método G&S presentó resultados exitosos, obteniendo soluciones cuasióptimas para la mayoría de las instancias, empleando la estrategia de reducir artificialmente la cantidad de patrones de corte y explotándolos en un marco heurístico.