Algoritmo de multiajuste

Algoritmo de optimización en informática

El algoritmo multifit es un algoritmo para la partición de números de múltiples vías , desarrollado originalmente para el problema de la programación de máquinas idénticas . Fue desarrollado por Coffman, Garey y Johnson. ^[1] Su novedad proviene del hecho de que utiliza un algoritmo para otro problema famoso - el problema de empaquetamiento de contenedores - como una subrutina.

El algoritmo

La entrada del algoritmo es un conjunto S de números y un parámetro n . La salida requerida es una partición de S en n subconjuntos, de modo que la suma más grande de los subconjuntos (también llamada makespan ) sea lo más pequeña posible.

El algoritmo utiliza como subrutina un algoritmo llamado empaquetamiento de bins decreciente de primer ajuste (FFD). El algoritmo FFD toma como entrada el mismo conjunto S de números y una capacidad de bin c . Empaca heurísticamente los números en bins de modo que la suma de los números en cada bin sea como máximo C , con el objetivo de utilizar la menor cantidad posible de bins. Multifit ejecuta FFD varias veces, cada vez con una capacidad C diferente , hasta que encuentra algún C tal que FFD con capacidad C empaquete S en como máximo n bins. Para encontrarlo, utiliza la búsqueda binaria de la siguiente manera.

1. Sea L  := max ( suma( S ) / n , max( S ) ). Nótese que, con una capacidad de contenedores menor que L , cada empaque debe utilizar más de n contenedores.
2. Sea U  := max ( 2 suma( S ) / n , max( S ) ). Nótese que, con capacidad de bin al menos U , FFD utiliza como máximo n bins. Demostración : supongamos por contradicción que alguna entrada s _i no encaja en ninguno de los primeros n bins. Claramente, esto es posible solo si i ≥ n +1. Si s _i > C/2, entonces, dado que las entradas están ordenadas en orden descendente, la misma desigualdad se cumple para todas las primeras n +1 entradas en S . Esto significa que suma(S) > (n+1) C /2 > n U /2, una contradicción con la definición de U . De lo contrario, s _i ≤ C/2. Por lo tanto, la suma de cada uno de los primeros n bins es mayor que C/2. Esto nuevamente implica suma(S) > n C /2 > n U /2, contradicción.
3. Iterar k veces (donde k es un parámetro de precisión):
   • Sea C  := ( L + U )/2. Ejecute FFD en S con capacidad C .
     • Si FFD necesita como máximo n contenedores, entonces disminuya U dejando U  := C .
     • Si FFD necesita más de n contenedores, entonces aumente L dejando L  := C.
4. Por último, ejecute FFD con capacidad U. Se garantiza que se utilizarán como máximo n contenedores. Devuelva la programación resultante.

Actuación

Multifit es un algoritmo de aproximación de factor constante . Siempre encuentra una partición en la que el makespan es como máximo un factor constante mayor que el makespan óptimo. Para encontrar esta constante, primero debemos analizar FFD. Mientras que el análisis estándar de FFD considera la aproximación con respecto al número de contenedores cuando la capacidad es constante, aquí necesitamos analizar la aproximación con respecto a la capacidad cuando el número de contenedores es constante. Formalmente, para cada tamaño de entrada S y entero n, sea la capacidad más pequeña tal que S pueda empaquetarse en n contenedores de esta capacidad. Tenga en cuenta que es el valor de la solución óptima para la instancia de programación original. ${\displaystyle OPT(S,n)}$ ${\displaystyle OPT(S,n)}$

Sea el número real más pequeño tal que, para cada entrada S , FFD con capacidad utiliza como máximo n contenedores. ${\displaystyle r_{n}}$ ${\displaystyle r_{n}\cdot OPT(S,n)}$

Límites superiores

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

