Programación del tiempo de procesamiento más largo primero

Algoritmo para la programación de tareas

El algoritmo LPT (Longest-processing-time-first) es un algoritmo voraz para la programación de trabajos . La entrada del algoritmo es un conjunto de trabajos , cada uno de los cuales tiene un tiempo de procesamiento específico. También hay un número m que especifica la cantidad de máquinas que pueden procesar los trabajos. El algoritmo LPT funciona de la siguiente manera:

1. Ordene los trabajos en orden descendente de su tiempo de procesamiento, de modo que el trabajo con el tiempo de procesamiento más largo sea el primero.
2. Programe cada trabajo de esta secuencia en una máquina en la que la carga actual (=tiempo total de procesamiento de los trabajos programados) sea la más pequeña.

El paso 2 del algoritmo es básicamente el algoritmo de programación de listas (LS). La diferencia es que LS recorre los trabajos en un orden arbitrario, mientras que LPT los ordena por adelantado en orden descendente de tiempo de procesamiento.

LPT fue analizado por primera vez por Ronald Graham en la década de 1960 en el contexto del problema de programación de máquinas idénticas . ^[1] Posteriormente, se aplicó a muchas otras variantes del problema.

LPT también se puede describir de una manera más abstracta, como un algoritmo para la partición de números de múltiples vías . La entrada es un conjunto S de números y un entero positivo m ; la salida es una partición de S en m subconjuntos. LPT ordena la entrada de mayor a menor y coloca cada entrada a su vez en la parte con la suma más pequeña hasta el momento.

Ejemplos

Si el conjunto de entrada es S = {4, 5, 6, 7, 8} y m = 2, entonces la partición resultante es {8, 5, 4}, {7, 6}. Si m = 3, entonces la partición de 3 vías resultante es {8}, {7, 4}, {6, 5}.

Propiedades

Es posible que LPT no encuentre la partición óptima. Por ejemplo, en el caso anterior, la partición óptima es {8,7}, {6,5,4}, donde ambas sumas son iguales a 15. Sin embargo, su suboptimalidad está limitada tanto en el peor de los casos como en el caso promedio; consulte Garantías de rendimiento a continuación.

El tiempo de ejecución de LPT está dominado por la clasificación, que toma un tiempo O( n log n ), donde n es el número de entradas.

LPT es monótona en el sentido de que, si uno de los números de entrada aumenta, la función objetivo (la suma más grande o la suma más pequeña de un subconjunto en la salida) aumenta débilmente. ^[2] Esto contrasta con el algoritmo Multifit .

Garantías de rendimiento: máquinas idénticas

Cuando se utiliza para la programación de máquinas idénticas , LPT alcanza las siguientes relaciones de aproximación.

Suma máxima en el peor de los casos

En el peor de los casos, la suma más grande en la partición codiciosa es en la mayoría de los casos la suma más grande óptima (mínima). ^{[3] [a]} ${\displaystyle {\frac {4}{3}}}$

Un análisis más detallado produce un factor de veces la suma máxima óptima (mínima). ^{[1] [4]} (por ejemplo, cuando m = 2 esta relación es ). ^[b] ${\displaystyle {\frac {4m-1}{3m}}={\frac {4}{3}}-{\frac {1}{3m}}}$ ${\displaystyle 7/6\approx 1.167}$

El factor es estricto. Supongamos que hay entradas (donde m es par): . Entonces el algoritmo voraz devuelve: ${\displaystyle {\frac {4m-1}{3m}}}$ ${\displaystyle 2m+1}$ ${\displaystyle 2m-1,2m-1,2m-2,2m-2,\ldots ,m+1,m+1,m,m,m}$

• ${\displaystyle 2m-1,m,m}$
• ${\displaystyle 2m-1,m}$
• ${\displaystyle 2m-2,m+1}$
• ${\displaystyle 2m-2,m+1}$,
• ...
• ${\displaystyle 3m/2,3m/2-1}$
• ${\displaystyle 3m/2,3m/2-1}$

con un máximo de , pero la partición óptima es: ${\displaystyle 4m-1}$

• ${\displaystyle m,m,m}$
• ${\displaystyle 2m-1,m+1}$
• ${\displaystyle 2m-1,m+1}$
• ${\displaystyle 2m-2,m+2}$
• ${\displaystyle 2m-2,m+2}$
• ...
• ${\displaystyle 3m/2,3m/2}$

con un máximo de . ${\displaystyle 3m}$

Consideración de entrada

Un análisis aún más detallado tiene en cuenta el número de entradas en la parte de suma máxima.

