Solución al Problema de Programación de Tareas mediante Algoritmos Genéticos Cooperantes en Paralelo -Edición Única

Abstract

Este trabajo trata sobre el problema de programación de tareas en una máquina minimizando el criterio justo a tiempo. En la solución de este problema se combina el uso de una heurística de dinámica de cuello de botella con una variante de algoritmo genético llamada algoritmo genético cooperante, ejecutado en paralelo. Los algoritmos genéticos cooperantes son un conjunto de algoritmos genéticos, cada uno destinado a resolver por separado una de las partes de un problema, pero que cooperan entre sí durante la etapa de evaluación de individuos, al usar la información de los mejores individuos encontrados por los otros algoritmos, con el fin de generar una solución completa al problema. Las propuestas de este trabajo se basan en la hipótesis de que un algoritmo genético cooperante que genere resultados tan buenos como los de un algoritmo genético simple y que se ejecute en un menor tiempo, será una buena alternativa para abordar la solución de problemas de programación de tareas en una máquina en los que, debido a su tamaño, se justificaría el uso de varias computadoras para resolverlo en un tiempo razonable. En este trabajo se experimenta con dos modelos de procesamiento en paralelo del algoritmo genético cooperante, utilizando mecanismos de programación que permiten la distribución de procesos en equipos de cómputo heterogéneos. Mediante los resultados de los experimentos se muestra que el algoritmo genético cooperante propuesto es capaz de obtener mejores soluciones que el algoritmo genético simple en un tiempo menor.