Algoritmo GRASP para resolver el problema de la programación de tareas dependientes en máquinas diferentes (task scheduling)

Uno de los temas que se ponía de moda en el tiempo que terminaba la carrera, fue el de Inteligencia Artificial, ya en la maestría logré ver algo de eso, casi al terminar. Comúnmente se hacía referencia a ciertas técnicas, como el Algoritmo "Goloso" cuando los métodos de optimización exacta eran insuficientes o las iteraciones demasiado elevadas como para encontrar la respuesta adecuada en el tiempo preciso.

Si bien los operativos nos vamos casi siempre por el método que nos lleva al óptimo en forma exacta, a veces una muy buena alternativa es utilizar una heurística que nos permita ahorrar tiempo y llegar a una "buena" solución factible. A veces partimos de una solución factible empírica también y podemos en el mejor de los casos, llegar al óptimo.

Revisando el Solver (de Excel 2010) observé que este ya contempla el uso de Algoritmos Evolucionarios ¿Genéticos quizá? para resolver problemas de optimización.

Aún cuando el operativo tiende a usar el método exacto y siempre llegar al óptimo, no está demás que su formación incluya técnicas de inteligencia artificial. Revisando datos de un compañero de colegio encontré con interés su tesis de postgrado, en la cual aplica un algoritmo GRASP (goloso o voraz) y al final hace un comparativo con el óptimo que obtiene Lindo.

Lo recomiendo para aquel que busque introducirse en el tema o hacer un paralelo entre una heurística y un método determinístico (ya conocido).

El contenido de la tesis puede ser revisado aquí.