Programación de intervalos

Clase de problemas en informática

La programación de intervalos es una clase de problemas en informática , particularmente en el área de diseño de algoritmos . Los problemas consideran un conjunto de tareas. Cada tarea está representada por un intervalo que describe el tiempo en el que necesita ser procesada por alguna máquina (o, equivalentemente, programada en algún recurso). Por ejemplo, la tarea A podría ejecutarse de 2:00 a 5:00, la tarea B podría ejecutarse de 4:00 a 10:00 y la tarea C podría ejecutarse de 9:00 a 11:00. Un subconjunto de intervalos es compatible si no hay dos intervalos que se superpongan en la máquina/recurso. Por ejemplo, el subconjunto {A,C} es compatible, al igual que el subconjunto {B}; pero ni {A,B} ni {B,C} son subconjuntos compatibles, porque los intervalos correspondientes dentro de cada subconjunto se superponen.

El problema de maximización de la programación de intervalos (ISMP) consiste en encontrar el conjunto compatible más grande, es decir, un conjunto de intervalos no superpuestos de tamaño máximo. El objetivo aquí es ejecutar tantas tareas como sea posible, es decir, maximizar el rendimiento . Es equivalente a encontrar el conjunto independiente máximo en un gráfico de intervalos .

Una generalización del problema considera máquinas/recursos. ^[1] Aquí el objetivo es encontrar subconjuntos compatibles cuya unión sea la más grande. ${\displaystyle k>1}$ ${\displaystyle k}$

En una versión mejorada del problema, los intervalos se dividen en grupos. Un subconjunto de intervalos es compatible si no hay dos intervalos que se superpongan y, además, no hay dos intervalos que pertenezcan al mismo grupo (es decir, el subconjunto contiene como máximo un único representante de cada grupo). Cada grupo de intervalos corresponde a una única tarea y representa varios intervalos alternativos en los que se puede ejecutar.

El problema de decisión de programación de intervalos de grupo (GISDP) consiste en decidir si existe un conjunto compatible en el que estén representados todos los grupos. El objetivo es ejecutar una única tarea representativa de cada grupo. GISDPk es una versión restringida de GISDP en la que el número de intervalos en cada grupo es como máximo k .

El problema de maximización de la programación de intervalos de grupo (GISMP) consiste en encontrar el conjunto compatible más grande (un conjunto de representantes no superpuestos de tamaño máximo). El objetivo es ejecutar una tarea representativa de la mayor cantidad posible de grupos. GISMPk es una versión restringida de GISMP en la que el número de intervalos en cada grupo es como máximo k . Este problema se suele denominar JISPk, donde J significa Job .

GISMP es el problema más general; los otros dos problemas pueden verse como casos especiales del mismo:

• ISMP es el caso especial en el que cada tarea pertenece a su propio grupo (es decir, es igual a GISMP1).
• GISDP es el problema de decidir si el máximo es exactamente igual al número de grupos.

Todos estos problemas se pueden generalizar añadiendo un peso a cada intervalo, que represente la ganancia de ejecutar la tarea en ese intervalo. El objetivo es maximizar el peso total.

Todos estos problemas son casos especiales de programación de una sola máquina , ya que suponen que todas las tareas deben ejecutarse en un solo procesador. La programación de una sola máquina es un caso especial de programación óptima de trabajos .

Maximización de la programación de intervalo único

La programación de intervalo único se refiere a la creación de una programación de intervalos en la que ningún intervalo se superpone.

Sin ponderar

Varios algoritmos, que pueden parecer prometedores a primera vista, en realidad no encuentran la solución óptima: ^[2]

• Seleccionar los intervalos que comienzan más temprano no es una solución óptima, porque si el intervalo más temprano resulta ser muy largo, aceptarlo nos haría rechazar muchas otras solicitudes más cortas.
• Seleccionar los intervalos más cortos o seleccionar intervalos con menos conflictos tampoco es óptimo.

El siguiente algoritmo codicioso , llamado programación de fecha límite más temprana primero , encuentra la solución óptima para la programación de intervalo único no ponderado:

1. Seleccione el intervalo, x , con el tiempo de finalización más temprano .
2. Eliminar x y todos los intervalos que intersecan x del conjunto de intervalos candidatos.
3. Repita hasta que el conjunto de intervalos candidatos esté vacío.

