Algoritmo Goloso Para La eLaboracion Automatica De Horarios

Redalyc
Sistema de Información Científica
Red de Revistas Científicas de América Latina, el Caribe, España y Portugal

GRANADA E., MAURICIO; TORO OCAMPO, ELIANA M.; FRANCO BAQUERO, JOHN F. Programación óptima de horarios de clase usando un algoritmo memético Scientia Et Technica, vol. XII, núm. 30, mayo, 2006, pp. 255-260 Universidad Tecnológica de Pereira Pereira, Colombia
Disponible en:http://www.redalyc.org/src/inicio/ArtPdfRed.jsp?iCve=84920491051

Scientia Et Technica ISSN (Versión impresa): 0122-1701 scientia@utp.edu.co Universidad Tecnológica de Pereira Colombia

¿Cómo citar?

Número completo

Más información del artículo

Página de la revista

www.redalyc.org Proyecto académico sin fines de lucro, desarrollado bajo la iniciativa de acceso abierto

Scientia etTechnica Año XII, No 30, Mayo de 2006 UTP. ISSN 0122-1701

255

PROGRAMACIÓN ÓPTIMA DE HORARIOS DE CLASE USANDO UN ALGORITMO MEMÉTICO
RESUMEN El problema de programación óptima de horarios que se propone está conformado por un conjunto de eventos o clases que deben ser programados en 45 bloques de tiempo (5 días de 9 horas de clase cada uno), un conjunto de salones en los cuales se impartenlas clases, un conjunto de estudiantes los cuales asisten a las clases y un conjunto de características satisfechas por los salones y requeridas por las clases. Cada estudiante asiste a un determinado número de clases y cada salón tiene un tamaño. El objetivo es elegir un salón y un bloque de tiempo para cada clase de forma que se maximicen las preferencias de los estudiantes sin crear conflictosen la programación de estudiantes o salones. La técnica empleada para resolver este problema se basa en la modificación y adecuación del algoritmo genético propuesto por Chu-Beasley. PALABRAS CLAVES: optimización de horarios, Programación de cursos, Programación de salones. ABSTRACT The Timetabling problem proposed consists of a set of events to be scheduled in 45 timeslots (5 days of 9 hourseach), a set of rooms in which events can take place, a set of students who attend the events, and a set of features satisfied by rooms and required by events. Each student attends a number of events and each room has a size. The objective is to choose meeting rooms and times for each event that maximize student preferences without creating student or room schedule conflicts. The used technique tosolve this problem is based on the modification and adjustment of the genetic algorithm proposed by Chu-Beasley. KEYWORDS: scheduling. Timetabling problem, Course scheduling, Classroom MAURICIO GRANADA E. Ingeniero Electricista, M.Sc. Docente Programa de Ingeniería eléctrica. Universidad Tecnológica de Pereira magra@utp.edu.co ELIANA M. TORO OCAMPO Ingeniera Industrial, M.Sc. Docente CatedráticoFacultad de Ingeniería Industrial Universidad Tecnológica de Pereira eliana@utp.edu.co JOHN F. FRANCO BAQUERO Docente Catedrático Programa de Ingeniería eléctrica. Universidad Tecnológica de Pereira jffb@utp.edu.co

1. INTRODUCCIÓN El problema de programación óptima de horarios de clase que se aborda en este artículo corresponde a una versión simplificada, donde se consideran algunas restricciones defactibilidad y optimalidad de las muchas posibles así cómo un único recurso para ser asignado, los salones. La solución a este problema consiste en establecer una secuencia, en un período determinado de tiempo (típicamente una semana), de sesiones, clases o eventos ofrecidos a los estudiantes de forma que se cumpla un conjunto de restricciones de diferentes tipos. Es considerado un problemacombinatorial multidimensional NP-completo de difícil solución. En la literatura especializada es común encontrar soluciones que dividen el problema para posteriormente resolverlo de forma combinada e iterativa [2,3]. Generalmente, los subproblemas resultantes de esta división corresponden a uno de asignación de recurso único (programación de salones) y a otro de programación de horarios. Hertz [4]...