El problema de asignación de horarios consiste en asignar a una serie de asignaturas unos horarios. La dificultad reside en que los asignaturas se deben impartir ocupando el menor tiempo posible, haciendo que no se pisen unas asignaturas con otras, teniendo en cuenta los alumnos matriculados en éstas.
Así conseguiremos crear un horario para todas las asignaturas sin que coincidan unas a otras y asegurando que los alumnos puedan asistir a las asignaturas que han elegido sin perderse ninguna.
Resolución del problema
Para resolver este problema utilizaremos la coloración de grafos. Crearemos un grafo en el que los vértices sean las asignaturas y las aristas supondrán que las dos asignaturas que están uniendo, no pueden ir a la misma hora, ya que uno o mas alumnos se han matriculado a las dos asignaturas a la vez.
Explicación del algoritmo Vertice-Coloración
La clase AddAristasAsignaturas solo tiene un único método, que es anadeAristasAsignaturas, y lo que nos permite es pasar del grafo bipartito donde tenemos los alumnos y las asignaturas a un único grafo en el que solo se verán las relaciones existentes entre las asignaturas, para después poder colorear ese grafo, y hacer una vértice coloración.
Para añadir los alumnos y las asignaturas nos creamos dos clases, una para los alumnos que tendrán un atributo nombre, dni y una lista de asignaturas donde están matriculados, y otra clase para las asignaturas que tendrá un atributo con el nombre de la asignatura y un identificador para que no se repitan asignaturas.
Dicho algoritmo lo que hace es que cada alumno tiene una lista de asignaturas a las que esta matriculado, y vamos a hacer un recorrido de todos los alumnos y las asignaturas en las que este matriculado un mismo alumno le pondremos una arista entre ese par de asignaturas, indicando que esas dos asignaturas no pueden estar o mejor dicho darse en una misma hora. De esta manera obtendremos otro grafo, pero con tan solo las relaciones existentes entre todas las asignaturas.
A continuación veremos un ejemplo que aclarara todo lo explicado anteriormente, que es lo que en realidad hace el Algoritmo de anadeAristasAsignaturas.
Grafo Bipartito de alumnos y asignaturas:
Este grafo se contruye mediante la interfaz gráfica, añadiendo alumnos y asignaturas, de manera que introducimos las asignaturas y los alumnos y vamos matriculando a los alumnos a las asignaturas que se deseen.
En este ejemplo en concreto, el alumno 1 esta matriculado de las asignaturas 1, 2 y 3, luego estas asignaturas, a la hora de construir el grafo de solo asignaturas deben estar relacionadas entre ellas de forma que se añaden las aristas (As-1,As-2), (As-2,As-3) y (As-1,As-3).
El segundo alumno esta matriculado de las asignaturas 2 y 3, luego se debería de poner la arista (As-2,As-3), pero esa arista ya esta añadida del alumno anterior, luego este alumno no aporta ninguna arista nueva en el nuevo grafo.
El tercer alumno solo esta matriculado de la signatura 3, luego no hay problemas.
El cuarto alumno introduce una nueva arista, ya que esta matriculado de la signatura 3 y 4, y esas dos asignaturas no estaban relacionadas, luego se añade la arista (As-3,As-4).
Los alumnos quinto y sexto, no añaden nada nuevo al grafo, ya que las relaciones entre signaturas que aportan ya están contempladas.
A partir del grafo anterior se saca el siguiente grafo, con las dependencias entre asignaturas comentadas anteriormente:
Ahora vamos a explicar como hemos realizado la cloración del grafo. Para ello nos hemos creado la clase GrafoColor, a la que le pasamos el grafo y realiza un algoritmo voraz que lo colorea. El método que contiene el algoritmo voraz es el método público coloreaVertices(), y lo que en realidad hace este algoritmo es lo siguiente:
Empieza por todos los vértices del grafo (es decir las asignaturas). En principio todos tienen el color 0 que según nuestro ejemplo sería el color rojo.
Hacemos un recorrido de todos los vértices empezando por la asignatura 1, que le asignamos el color 1 que será el azul en nuestro ejemplo. Si ninguno de los vértices adyacentes tiene ese color, le asignamos ese color al vértice, y si no incrementamos el color y volvemos a empezar, hasta encontrar un color que no tenga ninguno de los vértices adyacentes.
Veamos como seria paso a paso en el ejemplo:
Paso 1: Intentamos asignar el color 1 (Azul) a la asignatura 1 (As-1). Podemos hacerlo ya que los vértices adyacentes {As-2 y As-3} tienen color distinto.
Paso 2: Ahora cogemos el segundo vértice y empezamos con el color 1(Azul). No podemos asignárselo, ya que uno de sus vértices adyacentes (As-1) tiene ese color, luego incrementamos el color e intentamos asignarle el color 2 , que será el Verde. En este caso si podemos asignárselo, ya que los dos vértices adyacentes no tienen ese color.
Paso 3: Cogemos el tercer vértice y empezamos intentando asignarle el color Azul, vemos que no podemos, porque un vértice adyacente tiene ese color. Lo intentamos de nuevo con el color verde, e igualmente tampoco se puede. Por último le damos otro color, que seria el tercer color usado y va a corresponder al color Amarillo. Ese color si lo podemos asignar.
Paso 4: Por último cogemos el cuarto vértice y empezamos con el color 1, el azul. Como el único vértice adyacente al As-4 es el As-3, y este tiene color 3(Amarillo), si podemos asignarle el color 1, es decir el color Azul.
Así quedaría el grafo coloreado y el número de colores usados serán las horas mínimas necesarias para poder dar todas las asignaturas y que todos los alumnos puedan asistir a clase. En este caso concreto serian tres horas, donde las asignaturas impartidas en cada hora serían las siguientes:
Hora 1 -> As-1 y As-4.
Hora 2 -> As-2.
Funcionamiento de la aplicación
Para poder ejecutar el programa debe tener instalado la Máquina Virtual de Java que se puede descargar de Sun.
El applet puede verse un poco más abajo en esta misma página. También se puede descargar su 
código fuente.
Como introducir las asignaturas:
Para introducir las asignaturas en la aplicación, debemos pinchar en la pestañita que pone Asignaturas. Se deben rellenar los campos Id Asignatura y Nombre Asignatura y posteriormente darle al botón Añadir Asignatura. Las asignaturas introducidas irán apareciendo en la lista vertical que está a la derecha de la ventana.
Como introducir los alumnos:
Para introducir los alumnos en la aplicación, debemos de pinchar en la pestañita que pone Alumnos. Aparecerá una ventana en la que debemos de rellenar los campos de Nombre Alumno y DNI Alumno. Una vez introducido, le damos al botón Añadir Alumno. Los alumnos introducidos aparecerán en la lista superior derecha.
En la lista inferior izquierda aparecerán las asignaturas introducidas y seleccionando un alumno y una asignatura y pulsando el botón Añadir, matricularemos al alumno seleccionado en la asignatura seleccionada y aparecerá en la lista inferior derecha.
Pulsando un alumno, se listará las asignaturas en las que está matriculado.
Crear los horarios:
Para crear los horarios, pulsamos sobre la pestaña Crear Horarios y pulsamos el botón Crea Horarios. Aparecerá en la tabla las horas necesarias para dar todos los cursos y en que horas se tendrán que dar cada asignatura.
Observación: Los ejemplos puestos en las capturas de pantalla son los mismos que se han expuesto en las explicaciones de cómo trabajan los algoritmos. La aplicación está programada para que tenga como entrada cualquier número de alumnos y de asignaturas, en lo único que afectará será en el tiempo de ejecución que será mayor conforme mas datos sean introducidos.
Applet