Meta-heurísticas aplicadas en la generación automática de horarios docentes

RESUMEN

En este trabajo se realiza una revisión de las meta-heurísticas más frecuentemente aplicadas al problema de la generación de horarios y sus principales fundamentos. Se relacionan un conjunto de técnicas heurísticas que han sido utilizadas, con diferentes niveles de éxito, de las que se exponen sus principios y casos de aplicación reportados en la literatura.

INTRODUCCIÓN

El problema de la generación automática de horarios es clásico en la computación. Reconocido en inglés como

Timetabling, se define como: “la asignación, sujeta a restricciones, de un grupo de recursos a objetos ubicados en tiempo y espacio, de tal manera que se satisfagan un conjunto de objetivos deseados” (Wren, 1996)⁠ y aparece en diversos ámbitos incluyendo: la planificación de transporte, programación de eventos deportivos, horarios laborales (Qu, 2002).

Pertenece a la categoría de problemas conocidos como NP-Completos, o sea, para los que no existe o no se conoce un algoritmo determinista que encuentre una solución en un tiempo polinomial (Martínez, García, Muñoz, & Castañeda, 1999)⁠. Generalmente tienen muchas restricciones (que varían de una institución docente a otra).

La construcción de horarios docentes es un problema muy complejo que compete a todas las instituciones que se dedican o tienen a la docencia entre sus objetivos. Dentro de los factores que influyen en su complejidad, se puede distinguir la necesidad de satisfacer una serie de restricciones. Estas restricciones se pueden clasificar en suaves o fuertes donde: las fuertes no pueden ser violadas y las suaves no son esenciales (Nandhini & Kanmani, 2009a)⁠.

Los problemas de generación de horarios educacionales (como también se les conoce) se clasifican, según (Schaerf, 1999)⁠, en:

• Generación de horarios de escuela.· Generación de horarios para cursos de universidad
• Generación de horarios de exámenes

Carter y Laporte descomponen el problema de la generación de horarios en cinco subproblemas, a saber:

1. 1. Horarios de cursos (course timetabling)
2. Horarios para grupo-profesor (class-teacher timetabling)
3. Asignación de estudiantes a grupos (student scheduling)
4. Asignación de profesores a grupos (teacher assignment)
5. Asignación de locales a actividades (classroom assignment)

Si a los subgrupos definidos por (Carter & Laporte, 1998)⁠ se les suma la programación de exámenes de (Schaerf, 1999)⁠, totalizan seis subgrupos que abarcan los posibles subproblemas de generación de horarios educacionales.

Cada una de estas clasificaciones tiene características propias pero no escapan de tener similitudes pues todas tratan de encontrar una distribución que asigne recursos a espacios de tiempo.

Como se mencionara anteriormente, cada institución puede tener su propio conjunto de restricciones pero, existen restricciones que son compartidas por cualquier horario educacional. Por ejemplo:

• Ningún grupo de estudiantes puede tener más de una actividad docente en el mismo espacio de tiempo.· Ningún profesor puede tener más de una actividad al mismo tiempo.
• Ningún grupo docente o profesor puede tener más actividades que espacios de tiempo disponibles para recibirlas o impartirlas respectivamente.
• Dos (o más) actividades no pueden tener asignadas el mismo local en un mismo espacio de tiempo.

Este problema ha sido objeto de numerosas investigaciones desarrolladas por la comunidad científica internacional. Sus características (complejidad), hacen necesaria una revisión previa para elegir las herramientas adecuadas para la aplicación en un centro determinado y precisamente ese es el objetivo de este trabajo.

Las meta-heurísticas aplicadas a Educational Timetabling

Los métodos heurísticos se utilizan para tratar de encontrar soluciones a problemas para los que no existe un algoritmo que converja a la solución ni exista una fórmula explícita que la encuentre.

Según (Hooker, 1995)⁠ “…un método heurístico es un procedimiento para resolver un problema complejo de optimización mediante una aproximación intuitiva, en la que la estructura del problema se utiliza de forma inteligente para obtener una buena solución de manera eficiente..”. Sobre la base de esta definición, y apoyándose en el hecho de que no se puede asegurar que existe el mejor de los métodos heurísticos que sea capaz de obtener los mejores resultados para cualquier problema de optimización, resultado conocido como Teorema No Free Lunch (Whitley & Watson, 2005)⁠, (Wolpert & Macready, 1997)⁠ se han empleado diferentes métodos para tratar de resolver diferentes instancias del problema de timetabling.