1. En cada parte de la partición codiciosa, el j -ésimo número más alto es como máximo . ^[5] ${\displaystyle OPT/j}$
2. Supongamos que, en la parte codiciosa P con la suma máxima, hay L entradas. Entonces, la razón de aproximación del algoritmo codicioso es . ^[4] Es estricto para L ≥ 3 (para L = 3, obtenemos el factor general ). Demostración . ^[5] Denotemos los números en P por x ₁ ,..., x _L . Antes de que x _L se insertara en P , su suma era la más pequeña. Por lo tanto, la suma promedio por parte es al menos la suma x ₁ +...+ x _L-1 + x _L / m . La suma máxima óptima debe ser al menos la suma promedio. En contraste, la suma codiciosa es x ₁ +...+ x _L-1 + x _L. Entonces la diferencia es como máximo (1-1/ m ) x _L , que por (1) es como máximo (1-1/ m )*OPT/ L . Entonces la razón es como máximo (1 + 1/ L - 1/ Lm ). ${\displaystyle {\frac {L+1}{L}}-{\frac {1}{Lm}}=1+{\frac {1}{L}}-{\frac {1}{Lm}}}$ ${\displaystyle {\frac {4}{3}}-{\frac {1}{3m}}}$

Suma mínima en el peor de los casos

En el peor de los casos, la suma más pequeña en la partición devuelta es al menos veces la suma más pequeña óptima (máxima). ^[6] ${\displaystyle {\frac {3}{4}}}$

Prueba

La prueba es por contradicción. Consideremos un contraejemplo mínimo , es decir, un contraejemplo con un m mínimo y la menor cantidad de números de entrada. Denotemos la partición voraz por P ₁ ,...,P _m , y la partición óptima por Q ₁ ,...,Q _m . Algunas propiedades de un contraejemplo mínimo son:

• La suma mínima en la partición óptima es 4, y la suma mínima en la partición codiciosa es menor que 3 (esto es solo normalización, no tiene pérdida de generalidad).
• La suma máxima en la partición codiciosa es mayor que 4 (ya que la suma total en ambas particiones es la misma y es al menos 4 m ).
• Si suma(P _i )≥3 para algún contenedor voraz P _i , entonces P _i no está dominado por ningún contenedor óptimo Q _j . Demostración : si P _i está dominado por Q _j , entonces podemos construir un contraejemplo más pequeño disminuyendo m a m -1 y eliminando los elementos en P _i . La suma mínima en la partición voraz permanece menor que 3. En la partición óptima, los elementos en P _i pueden reemplazarse por sus elementos dominantes en Q _j , por lo que la suma mínima permanece al menos en 4.
• Si suma(P _i )≥3 para algún contenedor voraz P _i , entonces P _i contiene al menos dos números. Demostración : si P _i contiene solo un número x, entonces está dominado por el contenedor óptimo Q _j que contiene x. Supongamos que alguna entrada x es al menos 3, y el algoritmo voraz la coloca en algún P _i . Entonces, dado que hay un conjunto con suma menor que 3, el algoritmo voraz no colocará ninguna otra entrada en P _i , contradiciendo el lema anterior.
• Cada contenedor voraz P _i contiene como máximo una entrada débilmente mayor que 3/2. Demostración : Sea P _i el primer contenedor voraz al que se le asignan dos de esas entradas. Como las entradas se asignan en orden descendente, P _i es el primer contenedor voraz al que se le asignan dos entradas. Esto significa que debe contener las dos entradas más pequeñas de entre las m +1 entradas más grandes. Además, como la suma de estos dos elementos es al menos 3/2+3/2=3, a P _i no se le asigna ninguna otra entrada. Por otro lado, por el principio del palomar , debe haber algún contenedor óptimo Q _j que contenga algunas dos entradas de entre las m +1 entradas más grandes; por lo que P _i está dominado por Q _j .
• Durante la ejecución del algoritmo voraz, la suma en cada bin P _i se convierte al menos en 8/3 antes de que la suma de cualquier bin exceda 4. Demostración : Sea y la primera entrada agregada a algún bin P _i , lo que hizo que su suma fuera mayor que 4. Antes de que se agregara y , P _i tenía la suma más pequeña, que por suposición era menor que 8/3; esto significa que y > 4/3. Sea T el conjunto de todas las entradas desde la primera hasta y ; todas estas entradas también son mayores que 4/3. Como P _i era menor que 8/3, contenía exactamente un elemento x de T. Entonces ahora P _i contiene exactamente 2 elementos {x, y}, y permanece con estos 2 elementos hasta que termina el algoritmo. Sea m el número de elementos desde el primero hasta x. Ahora mostramos una contradicción contando los elementos en T de dos maneras.
  • En primer lugar, consideremos los n contenedores óptimos. Si alguno de estos contenedores contiene un elemento al menos tan grande como x, entonces no puede contener ningún otro elemento de T, ya que de lo contrario domina a {x,y}. Además, ninguno de estos contenedores puede contener tres elementos de T, ya que la suma de dos de ellos es mayor que 8/3, que es mayor que x; y el tercero es al menos y, por lo que domina a {x,y}. Por lo tanto, el número de elementos en T es como máximo 1* m + 2*( n - m ) = 2 n - m .
  • Ahora, considere los n compartimentos voraces. Cuando y se agrega al conjunto que contiene x , es el conjunto con la suma más pequeña. Por lo tanto, todos los elementos de T que son más pequeños que x, deben estar en un compartimento voraz con al menos otro elemento de T. Lo mismo es cierto para x e y. Por lo tanto, el número de elementos en T es al menos (m-1)+2*(n-m+1) = 2 n - m +1 - contradicción.
