Algoritmo de horario del maestro

https://stackoverflow.com/questions/210635

03-07-2019
|

Pregunta

Este es un problema que he tenido en mente durante mucho tiempo. Siendo hijo de un maestro y un programador, se me ocurrió desde el principio ... pero todavía no he encontrado una solución para ello.

Entonces este es el problema. Uno necesita crear un horario para una escuela, usando algunas restricciones. Estos generalmente se dividen en dos categorías:

Comprobaciones de cordura

Un maestro no puede enseñar dos clases al mismo tiempo
Un estudiante no puede seguir dos lecciones al mismo tiempo
Algunos maestros deben tener al menos un día libre durante la semana
Todos los días de la semana deben estar cubiertos por el horario
El sujeto X debe tener exactamente unas horas cada semana
...

Preferencias

El horario de cada maestro debe ser lo más compacto posible (es decir, el maestro debe trabajar todas las horas durante el día consecutivo sin pausas si es posible)
Los maestros que tienen días libres deberían poder expresar una preferencia en qué día
Los maestros que trabajan a tiempo parcial deben poder expresar una preferencia si trabajan al principio o al final de la jornada escolar.
...

Ahora, después de unos años de no encontrar una solución (y aprender una o dos cosas mientras tanto ...), me di cuenta de que esto huele a un problema NP-difícil.

¿Está probado como NP-hard?

¿Alguien tiene una idea sobre cómo descifrar esto?

Mirando esta pregunta hecha Pienso en este problema y si los algoritmos genéticos serían utilizables en este caso. Sin embargo, sería bastante difícil mutar posibilidades mientras se mantienen las reglas de verificación de cordura. Tampoco está claro para mí cómo distinguir los requisitos incompatibles.

Un pequeño apéndice para especificar mejor el problema. Esto se aplica a las aulas de estilo escolar italiano donde todos los estudiantes están asociados en diferentes clases (por ejemplo: año 1 sección A) y los maestros se mueven entre clases. Todos los estudiantes de la misma clase tienen el mismo horario y no tienen otra opción sobre qué lecciones asistir.

Solución

Soy uno de los desarrolladores que trabaja en la parte del planificador de un sistema de información estudiantil. Durante nuestro enfoque original del problema de programación, investigamos algoritmos genéticos para resolver problemas de satisfacción de restricciones, y aunque tuvimos éxito inicialmente, nos dimos cuenta de que había una solución menos complicada para el problema (después de asistir a un taller de programación escolar)

Nuestra implementación actual funciona muy bien y utiliza la fuerza bruta con heurística inteligente para obtener un cronograma válido en un corto período de tiempo. El horario maestro (asignación de las clases a los maestros) se construye primero, teniendo en cuenta todas las limitaciones que tiene cada maestro y minimizando la posibilidad de conflictos para los estudiantes (en función de sus solicitudes de cursos). Los estudiantes se programan en las clases utilizando el mismo método.

Hacer esto le permite hacer que la máquina construya un horario maestro primero, y luego hacer que un humano lo modifique si es necesario.

La implementación actual del planificador está escrita en perl, pero otras opciones que visitamos al principio fueron Prolog y CLIPS (sistema experto)

Otros consejos

Este es un problema de mapeo: necesita asignar a cada hora en una semana y a cada maestro una actividad (enseñar a cierta clase u hora libre).

Divida el problema:

Cree la lista de profesores, clases y preferencias, luego permita que el usuario complete algunas de las preferencias en un mapa para tenerlas como punto de partida.
Tome aleatoriamente un elemento de la lista y colóquelo en una posición libre aleatoria en el mapa si no cruza ninguna comprobación de cordura hasta que la lista esté vacía. Si en alguna iteración determinada no puede colocar un elemento en el mapa sin cruzar un control de cordura, cambie dos posiciones en el mapa e intente nuevamente.
Cuando se llena el mapa, intente cambiar las posiciones en el mapa para optimizar el resultado.

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

No probé 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 más adecuada para esta clase de problema es "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 no factibles fallen rápidamente, para minimizar el cálculo requerido.

Buscar en Google " Razonamiento basado en restricciones " trae muchos recursos sobre la técnica y su aplicación a problemas de programación.

Respondiendo mi propia pregunta:

