Algoritmos de Aproximación para Problemas de Programación de Tareas (Scheduling Problems).

Ponente(s): Jaicer Jonas Lopez Rivero

Expondre un resumen de mi tesis de grado en la Licenciatura. En primer lugar se describirá de manera general, el problema de programación de tareas (en inglés Scheduling problems) y ademas se dará una clasificación básica de los problemas de programación de tareas, la cual es utilizada ampliamente en la literatura. De todos los problemas de programación de tareas, hay una gran cantidad que son N P-hard y por lo tanto no admiten algoritmos de tiempo polinomial que los resuelvan a optimalidad, es por ello que se utilizan algoritmos de aproximación. De la familia de los problemas de programación de tareas, se estudia la que tiene como función objetivo la tardanza ponderada total, esta familia esta relacionada con la que tiene como función objetivo el tiempo de completación ponderado total, y de cual se conocen algoritmos de aproximación específicos, los cuales se utilizaran para resolver el problema en estudio.