Siempre que seleccionamos un intervalo en el paso 1, es posible que tengamos que eliminar muchos intervalos en el paso 2. Sin embargo, todos estos intervalos necesariamente cruzan el tiempo de finalización de x y, por lo tanto, todos se cruzan entre sí. Por lo tanto, como máximo 1 de estos intervalos puede estar en la solución óptima. Por lo tanto, para cada intervalo en la solución óptima, hay un intervalo en la solución voraz. Esto demuestra que el algoritmo voraz de hecho encuentra una solución óptima.

Una explicación más formal se da mediante un argumento de carga .

El algoritmo voraz se puede ejecutar en un tiempo O( n log n ), donde n es el número de tareas, utilizando un paso de preprocesamiento en el que las tareas se ordenan por sus tiempos de finalización.

Ponderado

Los problemas que involucran programación de intervalos ponderados son equivalentes a encontrar un conjunto independiente de peso máximo en un gráfico de intervalos . Dichos problemas pueden resolverse en tiempo polinomial. ^[3]

Suponiendo que los vectores están ordenados desde el tiempo de finalización más temprano hasta el más tardío, el siguiente pseudocódigo determina el peso máximo de un cronograma de intervalo único en un tiempo Θ(n):

// Los vectores ya están ordenados desde el tiempo de finalización más temprano hasta el más tardío.int v [ numOfVectors + 1 ]; // lista de vectores de intervalo    int w [ numOfVectors + 1 ]; // w[j] es el peso de v[j].    int p [ numOfVectors + 1 ]; // p[j] es el número de vectores que terminan antes de que comience v[j].    int M [ numOfVectors + 1 ];    int finalSchedule []; // v[0] no existe y el primer vector de intervalo se asigna a v[1].w [ 0 ] = 0 ; p [ 0 ] = 0 ; M [ 0 ] = 0 ;        //El siguiente código determina el valor de M para cada vector.// El peso máximo de la programación es igual a M[numOfVectors].para ( int i = 1 ; i < numOfVectors + 1 ; i ++ ) {            M [ i ] = máx ( w [ i ] + M [ p [ i ]], M [ i - 1 ]);       }// Función para construir el cronograma óptimohorario ( j ) {   si ( j == 0 ) { devolver ; }       de lo contrario si ( w [ j ] + M [ p [ j ]] >= M [ j - 1 ]){         anteponer ( v [ j ], finalSchedule ); // antepone v[j] a la programación.   horario ( p [ j ]); } de lo contrario { programar ( j - 1 ); }      }

^[4]

Ejemplo

Si tenemos los siguientes 9 vectores ordenados por tiempo de finalización, con los pesos encima de cada intervalo correspondiente, podemos determinar cuáles de estos vectores están incluidos en nuestra tabla de peso máximo que solo contiene un subconjunto de los siguientes vectores.

Aquí, ingresamos nuestro vector final (donde j=9 en este ejemplo) en nuestra función de programación desde el bloque de código anterior. Realizamos las acciones de la tabla a continuación hasta que j se establece en 0, momento en el cual, solo incluimos en nuestra programación final los intervalos encontrados que cumplieron con el requisito. Esta programación final es la programación con el peso máximo. ${\textstyle w[j]+M[p[j]]\geq M[j-1]}$

Decisión de programación de intervalos grupales

NP-completo cuando algunos grupos contienen 3 o más intervalos

GISDPk es NP-completo cuando , ^[5] incluso cuando todos los intervalos tienen la misma longitud. ^[6] Esto se puede demostrar mediante una reducción de la siguiente versión del problema de satisfacibilidad booleano , que se demostró ^[7] que es NP-completo al igual que la versión sin restricciones. ${\displaystyle k\geq 3}$

Sea un conjunto de variables booleanas. Sea un conjunto de cláusulas sobre X tales que (1) cada cláusula en C tiene como máximo tres literales y (2) cada variable está restringida a aparecer una o dos veces positivamente y una vez negativamente en total en C. Decida si existe una asignación a variables de X tal que cada cláusula en C tenga al menos un literal verdadero. ${\displaystyle X=\{x_{1},x_{2},\dots ,x_{p}\}}$ ${\displaystyle C=\{c_{1},c_{2},\dots ,c_{q}\}}$

Dada una instancia de este problema de satisfacibilidad, construya la siguiente instancia de GISDP. Todos los intervalos tienen una longitud de 3, por lo que es suficiente representar cada intervalo por su tiempo de inicio:

