Programación de máquinas idénticas

La programación de máquinas idénticas es un problema de optimización en informática e investigación de operaciones . Se nos dan n trabajos J ₁ , J ₂ , ..., J _n de tiempos de procesamiento variables, que deben programarse en m máquinas idénticas, de modo que se optimice una determinada función objetivo, por ejemplo, se minimice el tiempo de ejecución .

La programación de máquinas idénticas es un caso especial de programación de máquinas uniformes , que a su vez es un caso especial de programación óptima de trabajos . En el caso general, el tiempo de procesamiento de cada trabajo puede ser diferente en diferentes máquinas; en el caso de la programación de máquinas idénticas, el tiempo de procesamiento de cada trabajo es el mismo en cada máquina. Por lo tanto, la programación de máquinas idénticas es equivalente a la partición de números multidireccional . Un caso especial de programación de máquinas idénticas es la programación de una sola máquina .

En la notación estándar de tres campos para problemas de programación óptima de trabajos , la variante de máquinas idénticas se denota con P en el primer campo. Por ejemplo, " P|| " es un problema de programación de máquinas idénticas sin restricciones, donde el objetivo es minimizar el tiempo máximo de finalización. ${\displaystyle C_{\max }}$

En algunas variantes del problema, en lugar de minimizar el tiempo máximo de finalización, se desea minimizar el tiempo de finalización promedio (promediado sobre todos los n trabajos); se denota por P|| . De manera más general, cuando algunos trabajos son más importantes que otros, puede ser deseable minimizar un promedio ponderado del tiempo de finalización, donde cada trabajo tiene un peso diferente. Esto se denota por P|| . ${\displaystyle \sum C_{i}}$ ${\displaystyle \sum w_{i}C_{i}}$

Algoritmos

Minimizar el tiempo de finalización promedio y promedio ponderado

La minimización del tiempo de finalización promedio ( P|| ) se puede realizar en tiempo polinomial. El algoritmo SPT (Shortest Processing Time First) ordena los trabajos por su longitud, el más corto primero, y luego los asigna al procesador con el tiempo de finalización más temprano hasta el momento. Se ejecuta en tiempo O( n log n ), y minimiza el tiempo de finalización promedio en máquinas idénticas, ^[1] P|| . ${\displaystyle \sum C_{i}}$ ${\displaystyle \sum C_{i}}$

• Puede haber muchos programas SPT; encontrar el programa SPT con el menor tiempo de finalización (también llamado OMFT – tiempo medio de finalización óptimo ) es NP-difícil.

Minimizar el tiempo de finalización promedio ponderado es NP-difícil incluso en máquinas idénticas, por reducción del problema de la mochila . ^[1] Es NP-difícil incluso si el número de máquinas es fijo y al menos 2, por reducción del problema de la partición . ^[2]

Sahni ^[2] presenta un algoritmo de tiempo exponencial y un esquema de aproximación de tiempo polinomial para resolver ambos problemas NP-difíciles en máquinas idénticas:

• Tiempo medio óptimo de finalización;
• Tiempo de finalización promedio ponderado.

Minimizar el tiempo máximo de finalización (makespan)

Minimizar el tiempo máximo de finalización ( P|| ) es NP-difícil incluso para máquinas idénticas , por reducción a partir del problema de partición . Se conocen muchos algoritmos exactos y de aproximación. ${\displaystyle C_{\max }}$

Graham demostró que:

• Cualquier algoritmo de programación de listas (un algoritmo que procesa los trabajos en un orden fijo arbitrario y programa cada trabajo en la primera máquina disponible) es una aproximación para máquinas idénticas . ^[3] El límite es estricto para cualquier m . Este algoritmo se ejecuta en un tiempo O( n ). ${\displaystyle 2-1/m}$
• El algoritmo específico de programación de listas llamado Longest Processing Time First (LPT), que ordena los trabajos por longitud descendente, es una aproximación para máquinas idénticas . ^{[4] : sec.5} También se llama partición de números codiciosos . ${\displaystyle 4/3-1/3m}$

Coffman, Garey y Johnson presentaron un algoritmo diferente llamado algoritmo multifit , utilizando técnicas de bin packing , que tiene un factor de aproximación de 13/11≈1.182.

Huang y Lu ^[5] presentaron un algoritmo simple de tiempo polinomial que alcanza una aproximación de 11/9≈1.222 en el tiempo O( m log m + n ), a través del problema más general de asignación de tareas con una participación máxima .

Sahni ^[2] presentó un PTAS que alcanza (1+ε)OPT en tiempo . Es un FPTAS si m es fijo. Para m=2, el tiempo de ejecución mejora a . El algoritmo utiliza una técnica llamada partición de intervalos . ${\displaystyle O(n\cdot (n^{2}/\epsilon )^{m-1})}$ ${\displaystyle O(n^{2}/\epsilon )}$

Hochbaum y Shmoys ^[6] presentaron varios algoritmos de aproximación para cualquier número de máquinas idénticas (incluso cuando el número de máquinas no es fijo):

