Metaheurística ACO aplicada a problemas de planificación en entornos dinámicos

Abstract

Las organizaciones industriales frecuentemente están sujetas a diferentes tipos de cambios como pueden ser: que se agregue una nueva tarea, la cancelación de una tarea, la ruptura de una maquina, como así también cambios en los tiempos de procesamiento o de la fecha estimada de terminación de la tarea. Debido a su naturaleza dinámica, los problemas de planificación real son computacionalmente complejos y el tiempo requerido para encontrar una solución óptima se incrementa exponencialmente con el tamaño del problema. Los problemas de planificación se pueden clasificar en: estáticos, donde todas las tareas son conocidas antes del comienzo de la planificación; y dinámicos, en donde sólo el tiempo de comienzo de la tarea es desconocido (dinamismo parcial) ó donde todas las propiedades de las tareas son desconocidas (dinamismo total). Los problemas de planificación (scheduling) estáticos se han abordado a través de distintas metaheurísticas (Simulating Annealing, Tabu Search, Algoritmos Evolutivos y Ant Colony Optimization), pero los problemas de scheduling dinámicos han sido encarados principalmente con Algoritmos Evolutivos, para problemas de job shop y para problemas de máquina única. Una metaheurística particularmente exitosa está inspirada para el comportamiento de las hormigas reales, conocida como la metaheurística Ant Colony Optimization (ACO). Numerosos enfoques algorítmicos basados sobre las mismas fueron desarrollados y aplicados con éxito para una variedad de problemas de optimización. Se pretende a través de esta línea de investigación, realizar un análisis comparativo de los trabajos realizados hasta el momento sobre scheduling dinámico con algoritmos evolutivos para diferentes problemas de máquina única (Weighted Tardiness, Average Tardiness, Weighted Number of Tardy Job), pero abordado con otra metaheurística diferente como es el caso de ACO.