Programación de intervalos

La programación de intervalos es una clase de problemas en ciencias de la computación , 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 necesita ser procesada por alguna máquina (o, de manera equivalente, programada en algún recurso). Por ejemplo, la tarea A puede ejecutarse de 2:00 a 5:00, la tarea B puede ejecutarse de 4:00 a 10:00 y la tarea C puede ejecutarse de 9:00 a 11:00. Un subconjunto de intervalos es compatible si no se superponen dos intervalos 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) es encontrar un 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 un conjunto independiente máximo en un gráfico de intervalo .

Una generalización del problema considera máquinas / recursos. ^[1] Aquí el objetivo es encontrar subconjuntos compatibles cuya unión sea la mayor.${\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 se superponen dos intervalos 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) es decidir si existe un conjunto compatible en el que estén representados todos los grupos. 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) es encontrar un 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 a menudo se denomina JISPk, donde J significa Job .

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 representa la ganancia de ejecutar la tarea en ese intervalo. Entonces, el objetivo es maximizar el peso total.

Todos estos problemas son casos especiales de programación de una sola máquina , ya que asumen 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 de trabajos óptima .

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

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 antes 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.
• Tampoco es óptimo seleccionar los intervalos más cortos o seleccionar los intervalos con la menor cantidad de conflictos.

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

1. Seleccione el intervalo, x , con la hora de finalización más temprana .
2. Quite 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í (ver figura). 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 codiciosa. Esto demuestra que el algoritmo codicioso encuentra una solución óptima.

Una explicación más formal viene dada por 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 ordenan por sus tiempos de finalización.

Ponderado

Cuando los intervalos tienen ponderaciones, el problema es equivalente a encontrar un conjunto independiente de ponderación máxima en una gráfica de intervalo . Se puede resolver en tiempo polinomial. ^[3]

Decisión de programación de intervalo de grupo

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

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

Sea un conjunto de variables booleanas. Vamos a ser un conjunto de cláusulas sobre X tal que (1) cada cláusula en C tiene a lo sumo tres literales y (2) cada variable se limita a aparecer una vez o dos veces positivamente y una vez negativamente general en C . Decida si hay una asignación a las variables de X tal que cada cláusula en C tenga al menos un literal verdadero.${\displaystyle X=\{x_{1},x_{2},...,x_{p}\}}$${\displaystyle C=\{c_{1},c_{2},...,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 hora de inicio:

• Para cada variable (para i = 1, ..., p ), cree un grupo con dos intervalos: uno que comienza en (que representa la asignación ) y otro que comienza en (que representa la asignación ).${\displaystyle x_{i}}$${\displaystyle 50i-10}$${\displaystyle x_{i}=false}$${\displaystyle 50i+10}$${\displaystyle x_{i}=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}=false}$
  • Para cada variable que aparece negativamente, un intervalo que comienza en . Este intervalo se cruza con el intervalo asociado con .${\displaystyle x_{i}}$${\displaystyle 50i+8}$${\displaystyle 50i+10}$${\displaystyle x_{i}=true}$

Tenga en cuenta que no hay superposición entre intervalos en grupos asociados con diferentes cláusulas. Esto está asegurado ya que una variable aparece como máximo dos veces de forma positiva y una vez de forma negativa.

El GISDP construido tiene una solución factible (es decir, una programació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 todos .${\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 : ^[5]

• Por cada grupo i crear 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 debe seleccionarse exactamente uno de estos dos intervalos.${\displaystyle x_{i}\cup y_{i}}$${\displaystyle \neg {x_{i}}\cup \neg {y_{i}}}$
• Para cada dos intervalos de intersección (es decir, y ) cree la cláusula:, que representa la afirmación de que, como máximo, debe seleccionarse 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 cláusulas O ( n ² ) (una para cada intersección entre intervalos, más dos para cada grupo). Cada cláusula contiene 2 literales. La satisfacibilidad de tales fórmulas se puede decidir en el 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 de grupo

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

GISMPk es NP-completo incluso cuando . ^[7]${\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 conserva la aproximación de MAX 3-SAT-3 a GISMP2. ^[7]

Aproximación polinomial 2

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

1. Seleccione el intervalo, x , con la hora de finalización más temprana .
2. Quite 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 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 n. ° 1: {[0..2], [4..6]}
• Grupo n. ° 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

Usando 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 alcanza una relación de aproximación de 5/3. ^[7] El factor de aproximación para k arbitrario se mejoró posteriormente a 1,582. ^[8]

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 un borde 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-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 intervalo de grupo (GISMPk) se puede describir mediante un gráfico de intersección de intervalo similar, con bordes adicionales entre cada dos intervalos del mismo grupo, es decir, esta es la unión de bordes 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 de 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 de intervalos es unidimensional; solo la dimensión de tiempo es relevante. El problema del conjunto disjunto máximo 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 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, pueden ejecutarse m diferentes tareas en paralelo. Consulte la programación de máquinas idénticas .

Fuentes

1. Kolen, A. (2007). "Programación de intervalos: una encuesta". Logística de investigación naval . 54 (5): 530–543.
2. Kleinberg, Jon; Tardos, Éva (2006). Diseño de algoritmos . 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 . 
4. Nakajima, K .; Hakimi, SL (1982). "Resultados de complejidad para la programación de tareas con tiempos de inicio discretos". Revista de algoritmos . 3 (4): 344. doi : 10.1016 / 0196-6774 (82) 90030-X .
5. 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 .
6. Papadimitriou, Christos H .; Steiglitz, Kenneth (julio de 1998). Optimización combinatoria: algoritmos y complejidad . Dover. ISBN 978-0-486-40258-1.
7. Spieksma, FCR (1999). "Sobre la aproximación de un problema de programación de 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
8. Chuzhoy, J .; Ostrovsky, R .; Rabani, Y. (2006). "Algoritmos de aproximación para el problema de selección de intervalo de trabajo y problemas de programación relacionados". Matemáticas de la investigación operativa . 31 (4): 730. CiteSeerX 10.1.1.105.2578 . doi : 10.1287 / moor.1060.0218 .