Algoritmo genético permutacional para el despliegue y la planificación de sistemas de tiempo real distribuidos

Abstract

Resumen: El despliegue y la planificación de tareas y mensajes en sistemas de tiempo real distribuidos son problemas NP-difíciles (NP- hard), por lo que no existen métodos óptimos para solucionarlos en tiempo polinómico. En consecuencia, estos problemas son adecuados para abordarse mediante algoritmos genéricos de búsqueda y optimización. En este artículo se propone un algoritmo genético multiobjetivo basado en una codificación permutacional de las soluciones para abordar el despliegue y la planificación de sistemas de tiempo real distribuidos. Además de desplegar tareas en computadores y de planificar tareas y mensajes, este algoritmo puede minimizar el número de computadores utilizados, la cantidad de recursos computacionales y de comunicaciones empleados y el tiempo de respuesta de peor caso medio de las aplicaciones. Los resultados experimentales muestran que este algoritmo genético permutacional puede desplegar y planificar sistemas de tiempo real distribuidos de forma satisfactoria y en tiempos razonables. Abstract: The deployment and scheduling of tasks and messages in distributed real-time systems are NP-hard problems, so there are no optimal methods to solve them in polynomial time. Consequently, these problems are suitable to be approached with generic search and optimisation algorithms. In this paper we propose a multi-objective genetic algorithm based on a permutational solution encoding for the deployment and scheduling of distributed real-time systems. Besides deploying and scheduling tasks and messages, the algorithm can minimize the number of the used computers, the utilization of computing and networking resources and the average worst-case response times of the applications. The experiments show that this genetic algorithm can successfully synthesize complex distributed real-time systems in reasonable times. Palabras clave: Sistemas de tiempo real, Algoritmos de planificación, Algoritmos genéticos, Optimizaciones multiobjetivo, Keywords: Real-time systems, Scheduling algorithms, Genetic algorithms, Multiobjective optimisations.