El proyecto FET mencionado por gnud usa 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 puede encuentra una solución que te indique posibles actividades imposibles, entonces Puedes corregir errores. El algoritmo intercambia actividades recursivamente si eso es posible para hacer espacio para una nueva actividad o, en casos extremos, orden de retrocesos e interruptores de evaluación. El código importante está en src / engine / generate.cpp. Por favor envíe un correo electrónico para más detalles o únete al correo lista. El algoritmo imita el operación de un calendario humano, yo pensar.

Enlace

Seguimiento del "Razonamiento basado en restricciones" liderado por Software estricto en Wikipedia, llévame a estos páginas que tienen un párrafo interesante:

Resolver una restricción de satisfacción problema en un dominio finito es un Problema NP-completo en general. La investigación ha demostrado una serie de subcasas de tiempo polinómico, principalmente obtenido mediante la restricción de dominios permitidos o restricciones o la se pueden colocar restricciones sobre el variables La investigación también ha relación establecida de la problema de satisfacción de restricciones con problemas en otras áreas como finito teoría de modelos y bases de datos.

Esto me recuerda a esto publicación de blog sobre la programación de una conferencia , con un explicación en video aquí .

Cómo lo haría:

Haga que la población incluya dos cosas:

Quién enseña en qué clase (espero que los maestros enseñen una materia).
Lo que una clase toma en un intervalo de tiempo específico.

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

La función de fitness incluiría:

Cuántos espacios de tiempo da cada maestro por semana.
Cuántos espacios de tiempo tiene un maestro 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 el mismo día (no pueden tener un día completo de matemáticas!).

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

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

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

Creo que es posible que te falten algunas restricciones.

Uno preferiría, siempre que sea posible, que los maestros estén programados para las clases para las cuales están certificados.

Uno sospecharía que las clases que se solicitan, y el recuento esperado en cada una sería significativo.

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

Luego cree algún tipo de motor para construir una solución de prueba, luego evalúe su idoneidad de acuerdo con las restricciones.

A continuación, podría arrojarle la parte divertida de los algoritmos genéticos y ver si puede aumentar la aptitud física 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)

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

Estoy de acuerdo. Suena como un desafío divertido

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 bonito posibilidades difíciles de mutar mientras manteniendo las reglas de control de cordura. Tampoco está claro para mí cómo distinguir requisitos incompatibles.

Los algoritmos genéticos se adaptan muy bien a problemas como este. Una vez que se te ocurre una representación decente del cromosoma (en este caso, probablemente un vector que representa todos los espacios de clase disponibles), estás casi todo el 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 levemente la aptitud.

Los requisitos incompatibles son un problema completamente diferente. Si son completamente incompatibles, obtendrás una población que no converge en nada útil.

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

Cuando era un niño, mi padre programaba oficiales de partidos en una liga deportiva local, esto tenía una larga lista de limitaciones e intenté escribir algo para ayudar. Cuando llegué a la Universidad, incluso lo utilicé como mi proyecto de último año, y finalmente me decidí por 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, por lo que, en lugar de suponer que hay una solución, me propongo encontrar lo mejor en un plazo determinado. Consideraría todas las limitaciones 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 romperlos una vez sería menos de la mitad del costo de romperlos dos veces).

La idea básica es que comencé con una solución 'aleatoria' y le costé; luego realizó cambios intercambiando un pequeño número de tareas, lo revalorizó y luego, probalísticamente, aceptó o rechazó el cambio.

Después de miles de iteraciones, te acercas a una solución aceptable.

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

También puede encontrar algún interés en el campo de la programación lineal, p. 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 maestro) que podía resolver sus problemas de programación para él si no encontraba un programa adecuado para ello (esto fue en 1990 más o menos )

No tenía idea de en qué me metí. Afortunadamente para nosotros, todo lo que tenía que hacer era encontrar una solución que se ajustara a las limitaciones. Pero en mis pruebas siempre me preocupaba determinar si había una solución en absoluto. Nunca tuvo demasiadas limitaciones y el programa usó diferentes heurísticas y seguimiento posterior. Fue muy divertido.

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

Buena suerte. Todas mis notas se han ido y nunca pude implementar una solución que pudiera comercializar. Fue un proyecto especializado que volví a codificar a medida que aprendía nuevos idiomas (Básico, Esquema, C, VB, C ++)

Diviértete con ella

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 tenga un conjunto de restricciones leer abt " Restricción de satisfacción Problema prólogo "

Licenciado bajo: CC-BY-SA con atribución

No afiliado a StackOverflow