Cuando los problemas son demasiado complejos, puede ser que los métodos heurísticos tradicionales no sean suficiente para encontrar soluciones a ellos, surgen las meta-heurísticas:

…una clase de métodos aproximados que están diseñados para resolver problemas complejos de optimización, en los que los heurísticos clásicos no son efectivos. Las meta-heurísticas proporcionan un marco general para crear nuevos algoritmos híbridos combinando diferentes conceptos derivados de la inteligencia artificial, la evolución biológica y los mecanismos estadísticos… (Osman & Kelly, 1996)⁠.

A continuación, se describen algunas de las heurísticas y meta-heurísticas que se han empleado y se emplean para resolver problemas de educational timetabling. Se aprecian diferencias, puntos de contacto y combinaciones entre ellas, siempre con el objetivo de mejorar las soluciones o reducir el costo computacional de obtenerlas.

Coloreado de grafos

Historia y principio de funcionamiento

Una de las primeras técnicas heurísticas que se utilizaron para la solución de problemas de timetabling fue el coloreado de grafos (De Werra, 1974)⁠. Su utilización incluye problemas de planificación general como lo reportara (Marx, 2004)⁠.

La técnica original consiste en encontrar una coloración adecuada para cada nodo del grafo, de forma tal que no exista ningún par de nodos adyacentes con el mismo color.

La técnica del coloreado de grafos en problemas de timetabling

Estableciendo una analogía con el problema que dio origen a esta técnica, un problema de timetabling puede modelarse de la siguiente forma:

Cada nodo representa un grupo y cada arista significa que esos dos grupos están involucrados en una restricción. No se pueden colorear del mismo color. Los colores pueden ser los espacios de tiempo o los locales disponibles. Esta representación no permite modelar un amplio conjunto de restricciones que se encuentran normalmente en un problema de generación de horarios académicos (De Werra, 1996a)⁠.

Se han reportado casos exitosos de solución del problema de generación horaria utilizando la técnica del coloreado de grafos, tal es el reporte de (Koyuncu & Seçir, 2007)⁠.

Esta estrategia puede resultar muy conveniente para generar horarios de exámenes. Los nodos constituirían los exámenes y las aristas relacionan a dos exámenes a los que deben asistir al menos un mismo estudiante (Abdullah, 2006)⁠, aunque se han reportado casos de éxito en la generación de horarios sencillos que se repiten semanalmente (De Werra, 1996b)⁠ o para encontrar la menor cantidad de locales necesarios reduciendo el número de colores disponibles (Selim, 1988)⁠.

Búsqueda tabú

Bases de la búsqueda tabú

Una meta-heurística muy aplicada y trabajada por los investigadores en la comunidad internacional. Una descripción bien detallada de todas sus características se puede encontrar en el libro de (Glover & Laguna, 1997)⁠.

El algoritmo de búsqueda tabú (TS por sus siglas en inglés) realiza una búsqueda exhaustiva en una vecindad o subconjunto de una vecindad, seleccionando el mejor movimiento de los que se consideraron, de acuerdo a una función objetivo. Para evitar atascos en óptimos locales se utiliza una lista con las n soluciones previamente visitadas, las que estarán ahí por un número determinado de movimientos (esta lista da el nombre al método) (Gendreau & Potvin, 2005)⁠.

Formalmente, el algoritmo comienza con una solución x que se obtiene, generalmente por un método más rápido y se va mejorando en cada movimiento escogiendo otra solución dentro de una vecindad, N(x), de x hasta que se encuentre una condición de parada. Es muy importante la vecindad que se escoja para obtener buenos resultados y puede ser seleccionada por cualquier algoritmo de búsqueda local (Eckersley, 2007)⁠.

La búsqueda tabú y el educational timetabling

Otro trabajo interesante sobre este versátil método es el de (Alvarez-Valdés, Crespo, & Tamarit, 1997)⁠, referido a su utilización en la generación de horarios de exámenes. Sobre este problema resalta el trabajo de (Kendall & Hussin, 2005)⁠, quienes la incorporaron como parte de una hiper-heurística  para seleccionar heurísticas que resuelven tanto problemas de horarios de exámenes como horarios de actividades lectivas.

