Programación de máquinas uniformes

La programación uniforme de la máquina (también denominada programación de la máquina relacionada de manera uniforme o programación de la máquina relacionada ) es un problema de optimización en la ciencia de la computación y la investigación de operaciones . Es una variante de la programación de trabajos óptima . Se nos asignan n trabajos J ₁ , J ₂ , ..., J _n de diferentes tiempos de procesamiento, que deben programarse en m máquinas diferentes. El objetivo es minimizar el lapso de tiempo : el tiempo total requerido para ejecutar el cronograma. El tiempo que la máquina yonecesidades para el trabajo proceso de 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 denominada programación uniforme de la máquina , 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 de trabajos óptimos , la variante de máquina uniforme se indica con Q en el primer campo. Por ejemplo, el problema denotado por " Q || " es un problema de programación uniforme de la máquina sin restricciones, donde el objetivo es minimizar el tiempo máximo de finalización. Un caso especial de programación uniforme de la máquina es la programación idéntica de la máquina , en la que todas las máquinas tienen la misma velocidad. Esta variante se indica con P en el primer campo. ${\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 sobre los n trabajos); se denota por Q || . De manera más general, cuando algunos trabajos son más importantes que otros, se puede desear minimizar un promedio ponderado del tiempo de finalización, donde cada trabajo tiene un peso diferente. Esto se denota con Q || . ${\displaystyle \sum C_{i}}$${\displaystyle \sum w_{i}C_{i}}$

Algoritmos

Minimizar el tiempo medio de finalización

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

Minimizar el tiempo de finalización promedio ponderado

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

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

Horowitz y Sahni ^[2] 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.
• Los esquemas de aproximación de tiempo polinómico , que para cualquier ε > 0, alcanzan como máximo (1 + ε) OPT. Para minimizar el tiempo medio ponderado de finalización en dos máquinas uniformes , el tiempo de ejecución es = , por lo que es un FPTAS. Afirman que sus algoritmos se pueden ampliar 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 .${\displaystyle O(10^{l}n^{2})}$${\displaystyle 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 , al reducir el problema de la partición .

Horowitz y Sahni ^[2] 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).
• Los esquemas de aproximación de 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 número 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 ampliar fácilmente para cualquier número de máquinas uniformes, pero no analizan el tiempo de ejecución en este caso.${\displaystyle O(10^{2l}n)}$${\displaystyle l}$${\displaystyle \epsilon \geq 2\cdot 10^{-l}}$${\displaystyle O(n/\epsilon ^{2})}$${\displaystyle O(10^{l}n^{2})}$${\displaystyle O(n^{2}/\epsilon )}$

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

Epstein y Sgall ^[7] generalizaron el PTAS para máquinas uniformes para manejar funciones objetivas más generales. Sea C _i (para i entre 1 y m ) la capacidad de fabricació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 suma de la función objetivo ( f ( C _i )).

Extensiones

Trabajos dependientes : en algunos casos, los trabajos pueden ser dependientes. Por ejemplo, tome el caso de leer las credenciales de usuario desde la consola, luego utilícelo para autenticarse, luego, si la autenticación es exitosa, muestre algunos datos en la consola. Claramente, 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 de celosía . Esto agrega una mayor complicación al problema de programación de multiprocesador.

Estático versus dinámico : los algoritmos de programación de la máquina son estáticos o dinámicos. Un algoritmo de programación es estático si las decisiones de programación en cuanto a 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 de acuerdo con sus relaciones de precedencia y utilizar una técnica de programación de listas para programarlas en los procesadores. ^[8]

Trabajos de varias etapas : en varias configuraciones, cada trabajo puede tener varias operaciones que deben ejecutarse en paralelo. Algunos de tales ajustes son manejados por la programación de tienda abierta , tienda de flujo de programación y taller de trabajo de programación .

enlaces externos

• Resumen de problemas de máquinas paralelas sin preeminencia

Referencias

1. 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 .
2. 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 . 
3. 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 . 
4. Sahni, Sartaj K. (1 de enero de 1976). "Algoritmos para programar tareas independientes" . Revista de la ACM . 23 (1): 116-127. doi : 10.1145 / 321921.321934 . ISSN 0004-5411 . 
5. Hochbaum, Dorit S .; Shmoys, David B. (1 de enero de 1987). "Utilización de algoritmos de aproximación dual para la programación de resultados teóricos y prácticos de problemas" . Revista de la ACM . 34 (1): 144-162. doi : 10.1145 / 7531.7535 . ISSN 0004-5411 . S2CID 9739129 .  
6. Hochbaum, Dorit S .; Shmoys, David B. (1 de junio de 1988). "Un esquema de aproximación polinomial para la programación en procesadores uniformes: utilizando el enfoque de aproximación dual" . Revista SIAM de Computación . 17 (3): 539–551. doi : 10.1137 / 0217033 . ISSN 0097-5397 . 
7. 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" . Algoritmica . 39 (1): 43–57. doi : 10.1007 / s00453-003-1077-7 . ISSN 1432-0541 . 
8. Kwok, Yu-Kwong; Ahmad, Ishfaq (1 de diciembre de 1999). "Algoritmos de programación estática para la asignación de 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 .