• Podemos suponer, sin pérdida de generalidad, que todas las entradas son menores que 1/3, o al menos 1. Demostración : Supongamos que alguna entrada x está en (1/3,1). Reemplazamos x por 1. Obviamente, esto no disminuye la suma mínima óptima. Demostramos que no cambia la suma mínima voraz. Sabemos que algún paquete voraz P _i tiene una suma final mayor que 4. Antes de que se añadiera la última entrada a P _i , su suma era menor que 3; por lo que P _i se volvió mayor que 4 cuando se le añadió alguna entrada mayor que 1. Por el lema anterior, en ese punto la suma de todos los demás paquetes voraces era al menos 8/3. El algoritmo llega a x después. Una vez que el algoritmo añade x a algún contenedor P j _, la suma de P _j se convierte al menos en 8/3+1/3=3, por lo que no se añaden más elementos a P _j . Por lo tanto, P _j contiene solo una entrada con tamaño en [1/3,1). Una vez que x se reemplaza por 1, todavía se inserta en P _j , y su suma sigue siendo superior a 3. Por lo tanto, la suma mínima codiciosa no cambia.
• Ahora podemos dividir las entradas en pequeñas (menos de 1/3) y grandes (al menos 1). El conjunto de elementos pequeños en P _i se denota por S _i . Nótese que, cuando el algoritmo comienza a procesar elementos pequeños, la suma en todos los paquetes es al menos 8/3.

La prueba de que no existe un contraejemplo mínimo utiliza un esquema de ponderación . A cada entrada x se le asigna un peso w(x) según su tamaño y su paquete voraz P _i :

• Si x es un elemento grande:
  • Si x es el único elemento grande en P _i , entonces w(x)=8/3.
  • Si P _i contiene exactamente dos elementos {x,y} y ambos son grandes, y x>y, y suma(P _i )≥3, entonces w(x)=8/3.
  • De lo contrario, w(x)=4/3.
• Si x es un elemento pequeño:
  • si suma(P _i )≥3, entonces w(x) = 4x/(3 suma(S _i )); por lo tanto w(S _i ) = 4/3.
  • si suma(P _i )<3, entonces w(x) = 2x/(3 suma(S _i )); por lo tanto w(S _i ) = 2/3.

Este esquema de ponderación tiene las siguientes propiedades:

• Si x≥2, entonces w(x)=8/3. Demostración : x es grande. Supóngase que está en P _i . Si P _i contiene otro elemento grande y, entonces x+y≥3, por lo que no hay ningún otro elemento en P _i . Además, x>y, ya que hay como máximo un elemento mayor que 3/2. Por lo tanto, w(x)=8/3.
• Si x<1/3, entonces w(x) > 2x. Demostración : x es pequeña. Supóngase que está en P _i .
  • Si suma(P _i )≥3 entonces, dado que suma(P _i ) era menor que 3 antes de que se le añadiera x, ahora es menor que 10/3. Pero cuando el algoritmo empezó a procesar elementos pequeños, suma(P _i ) era al menos 8/3. Esto significa que suma(S _i ) < 2/3, por lo que w(x) = 4x/(3 suma(S _i )) > 2x.
  • Si suma(P _i )<3 entonces suma(S _i ) < 3-8/3=1/3, por lo que w(x) = 2x/(3 suma(S _i )) > 2x.
• El peso de cada contenedor voraz P _i es como máximo 4, y el peso de al menos un contenedor voraz es como máximo 10/3. Demostración :
  • Si todas las entradas en P _i son grandes, entonces contiene una sola entrada con peso 8/3, dos entradas con pesos 8/3+4/3 o tres entradas con pesos 4/3+4/3+4/3.
  • Si algunas entradas en P _i son pequeñas, entonces su peso total es como máximo 4/3. Hay como máximo dos entradas grandes y sus pesos son 8/3 o 4/3+4/3.
  • Finalmente, el peso del contenedor codicioso con una suma menor a 3 es como máximo 8/3 (si solo tiene entradas grandes) o 10/3 (si tiene algunas entradas pequeñas).
