Algoritmo multifit

Coffman, Garey y Johnson demuestran los siguientes límites superiores en${\displaystyle r_{n}}$: ^{[ 1 ]}

• ${\displaystyle r_{n}\leq 8/7\approx 1.14}$para n = 2;
• ${\displaystyle r_{n}\leq 15/13\approx 1.15}$para n = 3;
• ${\displaystyle r_{n}\leq 20/17\approx 1.176}$para n = 4,5,6,7;
• ${\displaystyle r_{n}\leq 122/100=1.22}$para todo n ≥ 8.

Durante el algoritmo MultiFit, el límite inferior L es siempre una capacidad para la cual es imposible empaquetar S en n contenedores. Por lo tanto,${\displaystyle L<r_{n}\cdot OPT(S,n)}$Inicialmente, la diferencia${\displaystyle UL}$es como máximo sum( S ) / n , que es como máximo${\displaystyle OPT(S,n)}$Después de que el algoritmo MultiFit se ejecuta durante k iteraciones, la diferencia se reduce k veces a la mitad, por lo que${\displaystyle UL\leq (1/2)^{k}\cdot OPT(S,n)}$. Por lo tanto,${\displaystyle U\leq (r_{n}+(1/2)^{k})\cdot OPT(S,n)}$Por lo tanto, la programación devuelta por MultiFit tiene un tiempo de finalización máximo${\displaystyle r_{n}+(1/2)^{k}}$veces el tiempo de finalización óptimo. Cuando${\displaystyle k}$es suficientemente grande, el factor de aproximación de MultiFit puede hacerse arbitrariamente cercano a${\displaystyle r_{n}}$, que es como máximo 1,22 .

Trabajos posteriores realizaron un análisis más detallado de MultiFit y demostraron que su razón de aproximación es como máximo 6/5 = 1,2 [ ^{2 ] y} , posteriormente, como máximo 13/11 ≈ 1,182 ^{[ 3 ]} . La demostración original de esto omitió algunos casos; ^{[ 4 ] presentó una demostración completa y más sencilla. El valor 13/11 no se puede mejorar: véase la cota inferior a continuación [ 2 ]} .

Para n = 4 : lo siguiente ^{[ 5 ]} muestra que${\displaystyle r_{n}\geq 20/17}$, que es ajustado. Las entradas son 9, 7, 6, 5, 5, 4, 4, 4, 4, 4, 4, 4, 4. Se pueden empaquetar en 4 contenedores con capacidad para 17 de la siguiente manera:

• 9, 4, 4
• 7, 6, 4
• 5, 4, 4, 4
• 5, 4, 4, 4

Pero si ejecutamos FFD con una capacidad de contenedores menor a 20, entonces los contenedores llenos son:

• 9,7 [4 no cabe]
• 6,5,5 [4 no cabe]
• 4,4,4,4 [4 no cabe]
• 4,4,4,4
• 4

Tenga en cuenta que la suma en cada uno de los primeros 4 compartimentos es 16, por lo que no podemos colocar otro 4 dentro. Por lo tanto, 4 compartimentos no son suficientes.

Para n = 13 : lo siguiente ^{[ 2 ]} muestra que${\displaystyle r_{n}\geq 13/11}$, lo cual es ajustado. Los insumos se pueden empacar en 13 contenedores con capacidad para 66 de la siguiente manera:

• 40,13,13 {8 veces}
• 25,25,16 {3 veces}
• 25,24,17 {2 veces}

Pero si ejecutamos FFD con una capacidad de contenedores menor que 66*13/11 = 78, entonces los contenedores llenos son:

• 40,25 {8 veces}
• 24, 24, 17
• 17, 16, 16, 16
• 13, 13, 13, 13, 13 {3 veces}
• 13

Tenga en cuenta que la suma en cada uno de los primeros 13 compartimentos es 65, por lo que no podemos colocar otros 13 dentro. Por lo tanto, 13 compartimentos no son suficientes.

MultiFit también se puede utilizar en el entorno más general denominado programación de máquinas uniformes , donde las máquinas pueden tener diferentes velocidades de procesamiento. ^{[ 6 ]} Cuando hay dos máquinas uniformes, el factor de aproximación es${\displaystyle {\sqrt {6}}/2}$Cuando MultiFit se combina con el algoritmo LPT , la relación mejora a${\displaystyle {\sqrt {2}}+1/2}$.

Un objetivo dual para minimizar la suma más grande (makespan) es maximizar la suma más pequeña. Deuermeyer, Friesen y Langston afirman que MultiFit no tiene un buen factor de aproximación para este problema: ^{[ 7 ]}

