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

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.

Referencias no citadas

Achterberg, 2009, Azketa et al., 2012a, Azketa et al., 2011a, Azketa et al., 2011b, Azketa et al., 2012b, Boyd et al., 2007, Chen and Lin, 2000, Davare et al., 2007, Davis, 1991, Deb et al., 2002, Di Natale and Stankovic, 1995, Di Natale et al., 2007, Dick and Jha, 2002, Garey et al., 1976, Glover, 1986, Gutiérrez and Harbour, 1995, Hamann et al., 2006, Hladik et al., 2008, Holland, 1975, Kirkpatrick, 1984, Metzner and Herde, 2006, Minoux, 1986, Mitra and Ramanathan, 1993, Monnier et al., 1998, Palencia and Harbour, 1998, Palencia and Harbour, 1999, Pearl, 1984, Pop et al., 2002, Pop et al., 2003a, Pop et al., 2003b, Porto et al., 2000, Porto and Ribeiro, 1995, Samii et al., 2009, Schrijver, 1998, Shang et al., 2007, Tindell et al., 1992, Tindell and Clark, 1994, Tsang, 1993, Zheng et al., 2007 and Zhu et al., 2009.