• El peso de cada contenedor óptimo Q _j es al menos 4. Demostración :
  • Si Q _j contiene sólo elementos pequeños, entonces cada uno de ellos satisface w(x) > 2x, por lo que w(Q _j ) > 2 suma(Q _j ) ≥ 8.
  • Si Q _j contiene exactamente un elemento grande x, entonces debe contener algunos elementos pequeños cuya suma sea al menos 4-x y peso al menos 8-2x. Entonces, o bien x<2 y el peso de los elementos pequeños es al menos 8-4=4, o bien x en (2,3) y w(x)=8/3 y el peso de los elementos pequeños es al menos 8-6=2. En ambos casos el peso total es al menos 4.
  • Si Q _j contiene exactamente dos elementos grandes x>y, y x≥2, entonces hay al menos 8/3+4/3=4. Si x+y≤10/3, entonces la suma de los elementos pequeños debe ser al menos 2/3, por lo que el peso total es al menos 4/3+4/3+2*2/3=4. De lo contrario, x>5/3. Entonces x fue la primera entrada en algún contenedor voraz P _m . Sea z la segunda entrada agregada a P _m . Si x+z≥3, entonces no hay más entradas en P _m , por lo que w(x)=8/3 y hemos terminado. De lo contrario, x+z<3. Sea v la entrada más pequeña en algún contenedor voraz cuya suma exceda 4. Como x<8/3, z debe haber sido procesado antes que v, por lo que z≥v. Considere ahora cualquier elemento pequeño t en Q _j , y suponga que está en algún contenedor voraz P _i .
    • Si suma(P _i ) < 3, entonces el hecho de que v no se haya incluido en P _i implica que v > 4-suma(elementos-grandes-en-P _i ) > 1+suma(elementos-pequeños-en-P _i ). Por lo tanto, 1+suma(S _i )+x < v+x ≤ z+x < 3 y suma(S _i ) < 2-x. Esto significa que 2*suma(S _i ) < 4-2x ≤ 4-xy ≤ suma(elementos-pequeños-en-Q _j ). Por lo tanto, w(t) = 2t/(3suma(S _i )) > 4t/(3suma(elementos-pequeños-en-Q _j )).
    • Si suma(P _i )≥3, y suma(S _i )≤1, entonces w(t)=4/3 y hemos terminado. Como suma(P _i ) era menor que 3 antes de que se le añadiera t, suma(P _i )<3+suma(S _i )/2. El hecho de que v no se haya incluido en P _i implica que v > 4-suma(ítems-grandes-en-P _i ) > 1+suma(ítems-pequeños-en-P _i )/2. De manera similar al párrafo anterior, w(t) > 4t/(3suma(ítems-pequeños-en-Q _j )).
    • Por lo tanto, el peso total de todos los elementos pequeños en Q _j es al menos 4/3, por lo que el peso total de Q _j es al menos 4/3+10/3>4.
  • Si Q _j contiene exactamente tres o más elementos grandes, entonces su peso total es al menos 4/3+4/3+4/3=4.
• Las dos últimas afirmaciones son contradictorias, ya que la primera implica que el peso de todas las entradas es como máximo 4 m -2/3, y la segunda implica que el peso de todas las entradas es como mínimo 4 m. Por lo tanto, no existe un contraejemplo.

Límite superior de la relación

Un análisis más sofisticado muestra que la relación es como máximo (por ejemplo, cuando m = 2 la relación es 5/6). ^{[7] [8]} ${\displaystyle {\frac {3m-1}{4m-2}}}$

Rigidez y ejemplo

La relación anterior es ajustada. ^[6]

Supongamos que hay 3 m -1 entradas (donde m es par). Las primeras 2 m entradas son: 2 m -1, 2 m -1, 2 m -2, 2 m -2, ..., m , m . Las últimas m -1 entradas son todas m . Entonces, el algoritmo voraz devuelve:

• 2 m -1, m , m
• 2 m -1, m , m
• 2m - 2 , m+1 , m
• 2m - 2 , m+1 , m
• ...
• 3m/2, 3m/2-1, m
• 3m/2, 3m/2-1

con un mínimo de 3 m -1 . Pero la partición óptima es:

• 2m -1, 2m - 1
• 2 m -2, m , m
• 2 m -2, m , m
• 2m - 3, m +1, m
• 2m - 3, m +1, m
• ...
• 3m/2, 3m/2-2, m
• 3m/2, 3m/2-2, m
• 3 m/2-1, 3 m/2-1, m

con un mínimo de 4m -2.

LPT restringido

Existe una variante de LPT, llamada LPT restringida o RLPT, ^[9] en la que las entradas se dividen en subconjuntos de tamaño m llamados rangos (el rango 1 contiene las m entradas más grandes, el rango 2 las m entradas siguientes más grandes , etc.). Las entradas en cada rango deben asignarse a m contenedores diferentes: primero el rango 1, luego el rango 2, etc. La suma mínima en RLPT es como máximo la suma mínima en LPT. La razón de aproximación de RLPT para maximizar la suma mínima es como máximo m .

Suma máxima del caso promedio

En el caso promedio, si los números de entrada se distribuyen uniformemente en [0,1], entonces la suma más grande en una programación LPT satisface las siguientes propiedades:

