info:eu-repo/semantics/masterThesis
Exploración de técnicas de optimización para la programación de tareas con precedencia
Autor
JAVIER ALEJANDRO HERRERA ZAMORA
Resumen
La problemática de la programación de tareas para el caso de tipo taller en general es difícil de resolver. La complejidad del problema radica en que si se tienen m máquinas y n tareas del número total de trabajos a programar se representa de la siguiente forma (n!)m. Entonces, un ejemplo que ayuda ver la magnitud de la problemática es imaginar una situación donde se tienen n=20 y m=10 el número posible de soluciones es de 7.2651 x 10 183. Adicionalmente la complejidad se incrementa cuando las tareas se identifican como un conjunto de subtareas que a su vez cuentan con cierta precedencia la cual puede ser única o múltiple. Otro asunto que aumenta la dificultad para resolver y generar la mejor solución está cuando en el escenario existe una cantidad mayor a uno de máquinas del mismo tipo. Con estas consideraciones se coloca ante una situación aún más desafiante y entonces la utilización de la técnica apropiada para encontrar la solución óptima se convierte en una cuestión a descifrar.
Este trabajo presenta los resultados obtenidos al explorar los beneficios y alcances logrados al aplicar diferentes técnicas de optimización a la problemática de la programación de tareas en un escenario real. Durante la experimentación se aplicaron las reglas de secuenciación comunes (heurísticas), búsqueda aleatoria, búsqueda del método del alpinista y algoritmos genéticos con representación de llaves aleatorias y permutación con el propósito de compararlas como técnicas de optimización para la programación de tareas considerando las precedencias múltiples.