El problema del conjunto independiente en la selección de horarios de cursos

Abstract

Registration process at the Universidad Aut´onoma Metropolitana is such thatevery student is free to choose his/her own subjects and schedule. Success of thissystem, based in the percentage of students that obtain a place in the lectures chosen, depends principally on the characteristics of the supply of scheduled lectures, relativesto quantity and variety of timetables, as well as the oportunity of the students todo an adequate selection of lectures. An adequate selection of lectures is a subset ofthe lectures set with pairwise different subjects and timetables. The Choose LecturesProblem is to find the maximal adequate selection of lectures. A Graph Theory modelof the problem and an algorithm to solve it will be shown.Keywords: Graph Theory, Independent Set, Operations Research, Educational Timetabling.

El proceso de inscripci´on para alumnos de la Universidad Aut´onoma Metropolitanatiene como fundamento la libertad de cada alumno de seleccionar las asignaturas quecursar´a, as´? como los grupos en los que quedar´a inscrito. El ´exito de este sistema,medido en t´erminos del porcentaje de alumnos que obtienen inscripci´on en los cursosque seleccionaron, depende en gran medida tanto de las caracter´?sticas de la oferta degrupos, relativas principalmente a la cantidad y a la variedad de horarios, como dela posibilidad por parte de los alumnos de hacer una selecci´on adecuada de horariospara los cursos por los que optaron. Una selecci´on adecuada de horarios de cursos esaquella en la que las asignaturas seleccionadas tienen horarios dos a dos compatibles.El problema de selecci´on de horarios consiste en la obtenci´on de una selecci´on dehorarios adecuada de cardinalidad m´axima. En este trabajo se presentar´a un modelode Teor´?a de Gr´aficas para este problema as´? como un algoritmo de soluci´on para elmismo.Palabras clave: Calendarizaci´on, Conjunto Independiente, Investigaci´on de Operaciones,Teor´?a de Gr´aficas.