Browsing by Subject "Cut stock problem (CSP)"

Now showing 1 - 1 of 1
  • Thumbnail Image
    Item
    Optimización del proceso de corte bidimensional tipo guillotina en una empresa local de servicios metalmecánicos mediante metaheurística
    (Pontificia Universidad Javeriana Cali, 2025) Arango Ruiz, Ángela María; Morillo Torres, Daniel
    Esta tesis aborda el problema de corte bidimensional con restricciones de tipo guillotina (2D-GCSP), una variante clásica del Cutting Stock Problem ampliamente utilizada en industrias que transforman materiales planos, como la metalmecánica. El objetivo central es desarrollar y comparar un modelo exacto de programación entera mixta (MILP) y una metaheurística diseñada para generar patrones de corte eficientes, minimizando el desperdicio y cumpliendo la demanda de piezas definidas bajo restricciones geométricas estrictas. En primera instancia se formula un modelo matemático exacto que integra variables asociadas a subespacios generados por cortes, cantidades producidas, inventarios y desperdicios. El modelo garantiza cortes guillotina, satisface la demanda y conserva la estructura jerárquica de generación de subespacios. Esta formulación se implementa en AMPL y se resuelve mediante CPLEX, permitiendo obtener soluciones óptimas para instancias pequeñas y medianas. Sin embargo, como ocurre típicamente en problemas NP-Hard, el tiempo computacional crece de manera significativa con la escala geométrica y la densidad de ocupación del material, lo que limita su aplicabilidad en entornos reales donde se manejan múltiples ítems y placas de gran tamaño. Para superar estas limitaciones se diseña una metaheurística conformada en tres componentes: (1) un esquema de codificación (encoding) que representa una solución mediante vectores de permutación; (2) un proceso de decodificación (decoding) que transforma dicha permutación en un patrón de corte utilizando la regla constructiva Bottom-Left; y (3) una estructura heurística basada en VNS (Variable Neighborhood Search) que explora vecindarios mediante permutaciones y selecciona la mejor configuración con base en una función fitness que combina desperdicio y penalización por demanda no satisfecha. Este enfoque permite evaluar múltiples patrones y seleccionar el más denso mediante un criterio de mejora incremental. Para la validación experimental se generaron tres casos de instancias clasificadas en Small, Medium y Large, junto con un conjunto de instancias reales proporcionadas por una empresa del sector metalmecánico. Los resultados muestran que el modelo exacto resuelve eficientemente las instancias Small y Medium, mientras que la metaheurística reproduce el óptimo (gap = 0) en estas mismas clases y se mantiene computacionalmente superior. Para las instancias Large y Reales, donde el MILP resulta inviable, la metaheurística produce soluciones consistentes, estables y con niveles de desperdicio acordes con la literatura y con tiempos compatibles con aplicaciones industriales.