Programación de máquinas uniformes

La programación uniforme de máquinas (también llamada programación uniformemente relacionada de máquinas o programación relacionada de máquinas ) es un problema de optimización en ciencias de la computación e investigación de operaciones . Es una variante de la programación óptima de trabajos . Se nos dan n trabajos J ₁ , J ₂ , ..., J _n con tiempos de procesamiento variables, que deben programarse en m máquinas diferentes. El objetivo es minimizar el tiempo de finalización (makespan) , es decir, el tiempo total requerido 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|| $C_{\max }$ " es un problema de programación de máquinas uniforme sin restricciones, donde el objetivo es minimizar el tiempo máximo de finalización. Un caso especial de programación de máquinas 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.

En algunas variantes del problema, en lugar de minimizar el tiempo máximo de finalización, se desea minimizar el tiempo promedio de finalización (promediado sobre todos los n trabajos); se denota por Q||. $\sum C_{i}$ . 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 w_{i}C_{i}$ .

Algoritmos

Minimizar el tiempo medio de finalización

Minimizar el tiempo medio de finalización se puede hacer en tiempo polinomial:

El algoritmo SPT (Shortest Processing Time First) ordena los trabajos por su duración, del más corto al más largo, 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 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 tiempo $O(\max(mn^{2},n^{3}))$ , para minimizar el tiempo promedio de finalización en máquinas no relacionadas , R|| $\sum C_{i}$ .

Minimizar el tiempo promedio ponderado de finalización

Minimizar el tiempo promedio ponderado de finalización 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 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 exactos de programación dinámica 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 $O(10^{l}n^{2})$ = $O(n^{2}/\epsilon )$ Por lo tanto, se trata de un FPTAS. Afirman que sus algoritmos pueden extenderse fácilmente a 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 .

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 .

El algoritmo de procesamiento con mayor tiempo de procesamiento (LPT, por sus siglas en inglés) permite obtener una aproximación con factor constante .

Horowitz y Sahni ^{[ 1 ]} presentaron:

Algoritmos exactos de programación dinámica para minimizar el tiempo máximo de finalización en máquinas uniformes y no relacionadas. Estos algoritmos se ejecutan en tiempo exponencial (recordemos que todos estos problemas son NP-difíciles).
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 tiempo $O(10^{2l}n)$ , dónde $l$ es el entero más pequeño para el cual $\epsilon \geq 2\cdot 10^{-l}$ Por lo tanto, el tiempo de ejecución está en $O(n/\epsilon ^{2})$ , 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 $O(10^{l}n^{2})$ = $O(n^{2}/\epsilon )$ Afirman que sus algoritmos se pueden extender fácilmente a cualquier número de máquinas uniformes, pero no analizan el tiempo de ejecución en este caso.

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 objetivo más generales. Sea C _i (para i entre 1 y m ) el tiempo de finalización de la máquina i en una programación dada. 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 casos, la velocidad de la máquina es información privada de la misma, y queremos incentivar a las máquinas a revelar su velocidad real; es decir, queremos un mecanismo veraz . Una consideración importante para lograr la veracidad es la monotonicidad . ^{[ 7 ]} Esto significa que, si una máquina informa una velocidad mayor y todas las demás entradas permanecen iguales, entonces el tiempo total de procesamiento asignado a la máquina aumenta ligeramente. Para este problema:

Auletta, De Prisco, Penna y Persiano ^{[ 8 ]} presentaron un algoritmo monótono de 4 aproximaciones, que se ejecuta en tiempo polinomial 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 las máquinas sean potencias de algún c ≥ 2, pero no cuando c ≤ 1,78. Por el contrario, la planificació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 tiempo polinomial incluso cuando el número de máquinas es variable.
Kovacz ^{[ 11 ]} presentó un algoritmo monótono de 3 aproximaciones.

Extensiones

Tareas dependientes : En algunos casos, las tareas pueden ser dependientes. Por ejemplo, consideremos el caso de leer las credenciales de usuario desde la consola, 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 donde existe algún tipo de orden entre las tareas. De hecho, es evidente que se puede modelar con un orden parcial . Entonces, por definición, el conjunto de tareas constituye una estructura reticular . Esto añade una mayor complejidad al problema de la planificación de multiprocesadores.

Estático versus Dinámico : Los algoritmos de planificación de máquinas son estáticos o dinámicos. Un algoritmo de planificación es estático si las decisiones 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 planificación estática, un enfoque típico consiste en clasificar las tareas según sus relaciones de precedencia y utilizar una técnica de planificación por listas para asignarlas a los procesadores. ^{[ 12 ]}

Trabajos multietapa : En diversos entornos, cada trabajo puede tener varias operaciones que deben ejecutarse en paralelo. Algunos de estos entornos se gestionan mediante la planificación de taller abierto , la planificación de taller de flujo y la planificación de taller de trabajos .

Enlaces externos

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

Referencias

