Parallelism and Hybridization in Differential Evolution to solve the Flexible Job Shop Scheduling Problem

Abstract

El problema de programación flexible del taller de trabajos (FJSSP) es uno de los problemas de optimización combinatoria más desafiantes, con aplicabilidad práctica en un entorno de producción real. En este trabajo, proponemos un algoritmo de Evolución Diferencial (DE) simple para abordar este problema. Para representar una solución FJSSP, se adopta una representación de valor real, lo que requiere un mecanismo de conversión muy simple para obtener un cronograma factible. En consecuencia, el algoritmo DE todavía funciona en el dominio continuo para explorar el espacio de búsqueda de problemas del FJSSP discreto. Además, para mejorar la capacidad de búsqueda local y equilibrar las capacidades de exploración y explotación, se incorpora un algoritmo de búsqueda local simple en el marco DE. Además, se incluye el paralelismo de las operaciones DE para mejorar la eficiencia de todo el algoritmo. Los resultados experimentales confirman la significativa mejora lograda al integrar las modificaciones introducidas en este estudio. Además, los resultados de las pruebas muestran que nuestro algoritmo es competitivo en comparación con la mayoría de los enfoques existentes para FJSSP.

The Flexible Job Shop Scheduling Problem (FJSSP) is one of the most challenging combinatorial optimization problems, with practical applicability in a real production environment. In this work, we propose a simple Differential Evolution (DE) algorithm to tackle this problem. To represent a FJSSP solution, a real value representation is adopted, which requires a very simple conversion mechanism to obtain a feasible schedule. Consequently, the DE algorithm still works on the continuous domain to explore the problem search space of the discrete FJSSP. Moreover, to enhance the local search ability and to balance the exploration and exploitation capabilities, a simple local search algorithm is embedded in the DE framework. Also, the parallelism of the DE operations is included to improve the efficiency of the whole algorithm. Experimental results confirm the significant improvement achieved by integrating the modifications introduced in this study. Additionally, test results show that our algorithm is competitive when compared with most existing approaches for FJSSP.