Resolución de problemas de planificación de tareas en ambientes de máquinas paralelas usando algoritmos evolutivos

Abstract

La planificación en un ambiente de máquinas idénticas en paralelo (Pm) implica efectuar un cierto número de tareas (jobs) que utilizan varios recursos (un banco de máquinas en paralelo) por un cierto periodo de tiempo. Un modelo sencillo que consiste de m máquinas y n tareas independientes es la base de modelos más complejos. En este modelo, las tareas son asignadas de acuerdo con la disponibilidad de los recursos existentes siguiendo alguna regla de despacho determinada. El tiempo de finalización de la última tarea que abandona el sistema, conocido como makespan (Cmax), es uno de los objetivos más importantes a ser minimizado debido a que usualmente implica una alta utilización de los recursos; sin embargo, deben ser considerados otros objetivos tratados comúnmente en la literatura [9, 11], los cuales además de tener importancia teórica son de relevancia práctica. Muchos de estos problemas son NP-Hard para 2 ≤ m ≤ n y por ende, se han desarrollado heurísticas convencionales, Algoritmos Evolutivos (AEs) y otras heurísticas poblacionales para proveer planes o planificaciones aceptables como soluciones. Este trabajo, expone las conclusiones obtenidas en la resolución de problemas de planificación de tareas sin restricciones de precedencia, en ambientes de planificación de 2 y 5 máquinas idénticas en paralelo, mediante el uso de AEs que implementan distintas técnicas de recombinación y utilizan distintas representaciones indirectas de cromosoma. La performance lograda por los distintos AEs implementados, se compara con los resultados obtenidos por un conjunto de heurísticas convencionales que se aplican usualmente a diferentes problemas de planificación de máquinas idénticas en paralelo.