Abstract: Schedule elaboration in Instituto Tecnológico de Hermosi-
llo takes too much time; in order to have them ready for the next semester
the process needs to start before the actual semester ends. Coordinators
make projections of the expected demand and sometimes they are not
correct; once they get the definitive data, the time to make corrections
in a proper way is very limited. Automated timetable in a university is
a complex process that has been studied by several investigators. It is a
NP-Complete problem. There is not a known universal method to solve
it. Genetic Algorithms fit perfectly in situations where it is unknown how
to solve a problem but it is easy to evaluate a given solution. The present
article consist in the analysis, design and implementation of a system that
provides solution proposal for schedules using metaheuristic evolutive te-
chniques, such Genetic Algorithms.
+ Keywords: Genetic Algorithm, automated timetabling, schedule and evolu-
tive computing.
Introducción
En el Instituto Tecnológico de Hermosillo, como en cualquier otra ins-
titución educativa, cada semestre tienen que definirse las materias que se
van a ofrecer. Estas materias, regularmente, están agrupadas en paquetes,
con horario corrido, de acuerdo a las necesidades de cada generación de
alumnos.
Los encargados de determinar el contenido de estos paquetes son los
coordinadores de carrera y los jefes de departamento. Ellos tienen que decidir
cuántos grupos de cada materia abrirán, qué maestros las impartirán y qué
horarios tendrán los alumnos y los maestros. Se tiene que cuidar que no se
empalmen grupos y que la menor cantidad de alumnos tengan horas libres en
su horario. Se tienen que respetar también los horarios que desean los maes-
tros. Además, existen las restricciones de tipo administrativo, por ejemplo, un
maestro no debe impartir más de tres materias diferentes. Por otro lado, cada
docente tiene asignada una carga (un número de horas de clase a la semana),
la cual no puede ser excedida. No es sencillo asignar las cargas, debido a que
no todas las materias tienen el mismo número de horas por semana.
No es posible esperar a que un semestre termine para comenzar a orga-
nizar los horarios para el ciclo siguiente, esto es debido a que el período es
pequeño, desde que todos los maestros entregan sus listas hasta el momento
de las inscripciones. Por este motivo, los coordinadores hacen proyecciones
de los grupos que se necesitarán abrir para el siguiente semestre, con base a
las materias que se están impartiendo y a un índice de reprobación determi-
nado de acuerdo a su experiencia; sin embargo, los datos definitivos no los
tienen hasta que terminan los cursos.
La gran cantidad de variables que tiene el proceso y el hecho de que
sean humanos los encargados de realizarlo, además de tomar demasiado
tiempo, propicia que se cometan errores y omisiones, como por ejemplo
que se programe a un docente dos grupos diferentes a la misma hora, que se
abran grupos con menos alumnos de los requeridos, que se exceda la carga
reglamentaria de un maestro, etcétera. Estos errores y omisiones provocan
inconformidades por parte de los maestros y alumnos; además, no se apro-
vecha al cien por ciento a la planta docente, en ocasiones se da el caso de
que los semestres empiecen con grupos descubiertos, hay contrataciones
apresuradas de maestros que, entre otros detalles, merman la calidad educa-
tiva que debe brindar la institución.
Antecedentes
La elaboración de horarios (timetabling/scheduling) es un problema
que ha sido bastante estudiado. De acuerdo a Fang (1994), la dificultad de
automatizar este proceso radica en que son problemas computacionales
clasificados como NP-completos. Esto significa que no se conoce ningún
algoritmo determinístico que pueda llegar a una solución en un tiempo
razonable. Además, el espacio de soluciones posibles para la mayoría de
los problemas en el mundo real es demasiado grande para los métodos de
búsqueda tradicionales.
De acuerdo a Goldberg (1989) y Horman (1989), los algoritmos genéti-
cos encajan perfectamente en situaciones donde se conoce muy poco acerca
de cómo resolver el conflicto, pero está disponible algún método para eva-
luar la solución encontrada.
En los algoritmos genéticos no es necesario conocer el método para lle-
gar a la solución del problema, únicamente necesitamos conocer qué carac-
terísticas debe tener dicha solución. Para encontrar una solución se utiliza el
azar y la selección, tal y como se da en la evolución natural (Koza, Bennett,
Andre y Keane, 1999; Dawkins, 1996).
Algoritmos genéticos
Los pasos a seguir por el algoritmo genético son:
A) Inicialización
El primer paso para utilizar un algoritmo genético es parametrizar el
problema en una serie de variables, donde cada variable representa a un gen.
El conjunto de valores para dichas variables se concatenan en una cadena
de caracteres, a la cual se le denomina cromosoma. Al comenzar el proceso
se inicializa un conjunto de soluciones potenciales obtenidas al azar, y se
obtiene su cromosoma correspondiente. Al conjunto de cromosomas se les
llama población.
Debe elegirse cuidadosamente el tamaño de la población; si es demasia-
do pequeño, puede que el algoritmo genético no explore suficientemente el
espacio de soluciones para encontrar la mejor. Si es demasiado grande, el
algoritmo tardará más tiempo del necesario para finalizar.
B) GENERACIÓN
Se itera cada uno de los siguientes pasos hasta que se cumpla un deter-
minado criterio