1 2 3 4 5 Horowitz, Ellis; Sahni, Sartaj (1976-04-01). "Algoritmos exactos y aproximados para la planificación de procesadores no idénticos" . Journal of the 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" . Communications of the ACM . 17 (7): 382– 387. doi : 10.1145/361011.361064 . ISSN 0001-0782 .
1 2 Sahni, Sartaj K. (1976-01-01). "Algoritmos para la programación de tareas independientes" . Journal of the ACM . 23 (1): 116– 127. doi : 10.1145/321921.321934 . ISSN 0004-5411 .
↑ Hochbaum, Dorit S.; Shmoys, David B. (1987-01-01). "Uso de algoritmos de aproximación dual para problemas de programación: resultados teóricos y prácticos" . Journal of the ACM . 34 (1): 144– 162. doi : 10.1145/7531.7535 . ISSN 0004-5411 . S2CID 9739129 .
↑ Hochbaum, Dorit S.; Shmoys, David B. (1988-06-01). "Un esquema de aproximación polinomial para la planificación en procesadores uniformes: utilizando el enfoque de aproximación dual" . SIAM Journal on Computing . 17 (3): 539– 551. doi : 10.1137/0217033 . ISSN 0097-5397 .
↑ Epstein, Leah; Sgall, Jiri (2004-05-01). "Esquemas de aproximación para la planificación en máquinas paralelas idénticas y relacionadas uniformemente" . 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. S2CID 11377808 .
↑ Auletta, Vincenzo; De Prisco, Roberto; Penna, Paolo; Persiano, Giuseppe (2004). «Mecanismos de aproximación veraces deterministas para máquinas relacionadas con la planificación» . En Diekert, Volker; Habib, Michel (eds.). Stacs 2004. Lecture Notes in Computer Science. Vol. 2996. Berlín, Heidelberg: Springer. pp. 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 planificación en máquinas relacionadas» . En Persiano, Giuseppe; Solis-Oba, Roberto (eds.). Aproximación y algoritmos en línea . Lecture Notes in Computer Science. Vol. 3351. Berlín, Heidelberg: Springer. pp. 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 la planificació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. pp. 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 3 para la planificación de máquinas relacionadas" . En Brodal, Gerth Stølting; Leonardi, Stefano (eds.). Algoritmos – ESA 2005. Lecture Notes in Computer Science. Vol. 3669. Berlín, Heidelberg: Springer. pp. 616–627 . doi : 10.1007/11561071_55 . ISBN 978-3-540-31951-1.
↑ Kwok, Yu-Kwong; Ahmad, Ishfaq (1999-12-01). "Algoritmos de planificación estática para la asignación de grafos 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 .

[:0-1] 1 2 3 4 5 Horowitz, Ellis; Sahni, Sartaj (1976-04-01). "Algoritmos exactos y aproximados para la planificación de procesadores no idénticos" . Journal of the ACM . 23 (2): 317– 327. doi : 10.1145/321941.321951 . ISSN 0004-5411 . S2CID 18693114 .

[2] Bruno, J.; Coffman, EG; Sethi, R. (1974-07-01). "Programación de tareas independientes para reducir el tiempo medio de finalización" . Communications of the ACM . 17 (7): 382– 387. doi : 10.1145/361011.361064 . ISSN 0001-0782 .

[:3-3] 1 2 Sahni, Sartaj K. (1976-01-01). "Algoritmos para la programación de tareas independientes" . Journal of the ACM . 23 (1): 116– 127. doi : 10.1145/321921.321934 . ISSN 0004-5411 .

[:02-4] Hochbaum, Dorit S.; Shmoys, David B. (1987-01-01). "Uso de algoritmos de aproximación dual para problemas de programación: resultados teóricos y prácticos" . Journal of the ACM . 34 (1): 144– 162. doi : 10.1145/7531.7535 . ISSN 0004-5411 . S2CID 9739129 .

[5] Hochbaum, Dorit S.; Shmoys, David B. (1988-06-01). "Un esquema de aproximación polinomial para la planificación en procesadores uniformes: utilizando el enfoque de aproximación dual" . SIAM Journal on Computing . 17 (3): 539– 551. doi : 10.1137/0217033 . ISSN 0097-5397 .

[6] Epstein, Leah; Sgall, Jiri (2004-05-01). "Esquemas de aproximación para la planificación en máquinas paralelas idénticas y relacionadas uniformemente" . Algorithmica . 39 (1): 43– 57. doi : 10.1007/s00453-003-1077-7 . ISSN 1432-0541 . S2CID 12965369 .

[7] 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. S2CID 11377808 .

[8] Auletta, Vincenzo; De Prisco, Roberto; Penna, Paolo; Persiano, Giuseppe (2004). «Mecanismos de aproximación veraces deterministas para máquinas relacionadas con la planificación» . En Diekert, Volker; Habib, Michel (eds.). Stacs 2004. Lecture Notes in Computer Science. Vol. 2996. Berlín, Heidelberg: Springer. pp. 608–619 . doi : 10.1007/978-3-540-24749-4_53 . ISBN 978-3-540-24749-4.

[9] Ambrosio, Pasquale; Auletta, Vincenzo (2005). «Algoritmos monótonos deterministas para la planificación en máquinas relacionadas» . En Persiano, Giuseppe; Solis-Oba, Roberto (eds.). Aproximación y algoritmos en línea . Lecture Notes in Computer Science. Vol. 3351. Berlín, Heidelberg: Springer. pp. 267–280 . doi : 10.1007/978-3-540-31833-0_22 . ISBN 978-3-540-31833-0.

[10] Andelman, Nir; Azar, Yossi; Sorani, Motti (2005). «Mecanismos de aproximación veraces para la planificació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. pp. 69–82 . doi : 10.1007/978-3-540-31856-9_6 . ISBN 978-3-540-31856-9.

[11] Kovács, Annamária (2005). "Algoritmo rápido de aproximación monótona 3 para la planificación de máquinas relacionadas" . En Brodal, Gerth Stølting; Leonardi, Stefano (eds.). Algoritmos – ESA 2005. Lecture Notes in Computer Science. Vol. 3669. Berlín, Heidelberg: Springer. pp. 616–627 . doi : 10.1007/11561071_55 . ISBN 978-3-540-31951-1.

[12] Kwok, Yu-Kwong; Ahmad, Ishfaq (1999-12-01). "Algoritmos de planificación estática para la asignación de grafos 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 .

[ 2 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]