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 del 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 debe ser procesada por alguna máquina (o, de manera equivalente, 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 de tamaño máximo que no se superpongan. El objetivo aquí es ejecutar tantas tareas como sea posible, es decir, maximizar el rendimiento . Es equivalente a encontrar un conjunto máximo independiente 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 a intervalos de grupos (GISDP) consiste en decidir si existe un conjunto compatible en el que todos los grupos estén representados. El objetivo aquí 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 de tamaño máximo que no se superpongan. El objetivo aquí es ejecutar una tarea representativa de tantos grupos como sea posible. 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 suele denominarse JISPk, donde J significa Trabajo .

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

• 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 agregando un peso para cada intervalo, que represente el beneficio de ejecutar la tarea en ese intervalo. Entonces, el objetivo es maximizar el peso total.

Todos estos problemas son casos especiales de programación en una sola máquina , ya que suponen que todas las tareas deben ejecutarse en un único 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 no se superponen intervalos.

no ponderado

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 la menor cantidad de conflictos tampoco es óptimo.

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

1. Seleccione el intervalo, x , con el tiempo de finalización más temprano .
2. Elimine x y todos los intervalos que se cruzan con 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 final 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 tanto, para cada intervalo en la solución óptima, hay un intervalo en la solución codiciosa. Esto demuestra que el algoritmo codicioso realmente encuentra una solución óptima.

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

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

Ponderado

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

Suponiendo que los vectores están ordenados desde la hora de finalización más temprana hasta la más tardía, el siguiente pseudocódigo determina el peso máximo de una programación de intervalo único en tiempo Θ(n):

// Los vectores ya están ordenados desde la hora de finalización más temprana hasta la más tardía.int v [ númDeVectores + 1 ]; // lista de vectores de intervalo    int w [ númDeVectores + 1 ]; // w[j] es el peso de v[j].    int p [ númDeVectores + 1 ]; // p[j] es el número de vectores que terminan antes de que comience v[j].    int M [ númDeVectores + 1 ];    int finalProgramación []; // 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 del cronograma es igual a M[numOfVectors].for ( int i = 1 ; i < numDeVectores + 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 ) { retorno ; }       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 ]); } más { programar ( j - 1 ); }      }

^[4]

Ejemplo

Si tenemos los siguientes 9 vectores ordenados por hora de finalización, con los pesos encima de cada intervalo correspondiente, podemos determinar cuáles de estos vectores están incluidos en nuestro programa 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 en la siguiente tabla hasta que j se establece en 0, momento en el cual, solo incluimos en nuestro cronograma final los intervalos encontrados que cumplieron con el requisito. Este horario final es el horario con el peso máximo. ${\textstyle w[j]+M[p[j]]\geq M[j-1]}$

Decisión de programación de intervalos de grupo

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 booleana , que se demostró que ^[7] 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 tal que (1) cada cláusula en C tenga como máximo tres literales y (2) cada variable esté restringida a aparecer una o dos veces positivamente y una vez negativamente en general 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}\}}$

Dado un ejemplo de este problema de satisfacibilidad, construya el siguiente ejemplo de GISDP. Todos los intervalos tienen una longitud de 3, por lo que es suficiente representar cada intervalo por su hora 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 represente 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 . Tenga en cuenta que ambos intervalos se cruzan con el intervalo asociado con . ${\displaystyle x_{i}}$ ${\displaystyle 50i-8}$ ${\displaystyle 50i-10}$ ${\displaystyle x_{i}=\mathrm {false} }$
  • Para cada variable que aparece negativamente, 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}}}$

Tenga en cuenta que no hay superposición entre intervalos en grupos asociados con diferentes cláusulas. Esto está garantizado porque una variable aparece como máximo dos veces positivamente y una vez negativamente.

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

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

GISDP2 se puede resolver en tiempo polinómico 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}}}$
• Por cada dos intervalos que se cruzan (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 para cada intersección entre intervalos, más dos para cada grupo). Cada cláusula contiene 2 literales. La satisfacibilidad de este tipo de fórmulas se puede decidir en el tiempo lineal en el número de cláusulas (ver 2-SAT ). Por tanto, el GISDP2 se puede resolver en tiempo polinomial.

Maximización de la programación de intervalos de grupo

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 del polinomio 2

El siguiente algoritmo codicioso 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. Elimine x y todos los intervalos que intersectan a 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 viene dada por un argumento de carga .

El factor de aproximación de 2 es ajustado. 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 #1, mientras que una programación óptima es seleccionar [1..3] del grupo #2 y luego [4..6] del grupo #1.

Un algoritmo de aproximación más general logra una aproximación de 2 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 programació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 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 equivale a encontrar el conjunto independiente máximo en este gráfico de intersección. Encontrar un conjunto máximo independiente es NP-difícil en los gráficos generales, pero se puede hacer en tiempo polinomial en el caso especial de los gráficos 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 intervalo y un gráfico que consta de n disjuntos. camarillas 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. El óptimo para la versión no ponderada se puede encontrar con la primera programación con la fecha límite más temprana . 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 tiene por qué ser única.

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

Otra variación es la asignación de recursos, en la que se programa un conjunto de intervalos s utilizando recursos k de modo 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, se pueden ejecutar m tareas diferentes en paralelo. Consulte 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". Logística de Investigación Naval . 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, José; 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 programar tareas con tiempos de inicio discretos". Revista de algoritmos . 3 (4): 344. doi :10.1016/0196-6774(82)90030-X.
6. Mark Keil, J. (1992). "Sobre la complejidad de programar tareas con tiempos de inicio discretos". Cartas de investigación operativa . 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 proximidad de un problema de programación a intervalos". Diario de programación . 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, Rafael ; 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.