A memetic algorithm for minimizing the makespan in the Job Shop Scheduling problem

Un algoritmo memético para minimizar el makespan en el problema del Job Shop Scheduling

El Job Shop Scheduling Problem (JSP) es un problema de optimización combinatoria catalogado de tipo NP-Hard. Para dar solución a este problema han sido utilizados diversos métodos heurísticos y metaheurísticos. Con el objetivo de minimizar el makespan se propone un algoritmo memético (MA) que combina la exploración del espacio de búsqueda mediante un algoritmo genético (GA) y la explotación de las soluciones, usando una búsqueda local basada en la estructura de vecindario de Nowicki y Smutnicki. La estrategia genética usa una representación basada en operaciones que le permite generar programas factibles y una probabilidad de selección de los mejores individuos que son cruzados usando el operador JOX. Los resultados obtenidos en la ejecución demuestran que el algoritmo es competitivo frente a otros enfoques propuestos en la literatura.

I. INTRODUCCIÓN

El Problema de Programación de Puestos de Trabajo (PTP) es uno de los problemas de programación más estudiados en la literatura ^[1]. Al igual que otros problemas de programación, se clasifica como un problema de naturaleza combinatoria ya que requiere desarrollar una configuración para programar un conjunto de trabajos en un conjunto de máquinas, donde cada trabajo tiene una serie de operaciones que deben ser procesadas en una secuencia definida, y en un tiempo de procesamiento establecido. En la mayoría de los casos de programación de talleres, es deseable encontrar la mejor configuración para minimizar el makespan (tiempo total en el que se han ejecutado todos los trabajos). Otros objetivos directamente relacionados con la programación son la minimización de la tardanza, el retraso y el flujo total. El JSP se considera un problema NP-Hard ^[2]; por lo tanto, es computacionalmente difícil encontrar una solución óptima en un tiempo razonable ya que el espacio de búsqueda crece exponencialmente a medida que aumentan las entradas del problema.

Desde principios de los años 50, numerosas investigaciones se han centrado en la resolución del JSP. En 1956, Jackson ^[3] propuso un nuevo enfoque generalizando el algoritmo de Johnson´s Flow Shop ^[4]. Akers y Friedman ^[5] emplearon un enfoque algebraico para representar las secuencias de procesamiento. Posteriormente, Roy y Sussmann ^[6] propusieron una representación con el grafo disyuntivo; y finalmente, Balas ^[7] aplicó un enfoque enumerativo basado en este grafo. Entre los diferentes enfoques para resolver el JSP, es común encontrar métodos exactos que pretenden encontrar soluciones óptimas a un alto coste computacional; sin embargo, resultan ser eficientes sólo para aplicaciones pequeñas.