Algoritmos para el problema de dimensionamiento del lote económico con múltiples niveles y restricciones de capacidad

Abstract

En una red de distribución típica de un producto, existen múltiples niveles, desde el productor, pasando por varios distribuidores intermedios hasta llegar al minorista. Estos niveles con sus características específicas conforman la red de distribución necesaria para satisfacer a tiempo la cantidad de producto demandado por el consumidor final. Seleccionar una adecuada política de distribución significa un complejo desafío para las organizaciones, teniendo que decidir cuándo y cuánto producir o almacenar para minimizar los costos implicados. Por esta razón, surge El Problema de Dimensionamiento de Lote; un modelo de planificación de producción que procura establecer los tamaños de lotes a producir en cada período, considerando las características de los niveles y la demanda futura para minimizar los costos de inventario y producción. En este proyecto de grado se abordó en particular, un problema de Dimensionamiento de Lotes con múltiples niveles y capacidades de producción variables (en cada período y nivel el límite máximo de producción cambia). Este es una extensión del problema de un solo nivel con restricciones de capacidades, el cual se ha demostrado pertenecer a la clase de problemas NP-Hard. El objetivo del proyecto fue el desarrollo de un procedimiento heurístico que elabore una planificación de producción conveniente en tiempos computacionales razonables. La heurística implementada se basó en el algoritmo Dijkstra para el problema del camino más corto en un grafo. Para analizar los resultados obtenidos se realizó un estudio comparativo con un método de resolución exacta y otros procedimientos heurísticos existentes (Lote por Lote, Lote de Tamaño Fijo y Silver-Meal). Para el método de resolución exacta se utilizó el solver de GLPK (herramienta de uso académico).

El tiempo de búsqueda de una solución óptima se acotó explícitamente por la naturaleza del problema, respondiendo a este hecho, a medida que crece el tamaño del problema la desviación al óptimo aumenta por parte de GLPK y los métodos de resolución heurísticos van tomando mayor relevancia. Todos los métodos de resolución propuestos se evaluaron con un gran número casos de prueba, las instancias fueron generadas teniendo en cuenta una amplia variedad de configuraciones (costos, capacidades, etcétera). De los resultados obtenidos se puede concluir que el objetivo del inicio del proyecto se logró concretar. Para todos los casos de prueba en el cual el método de resolución exacto logró encontrar una solución óptima, la heurística propuesta basada en Dijkstra fue capaz de obtener una solución con un valor muy cercano a éste en tiempos computacionales razonables.