Según reportan (Alvarez-Valdés, Crespo, & Tamarit, 2000)⁠ y (Alada, 2007)⁠, la búsqueda tabú es una técnica potente para resolver problemas de timetabling con resultados de alta calidad para instancias de grandes dimensiones.

Programación con restricciones

Bases de la programación con restricciones

El enfoque de programación para resolver el constraint satisfaction problem (CSP) es el estudio de sistemas computacionales basados en restricciones (Freuder & Wallace, 2005)⁠.

Los problemas de satisfacción de restricciones pueden ser formulados como CSP = (X, D, C) donde X es un conjunto finito de variables X = x1, x2,…, xn (por ejemplo períodos o aulas para cada curso), D es un conjunto finito de valores del dominio D = d1x, d2x,…, dnx, los cuales la variable puede tomar (por ejemplo posibles horas de inicio de los períodos o aulas disponibles); y C es un conjunto finito de restricciones, C = c1,…, cm donde las restricciones son relaciones entre subconjuntos de variables (por ejemplo requerimientos de aulas o relaciones de precedencia entre horas). De aquí que la solución final del CSP es una asignación de valores a cada variable de tal forma que todas las restricciones sean satisfechas (Müller, 2005)⁠, (Zhang & Lau, 2005)⁠.

La programación con restricciones aplicada al educational timetabling

Se conoce de experiencias cubanas aplicando esta técnica. Tal es el caso del trabajo de (Tamayo, Campaña, & Expósito, 2007)⁠ quienes proponen una alternativa para el proceso de planificación basado en CSP que tienen en cuenta no solo las restricciones explícitamente declaradas sino que tiene en cuenta un conjunto de criterios de higiene (Chiong, 1995)⁠ que otorgan mayor calidad a los horarios generados.

Las restricciones están en la naturaleza de los problemas de timetabling lo que hace que modelar las instancias de un problema, siguiendo esta meta-heurística se vea muy natural.

Algoritmos genéticos

Surgimiento de los algoritmos genéticos

En las ciencias de la computación, un algoritmo genético (GA por sus siglas en inglés), es un método heurístico que simula el proceso de evolución natural. Aunque sus orígenes se remontan a la década del 50 con los trabajos de (Barricelli, 1954)⁠, existen autores que atribuyen su creación a John Holland y sus colegas en la Universidad de Michigan (Melanie, 1996)⁠. Su estudio se hizo más intensivo en los 60, con (Fraser, 1960)⁠, y 70, con (Fraser & Burnell, 1970)⁠ a los que siguieron muchos otros.

Toda vez que esta técnica esta basada en el proceso de evolución natural, usa un conjunto de términos de las ciencias biológicas para un mejor entendimiento. El término cromosoma, se refiere a una solución candidata al problema que se trate. Recombinación o cruce y mutación son otros de los conceptos que se manejan en los algoritmos genéticos.

Componentes y funcionamiento de los algoritmos genéticos

Aunque no existe una definición rigurosa de GA que sea aceptada por toda la comunidad científica, se puede decir, según (Melanie, 1996)⁠, que todos los métodos que se consideren GA tiene, al menos, en común los siguientes elementos:

• Población de cromosomas,· selección de acuerdo a la aptitud,
• cruce para obtener nuevas generaciones y
• mutación aleatoria de la nueva generación.

El más simple de los algoritmos genéticos incluye tres tipos de operadores a saber:

• Métodos de selección: Estos métodos se utilizan para seleccionar los cromosomas para reproducción. Generalmente, mientras mejor es un cromosoma, mayor será la probabilidad de que sea seleccionado.
• Operadores de cruce o recombinación: Estos operadores son los encargados de intercambiar secuencias de genes de los padres para obtener la descendencia.
• Operadores de mutación:Estos operadores aleatoriamente cambian genes en la el cromosoma.

(Sastry, Goldberg, & Kendall, 2005)⁠ adicionan una cuarta operación, la de reemplazo, encargada de insertar a los cromosomas generados dentro de la población.

Para resolver problemas usando GA es necesario modelar los cromosomas, que serán soluciones candidatas, así como los operadores de cruce y mutación que se utilizarán. Otro componente fundamental de esta meta-heurística es la función de aptitud o calidad, fitness en inglés, que es la encargada de evaluar cuán bueno es cada cromosoma.

Los algoritmos genéticos y el educational timetabling

