Una heurística para la asignación de máquinas a trabajos fijos

Resumen

En este trabajo se estudia el problema de la asignación de recursos a actividades fijas, conocido como Fixed Job Scheduling Problem (FSP). FSP se caracteriza como el problema de planificar, sobre un conjunto de máquinas en paralelo, un conjunto de trabajos no interrumpibles, caracterizados cada uno de ellos por un instante fijo de comienzo y finalización. El objetivo considerado en el problema es maximizar el numero de trabajos procesados con un número fijo de máquinas, asumiendo que existen diferentes clases de máquinas y trabajos. Para la resolución del problema se propone una aproximación heurística formada por un procedimiento constructivo y fase de mejora local. La calidad del mismo se compara con otros métodos heurísticos existentes en la bibliografía, así como con un método exacto. Los resultados computacionales ponen de manifiesto que el método encuentra soluciones de mejor calidad que esos otros métodos con tiempos de computación aceptables. Palabras clave: Heurística, Trabajos fijos.