Un algoritmo memético para el job shop scheduling problem

Abstract

RESUMEN: Planificar tareas es un proceso que los humanos realizamos diariamente, de forma inconsciente, para llevar a cabo distintas labores. Sin embargo, en el ámbito industrial, la planificación de tareas no puede realizarse sin un análisis previo, pues las decisiones afectarán a los resultados y estos a las ganancias económicas. El job shop scheduling problem es un problema clásico que trata de modelar de forma genérica aquellas situaciones en las que hay que planificar la ejecución de una serie de operaciones sobre un conjunto finito de recursos. Desafortunadamente, la complejidad del problema es NP-hard, lo que hace inviable el uso de técnicas que aseguren encontrar una solución óptima. Es en esta situación donde cobran relevancia las técnicas metaheurísticas, porque aunque no dan garantías acerca de la optimalidad de la solución retornada, permiten encontrar soluciones suficientemente buenas en un tiempo razonable. Además, los algoritmos metaheurísticos son especialmente interesantes porque su funcionamiento es independiente del problema que tratan de resolver, es decir, pueden ser adaptados con facilidad para resolver una amplia variedad de problemas. Por esta razón, son una de las áreas de investigación más activas en el ámbito de los problemas de optimización. En este trabajo se propone un algoritmo memético, un tipo concreto de metaheurística que explota las sinergias entre dos estrategías metaheurísticas distintas, un algoritmo evolutivo y un algoritmo de búsqueda local. Este método se adapta para resolver distintas variantes del job shop scheduling problem, tratando de minimizar tanto el tiempo total de ejecución como el retraso con respecto a fechas de entrega, con la posibilidad en ambos casos de que haya incertidumbre en la duración de las tareas. Los algoritmos diseñados se evalúan sobre un conocido conjunto de instancias, obteniendo resultados altamente competitivos.

ABSTRACT: Scheduling is a process that we humans perform daily, unconsciously, to carry out different jobs. However, in the industrial field, task scheduling cannot be carried out without prior analysis, since the decisions will affect the results and these will affect the economic gains. The job shop scheduling problem is a classic problem that tries to model in a generic way those situations in which it is necessary to plan the execution of a series of operations on a finite set of resources. Unfortunately, the complexity of the problem is NP-hard, which makes the use of techniques that ensure an optimal solution inviable. It is in this situation where metaheuristic techniques become relevant, because although they do not give any guarantee about the optimality of the returned solution, they allow to find sufficiently good solutions in a reasonable time. In addition, metaheuristic algorithms are especially interesting because their functioning is independent of the problem they are trying to solve, that is, they can be easily adapted to solve a wide variety of problems. For this reason, they are one of the most active research areas in the field of optimization problems. In this work a memetic algorithm is proposed, a concrete type of metaheuristic that exploits the synergies between two different metaheuristic strategies, an evolutionary algorithm and a local search algorithm. This method is adapted to solve different variants of the job shop scheduling problem, trying to minimize the total execution time as well as the delay with regard to delivery dates, with the possibility in both cases of uncertainty in the duration of the tasks. The designed algorithms are evaluated on a well-known set of instances, obtaining highly competitive results.