Modelos de programación lineal entera y una heurística basada en path-relinking para el problema de minimización de cambios de cuchillas en la industria del cartón corrugado

Abstract

El problema de minimización de cambios de cuchillas surge en la producción de cartón corrugado, en particular al tener en cuenta el costo de cambiar de un patrón de corte al siguiente. Dado un programa de cortes, este problema pide una permutación de los patrones de corte y una permutación de los ítems de cada patrón de corte de modo tal de minimizar los cambios de cuchillas longitudinales necesarios para fabricar el programa permutado. Se trata de un problema NP-hard, incluso cuando se restringe a programas de cortes con dos patrones de corte o bien a patrones de corte con una cantidad constante (mayor a 1) de elementos. En este trabajo presentamos tres modelos de programación lineal entera para este problema, junto con familias de cortes de optimalidad que permiten reforzar estas formulaciones y permiten acelerar los tiempos de resolución de solvers generales de programación lineal entera sobre estas formulaciones. Presentamos también una heurística basada en path-relinking para este problema, y analizamos la contribución de estos elementos para la resolución en forma óptima de instancias reales del problema.