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 diferentes tiempos de procesamiento, que deben programarse en m máquinas idénticas, de modo que se optimice una determinada función objetivo, por ejemplo, se minimice el intervalo de producción .

La programación de máquinas idénticas es un caso especial de programación uniforme de máquinas , que en sí misma 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 una programación de máquina idéntica, 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 de múltiples vías . 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 indica con P en el primer campo. Por ejemplo, " P|| " es un problema de programación de máquina idéntico 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 medio de finalización (promediado de 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

Minimizar el tiempo promedio de finalización ( P|| ) se puede hacer en tiempo polinomial. El algoritmo SPT (el tiempo de procesamiento más corto primero) clasifica 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 el tiempo O ( n log n ) y minimiza el tiempo promedio de finalización en máquinas idénticas, ^[1] P|| . ${\displaystyle \sum C_{i}}$ ${\displaystyle \sum C_{i}}$

• Puede haber muchos horarios del SPT; encontrar el cronograma SPT con el tiempo de finalización más pequeño (también llamado OMFT – tiempo de finalización medio óptimo ) es NP-difícil.

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

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

• Tiempo promedio de finalización óptimo;
• 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 , al reducir el 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 el tiempo O ( n ). ${\displaystyle 2-1/m}$
• El algoritmo de programación de listas específico llamado Tiempo de procesamiento más largo primero (LPT), que ordena los trabajos por longitud descendente, es una aproximación para máquinas idénticas . ^{[4] : sección 5} También se le 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 packaging , que tiene un factor de aproximación de 13/11≈1.182.

Huang y Lu ^[5] presentaron un algoritmo de tiempo polinomial simple que logra una aproximación 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 maximin-share .

Sahni ^[2] presentó un PTAS que alcanza (1+ε)OPT en el 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 una relació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 una relació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 una relación de aproximación como máximo (1+ε) en el tiempo . Este es un PTAS . Tenga en cuenta 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 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 repuestos 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 el mayor tiempo posible. ^[8] El algoritmo LPT alcanza al menos el ó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 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 objetivo generales

Alon, Azar, Woeginger y Yadid ^[10] consideran una función objetivo más general. Dada una función real positiva f , que depende sólo de los tiempos de finalización Ci _, consideran los objetivos de minimizar , minimizar , maximizar y maximizar . Demuestran que, si f es no negativo, convexo y satisface un fuerte supuesto de continuidad que llaman "F*", entonces ambos problemas de minimización tienen un PTAS. De manera similar, si f es no negativo, cóncavo y satisface F*, entonces ambos problemas de maximización tienen un PTAS. En ambos casos, el tiempo de ejecución del PTAS es O( n ), pero con constantes 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})}$

Ver también

• El método de Fernández.

Referencias

1. Horowitz, Ellis; Sahni, Sartaj (1 de abril de 1976). "Algoritmos exactos y aproximados para programar 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 de determinadas anomalías de multiprocesamiento". Revista técnica del sistema Bell . 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 de las anomalías de sincronización del multiprocesamiento". Revista SIAM de Matemática Aplicada . 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 compartidas de Maximin". Actas de la 22ª Conferencia ACM sobre Economía y Computación . CE '21. Budapest, Hungría: Asociación de Maquinaria Informática. 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 programación de 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 información . 31 (3): 145-149. doi :10.1016/0020-0190(89)90223-8. ISSN  0020-0190.
8. Friesen, DK; Deuermeyer, BL (1 de febrero de 1981). "Análisis de soluciones codiciosas 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. (1 de mayo de 1997). "Un esquema de aproximación de tiempo polinomial para maximizar el tiempo mínimo de finalización de la máquina". Cartas de investigación operativa . 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 programación en máquinas paralelas". Diario de programación . 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 preferencia