"En la solución del problema de tiempo de finalización mediante MULTIFIT, es fácil construir ejemplos donde un procesador nunca se utiliza. Dicha solución es aceptable para el problema de tiempo de finalización, pero totalmente inaceptable para nuestro problema _{[ya que la suma mínima es 0]} . Se pueden idear modificaciones de MULTIFIT que serían más adecuadas para nuestro problema, pero no pudimos encontrar ninguna que produzca una cota en el peor de los casos mejor que la de LPT ."

Los límites superiores en${\displaystyle r_{n}}$se demuestran por contradicción. Para cualesquiera enteros p ≥ q, si${\displaystyle r_{n}>p/q}$, entonces existe un ( p / q )-contraejemplo, definido como una instancia S y un número n de contenedores tales que

• S se puede empaquetar en n contenedores con capacidad q ;
• FFD no logra empaquetar S en n contenedores con capacidad p .

Si existe tal contraejemplo, entonces también existe un contraejemplo mínimo (p/q) , que es un contraejemplo ( p / q ) con el menor número de elementos en S y el menor número de contenedores n . En un contraejemplo mínimo (p/q) , FFD coloca todos los elementos en S excepto el último (el más pequeño) en n contenedores con capacidad p . Dado un contraejemplo mínimo (p/q) , denotemos por _P₁ , ..., Pₙ _el empaquetamiento (incompleto) de FFD en estos n contenedores con capacidad p , por Pₙ _+₁ el contenedor que contiene el único elemento más pequeño, y por Q₁ _, ..., Qₙ _el empaquetamiento óptimo (completo) en n contenedores con capacidad q . Se pueden demostrar los siguientes lemas:

• Ninguna unión de k subconjuntos de {Q _1,..., Q _n } está dominada por una unión de k subconjuntos de {P _1,..., P _n+1 } ("dominado" significa que cada elemento en el subconjunto dominado se asigna a un elemento débilmente mayor en el subconjunto dominante). De lo contrario, podríamos obtener un contraejemplo más pequeño como sigue. [1] Eliminar todos los elementos en P _i . Claramente, el empaquetamiento FFD incompleto ahora necesita n - k contenedores, y aún el elemento más pequeño (o un contenedor completo) permanece sin empaquetar. [2] En el empaquetamiento óptimo Q _i , intercambiar cada elemento con su elemento dominante. Ahora, los k subconjuntos Q _i son más grandes (probablemente más grandes que q ), pero todos los demás n - k subconjuntos son más pequeños (en particular, como máximo q ). Por lo tanto, después de eliminar todos los elementos en P _i , los elementos restantes se pueden empaquetar en como máximo n - k contenedores de tamaño q .
• Cada uno de Q _1,..., Q _n contiene al menos 3 elementos. De lo contrario, tendríamos dominación y, por el lema anterior, podríamos obtener un contraejemplo más pequeño. Esto se debe a que [a] cada Q _i con un solo elemento es dominado por el P _j que contiene ese elemento; [b] para cada Q _i con dos elementos x e y , si tanto x como y están en el mismo P _j , entonces Q _i es dominado por este P _j ; [c] Supongamos que x≥y, x está en algún P _j , e y está en algún P _k a su derecha. Esto significa que y no encajaba en P _j . Pero x+y ≤ q. Esto significa que P _j debe contener algún elemento z ≥ y. Entonces Q _i es dominado por P _j . [d] Supongamos que x≥y, x está en algún P _j , e y está en algún P _k a su izquierda. Esto significa que debe haber un elemento anterior z ≥ x. Entonces Q _i es dominado por P _k .
• Cada uno de los conjuntos P _1,..., P _n contiene al menos dos elementos. Esto se debe a que, si algún P _i contiene un solo elemento, esto implica que el último (el más pequeño) no cabe en él. Esto significa que este único elemento debe estar solo en un conjunto óptimo, lo que contradice el lema anterior.
• Sea s el tamaño del elemento más pequeño. Entonces${\displaystyle s>{\frac {n}{n-1}}(pq)}$. Prueba : Dado que s no cabe en los primeros n haces, tenemos${\displaystyle sum(P_{i})+s>p}$, entonces${\displaystyle \sum _{i=1}^{n}sum(P_{i})+n\cdot s>n\cdot p}$Por otro lado, dado que todos los artículos caben en n contenedores de capacidad q , tenemos${\displaystyle \sum _{i=1}^{n}sum(P_{i})+s\leq n\cdot q}$Restando las desigualdades se obtiene${\displaystyle s>{\frac {n}{n-1}}(pq)}$.
• El tamaño de cada artículo es como máximo${\displaystyle q-2s}$Esto se debe a que hay al menos 3 artículos en cada contenedor óptimo (con capacidad q ).
• La suma de los elementos en cada contenedor P _1,..., P _n es mayor que${\displaystyle ps}$; de lo contrario podríamos añadir el artículo más pequeño.