• La suma máxima esperada para m = 2 máquinas es al menos y como máximo , donde n es el número de entradas. ^[10] ${\displaystyle {\frac {n}{4}}+{\frac {1}{4n+4}}}$ ${\displaystyle {\frac {n}{4}}+{\frac {e}{2n+2}}}$
• La suma más grande es en la mayoría de los casos la óptima casi con seguridad , y en expectativa, donde es el número de entradas. ^[11] ${\displaystyle 1+O(\log {\log {n}}/n)}$ ${\displaystyle 1+O(1/n)}$ ${\displaystyle n}$
• La diferencia entre la suma máxima LPT y la suma máxima óptima es, como máximo, casi con seguridad (para distribuciones uniformes o exponenciales negativas ), y, como máximo, en expectativa (para distribuciones uniformes). Estos resultados también son válidos para máquinas con diferentes velocidades . ^[12] ${\displaystyle O(\log {n}/n)}$ ${\displaystyle O(m^{2}/n)}$

Objetivos generales

Sea C _i (para i entre 1 y m ) la suma del subconjunto i en una partición dada. En lugar de minimizar la función objetivo max( C _i ), se puede minimizar la función objetivo max( f ( C _i )), donde f es cualquier función fija. De manera similar, se puede minimizar la función objetivo sum( f ( C _i )). Alon, Azar, Woeginger y Yadid ^[13] demuestran que, si f satisface las dos condiciones siguientes:

1. Una condición de continuidad fuerte llamada Condición F* : para todo ε>0 existe δ>0 tal que, si | y - x |<δ x , entonces |f( y )-f( x )|<ε f ( x ).
2. Convexidad .

Entonces la regla LPT tiene una relación de aproximación finita para minimizar la suma ( f ( C _i )).

Rendimiento con tamaños de elementos divisibles

Un caso especial importante es que los tamaños de los elementos forman una secuencia divisible (también llamada factorizada ). Un caso especial de tamaños de elementos divisibles ocurre en la asignación de memoria en sistemas informáticos, donde los tamaños de los elementos son todos potencias de 2. Si los tamaños de los elementos son divisibles y, además, el tamaño de elemento más grande divide el tamaño del contenedor, entonces LPT siempre encuentra una programación que minimiza el tamaño máximo, ^{[14] : Thm.4} y maximiza el tamaño mínimo. ^{[14] : Thm.5}

Adaptaciones a otros entornos

Además del caso simple de programación de máquinas idénticas, LPT se ha adaptado a configuraciones más generales.

Maquinas uniformes

En la programación de máquinas uniformes , las distintas máquinas pueden tener distintas velocidades. La regla LPT asigna cada trabajo a la máquina en la que su tiempo de finalización será más temprano (es decir, LPT puede asignar un trabajo a una máquina con una carga actual mayor , si esta máquina es tan rápida que terminaría ese trabajo antes que todas las demás máquinas). ^[15]

• Gonzalez, Ibarra y Sahni ^[15] muestran que la razón de aproximación de LPT con m máquinas uniformes es como máximo . No es estricta, pero hay un límite inferior asintótico de 1,5 cuando m tiende a infinito. Para el caso especial de m = 2 máquinas, la razón de aproximación es como máximo y es estricta. ${\displaystyle 2m/(m+1)}$ ${\displaystyle (1+{\sqrt {17}})/4\approx 1.281}$
• Mireault, Orlin y Vohra ^[16] estudian un entorno con dos máquinas, en el que una máquina es q veces más rápida que la otra. Calculan la razón de aproximación de LPT en función de q . Cuando q = 1, su resultado coincide con el factor 7/6 conocido para máquinas idénticas.
• Koulamas y Kyparisis ^[17] presentan una modificación de LPT en la que los tres trabajos más largos se programan de manera óptima y los trabajos restantes se programan según la regla LPT. La relación de aproximación para dos máquinas es y es ajustada. ${\displaystyle {\sqrt {1.5}}\approx 1.2247}$

Restricciones de cardinalidad

En el problema de partición balanceada , existen restricciones sobre la cantidad de trabajos que se pueden asignar a cada máquina. Una restricción simple es que cada máquina puede procesar c trabajos como máximo. La regla LPT asigna cada trabajo a la máquina con la carga más pequeña de entre aquellas con menos de c trabajos. Esta regla se denomina LPT modificada o MLPT .

• Kellerer y Woeginger ^[18] estudian una variante en la que hay como máximo 3* m trabajos, y cada máquina debe contener como máximo 3 trabajos (esto puede verse como una generalización del problema de 3 particiones ). Muestran que MLPT alcanza como máximo la suma mínima más grande , que es la misma razón de aproximación que LPT alcanza para el problema sin restricciones. El límite es estricto para MLPT. Se conjetura ^[19] que MLPT tiene la misma razón de aproximación para restricciones de cardinalidad más generales ( c >3). Actualmente, se sabe que la razón de aproximación de MLPT para c >3 general es como máximo 2. ^[20] ${\displaystyle (4m-1)/(3m)}$
• Chen, He y Lin ^[21] muestran que, para el mismo problema, MLPT alcanza al menos la suma más pequeña máxima , que es nuevamente la misma relación que LPT alcanza para el problema sin restricciones. ${\displaystyle (3m-1)/(4m-2)}$

