Planificación de tareas en paralelo

La planificación de tareas paralelas (también llamada planificación de trabajos paralelos ^{[ 1 ] [ 2 ]} o planificación de procesamiento paralelo ^{[ 3 ]} ) es un problema de optimización _en ciencias de la computación e investigación de operaciones . Es una variante de la planificación óptima de trabajos . En un problema general de planificación de trabajos, se nos dan n trabajos J1 , J2 _, ... , Jn _de tiempos de procesamiento variables, que deben planificarse en m máquinas mientras se intenta minimizar el makespan - la duración total de la planificación (es decir, cuando todos los trabajos han terminado de procesarse). En la variante específica conocida como planificación _de tareas paralelas , todas las máquinas son idénticas. Cada trabajo j tiene un parámetro _de duración pj y un parámetro de tamaño qj , y debe ejecutarse durante exactamente pj pasos de tiempo en _exactamente qj _máquinas en paralelo .   

Veltman et al. ^{[ 4 ]} y Drozdowski ^{[ 3 ]} denotan este problema por${\displaystyle P|size_{j}|C_{\max }}$En la notación de tres campos introducida por Graham et al. ^{[ 5 ],} P significa que hay varias máquinas idénticas funcionando en paralelo; tamaño _j significa que cada trabajo tiene un parámetro de tamaño; C _max significa que el objetivo es minimizar el tiempo máximo de finalización. Algunos autores utilizan ${\displaystyle P|m_{j}|C_{\max }}$en cambio. ^{[ 1 ]} Nótese que el problema de la planificación de máquinas paralelas es un caso especial de planificación de tareas paralelas donde${\displaystyle size_{j}=1}$para todos los j , es decir, cada trabajo debe ejecutarse en una sola máquina.

Los orígenes de esta formulación del problema se remontan a 1960. ^{[ 6 ]} Para este problema, no existe ningún algoritmo de aproximación de tiempo polinomial con una razón menor que${\displaystyle 3/2}$a menos que${\displaystyle P=NP}$. ^{[ 7 ]}

Hay un conjunto${\displaystyle {\mathcal {J}}}$de${\displaystyle n}$empleos y${\displaystyle m}$máquinas idénticas. Cada trabajo${\displaystyle j\in {\mathcal {J}}}$tiene un tiempo de procesamiento${\displaystyle p_{j}\in \mathbb {N} }$(también llamada la longitud de j ), y requiere el uso simultáneo de${\displaystyle q_{j}\in \mathbb {N} }$máquinas durante su ejecución (también llamado tamaño o ancho de j).

Un cronograma asigna cada trabajo${\displaystyle j\in {\mathcal {J}}}$a una hora de inicio${\displaystyle s_{j}\in \mathbb {N} _{0}}$y un conjunto${\displaystyle m_{j}\subseteq \{1,\dots ,m\}}$de${\displaystyle |m_{j}|=q_{j}}$máquinas en las que se procesará. Un cronograma es factible si cada procesador ejecuta como máximo un trabajo en un momento dado. El objetivo del problema denotado por${\displaystyle P|size_{j}|C_{\max }}$es encontrar un horario con duración mínima${\displaystyle C_{\max }=\max _{j\in {\mathcal {J}}}(s_{j}+p_{j})}$, también llamado tiempo de finalización del cronograma. Una condición suficiente para la viabilidad de un cronograma es la siguiente:

${\displaystyle \sum _{j\in {\mathcal {J}},s_{j}\leq t<s_{j}+p_{j}}q_{j}\leq m\,\forall t\in \{s_{1},\dots ,s_{n}\}}$.

Si esta propiedad se cumple para todos los tiempos de inicio, se puede generar un cronograma factible asignando máquinas libres a los trabajos en cada momento a partir del tiempo${\displaystyle t=0}$. ^{[ 1 ] [ 2 ]} Además, el número de intervalos de máquina utilizados por los trabajos y los intervalos de inactividad en cada paso de tiempo se puede limitar por${\displaystyle |{\mathcal {J}}|+1}$[ ^{1 ] Aquí ,} un intervalo de máquina es un conjunto de máquinas consecutivas de cardinalidad máxima, de modo que todas las máquinas de este conjunto procesan el mismo trabajo. Un intervalo de máquina se especifica completamente mediante el índice de su primera y última máquina. Por lo tanto, es posible obtener una forma compacta de codificar la salida con tamaño polinomial.

