Problemas de programación de tareas en máquinas en paralelo

Resumen

En este trabajo se presenta un análisis de los enfoques usados para resolver problemas de programación de tareas en máquinas en paralelo, haciendo énfasis en los problemas en los que se considera la asignación de recursos limitados. El problema general de programación de tareas contempla la asignación y secuenciación de un conjunto de n tareas que deben ser procesadas en un conjunto de m máquinas. En el caso de máquinas en paralelo, los problemas de programación de tareas presentan un alto nivel de complejidad y son muy difíciles de resolver, por lo que en general se estudian casos muy simples cuyos supuestos consideran: máquinas idénticas que pueden procesar un número arbitrario de tareas, máquinas que pueden procesar una sola tarea a la vez, no se permiten interrupciones, no hay tiempos de setup y si los hay son independientes de la secuencia de las tareas, los tiempos de proceso son fijos, conocidos a priori e independientes de la secuencia, no hay restricciones de precedencia y las funciones de optimización son monoobjetivo. En los problemas más complejos se varía uno (o más) de dichos supuestos. Palabras clave: programación, secuenciación, máquinas en paralelo.