• Para cada variable (para i = 1,..., p ), cree un grupo con dos intervalos: uno que comience en (que representa la asignación ) y otro que comience en (que representa la asignación ). ${\displaystyle x_{i}}$ ${\displaystyle 50i-10}$ ${\displaystyle x_{i}=\mathrm {false} }$ ${\displaystyle 50i+10}$ ${\displaystyle x_{i}=\mathrm {true} }$
• Para cada cláusula (para j = 1,..., q ), cree un grupo con los siguientes intervalos: ${\displaystyle c_{j}}$
  • Para cada variable que aparece positivamente por primera vez en C (un intervalo que comienza en ) . ${\displaystyle x_{i}}$ ${\displaystyle 50i-12}$
  • Para cada variable que aparece positivamente por segunda vez en C , un intervalo que comienza en . Nótese que ambos intervalos intersecan el intervalo , asociado con . ${\displaystyle x_{i}}$ ${\displaystyle 50i-8}$ ${\displaystyle 50i-10}$ ${\displaystyle x_{i}=\mathrm {false} }$
  • Para cada variable que aparece negativamente, se crea un intervalo que comienza en . Este intervalo interseca el intervalo asociado con . ${\displaystyle x_{i}}$ ${\displaystyle 50i+8}$ ${\displaystyle 50i+10}$ ${\displaystyle x_{i}={\text{true}}}$

Obsérvese que no hay superposición entre intervalos en grupos asociados a diferentes cláusulas. Esto está garantizado porque una variable aparece como máximo dos veces de forma positiva y una de forma negativa.

El GISDP construido tiene una solución factible (es decir, una planificación en la que cada grupo está representado), si y solo si el conjunto dado de cláusulas booleanas tiene una asignación satisfactoria. Por lo tanto, GISDP3 es NP-completo, y también lo es GISDPk para cada . ${\displaystyle k\geq 3}$

Polinomio cuando todos los grupos contienen como máximo 2 intervalos

GISDP2 se puede resolver en tiempo polinomial mediante la siguiente reducción al problema de 2-satisfacibilidad : ^[6]

• Para cada grupo creo dos variables, que representan sus dos intervalos: y . ${\displaystyle x_{i}}$ ${\displaystyle y_{i}}$
• Para cada grupo i , cree las cláusulas: y , que representan la afirmación de que se debe seleccionar exactamente uno de estos dos intervalos. ${\displaystyle x_{i}\cup y_{i}}$ ${\displaystyle \neg {x_{i}}\cup \neg {y_{i}}}$
• Para cada dos intervalos que se intersecan (es decir, y ), cree la cláusula: , que representa la afirmación de que, como máximo, se debe seleccionar uno de estos dos intervalos. ${\displaystyle x_{i}}$ ${\displaystyle y_{j}}$ ${\displaystyle \neg {x_{i}}\cup \neg {y_{j}}}$

Esta construcción contiene como máximo O( n ² ) cláusulas (una por cada intersección entre intervalos, más dos por cada grupo). Cada cláusula contiene 2 literales. La satisfacibilidad de tales fórmulas se puede decidir en tiempo lineal en el número de cláusulas (ver 2-SAT ). Por lo tanto, el GISDP2 se puede resolver en tiempo polinomial.

Maximización de la programación de intervalos grupales

MaxSNP-completo cuando algunos grupos contienen 2 o más intervalos

GISMPk es NP-completo incluso cuando . ^[8] ${\displaystyle k\geq 2}$

Además, GISMPk es MaxSNP -completo, es decir, no tiene un PTAS a menos que P=NP. Esto se puede demostrar mostrando una reducción que preserva la aproximación de MAX 3-SAT-3 a GISMP2. ^[8]

Aproximación polinómica de 2 ejes

El siguiente algoritmo voraz encuentra una solución que contiene al menos la mitad del número óptimo de intervalos: ^[8]

1. Seleccione el intervalo, x , con el tiempo de finalización más temprano .
2. Eliminar x , y todos los intervalos que intersecan x , y todos los intervalos en el mismo grupo de x , del conjunto de intervalos candidatos.
3. Continúe hasta que el conjunto de intervalos candidatos esté vacío.

Una explicación formal se da mediante un argumento de carga .

El factor de aproximación de 2 es estricto. Por ejemplo, en la siguiente instancia de GISMP2:

• Grupo #1: {[0..2], [4..6]}
• Grupo #2: {[1..3]}

El algoritmo codicioso selecciona solo 1 intervalo [0..2] del grupo n.° 1, mientras que una programación óptima es seleccionar [1..3] del grupo n.° 2 y luego [4..6] del grupo n.° 1.

Un algoritmo de aproximación más general logra una aproximación de dos factores para el caso ponderado. ^[3]

Algoritmos de aproximación basados ​​en LP