Los problemas de timetabling y scheduling figuran entre los más apropiados para resolver con esta popular técnica y una prueba de ello es la cantidad de autores que los han utilizado y continúan investigando sobre el tema como es el caso de (Burke, Elliman, & Weare, 1994)⁠, (Jat & Yang, 2009)⁠, (Martínez et al., 1999)⁠.

Se han reportado varias aplicaciones exitosas basadas en GA para el problema de timetabling, se pueden mencionar los trabajos de (Koizumi, Yamamori, & Yoshihara, 2002)⁠, (David, Barrientos, & Laredo, 2007)⁠, (Mejía, 2008)⁠, (Bratkovi

ć et al, 2009)⁠ y (Carrasco, 2011)⁠ entre otros. Es innegable que es una buena opción para afrontar problemas de planificación aunque no carece de detractores por su carácter estocástico y tiempos elevados de ejecución.

Optimización con enjambre de partículas

Origen de la optimización basada en enjambres de partículas

La optimización con enjambre de partículas se utilizó, inicialmente, para simular el comportamiento social (Kennedy, 1997)⁠. El origen de esta técnica se atribuye a (Kennedy & Eberhart, 1995)⁠ y (Shi & Eberhart, 1998)⁠. Tiene sus bases en el comportamiento de los cardúmenes de peces y las bandadas de aves en su búsqueda de un buen lugar para alimentarse y es un método que se emplea mayormente para encontrar valores máximos y mínimos de una función. (Merkle & Middendorf, 2005)⁠

Es una de las dos principales meta-heurísticas que componen lo que se conoce como Swarm Intelligence .

PSO aplicado a educational timetabling

Para aplicar PSO en timetabling (problema con dominio discreto) se necesitan realizar algunos ajustes a su enfoque tradicional (orientado a problemas con dominio continuo).

Según (Poli, 2008)⁠, quien realizara un estudio sobre las diferentes aplicaciones de PSO (siglas para Particle Swarm Optimization en inglés), de todas las aplicaciones revisadas solo el 3,5 % corresponden a problemas de optimización combinatoria. Se concluye que PSO no es muy popular a la hora de resolver problemas de este tipo.

Sin embargo, han reportado experiencias positivas utilizando esta técnica, tal es el trabajo de (Montero & Altamirano, 2011)⁠ quienes lo utilizan en lo que denominan la primera de dos fases en un algoritmo diseñado para generar horarios docentes que variarán dinámicamente al introducirles actividades durante el semestre.

Optimización con colonia de hormigas

Historia y bases

La Optimización con Colonia de Hormigas (ACO por sus siglas en inglés), es una meta-heurística que tiene su base en el comportamiento de las colonias de hormigas reales, por lo que se clasifica como biológicamente inspirada (Dorigo, 1992)⁠. Es una de las dos principales meta-heurísticas que entran en la categoría de Swarm Intelligence.

Un aspecto esencial en las colonias de hormigas es la comunicación indirecta de los individuos por medio de las feromonas (una sustancia química que es liberada por cada individuo al ambiente y que influye en el comportamiento y evolución de los otros de la misma especie). Las hormigas marcan sus caminos hacia las fuentes de alimento dejando un rastro de feromonas a su paso. Los rastros de feromonas pueden ser olfateados por otras hormigas y guiarlas hasta el alimento.(Merkle & Middendorf, 2005)⁠

Una condición necesaria para emplear esta técnica es que el problema debe poder ser modelado mediante un grafo que las hormigas artificiales deben «recorrer» en busca de una solución. El carácter cooperativo de este algoritmo es su sello distintivo. Es muy buena para resolver problemas de optimización combinatoria.

ACO aplicado al educational timetabling

Esta meta-heurística también ha sido utilizada en el afán de encontrar mejores soluciones al problema de la generación automática de horarios docentes; como reportan (Socha, Sampels, & Manfrin, 2003)⁠, quienes experimentaron con diferentes variaciones de ACO y otras meta-heurísticas en busca de evaluar su comportamiento con algunas instancias del problema. Los mejores resultados para instancias grandes se obtuvieron con el MMAS (Min-Max Ant System), mientras que para instancias de tamaño medio resultó mejor la aplicación del recocido simulado (SA).

