Un algoritmo para la asignación de recursos académicos como un problema de Scheduling

Abstract

Resumen: Baker definió en 1974 en forma sencilla el scheduling como el problema de asignar recursos escasos a actividades en el tiempo. De esta definición han surgido variaciones tales como invertir el orden de la asignación: actividades a recursos en lugar de recursos a actividades, suprimir la palabra escasos, ya que en realidad los recursos no tienen que ser escasos para realizar la asignación, pero todas estas definiciones dan una idea muy general del problema que se trata de resolver, y que así sea sin plantearlo formalmente, lo viene resolviendo la humanidad desde hace miles de años, ya que aunque el problema se trata de resolver en instituciones de gran tamaño, tiene pleno sentido a nivel del hogar, y en general de muchas de las actividades cuotidianas, familiares y rutinarias del hombre. Esta definición, aparentemente tan sencilla y meramente cualitativa da origen a definiciones, formalizaciones y discusiones de tipo matemático cuando se trata de resolver el problema general del scheduling, que se vuelve un problema muy complejo en la medida en que crece su tamaño y en la medida en que se descubre la imposibilidad matemática de encontrar un algoritmo general que resuelva en forma práctica el problema, a pesar de la existencia de los computadores actuales. De hecho se ha demostrado que el problema de scheduling en su forma general es un problema NP-hard y por tanto no existen algoritmos polinómicos de solución. Teóricamente, es fácil "plantear" un algoritmo que resuelva el problema más general de scheduling, el cual si se ejecuta en un computador al que se le diera un tiempo no limitado para encontrar la solución, la encontraría o detectaría la no existencia de ella (no factibilidad) en caso de no haberla.