Programación de molinete
En matemáticas y ciencias de la computación, el problema de programación de molinetes es un problema en la programación en tiempo real con tareas repetidas de longitud unitaria y restricciones estrictas en el tiempo entre repeticiones.
La entrada para la programación de molinetes consiste en una lista de tareas, cada una de las cuales se supone que toma tiempo unitario por instanciación. Cada tarea tiene un valor entero positivo asociado, su tiempo mínimo de repetición (el tiempo mínimo desde el inicio de una instanciación de la tarea a la siguiente). Solo se puede realizar una tarea en un momento dado. [1]
La salida deseada es una secuencia infinita que especifica qué tarea realizar en cada unidad de tiempo. Cada tarea de entrada debe aparecer infinitamente a menudo en la secuencia, con el mayor espacio entre dos instancias consecutivas de una tarea como máximo igual al tiempo de repetición de la tarea. [1]
Por ejemplo, la secuencia infinitamente repetida abacabacabac ... sería un programa de molinete válido para tres tareas a , byc con tiempos de repetición que son al menos 2, 4 y 4 respectivamente.
Si las tareas que se van a programar están numeradas del a , denote el tiempo de repetición de la tarea . Entonces la densidad de un problema de programación de molinete es . Para que exista una solución, es necesario que la densidad sea como máximo . [2]
Esta condición de densidad también es suficiente para que exista un programa en el caso especial de que todos los tiempos de repetición sean múltiplos entre sí (por ejemplo, si todos son potencias de dos ), porque en este caso se puede resolver el problema utilizando una cobertura disjunta. sistema . [1] Tener densidad como máximo también es suficiente cuando hay exactamente dos tiempos de repetición distintos. [2] Sin embargo, no es suficiente en otros casos. En particular, no hay un cronograma para tres elementos con tiempos de repetición , y , no importa cuán grande sea, aunque la densidad de este sistema es solo . [3]