Otro resultado positivo fue el obtenido por (Matijaš et al., 2010)⁠, quienes, con relativamente bajo consumo de memoria, obtuvieron un algoritmo ajustable a diferentes tipos de instituciones que trabaja muy bien con instancias grandes del problema.

Recocido simulado

Surgimiento y principios

El recocido simulado (SA por simulated annealing en inglés) es una meta-heurística que también se basa en un proceso natural   y que su dominio son los problemas de optimización combinatoria. Se atribuye su creación a los autores (Kirkpatrick, Gelatt, & Vecchi, 1983)⁠ y (

Černý, 1985)⁠ quienes llegaron al resultado de manera independiente.

El proceso comienza eligiendo una solución aleatoria que se va sustituyendo en cada iteración por otra, en una vecindad, elegida mediante una probabilidad influida por un parámetro T que representa la temperatura que decrece gradualmente durante el proceso.(Aarts, Korst, & Michiels, 2005)⁠

El recocido simulado aplicado al educational timetabling

Como se reportara por (Socha et al., 2003)⁠, usando SA, se pueden obtener buenas soluciones para instancias del problema de asignación de horarios de tamaño medio .

Otras propuestas han sido enfocadas al uso de hiper-heurísticas con base en el SA o su hibridación con otras meta o hiper heurísticas ya que el carácter particular de cada instancia del problema, sobre el supuesto de las diferencias entre las instituciones que lo presenten, hacen que la selección de un método u otro sea crítica para obtener un buen tiempo de respuesta, menor espacio de almacenamiento y el valor real de la solución (Nandhini & Kanmani, 2009b)⁠.

Conclusiones

Luego de completar la investigación, se pudo apreciar la variedad de enfoques que se pueden utilizar para resolver los problemas relacionados con la generación automática de horarios docentes, siempre teniendo en cuenta las características de la institución donde se vaya a aplicar una u otra técnica y el tipo de horario que se desee obtener así como las dimensiones. Todos estos son factores que condicionan la utilización de una u otra técnica.

Se constató la evolución de las técnicas meta-heurísticas aplicadas al problema de

educational timetabling y se realizó una caracterización de cada una de las técnicas revisadas, valorando su grado de éxito en el campo. Se aprecia una tendencia a la combinación de meta-heurísticas (hiper-heurísticas) para aplicar al problema aquí tratado.

Este documento se puede constituir en un marco teórico (o al menos una parte de él) para fundamentar futuras investigaciones en la materia.

Referencias

Aarts, E., Korst, J., & Michiels, W. (2005). Simulated Annealing. In E. K. Burke & G. Kendall (Eds.), Search Methodologies (pp. 187–210). Springer US. Retrieved from http://dx.doi.org/10.1007/0-387-28356-0_7

Abdullah, S. (2006). Heuristics Approaches for University Timetabling Problems. Structure. University of Nottingham.

Alada, H. (2007). A tabu search algorithm to solve a course timetabling problem. Journal of Mathematics and Statistics, 36(1), 53–64.

Alvarez-Valdés, Crespo, & Tamarit. (1997). A Tabu Search Algorithm to schedule university examinations. Qüestiió, 21(2), 201–215.

Alvarez-Valdés, R., Crespo, E., & Tamarit, J. (2000). Experiencias de utilización del método de búsqueda tabú en la resolución de problemas de organización universitaria. Recta, 8(1), 31.

Barricelli, N. A. (1954). Esempi numerici di processi di evoluzione. Methodos, 45–68.

Bratković, Z., Herman, T., Omrčen, V., Čupić, M., & Jakobović, D. (2009). University Course Timetabling with Genetic Algorithm: A Laboratory Excercises Case Study. In C. Cotta & P. Cowling (Eds.), Evolutionary Computation in Combinatorial Optimization (Vol. 5482, pp. 240–251). Springer Berlin / Heidelberg. Retrieved from http://dx.doi.org/10.1007/978-3-642-01009-5_21

Burke, E., Elliman, D., & Weare, R. (1994). A Genetic Algorithm Based University Timetabling System. East-West Conference on Computer Technologies in Education (pp. 35–40). Crimea, Ucrania.

Carrasco, T. (2011). Generación de horarios para el nivel secundario de la Unidad Educativa América Panorámica de la ciudad El Alto en Bolivia aplicando Algoritmos Genéticos. Camagüey, Cuba.