Otra restricción es que el número de trabajos en todas las máquinas debe redondearse hacia arriba o hacia abajo. En una adaptación de LPT llamada LPT restringida o RLPT , las entradas se asignan en pares: una a cada máquina (para m = 2 máquinas). ^[10] La partición resultante está equilibrada por diseño. ${\displaystyle n/m}$

• Coffman, Frederickson y Lueker ^[10] muestran que la suma máxima esperada de RLPT cuando las entradas son variables aleatorias uniformemente distribuidas es exactamente . La diferencia esperada entre la suma máxima y la mínima es . ^[22] ${\displaystyle {\frac {n}{4}}+{\frac {1}{2n+2}}}$ ${\displaystyle \Theta (1/n)}$

Restricciones del kernel: disponibilidad no simultánea

En el problema de partición del núcleo , hay algunos trabajos predefinidos denominados núcleos, y cada núcleo debe programarse para una máquina única. Un problema equivalente es la programación de cuándo las máquinas están disponibles en diferentes momentos: cada máquina i se vuelve disponible en algún momento t _i ≥ 0 (el momento t _i puede considerarse como la duración del trabajo del núcleo).

Un algoritmo heurístico simple, llamado SLPT, ^[23] asigna cada núcleo a un subconjunto diferente y luego ejecuta el algoritmo LPT .

• Lee ^[24] demuestra que esta heurística tiene una razón de aproximación ajustada para la suma mínima más grande. Luego sugiere ejecutar, en el segundo paso, una versión modificada de LPT y demuestra que alcanza una razón de aproximación . ${\displaystyle {\frac {3m-1}{2m}}}$ ${\displaystyle {\frac {4}{3}}}$
• Lin, Yao y He ^[25] demuestran que esta heurística tiene una relación de aproximación estricta para la suma máxima más pequeña. ${\displaystyle {\frac {2m-1}{3m-2}}}$
• Shen, Wang y Wang ^[26] estudian diferentes funciones objetivo para esta configuración y presentan algoritmos de tiempo polinomial.

Configuración en línea

A menudo, las entradas se ponen en línea y sus tamaños se conocen solo cuando llegan. En este caso, no es posible ordenarlas de antemano. La programación de listas es un algoritmo similar que toma una lista en cualquier orden, no necesariamente ordenada. Su razón de aproximación es . ${\displaystyle {\frac {2m-1}{m}}=2-{\frac {1}{m}}}$

Una adaptación más sofisticada de LPT a un entorno en línea alcanza una relación de aproximación de 3/2. ^[27]

Implementaciones

• Python : hay una implementación de LPT ("greedy") en el paquete numberpartitioning, así como en el paquete prtpy.

Véase también

• Particionamiento de números codiciosos : generalizaciones y extensiones de LPT para el problema del particionamiento de números multidireccional.

Notas

1. Demostración . Normalice los elementos de entrada de modo que OPT=1. Esto implica que la suma de todos los elementos es como máximo m. Divida los elementos en grandes (más de 2/3), medianos (entre 1/3 y 2/3) y pequeños (menos de 1/3). Sean sus números nL, nM y nS. En cada partición óptima, cada parte contiene como máximo un elemento grande, por lo que nL ≤ m. Además, cada parte óptima no puede contener un elemento grande y uno mediano, o tres elementos medianos; por lo que nM ≤ 2(m-nL). El funcionamiento del algoritmo voraz se puede dividir en tres fases: 1. Asignación de los elementos grandes, cada uno de los cuales se coloca en un contenedor diferente. Como nL ≤ m, cuando se completa esta fase, cada contenedor contiene como máximo un elemento, por lo que la suma máxima es como máximo 1. 2. Asignación de los elementos medianos. Los primeros m-nL se colocan en contenedores vacíos, y los siguientes m-nL (si los hay) se agregan en los mismos contenedores. Dado que nM ≤ 2(m-nL), cuando se completa esta fase, cada contenedor contiene un elemento grande, con una suma de como máximo 1, o como máximo dos elementos medianos, con una suma de como máximo 4/3. 3. Asignación de los elementos pequeños. Cada elemento se agrega al contenedor con la suma más pequeña. La suma más pequeña es como máximo la suma promedio, que es como máximo 1. Por lo tanto, una vez que se agrega un elemento pequeño, la nueva suma se convierte como máximo en 4/3.
2. Demostración. La demostración anterior se puede refinar de dos maneras. Primero, se puede probar que, una vez que se asignan todos los elementos grandes y medianos, la suma en cada contenedor es como máximo 1. Si hay como máximo m-nL elementos medianos, entonces cada elemento grande y mediano se coloca en un contenedor separado, por lo que la suma es claramente como máximo 1. De lo contrario, denotemos los primeros m-nL elementos medianos como elementos medianos superiores, y los otros (como máximo m-nL) como elementos medianos inferiores. Supongamos primero que el elemento #m es mayor que 1/2. Esto significa que los elementos #1,...,#m son todos mayores que 1/2, por lo que cada uno debe estar en una parte óptima diferente. Cada uno de los elementos medianos inferiores (elementos #m+1,...#nM) debe encajar en una parte óptima con exactamente uno de los elementos #1,...,#m . Llamemos a dos elementos coincidentes si su suma es como máximo 1, de modo que puedan encajar en la misma parte óptima. Según el teorema de Hall, cada subconjunto de k elementos de nivel medio-bajo debe poder coincidir con al menos k de los elementos n.º 1,...,n.º m. En particular, el elemento n.º m+1 debe poder coincidir con el elemento n.º m; los elementos n.º m+1 y n.º m+2 deben poder coincidir con el elemento n.º m-1; y, en general, el elemento n.º m+k debe poder coincidir con el elemento n.º m-k+1. La LPT, de hecho, coloca el elemento n.º m+k en el mismo contenedor que el n.º m-k+1, por lo que la suma de cada contenedor es, como máximo, 1. En segundo lugar, se puede demostrar que, al asignar los insumos pequeños, la suma de cada nuevo contenedor es, como máximo, 4/3-1/(3m). Hay dos casos: 1. Si la suma más pequeña actual es, como máximo, 1-1/(3m), entonces la nueva suma (después de agregar un insumo pequeño) es, como máximo, 1-1/(3m)+1/3 = 4/3-1/(3m). 2. De lo contrario, todas las sumas son mayores que 1-1/(3m), por lo que la suma de los m-1 contenedores más grandes es mayor que m-1-1/3+1/(3m) = m-(4/3-1/(3m)). Como la suma total de todas las entradas es como máximo m, la nueva suma debe ser menor que 4/3-1/(3m).

