Meta-heurísticas híbridas multi-objetivo en problemas de secuenciación de operaciones bajo un entorno job-shop

Abstract

La planificación, programación y control de la producción se encargan de diseñar, coordinar y administrar todas las operaciones que se hallan presentes en la explotación de los sistemas productivos. En las últimas décadas muchos problemas de optimización multi-objetivo han surgido en este ámbito y fueron tratados con éxito con técnicas de resolución basadas en metaheurísticas, en general, y con algoritmos evolutivos, en particular. Dichas técnicas, sin descartar otras, constituyen potentes herramientas para tratar adecuadamente estos problemas en el marco de las operaciones productivas y logísticas. La complejidad que se presenta en estos problemas se debe a los criterios de eficiencia que se imponen a los distintos sistemas productivos. Este estudio se extiende al desarrollo y análisis de un procedimiento, enmarcado en la estructura particular de un algoritmo evolutivo para resolver el problema de secuenciación de trabajos (JSSP, Job-Shop Scheduling Problem). Además, se explora la vecindad de las distintas soluciones dentro de la misma evolución, lo que mejora significativamente los resultados. El algoritmo propuesto utiliza una codificación basada en asignación de secuencias para poder establecer permutaciones con repeticiones. Esta representación, muy sencilla y compacta, distingue a este estudio de otros. Luego de finalizar el procedimiento, se adiciona una etapa de simulación a modo de examinar las soluciones obtenidas en la etapa resolutiva. Se realiza un análisis comparativo con otros algoritmos para constatar la eficiencia del procedimiento. Finalmente, se presenta una aplicación de la técnica en varias empresas, lo que permitió contrastar los resultados obtenidos con la realidad.

The study of planning, programming and controlling production processes yields methods of design, coordination and management of the operations involved in productive systems. In the last decades several multi-objective optimization problems have arisen in those studies and have been solved successfully with techniques based on meta-heuristics, in general, and evolutionary algorithms in particular. These techniques, notwithstanding the existence of other useful tools, provide the adequate means for treating those optimization problems in the realm of logistics and operations analysis. The complexity of the problems stems from the efficiency criteria imposed over the solution candidates. This work extends those tools to the development and analysis of an evolutionary procedure aimed to solving the Job-Shop Scheduling Problem (JSSP). We explore ways of improving solutions in the vicinity of already found candidates. The algorithm generates sequences that allow permutations with repetition. This representation, simple enough, distinguishes this study from others. After running the procedure, a comparison with other algorithms is presented, based on simulations. Finally, the algorithm is applied to analyze real-world applications.