Carter, M., & Laporte, G. (1998). Recent developments in practical course timetabling. In M. Burke, Edmund K. Carter (Ed.), International Conference on the Practice and Theory of Automated Timetabling (PATAT II) (pp. 3–19). Toronto, Canadá: Springer-Verlag.

Chiong, M. O. (1995). Higiene de la actividad docente (p. 90). La Habana: Editorial Pueblo y Educación.

David, J., Barrientos, J., & Laredo, N. (2007). Modelo de asignación de carga académica usando algoritmos genéticos. Nuevo Laredo, México.

De Werra, D. (1974). Some results in chromatic scheduling. Mathematics and operations research, 18, 167–175. doi:10.1007/BF02026597

De Werra, D. (1996a). Some combinatorial models for course scheduling. Lecture Notes in Computer Science, 296–308.

De Werra, D. (1996b). Extensions of colouring models for scheduling purposes. European Journal of Operational Research, 92, 474–492.

Dorigo, M. (1992). Optimization, Learning and Natural Algorithms. Elsevier Publishing. Politecnico di Milano, Italia.

Eckersley, A. (2007). Novel Knowledge Based and Heuristic Approaches to University Timetabling. Work. University of Nottingham.

Fraser, A. (1960). Simulation of Genetic Systems by Automatic Digital Computers VI. Epistasis. Australian Journal of Biological Sciences, 13, 150–162. doi:10.1071/BI9600150

Fraser, A., & Burnell, D. (1970). Computer models in genetics (p. 206).

Freuder, E. C., & Wallace, M. (2005). Constraint Programming. In E. K. Burke & G. Kendall (Eds.), Search Methodologies (pp. 239–272). Springer US. Retrieved from http://dx.doi.org/10.1007/0-387-28356-0_9

Gendreau, M., & Potvin, J.-Y. (2005). Tabu Search. In E. K. Burke & G. Kendall (Eds.), Search Methodologies (pp. 165–186). Springer US. Retrieved from http://dx.doi.org/10.1007/0-387-28356-0_6

Glover, F. W., & Laguna, M. (1997). Tabu Search (p. 408). Boston: Kluwer Academic Publishers.

Hooker, J. (1995). Testing heuristics: We have it all wrong. Journal of heuristics, 1, 33–42.

Jat, S. N., & Yang, S. (2009). A Guided Search Genetic Algorithm for the University Course Timetabling Problem. The 4th Multidisciplinary International Scheduling Conference: Theory and Applications (pp. 10–12). Dublin, Ireland: MISTA 2009.

Kendall, G., & Hussin, N. M. (2005). A Tabu Search Hyper-heuristic Approach to the Examination Timetabling Problem at the MARA University of Technology. In E. Burke & M. Trick (Eds.), Practice and Theory of Automated Timetabling V (Vol. 3616, pp. 270–293). Springer Berlin / Heidelberg. Retrieved from http://dx.doi.org/10.1007/11593577_16

Kennedy, J. (1997). The particle swarm: social adaptation of knowledge. Proceedings of IEEE International Conference on Evolutionary Computation (pp. 303–308).

Kennedy, J., & Eberhart, R. (1995). Particle Swarm Optimization. Proceedings of IEEE International Conference on Neural Networks (pp. 1942–1948).

Kirkpatrick, S., Gelatt, C. D., & Vecchi, M. P. (1983). Optimization by Simulated Annealing. Science, 220, 671–680.

Koizumi, N., Yamamori, K., & Yoshihara, I. (2002). Genetic algorithm approach to university timetabling. Asia-Pacific Conference on Simulated Evolution and Learning (SEAL) (pp. 1–5). Singapur.

Koyuncu, B., & Seçir, M. (2007). Student time table by using graph coloring algorithm. Computer Engineering. Ankara, Turkey.

Martínez, F., García, E., Muñoz, J., & Castañeda, C. (1999). Timetabling académico usando algoritmos genéticos y programación celular. Congreso Nacional de sistemas computacionales. Zacatecas, México.

Marx, D. (2004). Graph colouring problems and their applications in scheduling. Periodica Polytechnica, Electrical Engineering, 48, 11–16.

Matijaš, D., Molnar, V., Čupić, G., Jakobović, M., Dalbelo, D., & Bojana, B. (2010). University Course Timetabling Using ACO: A Case Study on Laboratory Exercises. In R. Setchi, I. Jordanov, R. Howlett, & L. Jain (Eds.), Knowledge-Based and Intelligent Information and Engineering Systems (Vol. 6276, pp. 100–110). Springer Berlin / Heidelberg. Retrieved from http://dx.doi.org/10.1007/978-3-642-15387-7_14