Este problema es NP-difícil incluso cuando solo hay dos máquinas y los tamaños de todos los trabajos son${\displaystyle q_{j}=1}$(es decir, cada trabajo necesita ejecutarse solo en una sola máquina). Este caso especial, denotado por${\displaystyle P2||C_{\max }}$, es una variante del problema de partición , que se sabe que es NP-difícil.

Cuando el número de máquinas m es como máximo 3, es decir: para las variantes${\displaystyle P2|size_{j}|C_{\max }}$y${\displaystyle P3|size_{j}|C_{\max }}$Existe un algoritmo de tiempo pseudopolinomial que resuelve el problema exactamente. ^{[ 8 ]}

Por el contrario, cuando el número de máquinas es al menos 4, es decir: para las variantes${\displaystyle Pm|size_{j}|C_{\max }}$para cualquier${\displaystyle m\geq 4}$, el problema también es fuertemente NP-difícil ^{[ 9 ]} (este resultado mejoró un resultado anterior ^{[ 8 ]} que mostraba una fuerte NP-dificultad para${\displaystyle m\geq 5}$).

Si el número de máquinas no está limitado por una constante, entonces no puede haber ningún algoritmo de aproximación con una razón de aproximación menor que${\displaystyle 3/2}$a menos que${\displaystyle P=NP}$Esto se cumple incluso para el caso especial en el que el tiempo de procesamiento de todos los trabajos es${\displaystyle p_{j}=1}$, puesto que este caso especial es equivalente al problema de empaquetamiento de contenedores : cada paso de tiempo corresponde a un contenedor, m es el tamaño del contenedor, cada trabajo corresponde a un elemento de tamaño q _j , y minimizar el tiempo de finalización corresponde a minimizar el número de contenedores.

Se han estudiado varias variantes de este problema. ^{[ 3 ]} También se han considerado las siguientes variantes en combinación entre sí.

Restricciones de precedencia : En esta variante, existen relaciones de precedencia entre los trabajos, por ejemplo, si dos trabajos i y j tienen una relación de precedencia que establece que i debe preceder a j , es decir,${\displaystyle i\prec j}$, entonces i debe preceder a j en cualquier solución factible. Este problema es NP-difícil (reducción por clique ) incluso si todos los tiempos de procesamiento${\displaystyle p_{j}}$son iguales para m máquinas. Sin embargo, se podría resolver la variante de 2 máquinas en tiempo polinomial, ya que el problema se reduce efectivamente a encontrar un emparejamiento perfecto de cierta longitud. En caso de que no exista un emparejamiento perfecto para dos trabajos en algún instante de tiempo (lo que puede deberse a que no hay ningún trabajo disponible en ese instante), podemos agregar un trabajo ficticio para verificar la corrección. Encontrar la complejidad computacional para${\displaystyle P3|}$prec${\displaystyle |C_{max}}$Sin embargo, se desconoce. ^{[ 10 ]}

Trabajos contiguos : En esta variante, las máquinas tienen un orden fijo.${\displaystyle (M_{1},\dots ,M_{m})}$En lugar de asignar los trabajos a cualquier subconjunto${\displaystyle m_{j}\subseteq \{M_{1},\dots ,M_{m}\}}$Los trabajos deben asignarse a un intervalo contiguo de máquinas. Este problema corresponde a la formulación del problema de empaquetamiento en tiras .

Plataformas múltiples: En esta variante, el conjunto de máquinas se divide en plataformas independientes. Un trabajo programado solo puede usar las máquinas de una plataforma y no se le permite abarcar varias plataformas durante su procesamiento.

Trabajos moldeables : En esta variante cada trabajo${\displaystyle j\in {\mathcal {J}}}$tiene un conjunto de recuentos de máquinas factibles${\displaystyle D_{j}\subseteq \{1,\dots m\}}$. Por cada recuento${\displaystyle d\in D_{j}}$, el trabajo se puede procesar en d máquinas en paralelo, y en este caso, su tiempo de procesamiento será${\displaystyle p_{j,d}}$Para programar un trabajo${\displaystyle j\in {\mathcal {J}}}$, un algoritmo tiene que elegir un número de máquinas${\displaystyle d\in D_{j}}$y asignar j a un tiempo de inicio${\displaystyle s_{j}}$y a${\displaystyle d}$máquinas durante el intervalo de tiempo${\displaystyle [s_{j},s_{j}+p_{j,d}).}$ Una suposición habitual para este tipo de problema es que la carga de trabajo total de un trabajo, que se define como${\displaystyle d\cdot p_{j,d}}$, no es creciente para un número creciente de máquinas.

