Programación de máquinas uniformes

La programación uniforme de máquinas (también llamada programación de máquinas uniformemente relacionadas o programación de máquinas relacionadas ) es un problema de optimización en informática e investigación de operaciones . Es una variante de la programación óptima del trabajo . Se nos dan n trabajos J ₁ , J ₂ , ..., J _n de diferentes tiempos de procesamiento, que deben programarse en m máquinas diferentes. El objetivo es minimizar el makespan : el tiempo total requerido para ejecutar el cronograma. El tiempo que la máquina i necesita para procesar el trabajo j se denota por p _i,j . En el caso general, los tiempos p _i,j no están relacionados y es posible cualquier matriz de tiempos de procesamiento positivos. En la variante específica llamada programación uniforme de máquinas , algunas máquinas son uniformemente más rápidas que otras. Esto significa que, para cada máquina i , hay un factor de velocidad s _i , y el tiempo de ejecución del trabajo j en la máquina i es p _i,j = p _j / s _i .

En la notación estándar de tres campos para problemas de programación óptima de trabajos , la variante de máquina uniforme se denota con Q en el primer campo. Por ejemplo, el problema indicado por " Q|| " es un problema de programación de máquina uniforme sin restricciones, donde el objetivo es minimizar el tiempo máximo de finalización. Un caso especial de programación uniforme de máquinas es la programación de máquinas idénticas , en la que todas las máquinas tienen la misma velocidad. Esta variante se indica con P en el primer campo. $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 Q|| . 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 Q|| . $\sum C_{i}$ $\sum w_{i}C_{i}$

Algoritmos

Minimizar el tiempo medio de finalización

Minimizar el tiempo promedio de finalización se puede hacer en tiempo polinómico:

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|| . $\sum C_{i}$
Horowitz y Sahni ^[1] presentan un algoritmo exacto, con tiempo de ejecución O ( n log mn ), para minimizar el tiempo promedio de finalización en máquinas uniformes , Q|| . $\sum C_{i}$
Bruno, Coffman y Sethi ^[2] presentan un algoritmo, que se ejecuta en el tiempo , para minimizar el tiempo medio de finalización en máquinas no relacionadas , R|| . $O(\max(mn^{2},n^{3}))$ $\sum C_{i}$

Minimizar el tiempo de finalización promedio ponderado

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 . ^[3]

Sahni ^[3] presenta un algoritmo de tiempo exponencial y un algoritmo de aproximación de tiempo polinomial para máquinas idénticas .

Horowitz y Sahni ^[1] presentaron:

Algoritmos de programación dinámica exactos para minimizar el tiempo de finalización promedio ponderado en máquinas uniformes . Estos algoritmos se ejecutan en tiempo exponencial.
Esquemas de aproximación en tiempo polinomial , que para cualquier ε >0, alcanzan como máximo (1+ε)OPT. Para minimizar el tiempo de finalización promedio ponderado en dos máquinas uniformes , el tiempo de ejecución es = , por lo que es un FPTAS. Afirman que sus algoritmos pueden ampliarse fácilmente para cualquier número de máquinas uniformes, pero en este caso no analizan el tiempo de ejecución. No presentan un algoritmo para el tiempo de finalización promedio ponderado en máquinas no relacionadas . $O(10^{l}n^{2})$ $O(n^{2}/\epsilon )$

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

Minimizar el tiempo máximo de finalización es NP-hard incluso para máquinas idénticas , al reducir el problema de partición .

El algoritmo de tiempo de procesamiento más largo primero (LPT) logra una aproximación de factor constante .

Horowitz y Sahni ^[1] presentaron:

Algoritmos de programación dinámica exactos para minimizar el tiempo máximo de finalización en máquinas uniformes y no relacionadas. Estos algoritmos se ejecutan en tiempo exponencial (recuerde que todos estos problemas son NP-difíciles).
Esquemas de aproximación en tiempo polinómico , que para cualquier ε >0, alcanzan como máximo (1+ε)OPT. Para minimizar el tiempo máximo de finalización en dos máquinas uniformes , su algoritmo se ejecuta en el tiempo , donde es el entero más pequeño para el cual . Por lo tanto, el tiempo de ejecución está en , por lo que es un FPTAS . Para minimizar el tiempo máximo de finalización en dos máquinas no relacionadas , el tiempo de ejecución es = . Afirman que sus algoritmos pueden ampliarse fácilmente para cualquier número de máquinas uniformes, pero en este caso no analizan el tiempo de ejecución. $O(10^{2l}n)$ $l$ $\epsilon \geq 2\cdot 10^{-l}$ $O(n/\epsilon ^{2})$ $O(10^{l}n^{2})$ $O(n^{2}/\epsilon )$

Hochbaum y Shmoys ^[4] presentaron varios algoritmos de aproximación para cualquier número de máquinas idénticas . Posteriormente ^[5] desarrollaron un PTAS para máquinas uniformes .

Epstein y Sgall ^[6] generalizaron el PTAS para máquinas uniformes para manejar funciones objetivas más generales. Sea Ci (para i _entre 1 y m ) la duración de la máquina i en un programa dado. 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 suma ( f ( C _i )).

Monotonicidad y veracidad

En algunos entornos, la velocidad de la máquina es información privada de la máquina y queremos incentivar a las máquinas a que revelen su verdadera velocidad, es decir, queremos un mecanismo veraz . Una consideración importante para lograr la veracidad es la monotonicidad . ^[7] Significa que, si una máquina informa una velocidad más alta y todas las demás entradas permanecen iguales, entonces el tiempo total de procesamiento asignado a la máquina aumenta débilmente. Para este problema:

