Programación de tareas en paralelo

---

La programación de tareas en paralelo (también llamada programación de trabajos en paralelo ^{[1] [2]} o programación de procesamiento en paralelo ^[3] ) es un problema de optimización en informática e investigación de operaciones . Es una variante de la programación óptima de trabajos . En un problema general de programación de trabajos, tenemos n trabajos J ₁ ,  J ₂ , ...,  J _n de tiempos de procesamiento variables, que deben programarse en m máquinas mientras se intenta minimizar el rendimiento- la duración total de la programación (es decir, cuando todos los trabajos han terminado de procesarse). En la variante específica conocida como programación de tareas paralelas , todas las máquinas son idénticas. Cada trabajo j tiene un parámetro de longitud p _j y un parámetro de tamaño q _j , y debe ejecutarse exactamente p _j pasos de tiempo en exactamente q _j máquinas en paralelo .

Veltman et al. ^[4] y Drozdowski ^[3] denotan este problema 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 en su lugar. ^[1]${\displaystyle P|tamaño_{j}|C_{\max}}$ ${\displaystyle P|m_{j}|C_{\max}}$

Los orígenes de la formulación de este problema se remontan a 1960. ^[6] Para este problema, no existe un algoritmo de aproximación de tiempo polinomial con una relación menor que menos que . ^{[ cita requerida ]}${\displaystyle 3/2}$${\displaystyle P=NP}$

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

---