Diseño de un método de solución para el flexible job shop con tiempos de alistamiento dependientes de la secuencia
Loading...
Date
2020
Director
Journal Title
Journal ISSN
Volume Title
Publisher
Pontificia Universidad Javeriana Cali
Abstract
El Flexible Job Shop con Tiempos de Alistamiento Dependientes de la Secuencia (SDST-FJSP) es, al igual que el Job Shop Scheduling Problem (JSP), un problema de programación de trabajos. Sin embargo, el SDST-FJSP tiene en cuenta supuestos adicionales, tales como los tiempos de alistamiento dependientes de la secuencia y la multifuncionalidad de las máquinas, que permiten darle mayor cercanía a la realidad. Este problema ha sido catalogado como NP-hard, lo que ha despertado gran interés entre los investigadores, pues su alta complejidad hace que un método de solución exacta no sea una propuesta viable debido a la gran magnitud de los tiempos computacionales. Así pues, en este trabajo se proponen dos métodos para abordar el SDST-FJSP. El primero es un modelo matemático empleando MILP (Mixed-integer Linear Programming); si bien este es un método exacto, permite una comprensión más profunda del problema. El segundo es un algoritmo genético (AG) en el cual se empleó el método Tournament para el operador de cruce y el método Swap Mutation para el operador de mutación. Posteriormente, se realiza una comparación del desempeño obtenido por cada uno de los métodos, encontrando, como era de esperarse, mejores resultados en el AG para un mismo tiempo de ejecución.
Description
item.page.descriptioneng
The Flexible Job Shop with Sequence-Dependent Setup Times (SDST-FJSP) is like the Job Shop Scheduling Problem (JSP), a job scheduling problem. However, the SDST-FJSP considers additional assumptions, such as sequence-dependent setup times and the multipurpose of the machines, which allow it to be closer to reality. This problem has been classified as NP-hard, which has aroused great interest among researchers, because its high complexity means that an exact solution method is not a viable proposal due to the great magnitude of computational times. Thus, in this work, two methods are proposed to address the SDST-FJSP. The first is a mathematical model using MILP (Mixed Integer Linear Programming); although this is an exact method, it allows a deeper understanding of the problem. The second is a genetic algorithm (GA) in which the Tournament method was used for the crossover operator and the Swap Mutation method for the mutation operator. Afterward, a comparison of the performance obtained by each of the methods is made, finding, as expected, better results in the GA for the same execution time.
Keywords
Tiempos de alistamiento, Algoritmo genético, Modelo matemático, Flexible Job Shop, Sequence-dependent setup times, Genetic algorithm, Mathematical model