Representaciones indirectas en algoritmos genéticos y la alcanzabilidad de schedules semi-activos

Abstract

El problema de Job-Shop Scheduling (JSS) es de gran importancia práctica. Sin embargo, su dificultad inherente lo convierte en uno de los miembros más duros de la clase de problemas NP-Completos. Dada la inherente dificultad de los problemas de scheduling y en particular JSS, no siempre es posible aplicar métodos de búsqueda convencionales para encontrar soluciones cercanas al ´optimo en un tiempo razonable. Esto ha llevado a un creciente interés en el uso de metaheurísticas, particularmente Algoritmos Evolutivos, como métodos de búsqueda alternativa. En este artículo se presenta un estudio comparativo de los resultados obtenidos a partir de la aplicación de un Algoritmo Genético (AG) al problema JSS. El diseño del AG incluye dos propuestas para atacar un problema detectado en estudios previos con respecto de la alcanzabilidad de schedules semi-activos usando representaciones indirectas. Una de las propuestas consiste en incrementar el espacio de búsqueda de manera tal de poder alcanzar los schedules semi-activos a través de una representación y schedule builder apropiados. La segunda propuesta, la cual es una extensión de la primera, reduce el espacio de búsqueda respecto al alcanzado con la primera propuesta, para cubrir sólo a los schedules semi-activos. El objetivo del estudio está centrado en mostrar las posibles mejoras en la performance de un AG a medida que la representación y el schedule builder incorporan variantes que permitan cubrir regiones adicionales del espacio de búsqueda. El estudio incluye comparaciones con representaciones indirectas previamente estudiadas.