Fechas de lanzamiento : En esta variante, denotada por${\displaystyle P|size_{j},r_{j}|C_{\max }}$No todos los trabajos están disponibles en el tiempo 0; cada trabajo j estará disponible en un tiempo fijo y conocido r _j . Debe programarse después de ese tiempo.

Preemption : En esta variante, denotada por${\displaystyle P|size_{j},r_{j},{\text{pmtn}}|C_{\max }}$Es posible interrumpir trabajos que ya estén en ejecución y programar otros trabajos que estén disponibles en ese momento.

El algoritmo de planificación de listas de Garey y Graham ^{[ 11 ]} tiene una relación absoluta${\displaystyle 2}$, como señalan Turek et al. ^{[ 12 ]} y Ludwig y Tiwari. ^{[ 13 ]} Feldmann, Sgall y Teng ^{[ 14 ]} observaron que la longitud de una planificación no preemptiva producida por el algoritmo de planificación de listas es en realidad como máximo${\displaystyle (2-1/m)}$veces el tiempo de finalización preventivo óptimo. Un esquema de aproximación de tiempo polinomial (PTAS) para el caso en que el número${\displaystyle m}$de procesadores es constante, denotado por${\displaystyle Pm|size_{j}|C_{\max }}$, fue presentado por Amoura et al. ^{[ 15 ]} y Jansen et al. ^{[ 16 ]} Posteriormente, Jansen y Thöle ^{[ 2 ]} encontraron un PTAS para el caso en que el número de procesadores está acotado polinomialmente en el número de trabajos. En este algoritmo, el número de máquinas aparece polinomialmente en la complejidad temporal del algoritmo. Dado que, en general, el número de máquinas aparece solo logarítmicamente en el tamaño de la instancia, este algoritmo es también un esquema de aproximación de tiempo pseudopolinomial.${\displaystyle (3/2+\varepsilon )}$La aproximación fue dada por Jansen, ^{[ 17 ]} que cierra la brecha al límite inferior de${\displaystyle 3/2}$excepto por una cantidad arbitrariamente pequeña${\displaystyle \varepsilon }$.

Dado un ejemplo del problema de programación de tareas paralelas, el tiempo de finalización óptimo puede variar dependiendo de la restricción a la contigüidad de las máquinas. Si los trabajos se pueden programar en máquinas no contiguas, el tiempo de finalización óptimo puede ser menor que en el caso de que deban programarse en máquinas contiguas. La diferencia entre programaciones contiguas y no contiguas se demostró por primera vez en 1992 ^{[ 18 ]} en un ejemplo con${\displaystyle n=8}$ tareas,${\displaystyle m=23}$procesadores,${\displaystyle C_{\max }^{nc}=17}$, y${\displaystyle C_{\max }^{c}=18}$. Błądek et al. ^{[ 19 ]} estudiaron estas llamadas diferencias c/nc y demostraron los siguientes puntos:

• Para que surja la diferencia ac/nc, debe haber al menos tres tareas con${\displaystyle q_{j}>1.}$
• Para que surja la diferencia ac/nc, debe haber al menos tres tareas con ${\displaystyle p_{j}>1.}$
• Para que surja la diferencia ac/nc, al menos${\displaystyle m=4}$Se requieren procesadores (y existe una instancia con ac/nc-difference con${\displaystyle m=4}$).
• Para que surja la diferencia ac/nc, la longitud del cronograma no contiguo debe ser al menos${\displaystyle C_{\max }^{nc}=4.}$
• La diferencia máxima c/nc${\displaystyle \sup _{I}C_{\max }^{c}(I)/C_{\max }^{nc}(I)}$es al menos${\displaystyle 5/4}$y como máximo${\displaystyle 2.}$
• Decidir si existe una diferencia c/nc en una instancia dada es un problema NP-completo.

Además, propusieron las dos siguientes conjeturas, que aún no han sido probadas:

• Para que surja la diferencia ac/nc, al menos${\displaystyle n=7}$Se requieren tareas.
• ${\displaystyle \sup _{I}C_{\max }^{c}(I)/C_{\max }^{nc}(I)=5/4}$

Existen problemas de programación relacionados en los que cada trabajo consta de varias operaciones que deben ejecutarse en secuencia (en lugar de en paralelo). Estos son los problemas de programación de talleres abiertos , talleres de flujo y talleres de producción .