• ${\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, . Inicialmente, la diferencia es como máximo suma( S ) / n , que es como máximo . Después de que el algoritmo MultiFit se ejecuta durante k iteraciones, la diferencia se reduce k veces a la mitad, por lo que . Por lo tanto, . Por lo tanto, la programación devuelta por MultiFit tiene makespan en la mayoría de las veces el makespan óptimo. Cuando es suficientemente grande, el factor de aproximación de MultiFit se puede hacer arbitrariamente cercano a , que es como máximo 1,22 . ${\displaystyle L<r_{n}\cdot OPT(S,n)}$ ${\displaystyle U-L}$ ${\displaystyle OPT(S,n)}$ ${\displaystyle U-L\leq (1/2)^{k}\cdot OPT(S,n)}$ ${\displaystyle U\leq (r_{n}+(1/2)^{k})\cdot OPT(S,n)}$ ${\displaystyle r_{n}+(1/2)^{k}}$ ${\displaystyle k}$ ${\displaystyle r_{n}}$

En trabajos posteriores se realizó un análisis más detallado de MultiFit y se demostró 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 prueba original de esto omitió algunos casos; ^[4] presentó una prueba completa y más simple. La 13/11 no se puede mejorar: consulte el límite inferior a continuación. ^[2]

Límites inferiores

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

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

Pero si ejecutamos FFD con una capacidad de bin menor a 20, entonces los bins 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 de cada uno de los primeros 4 compartimentos es 16, por lo que no podemos colocar otros 4 dentro. Por lo tanto, 4 compartimentos no son suficientes.

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

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

Pero si ejecutamos FFD con una capacidad de contenedor 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 de 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.

Rendimiento con máquinas uniformes

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

Rendimiento para maximizar la suma más pequeña

Un objetivo doble de 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 makespan usando MULTIFIT, es fácil construir ejemplos donde nunca se usa un procesador. ^{[ aclaración necesaria ]} Tal solución es tolerable para el problema de makespan, pero es totalmente inaceptable para nuestro problema _{[ya que la suma más pequeña es 0]} . Se pueden idear modificaciones de MULTIFIT que serían más adecuadas para nuestro problema, pero no pudimos encontrar ninguna que produzca un mejor límite de peor caso que el de LPT ".

Idea de prueba

Contraejemplos mínimos

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

• 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 (p/q) mínimo , que es un contraejemplo ( p / q ) con un número más pequeño de elementos en S y un número más pequeño de contenedores n . En un contraejemplo (p/q) mínimo , FFD empaqueta todos los elementos en S excepto el último (el más pequeño) en n contenedores con capacidad p . Dado un contraejemplo (p/q) mínimo , denotemos por P ₁ ,...,P _n el empaquetamiento (incompleto) de FFD en estos n contenedores con capacidad p , por P _n+1 el contenedor que contiene el elemento más pequeño, y por Q ₁ ,...,Q _n 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 } ("dominada" significa que cada elemento del subconjunto dominado se asigna a un elemento débilmente más grande del 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 así el elemento más pequeño (o un contenedor entero) permanece sin empaquetar. [2] En el empaquetamiento óptimo Q _i , intercambia 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 está 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 está dominado por este P _j ; [c] Supóngase 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 encaja en P _j . Pero x+y ≤ q. Esto significa que P _j debe contener algún elemento z ≥ y. Por lo tanto, Q _i está dominado por P _j . [d] Supóngase 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. Por lo tanto, Q _i está dominado por P _k .
• Cada uno de P _1,..., P _n contiene al menos 2 elementos. Esto se debe a que, si algún P _i contiene solo un elemento, esto implica que el último elemento (el más pequeño) no cabe en él. Esto significa que este único elemento debe estar solo en un conjunto óptimo, contradiciendo el lema anterior.
• Sea s el tamaño del artículo más pequeño. Entonces . Demostración : Como s no cabe en los primeros n paquetes, tenemos , por lo que . Por otro lado, como todos los artículos caben en n contenedores de capacidad q , tenemos . Restando las desigualdades obtenemos . ${\displaystyle s>{\frac {n}{n-1}}(p-q)}$ ${\displaystyle sum(P_{i})+s>p}$ ${\displaystyle \sum _{i=1}^{n}sum(P_{i})+n\cdot s>n\cdot p}$ ${\displaystyle \sum _{i=1}^{n}sum(P_{i})+s\leq n\cdot q}$ ${\displaystyle s>{\frac {n}{n-1}}(p-q)}$
• El tamaño de cada elemento es como máximo . Esto se debe a que hay al menos 3 elementos en cada contenedor óptimo (con capacidad q ). ${\displaystyle q-2s}$
• La suma de elementos en cada contenedor P _1,..., P _n es mayor que ; de lo contrario, podríamos agregar el elemento más pequeño. ${\displaystyle p-s}$

5/4 Límite superior

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

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

Estructura del empaque FFD

Para demostrar límites más estrictos, es necesario observar más de cerca el empaquetamiento FFD del contraejemplo mínimo ( p / q ). Los elementos y los contenedores FFD P ₁ ,...,P _n se denominan de la siguiente manera:

• Un elemento regular es un elemento agregado a algún contenedor P _i , antes de que se abriera el siguiente contenedor P _{i+1 . De manera equivalente, un elemento regular es un elemento en P i} que es al menos tan grande como cada elemento en cada contenedor P _j para j > i .
• Un elemento de reserva es un elemento agregado a un contenedor P _i después de que se abrió el siguiente contenedor P _{i+1 . De manera 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 k-bin regular es un bin que contiene k elementos regulares y ningún elemento de respaldo.
• Un k-bin de respaldo es un contenedor que contiene k elementos regulares y algunos elementos de respaldo.

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 ₂ . Esto se debe a que todos los contenedores tienen la misma capacidad, por lo que si caben más elementos regulares en un contenedor, estos elementos deben ser más pequeños, por lo que deben asignarse más tarde.
• Si P _i es un k -bin, entonces la suma de los k elementos regulares en P _i es mayor que , ya que de lo contrario podríamos agregar otro elemento antes de abrir un nuevo bin. ${\displaystyle {\frac {k}{k+1}}\cdot p}$
• 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 están 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, por lo que deben asignarse más adelante.

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

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

1.22 límite superior

El límite superior ^[1] se demuestra suponiendo un contraejemplo mínimo (122/100). A cada elemento se le asigna un peso basado en su tamaño y su contenedor en el empaquetamiento de FFD. Los pesos se determinan de modo que el peso total en cada contenedor de FFD sea al menos x , y el peso total en casi cada contenedor óptimo sea como máximo x (para algún x predeterminado ). Esto implica que el número de contenedores de FFD es como máximo el número de contenedores óptimos, lo que contradice el supuesto de que es un contraejemplo. ${\displaystyle r_{n}\leq 1.22}$

Por 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 (piso(100/22)), y cada contenedor FFD contiene como máximo 5 elementos (piso(122/22)).
• El tamaño de cada elemento es como máximo q -2 s = 56-2 D .
• La suma en cada contenedor FFD es mayor que p - s = 100- D.
• No hay 1-bins, ya que en un 1-bin, el tamaño del elemento regular debe ser al menos p /2=61, mientras que aquí el tamaño de cada elemento 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. Por lo tanto, de ahora en adelante, asumimos que D ≤ 4. A los elementos se les asignan tipos y pesos de la siguiente manera.

• Los dos elementos de cada contenedor regular de 2, 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 es un caso especial: si ambos elementos tienen un tamaño mayor que (100- D )/2, entonces 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, entonces también son tipo-X ₃ ; de lo contrario, se denominan tipo-Z y su peso es igual a su tamaño.
• Los tres elementos regulares en cada contenedor de respaldo 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, 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 es un caso especial: si todos los elementos que contiene tienen un tamaño mayor que (100- D )/4, entonces 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 compartimentos, todos los contenedores de reserva de 4 compartimentos y todos los demás contenedores de 5 elementos) se denominan 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 modo que el peso sea siempre como máximo 22+ D , de modo que el peso sea siempre menor que el tamaño.

Tenga en cuenta que el peso de cada elemento es como máximo su tamaño (el peso se puede considerar como el tamaño "redondeado hacia abajo"). Aún así, el peso total de los elementos en cada contenedor FFD es al menos 100- D :

• Para contenedores regulares de 2, 3 y 4:
  • Para los que no quedan últimos, esto es inmediato.
  • Los últimos contenedores de este tipo contienen únicamente 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 de 2 compartimentos 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 3 contenedores de reserva contienen tres elementos de tipo Y _{3 con un peso total mayor que 3*122/4-3} D , más al menos un elemento 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 elemento de tipo -Y ₂ o un elemento de tipo -Y ₃ , ya que su peso es su tamaño menos D , los pesos de los otros elementos son como máximo su tamaño y el tamaño total de un contenedor óptimo es como máximo 100.
• Para los contenedores óptimos que contienen solo elementos de tipo -X ₂ , tipo -X ₃ , tipo -X ₄ y tipo -X ₅ , es posible verificar todas las configuraciones posibles (todas las combinaciones que encajan 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 elementos de tipo Z pueden 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 esos contenedores. Sin embargo, la cantidad de elementos de tipo Z es limitada:
  • Si D > 12/5, entonces hay como máximo 5 elementos de tipo Z (2 en el último contenedor regular de 2 y 3 en el último contenedor regular de 3; los elementos del último contenedor regular de 4 son todos de tipo X ₄ ). Por lo tanto, el exceso de peso es como máximo 5 D . Comparar el peso total de FFD con contenedores óptimos arroja 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 en exceso es como máximo 9 D. Al comparar el peso total de FFD con los contenedores óptimos, se obtiene s < 9 D ≤ 108/5 < 22, una contradicción.

13/11 límite superior

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

No monotonía

MultiFit no es monótono en el siguiente sentido: es posible que una entrada disminuya mientras que la suma máxima en la partición devuelta por MultiFit aumenta . Como ejemplo, ^{[1] : Fig.4} suponga que n = 3 y los números de entrada son:

44, 24, 24, 22, 21, 17, 8, 8, 6, 6.

FFD empaqueta estas entradas en 3 contenedores con una capacidad de 60 (lo cual es óptimo):

• 44, 8, 8;
• 24, 24, 6, 6;
• 22, 21, 17.

Pero si el "17" se convierte en "16", entonces el FFD con capacidad 60 necesita 4 contenedores:

• 44, 16;
• 24, 24, 8;
• 22, 21, 8, 6;
• 6.

Por lo tanto, MultiFit debe aumentar la capacidad, por ejemplo, a 62:

• 44, 16;
• 24, 24, 8, 6;
• 22, 21, 8, 6.

Esto contrasta con otros algoritmos de partición de números ( programación de listas y programación de tiempo de procesamiento más largo primero ), que son monótonos. ^[8]

Generalización: distribución justa de tareas

El método MultiFit se ha extendido al problema más general de asignación de tareas con la máxima proporción de tareas. ^[5] En este problema, S es un conjunto de tareas y hay n agentes que asignan valoraciones potencialmente diferentes a las tareas. El objetivo es dar a cada agente un conjunto de tareas que valga como máximo r veces el valor máximo en una programación óptima basada en las valoraciones de i . Un enfoque ingenuo es dejar que cada agente utilice a su vez el algoritmo MultiFit para calcular el umbral y luego utilizar el algoritmo en el que cada agente utiliza su propio umbral. Si este enfoque funcionara, obtendríamos una aproximación de 13/11. Sin embargo, este enfoque falla debido a la no monotonía de FFD .

Ejemplo

He aquí 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 la FFD con umbral 75 llena los 4 compartimentos óptimos. Pero supongamos que hay un agente del tipo B y los demás son del tipo A. Entonces, en la primera ronda, el agente del tipo B toma el paquete 51, 24 (los demás 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 del tipo A:

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

Así que las dos últimas tareas quedan sin asignar.

Garantía de valor óptimo

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 no se conoce dicho valor. ^[5]

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

Implementaciones

• Python: El paquete prtpy contiene una implementación de multifit.

Referencias

1. Coffman, Jr., EG; Garey, MR; Johnson, DS (1978-02-01). "Una aplicación del empaquetamiento de bins a la programación de multiprocesadores". Revista SIAM de Computación . 7 (1): 1–17. doi :10.1137/0207001. ISSN  0097-5397.{{cite journal}}: CS1 maint: varios nombres: lista de autores ( enlace )
2. Friesen, Donald K. (1 de febrero de 1984). "Límites más estrictos para el algoritmo de programación de procesadores Multifit". Revista SIAM de informática . 13 (1): 170–181. doi :10.1137/0213013. ISSN  0097-5397.
3. Yue, Minyi (1990-12-01). "Sobre el límite superior exacto para el algoritmo de programación de procesadores multiajuste". Anales de investigación de operaciones . 24 (1): 233–259. doi :10.1007/BF02216826. ISSN  1572-9338. S2CID  120965788.
4. Cao, Feng (1995), Du, Ding-Zhu; Pardalos, Panos M. (eds.), "Determinación de la relación de rendimiento del algoritmo Multifit para programación", Minimax and Applications , Nonconvex Optimization and Its Applications, vol. 4, Boston, MA: Springer US, págs. 79–96, doi :10.1007/978-1-4613-3557-3_5, ISBN 978-1-4613-3557-3, consultado el 23 de agosto de 2021
5. Huang, Xin; Lu, Pinyan (18 de julio de 2021). "Un marco algorítmico para aproximar la asignación de tareas con la máxima participación". Actas de la 22.ª Conferencia de la ACM sobre economía y computación . EC '21. Nueva York, NY, EE. UU.: Association for Computing Machinery. págs. 630–631. arXiv : 1907.04505 . doi :10.1145/3465456.3467555. ISBN 978-1-4503-8554-1.S2CID 195874333  .
6. Burkard, RE; He, Y. (1998-09-01). "Una nota sobre la programación MULTIFIT para máquinas uniformes". Computing . 61 (3): 277–283. doi :10.1007/BF02684354. ISSN  1436-5057. S2CID  37590584.
7. 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.
8. 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
9. Huang, Xin; Segal-Halevi, Erel (13 de diciembre de 2023), Una reducción de la asignación de tareas a la programación de trabajos, arXiv : 2302.04581 , consultado el 22 de febrero de 2024