Programación de máquinas uniformes - Uniform-machines scheduling
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 1 , J 2 , ..., 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 necesita la máquina i 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 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.
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 || .
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 , P || .
- Horowitz y Sahni 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 || .
- Bruno, Coffman y Sethi presentan un algoritmo, que se ejecuta en el tiempo , para minimizar el tiempo medio de finalización en máquinas no relacionadas , R || .
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 .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 .
Sahni presenta un algoritmo de tiempo exponencial y un algoritmo de aproximación de tiempo polinomial para máquinas idénticas .
Horowitz y Sahni 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 .
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 .
Se logra una aproximación de factor constante mediante el algoritmo de tiempo de procesamiento más largo (LPT).
Horowitz y Sahni 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.
Hochbaum y Shmoys presentaron varios algoritmos de aproximación para cualquier número de máquinas idénticas . Posteriormente, desarrollaron un PTAS para máquinas uniformes .
Epstein y Sgall 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 )).
Monotonicidad y veracidad
En algunos entornos, la velocidad de la máquina es la información privada de la máquina y queremos incentivar a las máquinas para que revelen su verdadera velocidad, es decir, queremos un mecanismo veraz . Una consideración importante para lograr la veracidad es la monotonicidad . Significa que, si una máquina informa una velocidad más alta, y todas las demás entradas siguen siendo las mismas, entonces el tiempo total de procesamiento asignado a la máquina aumenta débilmente. Para este problema:
- Auletta, De Prisco, Penna y Persiano presentaron un algoritmo monótono de 4 aproximaciones, que se ejecuta en tiempo múltiple cuando el número de máquinas es fijo.
- Ambrosio y Auletta 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 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 presentaron un algoritmo monótono de 5 aproximaciones, que se ejecuta en tiempo múltiple incluso cuando el número de máquinas es variable.
- Kovacz presentó un algoritmo monótono de 3 aproximaciones.
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.
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
Referencias
- ^ 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 .
- ^ a b c d 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 .
- ^ 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 .
- ↑ a b 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 .
- ↑ 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 .
- ↑ 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 .
- ^ 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 .
- ^ Archer, A .; Tardos, E. (1 de octubre de 2001). "Mecanismos veraces para agentes monoparámetros" . Actas 42º Simposio del IEEE sobre fundamentos de la informática : 482–491. doi : 10.1109 / SFCS.2001.959924 .
- ^ Auletta, Vincenzo; De Prisco, Roberto; Penna, Paolo; Persiano, Giuseppe (2004). Diekert, Volker; Habib, Michel (eds.). "Mecanismos deterministas de aproximación veraz para la programación de máquinas relacionadas" . STACS 2004 . Apuntes de conferencias en Ciencias de la Computación. Berlín, Heidelberg: Springer: 608–619. doi : 10.1007 / 978-3-540-24749-4_53 . ISBN 978-3-540-24749-4.
- ^ Ambrosio, Pasquale; Auletta, Vincenzo (2005). Persiano, Giuseppe; Solis-Oba, Roberto (eds.). "Algoritmos monótonos deterministas para la programación en máquinas relacionadas" . Aproximación y algoritmos online . Apuntes de conferencias en Ciencias de la Computación. Berlín, Heidelberg: Springer: 267–280. doi : 10.1007 / 978-3-540-31833-0_22 . ISBN 978-3-540-31833-0.
- ^ Andelman, Nir; Azar, Yossi; Sorani, Motti (2005). Diekert, Volker; Durand, Bruno (eds.). "Mecanismos de aproximación veraz para la programación de máquinas relacionadas egoístas" . STACS 2005 . Apuntes de conferencias en Ciencias de la Computación. Berlín, Heidelberg: Springer: 69–82. doi : 10.1007 / 978-3-540-31856-9_6 . ISBN 978-3-540-31856-9.
- ^ Kovács, Annamária (2005). Brodal, Gerth Stølting; Leonardi, Stefano (eds.). "Algoritmo de aproximación rápida monótono 3 para la programación de máquinas relacionadas" . Algoritmos - ESA 2005 . Apuntes de conferencias en Ciencias de la Computación. Berlín, Heidelberg: Springer: 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 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 .