Programación de máquinas uniformes

La programación uniforme de máquinas (también llamada programación uniforme de máquinas 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 de trabajos . Se nos dan n trabajos J ₁ , J ₂ , ..., J _n de tiempos de procesamiento variables, que deben programarse en m máquinas diferentes. El objetivo es minimizar el tiempo de ejecución , el tiempo total necesario para ejecutar la programación. 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 por Q en el primer campo. Por ejemplo, el problema denotado 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 de máquina uniforme es la programación de máquinas idénticas , en la que todas las máquinas tienen la misma velocidad. Esta variante se denota por 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 de finalización promedio (promediado sobre todos 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|| . $\suma C_{i}$ $\sum w_{i}C_{i}$

Algoritmos

Minimizar el tiempo medio de finalización

La minimización del tiempo medio de finalización se puede realizar en tiempo polinomial:

El algoritmo SPT (Shortest Processing Time First) ordena los trabajos por su longitud, comenzando por el más corto, y luego los asigna al procesador con el tiempo de finalización más temprano hasta el momento. Se ejecuta en un tiempo O( n log n ) y minimiza el tiempo de finalización promedio en máquinas idénticas , ^[1] P|| . $\suma 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|| . $\suma C_{i}$
Bruno, Coffman y Sethi ^[2] presentan un algoritmo, que se ejecuta en el tiempo , para minimizar el tiempo promedio de finalización en máquinas no relacionadas , R|| . $O(\max(mn^{2},n^{3}))$ $\suma 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 , 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 . ^[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 de 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 se pueden extender fácilmente para cualquier número de máquinas uniformes, pero no analizan el tiempo de ejecución en este caso. 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-difícil incluso para máquinas idénticas , por reducción del problema de partición .

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

Horowitz y Sahni ^[1] presentaron:

Algoritmos de programación dinámica exactos para minimizar el tiempo máximo de finalización tanto en máquinas uniformes como no relacionadas. Estos algoritmos se ejecutan en tiempo exponencial (recuerde que todos estos problemas son NP-hard).
Esquemas de aproximación de tiempo polinomial , 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 se pueden extender fácilmente para cualquier número de máquinas uniformes, pero no analizan el tiempo de ejecución en este caso. $O(10^{2l}n)$ ${\estilo de visualizació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 . Más tarde, ^[5] desarrollaron un PTAS para máquinas uniformes .

Epstein y Sgall ^[6] generalizaron el PTAS para máquinas uniformes para manejar funciones objetivo más generales. Sea C _i (para i entre 1 y m ) el tiempo de ejecució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 sum( f ( C _i )).

Monotonía y veracidad

En algunos entornos, la velocidad de la máquina es información privada de la máquina y queremos incentivarla para que revele su velocidad real, es decir, queremos un mecanismo veraz . Una consideración importante para lograr la veracidad es la monotonía . ^[7] Esto 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 sean potencias de algún valor 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

Trabajos dependientes : en algunos casos, los trabajos pueden ser dependientes. Por ejemplo, tomemos el caso de leer las credenciales de usuario desde la consola, luego usarlas para autenticarse y, si la autenticación es exitosa, mostrar algunos datos en la consola. Claramente, una tarea depende de otra. Este es un caso claro en el que existe algún tipo de orden entre las tareas. De hecho, está claro que se puede modelar con un orden parcial . Entonces, por definición, el conjunto de tareas constituye una estructura reticular . Esto agrega más complejidad al problema de programación de multiprocesadores.

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 toman 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áticos, un enfoque típico es clasificar las tareas según sus relaciones de precedencia y usar 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 gestionan mediante programación de taller abierto , programación de taller de flujo y programación de taller por trabajo .

Enlaces externos

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

Referencias

^ abcde Horowitz, Ellis; Sahni, Sartaj (1 de abril de 1976). "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.
^ Bruno, J.; Coffman, EG; Sethi, R. (1974-07-01). "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. (1976-01-01). "Algoritmos para programar 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 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.
^ 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 informática . 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 planificación en máquinas paralelas uniformemente relacionadas e idénticas". Algorithmica . 39 (1): 43–57. doi :10.1007/s00453-003-1077-7. ISSN 1432-0541. S2CID 12965369.
^ Archer, A.; Tardos, E. (1 de octubre de 2001). "Mecanismos veraces para agentes de un parámetro". Actas del 42.º Simposio IEEE sobre Fundamentos de la informática . págs. 482–491. doi :10.1109/SFCS.2001.959924. ISBN 0-7695-1390-5. Número de identificación del sujeto 11377808.
^ Auletta, Vincenzo; De Prisco, Roberto; Penna, Paolo; Persiano, Giuseppe (2004). "Mecanismos de aproximación veraz deterministas para la programación de máquinas relacionadas". En Diekert, Volker; Habib, Michel (eds.). Stacs 2004. Lecture Notes in Computer Science. 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 la programación en máquinas relacionadas". En Persiano, Giuseppe; Solis-Oba, Roberto (eds.). Aproximación y algoritmos en línea . Apuntes de clase en 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 veraz para la programación de máquinas relacionadas egoístas". En Diekert, Volker; Durand, Bruno (eds.). Stacs 2005. Lecture Notes in Computer Science. 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 3 aproximaciones monótonas para la programación de máquinas relacionadas". En Brodal, Gerth Stølting; Leonardi, Stefano (eds.). Algoritmos – ESA 2005. Apuntes de clase en 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 (1999-12-01). "Algoritmos de programación estática para asignar gráficos de tareas dirigidas a multiprocesadores". ACM Computing Surveys . 31 (4): 406–471. CiteSeerX 10.1.1.322.2295 . doi :10.1145/344588.344618. ISSN 0360-0300. S2CID 207614150.