Algoritmos híbridos para el problema de scheduling de máquinas paralelas

Abstract

En los últimos años ha surgido un gran interés en las metaheurísticas híbridas, las cuales han sido desarrolladas considerablemente en el campo de la optimización. Combinaciones de algoritmos han provisto técnicas muy poderosas de algoritmos de búsqueda. En esta etapa de nuestro trabajo hemos estudiado una variante de Algoritmos Genéticos (AGs) que pertenece a la clase de metaheurísticas poblacionales (P-metaheurísticas) y su hibridización con dos metaheurísticas de solución única (S-metaheurísticas) son: Recocido Simulado (SA) y Búsqueda Local (LS). El problema en estudio es minimizar la máxima tardanza (Maximum Tardiness) en scheduling de máquinas paralelas independientes. La notación usada en la literatura para describir el mismo es una triupla: ( | | ). El primer campo describe el ambiente de máquinas, el segundo campo indica las restricciones entre las tareas que son asignadas a las máquinas. Por último, el tercer campo, provee la o las funciones objetivo a ser optimizadas. Acorde a esta notación, nuestro problema se describe mediante (Pm || Tmax). Tal problema se ha considerado de complejidad NP-duro, cuando 2 m n (m es el número de máquinas y n el número de tareas). Los resultados obtenidos hasta ahora con la propuesta de un AG híbrido han mostrado una mejora considerable en la minimización de la máxima tardanza, esto se observa principalmente en las instancias de mayor complejidad.