Programación por intervalos

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 llevaría a rechazar muchas otras solicitudes más cortas.
• Seleccionar los intervalos más cortos o seleccionar los intervalos con menos conflictos tampoco es lo óptimo.

El siguiente algoritmo voraz , llamado planificación con fecha límite más temprana primero , encuentra la solución óptima para la planificación de intervalo único sin ponderación:

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 el proceso hasta que el conjunto de intervalos candidatos esté vacío.

Al seleccionar un intervalo en el paso 1, es posible que debamos eliminar varios intervalos en el paso 2. Sin embargo, todos estos intervalos necesariamente cruzan el tiempo de finalización de x , y por lo tanto, se cruzan entre sí. En consecuencia, como máximo uno de estos intervalos puede estar en la solución óptima. Por lo tanto, por cada intervalo en la solución óptima, existe un intervalo en la solución voraz. Esto demuestra que el algoritmo voraz efectivamente encuentra una solución óptima.

Una explicación más formal la proporciona 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.

Los problemas que implican la programación de intervalos ponderados son equivalentes a encontrar un conjunto independiente de peso máximo en un grafo 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 una programación de intervalo único en 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 intervaloint w [ numOfVectors + 1 ]; // w[j] es el peso para 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 del cronograma es igual a M[numOfVectors].para ( int i = 1 ; i < numOfVectors + 1 ; i ++ ) {M [ i ] = max ( w [ i ] + M [ p [ i ]], M [ i - 1 ]);}// Función para construir el cronograma óptimohorario ( j ) {Si ( j == 0 ) { regresar ; }else if ( w [ j ] + M [ p [ j ]] >= M [ j - 1 ]){anteponer ( v [ j ], finalSchedule ); // antepone v[j] a la programación.horario ( p [ j ]);} else { 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 nuestro programa de peso máximo que solo contiene un subconjunto de los siguientes vectores.

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

GISDPk es NP-completo cuando${\displaystyle k\geq 3}$, ^{[ 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ó ^{[ 7 ]} que es NP-completa al igual que la versión no restringida.

Dejar${\displaystyle X=\{x_{1},x_{2},\dots ,x_{p}\}}$Sea un conjunto de variables booleanas.${\displaystyle C=\{c_{1},c_{2},\dots ,c_{q}\}}$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 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.

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 tiempo de inicio:

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

Cabe destacar que no hay solapamiento entre los intervalos de los grupos asociados a distintas cláusulas. Esto se garantiza, ya que una variable aparece como máximo dos veces en sentido positivo y una vez en sentido negativo.

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 cada${\displaystyle k\geq 3}$.

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:${\displaystyle x_{i}}$y${\displaystyle y_{i}}$.
• Para cada grupo i , cree las cláusulas:${\displaystyle x_{i}\cup y_{i}}$y${\displaystyle \neg {x_{i}}\cup \neg {y_{i}}}$, que representan la afirmación de que se debe seleccionar exactamente uno de estos dos intervalos.
• Por cada dos intervalos que se intersecan (es decir,${\displaystyle x_{i}}$y${\displaystyle y_{j}}$) crear la cláusula:${\displaystyle \neg {x_{i}}\cup \neg {y_{j}}}$, que representan la afirmación de que se debe seleccionar como máximo uno de estos dos intervalos.

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 dos literales. La satisfacibilidad de dichas fórmulas se puede determinar en tiempo lineal con respecto al número de cláusulas (véase 2-SAT ). Por lo tanto, el GISDP2 se puede resolver en tiempo polinomial.

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

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 ]}

El siguiente algoritmo voraz encuentra una solución que contiene al menos 1/2 del número óptimo de intervalos: ^{[ 8 ]}

1. Seleccione el intervalo, x , con el tiempo de finalización más temprano .
2. Eliminar x , todos los intervalos que intersecan x , y todos los intervalos del 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 acusación .

El factor de aproximación de 2 es ajustado. Por ejemplo, en el siguiente caso de GISMP2:

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

El algoritmo voraz 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 alcanza una aproximación de 2 factores para el caso ponderado. ^{[ 3 ]}

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 razó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 razón de aproximación de 5/3. ^{[ 8 ]} El factor de aproximación para un k arbitrario se mejoró posteriormente a 1,582. ^{[ 9 ]}