Algoritmo de horario del profesor

Este es un problema de mapeo: es necesario mapear cada hora en una semana y cada profesor una actividad (enseñar a una determinada clase o hora libre).

Divide el problema:

1. Cree la lista de profesores, clases y preferencias y luego deje que el usuario rellene algunas de las preferencias en un mapa para tener como punto de partida.
2. Tomar al azar un elemento de la lista y ponerlo en una posición libre al azar en el mapa si no cruza ninguna comprobación de cordura hasta que la lista esté vacía. Si en cualquier iteración determinada no se puede colocar un elemento en el mapa sin cruzar un sanity check shift dos posiciones en el mapa e intentarlo de nuevo.
3. Cuando el mapa esté lleno, intente cambiar de posición en el mapa para optimizar el resultado.

En los pasos 2 y 3 muestre cada iteración al usuario: los elementos que quedan en la lista, las posiciones en el mapa y el siguiente movimiento calculado y deje que el usuario intervenga.

No intenté esto, pero este sería mi enfoque inicial.

He abordado problemas similares de planificación/programación en el pasado y la técnica de IA que a menudo es la más adecuada para esta clase de problema es el "Razonamiento Basado en restricciones".

Es básicamente un método de fuerza bruta como sugirió Laurenty, pero el enfoque implica aplicar restricciones en un orden eficiente para hacer que las soluciones inviables fallen rápidamente, para minimizar el cálculo requerido.

Googlear "Razonamiento Basado en restricciones" trae muchos recursos sobre el técnica y su aplicación a problemas de programación.

Respondiendo a mi propia pregunta:

El proyecto FET mencionado por gnud utiliza este algoritmo:

Algunas palabras sobre el algoritmo: FET utiliza un algoritmo heurístico, colocando las actividades a su vez, comenzando con los más difíciles. Si no encontrar una solución que le apunta a la posibles actividades imposibles, así que puede corregir errores. Algoritmo intercambia actividades recursivamente si es posible con el fin de hacer espacio para una nueva actividad, o, en casos extremos, backtracks e interruptores orden de evaluación. El código importante está en src / engine / generate.cpp. Por favor, envíe un correo electrónico me para más detalles o unirse al correo lista. El algoritmo imita la operación de un timetabler humano, I pensar.

Link

Siguiendo el "Razonamiento Basado en Restricciones" liderado por un Software Estricto en Wikipedia, me llevan a estos páginas que tienen un párrafo interesante:

Resolviendo una satisfacción con restricciones problema en un dominio finito es un NP-problema completo en general. La investigación ha demostrado una serie de subcasas de tiempo polinómico, en su mayoría obtenido restringiendo bien la dominios o restricciones permitidos o forma en que se pueden colocar restricciones sobre variable. La investigación también ha relación establecida de la constraint satisfacción problema con problemas en otras áreas tales como finito model theory and databases (en inglés).

Esto me recuerda a esta entrada de blog sobre la programación de una conferencia, con una explicación de video aquí.

Cómo lo haría:

Que la población incluya dos cosas:

• Quién enseña qué clase (espero que los maestros enseñen una materia).
• Lo que una clase toma en una franja horaria específica.

De esta manera no podemos tener conflictos (un profesor en 2 lugares, o una clase que tiene dos asignaturas al mismo tiempo).

La aptitud la función incluiría:

• Cuántas franjas horarias da cada maestro por semana.
• Cuántos espacios de tiempo tiene un maestro en el mismo día (No pueden tener un día completo de enseñanza, esto también debe ser equilibrado).
• Cuántas franjas horarias de la misma materia tiene una clase en el mismo día (¡No pueden tener un día completo de matemáticas!).

Tal vez tomar la desviación estándar para todos ellos, ya que deben ser equilibrados.

No estoy seguro de si esto cubre el mismo terreno que @Stringent Software respuesta (ya que el nombre es ligeramente diferente), pero tengo un par de muy buenos amigos que están investigando el área de Restricción Programación. La creación de horarios es una aplicación de su investigación.

El Dr. Chris Jefferson creó un programa llamado Minion que puede descargar desde SourceForge, y es un solucionador de problemas de restricción de fuerza bruta muy rápido escrito en C++

Creo que le faltan algunas restricciones.

Uno preferiría, siempre que sea posible, tener a los profesores programados para las clases para las que están certificados.