• Para cualquier r > 0, un algoritmo con razón de aproximación como máximo (6/5+2 ^{− r} ) en el tiempo . ${\displaystyle O(n(r+\log {n}))}$
• Para cualquier r > 0, un algoritmo con razón de aproximación como máximo (7/6+2 ^{− r} ) en el tiempo . ${\displaystyle O(n(rm^{4}+\log {n}))}$
• Para cualquier ε >0, un algoritmo con razón de aproximación como máximo (1+ε) en el tiempo . Este es un PTAS . Nótese que, cuando el número de máquinas es parte de la entrada, el problema es fuertemente NP-hard , por lo que no es posible ningún FPTAS. ${\displaystyle O((n/\varepsilon )^{(1/\varepsilon ^{2})})}$

Leung ^[7] mejoró el tiempo de ejecución de este algoritmo a . ${\displaystyle O\left((n/\varepsilon )^{(1/\varepsilon )\log {(1/\varepsilon )}}\right)}$

Maximizar el tiempo mínimo de finalización

Maximizar el tiempo mínimo de finalización ( P|| ) es aplicable cuando los "trabajos" son en realidad piezas de repuesto que se requieren para mantener las máquinas en funcionamiento y tienen diferentes tiempos de vida. El objetivo es mantener las máquinas en funcionamiento durante el mayor tiempo posible. ^[8] El algoritmo LPT alcanza al menos el valor óptimo. ${\displaystyle C_{\min }}$ ${\displaystyle {\frac {3m-1}{4m-2}}}$

Woeginger ^[9] presentó un PTAS que alcanza un factor de aproximación de en el tiempo , donde una constante enorme que es exponencial en el factor de aproximación requerido ε. El algoritmo utiliza el algoritmo de Lenstra para programación lineal entera . ${\displaystyle 1-{\varepsilon }}$ ${\displaystyle O(c_{\varepsilon }n\log {k})}$ ${\displaystyle c_{\varepsilon }}$

Funciones objetivas generales

Alon, Azar, Woeginger y Yadid ^[10] consideran una función objetivo más general. Dada una función real positiva f , que depende solo de los tiempos de completitud C _i , consideran los objetivos de minimizar , minimizar , maximizar y maximizar . Demuestran que, si f es no negativo, convexo y satisface un supuesto de continuidad fuerte que llaman "F*", entonces ambos problemas de minimización tienen una PTAS. De manera similar, si f es no negativo, cóncavo y satisface F*, entonces ambos problemas de maximización tienen una PTAS. En ambos casos, el tiempo de ejecución de la PTAS es O( n ), pero con constantes que son exponenciales en 1/ ε. ${\displaystyle \sum _{i=1}^{m}f(C_{i})}$ ${\displaystyle \max _{i=1}^{m}f(C_{i})}$ ${\displaystyle \sum _{i=1}^{m}f(C_{i})}$ ${\displaystyle \min _{i=1}^{m}f(C_{i})}$

Véase también

• El método de Fernández

Referencias

1. Horowitz, Ellis; Sahni, Sartaj (1976-04-01). "Algoritmos exactos y aproximados para la programación de procesadores no idénticos". Revista de la ACM . 23 (2): 317–327. doi : 10.1145/321941.321951 . ISSN  0004-5411. S2CID  18693114.
2. Sahni, Sartaj K. (1 de enero de 1976). "Algoritmos para la programación de tareas independientes". Revista de la ACM . 23 (1): 116–127. doi : 10.1145/321921.321934 . ISSN  0004-5411. S2CID  10956951.
3. Graham, Ron L. (1966). "Límites para ciertas anomalías de multiprocesamiento". Bell System Technical Journal . 45 (9): 1563–1581. doi :10.1002/j.1538-7305.1966.tb01709.x. ISSN  1538-7305.
4. Graham, Ron L. (1 de marzo de 1969). "Límites en anomalías de tiempo de multiprocesamiento". Revista SIAM de Matemáticas Aplicadas . 17 (2): 416–429. doi :10.1137/0117039. ISSN  0036-1399.
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. Budapest, Hungría: 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. Hochbaum, Dorit S.; Shmoys, David B. (1 de enero de 1987). "Uso de algoritmos de aproximación dual para problemas de planificación: resultados teóricos y prácticos". Revista de la ACM . 34 (1): 144–162. doi : 10.1145/7531.7535 . ISSN  0004-5411. S2CID  9739129.
7. Leung, Joseph YT. (8 de mayo de 1989). "Embalaje en contenedores con tamaños de pieza restringidos". Cartas de procesamiento de la información . 31 (3): 145–149. doi :10.1016/0020-0190(89)90223-8. ISSN  0020-0190.
8. Friesen, DK; Deuermeyer, BL (1981-02-01). "Análisis de soluciones voraces para un problema de secuenciación de piezas de repuesto". Matemáticas de la investigación de operaciones . 6 (1): 74–87. doi :10.1287/moor.6.1.74. ISSN  0364-765X.
9. Woeginger, Gerhard J. (1997-05-01). "Un esquema de aproximación de tiempo polinomial para maximizar el tiempo mínimo de finalización de la máquina". Operations Research Letters . 20 (4): 149–154. doi :10.1016/S0167-6377(96)00055-7. ISSN  0167-6377.
10. 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.

Enlaces externos

• Resumen de problemas de máquinas paralelas sin preemisión