A partir de los lemas anteriores, ya es posible demostrar una cota superior aproximada.${\displaystyle r_{n}\leq 5/4=1.25}$. Demostración . Sea S , n un contraejemplo mínimo (5/4). Los lemas anteriores implican que -

• ${\displaystyle s>{\frac {n}{n-1}}(5-4)>1}$Dado que la capacidad óptima es 4, ningún contenedor óptimo puede contener 4 o más artículos. Por lo tanto, cada contenedor óptimo debe contener como máximo 3 artículos, y el número de artículos es como máximo 3n .
• El tamaño de cada artículo es como máximo${\displaystyle 4-2s}$y el tamaño de cada contenedor FFD es mayor que${\displaystyle 5-s}$. Si algún contenedor FFD contenía solo dos artículos, su suma sería como máximo${\displaystyle 8-4s=5+(3-3s)-s<5-s}$; por lo tanto, cada contenedor FFD debe contener al menos 3 elementos. Pero esto significa que FFD produce exactamente n contenedores, lo cual es una contradicción.

Para demostrar límites más estrictos, es necesario examinar más de cerca el empaquetamiento FFD del contraejemplo mínimo ( p / q ). Los elementos y contenedores FFD P1 _, ..., Pn _se denominan de la siguiente manera:

• Un artículo regular es un artículo agregado a algún contenedor P _i , antes de que se abriera el siguiente contenedor P _{i+1 . De manera equivalente, un artículo regular es un artículo en P i} que es al menos tan grande como todos los artículos en todos los contenedores P _j para j > i .
• Un elemento de reserva es un elemento añadido a algún contenedor P _i , después de que se haya abierto el siguiente contenedor P _i+1 . De forma equivalente, un elemento de reserva es un elemento en P _i que es más pequeño que el elemento más grande en P _i+1 .
• Un contenedor k regular es un contenedor que contiene k elementos regulares y ningún elemento de reserva.
• Un contenedor de reserva k es un contenedor que contiene k elementos regulares y algunos elementos de reserva.

Los siguientes lemas se derivan inmediatamente de estas definiciones y del funcionamiento de FFD.

• Si k ₁ < k ₂ , entonces todos los contenedores k ₁ están a la izquierda de todos los contenedores k _2. Esto se debe a que todos los contenedores tienen la misma capacidad, por lo que si caben más artículos regulares en un contenedor, estos artículos deben ser más pequeños, por lo que deben asignarse posteriormente.
• Si P _i es un k -bin, entonces la suma de los k elementos regulares en P _i es mayor que${\displaystyle {\frac {k}{k+1}}\cdot p}$, ya que de lo contrario podríamos agregar otro artículo antes de abrir un nuevo contenedor.
• Si P _i y P _i+1 son ambos k- bins, entonces la suma de los k elementos regulares en P _i es al menos tan grande como en P _i+1 (esto se debe a que los elementos están ordenados por tamaño decreciente).
• Todos los contenedores k regulares se encuentran a la izquierda de todos los contenedores k de reserva . Esto se debe a que todos los contenedores tienen la misma capacidad, por lo que si caben más elementos de reserva en un contenedor, estos elementos deben ser más pequeños y, por lo tanto, deben asignarse posteriormente.

En un contraejemplo mínimo, no hay contenedores regulares de 1 elemento (ya que cada contenedor contiene al menos 2 elementos), por lo que, según los lemas anteriores, los contenedores FFD P ₁ ,...,P _n están ordenados por tipo:

• Cero o más contenedores de reserva de 1;
• Luego, cero o más contenedores regulares de 2 compartimentos;
• Luego, cero o más contenedores de reserva de 2;
• Luego, cero o más contenedores regulares de 3 compartimentos;
• Luego, cero o más contenedores de reserva de 3;
• etcétera.

El límite superior${\displaystyle r_{n}\leq 1.22}$^{[ 1 ]} se demuestra asumiendo un contraejemplo mínimo (122/100). A cada elemento se le asigna unpesoen función de su tamaño y su contenedor en el empaquetado FFD. Los pesos se determinan de tal manera que el peso total en cada contenedor FFD sea al menosx, y el peso total en casi cada contenedor óptimo sea como máximox(para algúnx). Esto implica que el número de contenedores FFD es como máximo el número de contenedores óptimos, lo cual contradice la suposición de que se trata de un contraejemplo.