Mejía, J. (2008). Asignación de horarios de clases universitarias mediante algoritmos evolutivos. Barranquilla, Colombia.

Melanie, M. (1996). An Introduction to Genetic Algorithms. (M. Press, Ed.)Computers Mathematics with Applications, 32(6), 133. doi:10.1016/S0898-1221(96)90227-8

Merkle, D., & Middendorf, M. (2005). Swarm Intelligence. In E. K. Burke & G. Kendall (Eds.), Search Methodologies (pp. 401–435). Springer US. Retrieved from http://dx.doi.org/10.1007/0-387-28356-0_14

Montero, E., & Altamirano, L. (2011). A PSO algorithm to solve a Real Course+Exam Timetabling Problem ( 1 ). International conference on swarm intelligence (Vol. 2, pp. 1–8).

Müller, T. (2005). Constraint-based Timetabling. Charles University in Prague.

Nandhini, M., & Kanmani, S. (2009a). A Survey of Simulated Annealing Methodology for University Course Timetabling 2. International Journal of Recent Trends in Engineering, 1(2), 1–3.

Nandhini, M., & Kanmani, S. (2009b). A Survey of Simulated Annealing Methodology for University Course Timetabling 2. International Journal of Recent Trends in Engineering, 1(2), 1–3.

Osman, I., & Kelly, J. (1996). Meta-Heuristics: Theory and Applications. Ed. Kluwer Academic.

Poli, R. (2008). Analysis of the Publications on the Applications of Particle Swarm Optimisation. Journal of Artificial Evolution and Applications, 2008(2), 1–10. doi:10.1155/2008/685175

Qu, R. (2002). Case-based reasoning for course timetabling problems. Search. University of Nottingham.

Sastry, K., Goldberg, D., & Kendall, G. (2005). Genetic Algorithms. In E. K. Burke & G. Kendall (Eds.), Search Methodologies (pp. 97–125). Springer US. Retrieved from http://dx.doi.org/10.1007/0-387-28356-0_4

Schaerf, A. (1999). A Survey of Automated Timetabling. Artificial Intelligence Review, 13(2), 87–127. Retrieved from http://dx.doi.org/10.1023/A:1006576209967

Selim, S. (1988). Split vertices in vertex colouring and their application in developing a solution to the faculty timetable problem. The Computer Journal, 30(1), 76–82.

Shi, Y., & Eberhart, R. (1998). A modified particle swarm optimizer. Proceedings of IEEE International Conference on Evolutionary Computation (pp. 69–73).

Socha, K., Sampels, M., & Manfrin, M. (2003). Ant Algorithms for the University Course Timetabling Problem with Regard to the State-of-the-Art, 334–345.

Tamayo, C., Campaña, P., & Expósito, R. (2007). Alternativa para el proceso de planificación de horarios docentes de una Universidad. Ciencias Holguín, XIII(4), 1–8.

Whitley, D., & Watson, J. (2005). Complexity Theory and the No Free Lunch Theorem. In E. K. Burke & G. Kendall (Eds.), Search Methodologies (pp. 317–339). Springer US. Retrieved from http://dx.doi.org/10.1007/0-387-28356-0_11

Wolpert, D., & Macready, W. (1997). No Free Lunch Theorems for Optimization. IEEE Transactions of Evolutionary Computation, 1, 67–82.

Wren, A. (1996). Scheduling, timetabling and rostering – A special relationship? In E. Burke & P. Ross (Eds.), Practice and Theory of Automated Timetabling (Vol. 1153, pp. 46–75). Springer Berlin / Heidelberg. Retrieved from http://dx.doi.org/10.1007/3-540-61794-9_51

Zhang, L., & Lau, S. (2005). Constructing university timetable using constraint satisfaction programming approach. International Conference on Computational Intelligence for Modelling, Control and Automation International Conference on Intelligent Agents, Web Technologies and Internet Commerce (pp. 55–60). Wollongong, Australia.

Černý, V. (1985). Thermodynamical approach to the traveling salesman problem: An efficient simulation algorithm. Journal of Optimization Theory and Applications, 45, 41–51. doi:10.1007/BF00940812