Diagramación on-line de sistemas de tareas de tiempo real periódicas mandatorias duras/opcionales basadas en recompensas con factor de depreciación

Abstract

El trabajo aborda el problema de la diagramación on line de sistemas de tareas de tiempo real periódicas compuestas por una parte mandatoria dura y una parte opcional de cuya ejecución deriva una recompensa. Se consideran funciones recompensa con un factor de depreciación que disminuye el valor de la función a medida que la ejecución de la parte opcional se aleja de la finalización de su correspondiente mandatoria. La maximización del beneficio es un problema NP-duro cuya resolución on-line es impracticable. Se presentan cuatro algoritmos que diagraman las partes opcionales a partir de ciertos instantes singulares en la ejecución del sistema. Los métodos, llamados en forma genérica SH (Singularidades/Heurísticas), utilizan una heurística para resolver localmente la elección de la tarea optativa que más beneficio brinda al sistema. Al contrario de métodos propuestos previamente, los SH no requieren que la función recompensa sea continuamente diferenciable. La única exigencia es que sea computable, incluída la depreciación, en el instante en que va a ser usada. Se evalúa la performance de los métodos propuestos vs Best Incremental Result, usado como base de comparación en trabajos similares.