Auletta, De Prisco, Penna y Persiano ^[8] presentaron un algoritmo monótono de 4 aproximaciones, que se ejecuta en politiempo cuando el número de máquinas es fijo.
Ambrosio y Auletta ^[9] demostraron que el algoritmo de tiempo de procesamiento más largo es monótono siempre que las velocidades de la máquina son potencias de algún c ≥ 2, pero no cuando c ≤ 1,78. Por el contrario, la programación de listas no es monótona para c > 2.
Andelman, Azar y Sorani ^[10] presentaron un algoritmo monótono de 5 aproximaciones, que se ejecuta en politiempo incluso cuando el número de máquinas es variable.
Kovacz ^[11] presentó un algoritmo monótono de 3 aproximaciones.

Extensiones

Puestos de trabajo dependientes : En algunos casos, los puestos de trabajo pueden ser dependientes. Por ejemplo, tome el caso de leer las credenciales de usuario desde la consola, luego utilícelas para autenticarse y luego, si la autenticación es exitosa, muestre algunos datos en la consola. Es evidente que una tarea depende de otra. Este es un caso claro en el que existe algún tipo de ordenamiento entre las tareas. De hecho, está claro que se puede modelar con ordenamiento parcial . Entonces, por definición, el conjunto de tareas constituye una estructura reticular . Esto añade más complicaciones al problema de la programación multiprocesador.

Estático versus dinámico : los algoritmos de programación de máquinas son estáticos o dinámicos. Un algoritmo de programación es estático si las decisiones de programación sobre qué tareas computacionales se asignarán a qué procesadores se realizan antes de ejecutar el programa. Un algoritmo es dinámico si se toma en tiempo de ejecución. Para los algoritmos de programación estática, un enfoque típico es clasificar las tareas según sus relaciones de precedencia y utilizar una técnica de programación de listas para programarlas en los procesadores. ^[12]

Trabajos de varias etapas : en diversas configuraciones, cada trabajo puede tener varias operaciones que deben ejecutarse en paralelo. Algunas de estas configuraciones se manejan mediante programación de taller abierto , programación de taller de flujo y programación de taller de trabajo .

enlaces externos

Resumen de problemas de máquinas paralelas sin preferencia

Referencias

^ abcdeHorowitz , 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.
^ Bruno, J.; Coffman, EG; Sethi, R. (1 de julio de 1974). "Programación de tareas independientes para reducir el tiempo medio de finalización". Comunicaciones de la ACM . 17 (7): 382–387. doi : 10.1145/361011.361064 . ISSN 0001-0782.
^ ab 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.
^ 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.
^ Hochbaum, Dorit S.; Shmoys, David B. (1 de junio de 1988). "Un esquema de aproximación polinomial para la programación en procesadores uniformes: uso del enfoque de aproximación dual". Revista SIAM de Computación . 17 (3): 539–551. doi :10.1137/0217033. ISSN 0097-5397.
^ Epstein, Leah; Sgall, Jiri (1 de mayo de 2004). "Esquemas de aproximación para la programación en máquinas paralelas idénticas y uniformemente relacionadas". Algorítmica . 39 (1): 43–57. doi :10.1007/s00453-003-1077-7. ISSN 1432-0541. S2CID 12965369.
^ Arquero, A.; Tardos, E. (1 de octubre de 2001). "Mecanismos veraces para agentes uniparamétricos". Actas del 42º Simposio del IEEE sobre fundamentos de la informática . págs. 482–491. doi :10.1109/SFCS.2001.959924. ISBN 0-7695-1390-5. S2CID 11377808.
^ Auletta, Vincenzo; De Prisco, Roberto; Peña, Paolo; Persiano, Giuseppe (2004). "Mecanismos deterministas de aproximación veraz para la programación de máquinas relacionadas". En Diekert, Volker; Habib, Michel (eds.). Estadísticas 2004 . Apuntes de conferencias sobre informática. vol. 2996. Berlín, Heidelberg: Springer. págs. 608–619. doi :10.1007/978-3-540-24749-4_53. ISBN 978-3-540-24749-4.
^ Ambrosio, Pasquale; Auletta, Vincenzo (2005). "Algoritmos monótonos deterministas para programación en máquinas relacionadas". En persa, Giuseppe; Solís-Oba, Roberto (eds.). Aproximación y Algoritmos en Línea . Apuntes de conferencias sobre informática. vol. 3351. Berlín, Heidelberg: Springer. págs. 267–280. doi :10.1007/978-3-540-31833-0_22. ISBN 978-3-540-31833-0.
^ Andelman, Nir; Azar, Yossi; Sorani, Motti (2005). "Mecanismos de aproximación veraces para programar máquinas relacionadas egoístas". En Diekert, Volker; Durand, Bruno (eds.). Estadísticas 2005 . Apuntes de conferencias sobre informática. vol. 3404. Berlín, Heidelberg: Springer. págs. 69–82. doi :10.1007/978-3-540-31856-9_6. ISBN 978-3-540-31856-9.
^ Kovács, Annamária (2005). "Algoritmo rápido de aproximación monótona de 3 para programar máquinas relacionadas". En Brodal, Gerth Stølting; Leonardi, Stefano (eds.). Algoritmos – ESA 2005 . Apuntes de conferencias sobre informática. vol. 3669. Berlín, Heidelberg: Springer. págs. 616–627. doi :10.1007/11561071_55. ISBN 978-3-540-31951-1.
^ Kwok, Yu-Kwong; Ahmad, Ishfaq (1 de diciembre de 1999). "Algoritmos de programación estática para asignar gráficos de tareas dirigidas a multiprocesadores". Encuestas de Computación ACM . 31 (4): 406–471. CiteSeerX 10.1.1.322.2295 . doi :10.1145/344588.344618. ISSN 0360-0300. S2CID 207614150.