Estudio del problema de programación de la producción en un ambiente multi-propósito flexible con división de lotes

Abstract

El problema de programación de tareas conocido como programación de la producción en un ambiente multi-propósito flexible con división de lotes es una variante del problema de tipo programación de la producción, en la cual los lotes pueden dividirse en sublotes de diferentes tamaños y asignarse a diferentes máquinas, de tal forma que se disminuyen los tiempos muertos y el tiempo total de procesamiento. El objetivo consiste en minimizar la amplitud de proceso, es decir, la fecha de terminación de la última operación en la última máquina. Debido a la complejidad computacional de este problema, normalmente se recurre a técnicas heurísticas para poder resolverlo. En este trabajo, se propone un algoritmo que combina estrategias de Búsqueda Tabú, con vecindades y técnicas de división de lotes basados en la ruta crítica de cada solución generada. Para determinar la eficiencia del algoritmo propuesto, se adaptaron las instancias edata, rdata y vdata de Hurink. Debido a que este problema casi no se ha reportado en la literatura, no fue posible encontrar soluciones, que sirvieran como punto de comparación, para las instancias antes mencionadas. Por lo tanto, se emplearon dos estrategias para poder evaluar el desempeño del algoritmo propuesto. Primero, se resolvieron las instancias propuestas hasta donde fue posible, con el solver Gurobi. Segundo, se emplearon los mejores resultados reportados, sin división de lotes, para este mismo conjunto de instancias. Los experimentos realizados muestran que el algoritmo propuesto es capaz de generar buenas soluciones en tiempos de cómputo aceptables. Por otro lado, se evidencian los beneficios de la estrategia combinando flexibilidad y división de lotes, introducida en este trabajo.

The exible job shop scheduling problem with lot streaming or lot splitting is a variant of the job shop scheduling problem, in which a job can be divided into sublots of diferent sizes and assigned to diferent machines, in such a way that processing times can be reduced. In this version the objective is to minimize the makespan. Due to the computational complexity, heuristic techniques are usually used to solve this type of problem. In this thesis, we propose an algorithm that combines tabu search strategies, with specific neighborhoods and lot splitting techniques based on the critical path of each generated schedule. To determine the eficiency of the proposed algorithm, the Hurink's instances edata, rdata, vdata were adapted to the lot splitting policy. Since this problem has hardly been reported in the literature, it was not possible to find solutions to compare with, for the aforementioned instances. Therefore, two strategies were used to evaluate the performance of the proposed algorithm. First, the instances were solved as far as possible, with the Gurobi solver. Second, the best reported solutions, without lot streaming, were used as a reference for this set of instances. The experiments showed that the proposed algorithm is able to generate good solutions in an reasonable computing time. Besides, these results provide clear evidence regarding the benefits of strategy proposed in this work, combining exibilty and lot streaming.