SCHEDULING DE PROYECTOS DE OBSERVACIÓN ASTRONÓMICA CON ALGORITMO GENÉTICO PARALELO SOBRE UNA GRID MULTI-AGENTE

Abstract

El principal objetivo de esta memoria es presentar una alternativa paralela al grupo de algoritmos y procedimientos candidatos para realizar la labor de calendarización en el proyecto ALMA. Para lograr esto, se plantea un modelo de paralelización para algoritmos genéticos, basado en el enfoque maestro-esclavo, centrado en la función de evaluación, y extendido al operador de mutación y cruzamiento. Esta implementación se encuentra ligada a trabajos previos, tanto secuenciales como paralelos, con el mismo objetivo. Se utilizó un simulador de grid multi-agente como herramienta para realizar la paralelización, obteniéndose así una arquitectura de memoria distribuida. validada a través de una serie de casos de prueba respecto a la ejecución de su versión secuencial. Finalmente, se demuestra que en todos los casos la paralelización refleja superioridad en tiempos de ejecución en comparación con la versión secuencial, siendo en el peor de los casos el doble de rápida.

The main objective of this thesis is to present a parallel alternative to the aspirant group of algorithms for the scheduling in ALMA project. To achieve this, a genetic algorithm parallelization is presented. based on the master-slave mode], centered in the evaluation function. and extended to the mutation and crossing operator. This implementation is linked to previous works, both sequential and parallel, with the same objective. A multi agent grid simulator is used as parallelization tool. thus obtaining distributed memory architecture, validated through a series of test cases regarding its sequential version. Finally, it's proven that in all cases the parallelization shows superior execution times in comparison to its sequential version, being in the worst case twice as fast.