Utilizando la técnica de relajación de programación lineal , es posible aproximar la planificación óptima con factores de aproximación ligeramente mejores. La relación de aproximación del primer algoritmo de este tipo es asintóticamente 2 cuando k es grande, pero cuando k=2 el algoritmo logra una relación de aproximación de 5/3. ^{[8] El factor de aproximación para} un valor k arbitrario se mejoró posteriormente a 1,582. ^[9]

Problemas relacionados

Un problema de programación de intervalos se puede describir mediante un gráfico de intersección , donde cada vértice es un intervalo y hay una arista entre dos vértices si y solo si sus intervalos se superponen. En esta representación, el problema de programación de intervalos es equivalente a encontrar el conjunto independiente máximo en este gráfico de intersección. Encontrar un conjunto independiente máximo es NP-hard en grafos generales, pero se puede hacer en tiempo polinomial en el caso especial de grafos de intersección (ISMP).

Un problema de programación de intervalos de grupo (GISMPk) se puede describir mediante un gráfico de intersección de intervalos similar, con aristas adicionales entre cada dos intervalos del mismo grupo, es decir, esta es la unión de aristas de un gráfico de intervalos y un gráfico que consiste en n camarillas disjuntas de tamaño k .

Variaciones

Una clase importante de algoritmos de programación es la clase de algoritmos de prioridad dinámica. Cuando ninguno de los intervalos se superpone, la solución óptima es trivial. La solución óptima para la versión no ponderada se puede encontrar con la programación de la fecha límite más temprana primero . La programación de intervalos ponderados es una generalización en la que se asigna un valor a cada tarea ejecutada y el objetivo es maximizar el valor total. La solución no necesita ser única.

El problema de programación de intervalos es unidimensional: solo la dimensión temporal es relevante. El problema del conjunto disjunto máximo es una generalización a dos o más dimensiones. Esta generalización también es NP-completa.

Otra variante es la asignación de recursos, en la que se programa un conjunto de intervalos s utilizando recursos k de manera que k se minimice. Es decir, se deben programar todos los intervalos, pero el objetivo es minimizar el uso de recursos.

Otra variación es cuando hay m procesadores en lugar de un solo procesador. Es decir, m tareas diferentes pueden ejecutarse en paralelo. Véase programación de máquinas idénticas .

La programación de una sola máquina también es un problema muy similar.

Fuentes

1. Kolen, A. (2007). "Programación de intervalos: una encuesta". Naval Research Logistics . 54 (5): 530–543. doi : 10.1002/nav.20231 . S2CID  15288326.
2. Kleinberg, Jon; Tardos, Éva (2006). Diseño de algoritmos . Pearson/Addison-Wesley. ISBN 978-0-321-29535-4.
3. Bar-Noy, Amotz; Bar-Yehuda, Reuven; Freund, Ari; (Seffi) Naor, Joseph; Schieber, Baruch (1 de septiembre de 2001). "Un enfoque unificado para aproximar la asignación y programación de recursos". Revista de la ACM . 48 (5): 1069–1090. doi :10.1145/502102.502107. ISSN  0004-5411. S2CID  12329294.
4. Kleinberg, Jon; Tardós, Eva (2006). Diseño de algoritmos (1ª ed.). Pearson. pag. 254.ISBN​ 9780321295354.
5. Nakajima, K.; Hakimi, SL (1982). "Resultados de complejidad para la programación de tareas con tiempos de inicio discretos". Journal of Algorithms . 3 (4): 344. doi :10.1016/0196-6774(82)90030-X.
6. Mark Keil, J. (1992). "Sobre la complejidad de la programación de tareas con tiempos de inicio discretos". Operations Research Letters . 12 (5): 293–295. doi :10.1016/0167-6377(92)90087-j.
7. Papadimitriou, Christos H.; Steiglitz, Kenneth (julio de 1998). Optimización combinatoria: algoritmos y complejidad . Dover. ISBN 978-0-486-40258-1.
8. Spieksma, FCR (1999). "Sobre la aproximabilidad de un problema de programación de intervalos". Journal of Scheduling . 2 (5): 215–227. CiteSeerX 10.1.1.603.5538 . doi :10.1002/(sici)1099-1425(199909/10)2:5<215::aid-jos27>3.0.co;2-y. Citando a Kolen en comunicación personal
9. Chuzhoy, Julia ; Ostrovsky, Rafail ; Rabani, Yuval (2006). "Algoritmos de aproximación para el problema de selección de intervalos de trabajo y problemas de programación relacionados". Matemáticas de la investigación de operaciones . 31 (4): 730–738. CiteSeerX 10.1.1.105.2578 . doi :10.1287/moor.1060.0218.