Uno sospecharía que las clases que se solicitan, y el número de empleados esperado en cada una serían significativos.

Creo que el lugar para comenzar sería enumerar todas sus restricciones, encontrar una estructura de datos para representarlas.

Luego crea algún tipo de motor para que construya una solución de prueba, luego lo evalúa para la aptitud de acuerdo con las limitaciones.

A continuación, se podría lanzar la parte divertida algoritmos genéticos en ella, y ver si se puede conseguir que la aptitud para aumentar con el tiempo a medida que los genes se mezclan.

Comience con un pequeño conjunto de restricciones, y aumente a medida que vea el éxito (si ve el éxito)

Podría haber una manera de tomar las restricciones y calzarlas junto con algo así como un algoritmo de programación lineal.

Estoy de acuerdo. Suena como un divertido desafío

Una de las peores páginas web de código abierto de la historia, pero el proyecto parece prometedor: http://www.lalescu.ro/liviu/fet/

Un enfoque basado en la web:
phpScheduleIt (no específico de la escuela)

Mirar esta pregunta me hizo pensar sobre este problema, y si algoritmos genéticos serían utilizables en este caso. Sin embargo, sería bastante difícil de mutar posibilidades mientras mantener las reglas de control de cordura. También no está claro para mí cómo distinguir los requisitos incompatibles.

Los algoritmos genéticos son muy adecuados para problemas como este. Una vez que se llega a una representación decente del cromosoma (en este caso, probablemente un vector representando todos los espacios de clase disponibles) usted es la mayor parte del camino allí.

No se preocupe por mantener controles de cordura durante la fase de mutación. La mutación es aleatoria. Los controles de cordura y preferencia pertenecen a la fase de selección. Un control de cordura fallido reduciría drásticamente la aptitud de un individuo, mientras que una preferencia fallida solo disminuiría ligeramente la aptitud.

Los requisitos incompatibles son un problema completamente diferente. Si son completamente incompatibles, consigue una población que no converja en nada útil.

Buena suerte. Ser el hijo de un padre con este tipo de problema es lo que me llevó al grupo de investigación que terminé ...

Cuando era un niño, mi padre programó oficiales de partidos en una liga deportiva local, esto tenía una lista similarmente larga de restricciones y traté de escribir algo para ayudar. Cuando llegué a la Universidad, incluso lo utilicé como mi proyecto de último año, finalmente, estableciéndome en una implementación de Monte Carlo (utilizando un modelo de Recocido Simulado).

La idea básica es que si no es NP, está bastante cerca, así que en lugar de asumir que hay una solución, me propondría encontrar la mejor dentro de un plazo determinado. Ponderaría todas las restricciones con los costos para romperlas: los controles de cordura tendrían costos enormes, las preferencias tendrían costos más bajos (pero aumentarían para más descansos, por lo que romperlo una vez sería menos de la mitad del costo de romperlo dos veces).

La idea básica es que comencé con una solución 'aleatoria' y la costé; luego hice cambios al intercambiar un pequeño número de tareas, re-valorarlo y luego, probalísticamente aceptado o rechazado el cambio.

Después de miles de iteraciones que pulgadas más cerca de una solución aceptable.

Créanme, sin embargo, que esta clase de problemas tiene grupos de investigación produciendo doctorados por lo que están en muy buena compañía.

También puede encontrar algún interés en el ámbito de la Programación Lineal, por ejemplo, simplex y así sucesivamente.

Sí, creo que esto es NP completo - o al menos para encontrar la solución óptima es NP completo.

Trabajé en un problema similar en la universidad cuando le dije al padre de un amigo (que era profesor) que podía resolver sus problemas de programación si no encontraba un programa adecuado para ello (esto fue en 1990 o así)

Creo que Bill Gates también trabajó en un sistema como este en la escuela secundaria o en la universidad para su escuela secundaria. Aunque no estoy seguro.

Buena suerte. Todas mis notas se han ido y nunca llegué a implementar una solución que pudiera comercializar. Fue un proyecto de especialidad que re-codifiqué a medida que aprendía nuevos idiomas (Basic, Scheme, C, VB, C++)

Diviértete con él

Veo que este problema puede ser resuelto por el programa Prolog conectándolo a una base de datos y el programa puede hacer que el horario dado un conjunto de restricciones leer abt "Problema de satisfacción con restricciones prolog"