Algoritmo Tabu

Modelo para la asignación de recursos académicos
en instituciones educativas utilizando la técnica
metaheurística, búsqueda tabú
Model for academic resource assignment in
educational institutions using the tabu search
metaheuristics
Gerley E. Restrepo Ing. & Luis Fernando Moreno Velásquez M. Sc.
Escuela de Sistemas, Facultad de Minas, Universidad Nacional de Colombia, Sede Medellín.grestrep@unal.edu.co; lfmoreno@unal.edu.co
Recibido para revisión 30 de junio de 2011, aceptado 18 de octubre de 2011, versión final 16 de noviembre de 2011
Resumen ─ La asignación de recursos académicos en instituciones
educativas es un problema complejo, especialmente por tener un
gran número de restricciones, las cuales son definidas de forma
particular por cada institución, y por requerir unalto esfuerzo
computacional. El problema consiste en realizar la programación
de actividades académicas al tiempo que se asignan recursos a las
mismas, como por ejemplo el programar una clase y asignar a ésta
su respectivo docente y aula. Este documento presenta aspectos
generales del problema, algunos fundamentos relacionados con la
optimización combinatoria y las metaheurísticas. Proponeademás,
un modelo para la asignación de recursos académicos utilizando
la metaheurística Búsqueda Tabú (Tabu Search). Dicho modelo es
de aplicación general, sin embargo, para validar su desempeño se
ha empleado en un ambiente de pruebas real para la Universidad
Nacional de Colombia, Sede Medellín, obteniendo muy buenos
resultados, superiores a los ofrecidos por el método manual queactualmente se ejecuta.
Palabras Clave ─ Metaheurísticas, Programación de Horarios,
Asignación de Recursos Académicos, Asignación de Aulas,
Asignación de Docentes, Optimización Combinatoria.
Abstract ─ The assignment of academic resources in educational
institutions is a complex problem, especially for having a large
number of restrictions, which are defined in a particular way by
each institution,and for requiring a big computational effort. The
problem is to perform scheduling of academic activities, while
assigning resources to them, such as scheduling a class and assign to
it the respective teacher and the classroom. This document presents
general aspects of the problem, some basics related to combinatorial
optimization and metaheuristics. It also proposes a model for theallocation of academic resources using the metaheuristic Taboo
Search. This model is of general application, however, to validate

its performance it has been used in a real test for Universidad
Nacional de Colombia, Sede Medellín, achieving very good results,
better than those offered by the manual method currently used.
Keywords ─ Metaheuristics, Timetabling, Academic Scheduling
Resources,Classroom Assignment, Teacher Assignment,
Combinatorial Optimization.
I. INTRODUCCIÓN

E

l problema de la asignación de recursos académicos
tratado en este artículo, es un problema de optimización
combinatoria del tipo NP-Hard [1], lo que significa que los
recursos computacionales necesarios para encontrar una solución
se incrementan de forma exponencial con la magnitud del
problema,especialmente cuando son tratados con algoritmos
exactos. Este problema está presidido por un gran número
de restricciones, cuya importancia será ponderada por cada
institución educativa, pero que en esencia se pueden clasificar
en restricciones fuertes (estrictas o duras) y débiles (deseables
o suaves). La violación del primer tipo de restricción conduce
a rechazar cualquier solución encontrada.Por otro lado, se debe
minimizar la violación del segundo tipo de restricción con el fin
de obtener soluciones de mayor calidad.
Como objetivo general de investigación, este trabajo
busca desarrollar un Modelo para la Asignación de Recursos
Académicos (MARA) en una institución educativa, incorporando
la metaheurística Búsqueda Tabú, permitiendo la toma
de decisiones y la asignación de...