Diferentes heurísticas para la solución de problemas de máquina única en entornos dinámicos

Abstract

Existen dos conceptos de importancia en el contexto de problemas dinámicos y en particular de scheduling dinámicos: la búsqueda de soluciones robustas y flexibles. El concepto de robustez de las soluciones se refiere a un tipo de soluciones que pueden ser usadas de igual manera cuando se produce un cambio en el entorno y manteniendo su calidad relativa. En el caso de flexibilidad, se refiere a la posibilidad de que las soluciones encontradas puedan ser adaptadas sin mayores problemas cuando se produzca un cambio en el entorno. En consecuencia, soluciones robustas y flexibles son altamente deseables en este tipo de contexto. Para un problema de scheduling se podrían presentar dos niveles de dinamismo: uno de ellos establece un dinamismo en el cual el problema puede ser dividido en varios problemas estáticos, llamado “dinamismo off-line”; el otro nivel de dinamismo apunta a estudiar el comportamiento de un algoritmo cuando se producen cambios en el entorno, pero durante el proceso de búsqueda y se lo denomina “dinamismo on-line”. Los problemas de scheduling off-line han sido estudiados por distintos investigadores usando para su resolución distintas metaheurísticas: Simulating Annealing, Tabu Search, Algoritmos Evolutivos y Ant Colony Algorithms. Pero pocos han encarado los problemas de scheduling on-line; para problemas de job shop y para problemas de máquina única. Este trabajo presenta la línea de investigación a través de la cual se pretende comparar los trabajos realizados hasta el momento sobre scheduling dinámico con algoritmos evolutivos para problemas de máquina única, con otra metaheurística diferentes como es el caso de la Colonia de Hormigas.