Según los lemas anteriores, sabemos que:

• El tamaño del elemento más pequeño satisface s > p - q = 22, por lo que s = 22 + D para algún D > 0.
• Cada contenedor óptimo contiene como máximo 4 elementos (floor(100/22)), y cada contenedor FFD contiene como máximo 5 elementos (floor(122/22)).
• El tamaño de cada artículo es como máximo q -2 s = 56-2 D .
• La suma en cada intervalo FFD es mayor que p - s = 100- D .
• No hay contenedores de 1 unidad, ya que en un contenedor de 1 unidad, el tamaño del artículo regular debe ser al menos p /2=61, mientras que aquí el tamaño de cada artículo es menor que 56.

Si D > 4, el tamaño de cada elemento es mayor que 26, por lo que cada contenedor óptimo (con capacidad 100) debe contener como máximo 3 elementos. Cada elemento es menor que 56-2 D y cada contenedor FFD tiene una suma mayor que 100- D , por lo que cada contenedor FFD debe contener al menos 3 elementos. Por lo tanto, hay como máximo n contenedores FFD: contradicción. Así que de ahora en adelante, asumimos D ≤ 4. Los elementos se asignan tipos y pesos de la siguiente manera.

• Los dos elementos de cada contenedor regular de 2 compartimentos, excepto quizás el último, tienen un tamaño mayor que (100- D )/2 cada uno. Todos estos elementos se denominan tipo X ₂ y se les asigna un peso de (100- D )/2. El último contenedor regular de 2 compartimentos es un caso especial: si ambos elementos tienen un tamaño mayor que (100- D )/2, también son tipo X ₂ ; de lo contrario, se denominan tipo Z y su peso es igual a su tamaño.
• Los dos elementos regulares en cada contenedor de reserva 2 tienen un tamaño total mayor que 2*122/3; se denominan tipo-Y ₂ y su peso es igual a su tamaño menos D.
• Los tres elementos de cada contenedor regular de 3, excepto quizás el último, tienen un tamaño mayor que (100- D )/3 cada uno. Todos estos elementos se denominan tipo-X ₃ y se les asigna un peso de (100- D )/3. El último contenedor regular de 3 es un caso especial: si todos los elementos que contiene tienen un tamaño mayor que (100- D )/3, también son tipo-X ₃ ; de lo contrario, se denominan tipo-Z y su peso es igual a su tamaño.
• Los tres artículos regulares en cada contenedor de reserva 3 tienen un tamaño total mayor que 3*122/4; se denominan tipo-Y ₃ y su peso es igual a su tamaño menos D.
• Los cuatro elementos de cada contenedor regular de 4 compartimentos, excepto quizás el último, tienen un tamaño mayor que (100- D )/4 cada uno. Todos estos elementos se denominan tipo X ₄ y se les asigna un peso de (100- D )/4. El último contenedor regular de 4 compartimentos es un caso especial: si todos los elementos que contiene tienen un tamaño mayor que (100- D )/4, también son tipo X ₄ ; de lo contrario, se denominan tipo Z y su peso es igual a su tamaño.
• Los elementos restantes (incluidos todos los elementos de reserva en los contenedores de reserva de 2 y 3 elementos, todos los contenedores de reserva de 4 elementos y todos los demás contenedores de 5 elementos) se denominan todos tipo-X ₅ , y su peso es igual a 22 (si D ≤ 12/5) o (100- D )/4 (en caso contrario). El umbral 12/5 se calculó de tal manera que el peso siempre sea como máximo 22+ D , de modo que el peso siempre sea menor que el tamaño.

Tenga en cuenta que el peso de cada artículo es como máximo su tamaño (el peso puede considerarse como el tamaño "redondeado hacia abajo"). Aun así, el peso total de los artículos en cada contenedor FFD es al menos 100- D :

• Para contenedores estándar de 2, 3 y 4 compartimentos:
  • Para los que no son los últimos, esto es inmediato.
  • Los últimos contenedores de este tipo contienen solo artículos de tipo Z, cuyo peso es igual a su tamaño, por lo que el peso total de estos contenedores es igual a su tamaño total, que es más de 100- D .
