Programación en espiral

En matemáticas e informática, el problema de la planificación en espiral es un problema de planificación en tiempo real con tareas repetitivas de duración unitaria y restricciones estrictas en el tiempo entre repeticiones.

Cuando un problema de programación de tipo "pinwheel" tiene solución, esta se caracteriza por una repetición periódica de la programación. Este patrón repetitivo se asemeja al de los pines activados y desactivados en los engranajes de una máquina de cifrado de tipo "pinwheel" , lo que justifica su nombre. ^{[ 1 ]} Si la fracción de tiempo que requiere cada tarea es menor que 5/6 del tiempo total, siempre existe una solución; sin embargo, algunos problemas de programación de tipo "pinwheel" cuyas tareas consumen un poco más de 5/6 del tiempo total no tienen solución.

Ciertas formulaciones del problema de programación de molinete son NP-difíciles .

La entrada para la planificación de tipo pinwheel consiste en una lista de tareas, cada una de las cuales se supone que toma un tiempo unitario por instanciación. Cada tarea tiene un valor entero positivo asociado, su tiempo máximo de repetición (el tiempo máximo desde el inicio de una instanciación de la tarea hasta la siguiente). Solo se puede realizar una tarea a la vez. ^{[ 1 ]}

El resultado deseado es una secuencia infinita que especifica qué tarea realizar en cada unidad de tiempo. Cada tarea de entrada debe aparecer infinitas veces en la secuencia, con un intervalo máximo entre dos instanciaciones consecutivas de una tarea igual al tiempo de repetición de la tarea. ^{[ 1 ]}

Por ejemplo, la secuencia que se repite infinitamente ABACABACABAC ... sería una programación válida en espiral para tres tareas A, B y C con tiempos de repetición de al menos 2, 4 y 4 respectivamente.

Si las tareas a programar están numeradas desde${\displaystyle 1}$a${\displaystyle n}$, dejar${\displaystyle t_{i}}$denota el tiempo de repetición para la tarea${\displaystyle i}$. En cualquier cronograma válido, tarea${\displaystyle i}$debe utilizar un${\displaystyle 1/t_{i}}$fracción del tiempo total, la cantidad que se usaría en un cronograma que repite esa tarea exactamente en su tiempo de repetición especificado. La densidad de un problema de programación de molinete se define como la suma de estas fracciones,${\displaystyle \textstyle \sum 1/t_{i}}$Para que exista una solución, los tiempos dedicados a cada tarea no pueden sumar más que el tiempo total disponible, por lo que es necesario que la densidad sea como máximo${\displaystyle 1}$. ^{[ 2 ]}

Esta condición sobre la densidad también es suficiente para que exista un cronograma en el caso especial de que todos los tiempos de repetición sean múltiplos entre sí. Por ejemplo, esto sería cierto cuando todos los tiempos de repetición son potencias de dos . En este caso, se puede resolver el problema utilizando un sistema de cobertura disjunto . ^{[ 1 ]} Tener una densidad como máximo${\displaystyle 1}$También es suficiente cuando hay exactamente dos tiempos de repetición distintos. ^{[ 2 ]} Sin embargo, tener una densidad como máximo de 1 no es suficiente en algunos otros casos. En particular, no hay un programa para tres elementos con tiempos de repetición.${\displaystyle t_{1}=2}$,${\displaystyle t_{2}=3}$, y${\displaystyle t_{3}}$, sin importar cuán grande${\displaystyle t_{3}}$puede ser, aunque la densidad de este sistema es solo${\displaystyle 5/6+1/t_{3}}$. ^{[ 3 ]}

En 1993, se conjeturó que, cuando la densidad de una programación de molinete es como máximo${\displaystyle 5/6}$, existe una solución. ^{[ 3 ]} Esto se demostró en 2024. ^{[ 4 ]}

Cuando existe una solución, se puede suponer que es periódica, con un período como máximo igual al producto de los tiempos de repetición. Sin embargo, no siempre es posible encontrar un esquema repetitivo de longitud subexponencial. ^{[ 2 ]}

Con una representación de entrada compacta que especifica, para cada tiempo de repetición distinto, el número de objetos que tienen ese tiempo de repetición, la planificación de tipo pinwheel es NP-difícil . ^{[ 2 ]}

A pesar de la complejidad NP del problema de programación de la rueda de molinete para entradas generales, algunos tipos de entradas pueden programarse de manera eficiente. Un ejemplo de esto ocurre con entradas donde (cuando se listan en orden) cada tiempo de repetición divide uniformemente al siguiente, y la densidad es como máximo uno. En este caso, el problema puede resolverse mediante un algoritmo voraz que programa las tareas en orden, programando cada tarea para que se repita exactamente en su tiempo de repetición. En cada paso de este algoritmo, las ranuras de tiempo que ya se han asignado forman una secuencia repetitiva, con un período igual al tiempo de repetición de la tarea programada más recientemente. Este patrón permite que cada tarea sucesiva se programe de forma voraz, manteniendo el mismo invariante. ^{[ 1 ]}

La misma idea se puede usar para instancias arbitrarias con una densidad máxima de 1/2, redondeando cada tiempo de repetición a una potencia de dos menor o igual a él. Este proceso de redondeo duplica como máximo la densidad, manteniéndola como máximo en uno. Después del redondeo, todas las densidades son múltiplos entre sí, lo que permite que el algoritmo voraz funcione. La programación resultante repite cada tarea en su tiempo de repetición redondeado; como estos tiempos redondeados no superan los tiempos de entrada, la programación es válida. ^{[ 1 ]} En lugar de redondear a potencias de dos, se puede lograr un umbral de densidad mayor redondeando a otras secuencias de múltiplos, como los números de la forma${\displaystyle x\cdot 2^{i}}$para una cuidadosa elección del coeficiente${\displaystyle x}$, ^{[ 3 ]} o redondeando a dos series geométricas diferentes y generalizando la idea de que las tareas con dos tiempos de repetición distintos se pueden programar hasta una densidad de uno. ^{[ 3 ] [ 5 ]}

El trabajo original sobre la programación en espiral la propuso para una aplicación en la que una única estación base debe comunicarse con múltiples satélites o sensores remotos , uno a la vez, con requisitos de comunicación distintos. En esta aplicación, cada satélite se convierte en una tarea en un problema de programación en espiral, con un tiempo de repetición elegido para proporcionarle un ancho de banda adecuado. La programación resultante se utiliza para asignar intervalos de tiempo a cada satélite para que se comunique con la estación base. ^{[ 1 ]}

Otras aplicaciones de la programación de molinete incluyen la programación de sesiones de mantenimiento para un conjunto de objetos (como cambios de aceite para automóviles), la disposición de símbolos repetidos en las cadenas de impresión de impresoras de línea , ^{[ 3 ]} el procesamiento informático de datos multimedia, ^{[ 6 ]} y la resolución de contención en redes informáticas inalámbricas en tiempo real. ^{[ 7 ]}

• Programación en espiral (1989) , Douglas B. West, Universidad de Illinois