Referencias

1. Graham, RL (marzo de 1969). "Límites en anomalías de tiempo de multiprocesamiento". Revista SIAM de Matemáticas Aplicadas . 17 (2): 416–429. CiteSeerX  10.1.1.90.8131 . doi :10.1137/0117039. JSTOR  2099572. NAID  30006801878 ProQuest  917998761.
2. Segal-Halevi, Erel (17 de octubre de 2021), Sobre la monotonía de los algoritmos de partición de números, arXiv : 2110.08886 , consultado el 22 de febrero de 2024
3. Xiao, Xin (1 de abril de 2017). "Una prueba directa del límite 4/3 de la regla de programación LPT". Actas de la 5.ª Conferencia internacional de 2017 sobre las fronteras de la ciencia de la fabricación y la tecnología de medición (FMSMT 2017) . Atlantis Press. págs. 486–489. doi : 10.2991/fmsmt-17.2017.102 . ISBN. 978-94-6252-331-9.
4. Coffman, EG; Sethi, Ravi (29 de marzo de 1976). "Un límite generalizado en la secuenciación LPT". Actas de la conferencia ACM SIGMETRICS de 1976 sobre medición y evaluación de modelos de rendimiento informático - SIGMETRICS '76 . Nueva York, NY, EE. UU.: Association for Computing Machinery. págs. 306–310. doi :10.1145/800200.806205. ISBN 978-1-4503-7497-2.S2CID16980306  .​
5. Chen, Bo (1993-10-01). "Una nota sobre la programación LPT". Operations Research Letters . 14 (3): 139–142. doi :10.1016/0167-6377(93)90024-B. ISSN  0167-6377.
6. Deuermeyer, Bryan L.; Friesen, Donald K.; Langston, Michael A. (junio de 1982). "Programación para maximizar el tiempo mínimo de finalización del procesador en un sistema multiprocesador". Revista SIAM sobre métodos algebraicos y discretos . 3 (2): 190–196. doi :10.1137/0603019.
7. Csirik, János; Kellerer, Hans; Woeginger, Gerhard (junio de 1992). "El límite LPT exacto para maximizar el tiempo mínimo de finalización". Operations Research Letters . 11 (5): 281–287. doi :10.1016/0167-6377(92)90004-M.
8. Wu, Bang Ye (diciembre de 2005). "Análisis del algoritmo LPT para los problemas de partición de relación mínima y máxima". Theoretical Computer Science . 349 (3): 407–419. doi : 10.1016/j.tcs.2005.08.032 .
9. Walter, Rico (1 de enero de 2013). "Comparación de los tiempos mínimos de finalización de dos heurísticas de planificación más largas". Revista centroeuropea de investigación de operaciones . 21 (1): 125–139. doi :10.1007/s10100-011-0217-4. ISSN  1613-9178. S2CID  254144745.
10. Coffman, EG; Frederickson, GN; Lueker, GS (1 de mayo de 1984). "Una nota sobre los Makespans esperados para secuencias de tareas independientes de primer orden en dos procesadores". Matemáticas de la investigación de operaciones . 9 (2): 260–266. doi :10.1287/moor.9.2.260. ISSN  0364-765X.
11. Frenk, JBG; Kan, AHGRinnooy (junio de 1986). "La tasa de convergencia a la optimalidad de la regla LPT". Matemáticas Aplicadas Discretas . 14 (2): 187–197. doi :10.1016/0166-218X(86)90060-0. hdl : 1765/11698 .
12. Frenk, JBG; Rinnooy Kan, AHG (1987-05-01). "La optimalidad asintótica de la regla LPT". Matemáticas de la investigación de operaciones . 12 (2): 241–254. doi :10.1287/moor.12.2.241. ISSN  0364-765X. S2CID  31770203.
13. Alon, Noga; Azar, Yossi; Woeginger, Gerhard J.; Yadid, Tal (1998). "Esquemas de aproximación para la planificación en máquinas paralelas". Journal of Scheduling . 1 (1): 55–66. doi :10.1002/(SICI)1099-1425(199806)1:1<55::AID-JOS2>3.0.CO;2-J. ISSN  1099-1425.
14. Coffman, E. G; Garey, M. R; Johnson, D. S (1987-12-01). "Empaquetado de contenedores con tamaños de elementos divisibles". Journal of Complexity . 3 (4): 406–428. doi :10.1016/0885-064X(87)90009-4. ISSN  0885-064X.
15. Gonzalez, Teofilo; Ibarra, Oscar H.; Sahni, Sartaj (1977-03-01). "Límites para programaciones LPT en procesadores uniformes". Revista SIAM de Computación . 6 (1): 155–166. doi :10.1137/0206013. ISSN  0097-5397.
16. Mireault, Paul; Orlin, James B.; Vohra, Rakesh V. (1 de febrero de 1997). "Un análisis paramétrico del peor caso de la heurística LPT para dos máquinas uniformes". Investigación de operaciones . 45 (1): 116–125. doi :10.1287/opre.45.1.116. ISSN  0030-364X.
17. Koulamas, Christos; Kyparisis, George J. (1 de julio de 2009). "Un algoritmo LPT modificado para el problema de minimización de makespan de dos máquinas paralelas uniformes". Revista Europea de Investigación Operativa . 196 (1): 61–68. doi :10.1016/j.ejor.2008.02.008. ISSN  0377-2217.
18. Kellerer, Hans; Woeginger, Gerhard (7 de septiembre de 1993). "Un límite ajustado para la partición 3-dimensional". Matemáticas Aplicadas Discretas . 45 (3): 249–259. doi : 10.1016/0166-218X(93)90013-E . ISSN  0166-218X.
19. Babel, Luitpold; Kellerer, Hans; Kotov, Vladimir (1998-02-01). "El problema de la partición m". Métodos matemáticos de investigación de operaciones . 47 (1): 59–82. doi :10.1007/BF01193837. ISSN  1432-5217. S2CID  5594197.
20. Dell'Amico, Mauro; Martello, Silvano (2001). "Límites para el problema P∥Cmax con restricciones de cardinalidad". Journal of Scheduling . 4 (3): 123–138. doi :10.1002/jos.68. ISSN  1099-1425.
21. Chen, Shi Ping; He, Yong; Lin, Guohui (1 de marzo de 2002). "Problemas de 3 particiones para maximizar la carga mínima". Revista de optimización combinatoria . 6 (1): 67–80. doi :10.1023/A:1013370208101. ISSN  1573-2886. S2CID  9053629.
22. Tsai, Li-Hui (1992-02-01). "Análisis asintótico de un algoritmo para la programación de procesadores paralelos balanceados". Revista SIAM de Computación . 21 (1): 59–64. doi :10.1137/0221007. ISSN  0097-5397.
23. Chen, S. -P.; He, Y.; Yao, E. -Y. (1996-09-01). "Tres particiones que contienen núcleos: complejidad y heurística". Computing . 57 (3): 255–271. doi :10.1007/BF02247409. ISSN  1436-5057. S2CID  21935917.
24. Lee, Chung-Yee (7 de enero de 1991). "Programación de máquinas paralelas con tiempo disponible de máquina no simultáneo". Matemáticas Aplicadas Discretas . 30 (1): 53–61. doi : 10.1016/0166-218X(91)90013-M . ISSN  0166-218X.
25. Lin, Guo-Hui; Yao, En-Yu; He, Yong (1998-03-01). "Programación de máquinas paralelas para maximizar la carga mínima con tiempos disponibles de máquinas no simultáneos". Operations Research Letters . 22 (2): 75–81. doi :10.1016/S0167-6377(97)00053-9. ISSN  0167-6377.
26. Shen, Lixin; Wang, Dan; Wang, Xiao-Yuan (1 de abril de 2013). "Programación de máquinas paralelas con tiempo disponible de máquina no simultáneo". Modelado matemático aplicado . 37 (7): 5227–5232. doi :10.1016/j.apm.2012.09.053. ISSN  0307-904X.
27. Chen, Bo; Vestjens, Arjen PA (1 de noviembre de 1997). "Programación en máquinas idénticas: ¿Qué tan buena es la LPT en un entorno en línea?" (PDF) . Operations Research Letters . 21 (4): 165–169. doi :10.1016/S0167-6377(97)00040-0.