sistema de tareas métricas
Los sistemas de tareas son objetos matemáticos utilizados para modelar el conjunto de posibles configuraciones de algoritmos en línea . Fueron introducidos por Borodin , Linial y Saks (1992) para modelar una variedad de problemas en línea. Un sistema de tareas determina un conjunto de estados y costos para cambiar de estado. Los sistemas de tareas obtienen como entrada una secuencia de solicitudes tal que cada solicitud asigna tiempos de procesamiento a los estados. El objetivo de un algoritmo en línea para sistemas de tareas es crear un cronograma que minimice el costo total incurrido debido al procesamiento de las tareas con respecto a los estados y debido al costo de cambiar de estado.
Si la función de costo para cambiar estados es una métrica , el sistema de tareas es un sistema de tareas métricas (MTS). Este es el tipo más común de sistemas de tareas. Los sistemas de tareas métricas generalizan problemas en línea como la paginación , el acceso a listas y el problema del servidor k (en espacios finitos).
Un sistema de tareas es un par donde es un conjunto de estados y es una función de distancia. Si es una métrica, es un sistema de tareas métricas. Una entrada al sistema de tareas es una secuencia tal que para cada , hay un vector de entradas no negativas que determinan los costos de procesamiento para los estados al procesar la tarea th.