• Los contenedores de reserva 2 contienen dos artículos de tipo Y ₂ con un peso total mayor que 2*122/3-2 D , más al menos un artículo de tipo X ₅ con un peso de al menos 22 (si D ≤ 12/5) o (100- D )/4 (en caso contrario). En ambos casos , el peso total es mayor que 100- D.
• Los contenedores de reserva 3 contienen tres artículos de tipo Y ₃ con un peso total mayor que 3*122/4-3 D , más al menos un artículo de tipo X ₅ con un peso de al menos 22. Por lo tanto, el peso total es mayor que 3*122/4+22-3 D = 113,5-3 D ≥ 105,5- D > 100- D , ya que D≤ 4.
• Los contenedores de 5 artículos contienen 5 artículos con un tamaño de al menos 22+ D y un peso de al menos 22, por lo que su peso total es obviamente más de 100- D.

El peso total de los artículos en la mayoría de los contenedores óptimos es como máximo 100- D :

• Esto es claro para cualquier contenedor óptimo que contenga un artículo de tipo -Y ₂ o un artículo de tipo -Y ₃ , ya que su peso es su tamaño menos D , los pesos de otros artículos son como máximo su tamaño, y el tamaño total de un contenedor óptimo es como máximo 100.
• Para contenedores óptimos que contengan solo artículos de tipo -X ₂ , tipo -X ₃ , tipo -X ₄ y tipo -X ₅ , es posible comprobar todas las configuraciones posibles (todas las combinaciones que caben en un contenedor óptimo de tamaño 100) y verificar que el peso total en cada configuración sea como máximo 100- D .
• Los contenedores óptimos que contienen artículos de tipo Z podrían tener un peso total mayor que 100- D . Dado que el peso total es como máximo 100, existe un "exceso de peso" de como máximo D para cada uno de estos contenedores. Sin embargo, el número de artículos de tipo Z es limitado:
  • Si D > 12/5, entonces hay como máximo 5 elementos de tipo Z (2 en el último contenedor regular 2 y 3 en el último contenedor regular 3; los elementos en el último contenedor regular 4 son todos de tipo X ₄ ). Por lo tanto, el peso excedente es como máximo 5 D. Comparando el peso total de FFD con los contenedores óptimos se obtiene s < 5 D ≤ 20 < 22, una contradicción.
  • De lo contrario, hay como máximo 9 elementos de tipo Z (2+3+4). Por lo tanto, el peso excedente es como máximo 9 D. Comparando el peso total de FFD con los intervalos óptimos se obtiene s < 9 D ≤ 108/5 < 22, lo cual es una contradicción.

El límite superior${\displaystyle r_{n}\leq 13/11\approx 1.182}$^{[ 3 ]} se demuestra asumiendo un contraejemplo mínimo ((120-3d)/100), con algúnd<20/33, y derivando una contradicción.

Aquí hay un ejemplo. ^{[ 5 ] : Ej.5.2} Supongamos que hay cuatro agentes y que tienen valoraciones de dos tipos:

Ambos tipos pueden dividir las tareas en 4 partes con un valor total de 75. Tipo A:

• 51, 12, 12
• 27,5, 27,5, 10, 10
• 27,5, 27,5, 10, 10
• 25, 10, 10, 10, 10, 10

Tipo B:

• 51, 24
• 27,5, 27,5, 20
• 27,5, 27,5, 20
• 8.33 {9 veces}

Si los cuatro agentes son del mismo tipo, entonces FFD con umbral 75 llena los 4 contenedores óptimos. Pero supongamos que hay un agente de tipo B y los demás son de tipo A. Entonces, en la primera ronda, el agente de tipo B toma el paquete 51, 24 (los otros agentes no pueden tomarlo ya que para ellos los valores son 51, 25 cuya suma es mayor que 75). En las siguientes rondas, se llenan los siguientes paquetes para los agentes de tipo A:

• 27,5, 27,5, 12 [la suma es 67; no hay espacio para otro 10]
• 27,5, 27,5, 12 [la suma es 67; no hay espacio para otro 10]
• 10, 10, 10, 10, 10, 10, 10 [la suma es 70; no hay espacio para otro 10]

Así pues, las dos últimas tareas quedan sin asignar.

Utilizando un cálculo de umbral más sofisticado, es posible garantizar a cada agente como máximo 11/9≈1,22 de su valor óptimo si se conoce dicho valor, y como máximo 5/4≈1,25 de su valor óptimo (utilizando un algoritmo de tiempo polinomial) si se desconoce el valor óptimo. ^{[ 5 ]}

Utilizando argumentos más elaborados, es posible garantizar a cada agente la misma proporción de MultiFit. ^{[ 9 ]}