Estudio para el secuenciamiento de tareas independientes en entornos heterogéneos

Abstract

El objetivo del trabajo es estudiar, evaluar y analizar los algoritmos de secuenciamento de tareas independientes en entornos heterogéneos. Este problema de secuenciamiento aparece en procesos productivos y en procesos de servicios como por ejemplo 'call centers'

El presente trabajo de final de máster tiene por objetivo el estudio de la aplicación de distintas técnicas de planificación sobre un modelo de problema especificado por el departamento de Sistemas, Automática e Informática Industrial (ESAII). El problema es de secuenciación de tareas en entornos heterogéneos, con la especificidad de ser trabajos con llegadas dinámicas al sistema. Existe mucho conocimiento sobre metodologías de planificación de tareas, cuando la planificación es estática (se dispone de toda la información antes de iniciar el proceso de planificación) y también cuando es dinámica y se dispone igualmente de la información necesaria para poder ejecutar las planificaciones. En este caso de estudio, las llegadas de las solicitudes de trabajo a planificar no son conocidas ni previsibles, así como tampoco son conocidos los tiempos de proceso de cada trabajo que se solicite al sistema. Además el sistema es un sistema Soft Real-Time, por lo que es necesario tener en cuenta que debemos planificar con el objetivo de respetar los plazos máximos de entrega que se nos especifica. Dentro de este marco de trabajo, se evaluarán los resultados de aplicar 3 diferentes técnicas de planificación existentes en la literatura y más reconocidas, para extraer conclusiones sobre cuál de ellas puede ser más recomendable: Earliest Deadlines First, Least Laxity First y Myopic. Estas tres técnicas se tendrán que complementar con la gestión de estimaciones de tiempos de proceso como explicaremos en esta memoria. De estas 3 posibilidades, llegaremos a la conclusión que, teniendo en cuenta la gran influencia de no disponer de tiempos de proceso conocidos, parece más efectiva la metodología de Earliest Deadline First, por ser la más sencilla y por no gestionar las prioridades en base a tiempos de proceso no conocidos (o tiempos de proceso estimados). Finalmente, de los resultados de este estudio, se podrán extraer tres posibles caminos por los que se podría ampliar esta investigación para poder mejorar los resultados obtenidos con estas técnicas clásicas.