Algoritmo para la creación de un horario de la escuela
https://stackoverflow.com/questions/2177836
-
24-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
Me he estado preguntando si hay soluciones conocidas para el algoritmo de creación de un horario de la escuela.Básicamente, se trata de la optimización de la "hora de la dispersión" (tanto en los profesores y las clases de caso) para determinada clase-sujeto de asociaciones de maestros.Podemos asumir que tenemos conjuntos de clases, la lección asignaturas y profesores asociados el uno con el otro en la entrada y que el calendario debe caber entre las 8 am y las 4 de la tarde.
Supongo que no es, probablemente, que no precisa algoritmo para eso, pero tal vez alguien sabe una buena aproximación o sugerencias para el desarrollo de la misma.
Solución
Este problema es NP-COMPLETO!
En pocas palabras, uno debe explorar todas las combinaciones posibles para encontrar la lista de soluciones aceptables. Debido a las variaciones en las circunstancias en que el problema aparece en varias escuelas (por ejemplo: ¿hay restricciones con respecto a las aulas?, ¿Se dividen algunas de las clases en subgrupos algunas veces?, ¿Es este un horario semanal? etc.) no hay una clase de problemas bien conocida que corresponda a todos los problemas de programación. Quizas el Problema de mochila tiene muchos elementos de similitud con estos problemas en general.
Una confirmación de que este es tanto un problema difícil como para el cual las personas buscan una solución perennemente, es verificar esto (largo) Lista de herramientas de programación de software (en su mayoría comerciales)
Debido a la gran cantidad de variables involucradas, cuya mayor fuente son, típicamente, los deseos del miembro de la facultad;-) ..., es típicamente poco práctico a considerar enumerar todas las combinaciones posibles. En su lugar, necesitamos elegir un enfoque que visite un subconjunto de los espacios de problema/solución.
- Algoritmos genéticos, citado en otra respuesta es (o, en mi humilde opinión, parece) Bien equipado para realizar este tipo de búsqueda semi-guiada (el problema es encontrar una buena función de evaluación para que los candidatos se mantengan para la próxima generación)
- Reescritura de gráficos Los enfoques también son útiles con este tipo de problemas de optimización combinatoria.
En lugar de centrarse en implementaciones particulares de un programa de generador de programación automática, me gustaría sugerir Algunas estrategias que se pueden aplicar, a nivel de la definición del problema.
La justificación general es que en la mayoría de los problemas de programación del mundo real, se requerirán algunos compromisos, no todas las limitaciones, expresadas e implícitas: se satisfarán completamente. Por lo tanto, nos ayudamos a nosotros mismos:
- Definir y clasificar todas las limitaciones conocidas
- Reduciendo el espacio de problemas, manualmente, proporcionando un conjunto de adicional restricciones.
Esto puede parecer contradictorio pero, por ejemplo, proporcionando un horario inicial y parcialmente lleno (digamos aproximadamente el 30% de los espacios de tiempo), de una manera que satisfaga completamente todas Tiempo/espacio necesario para producir soluciones candidatas.
Otra forma en que la ayuda de restricciones adicionales es, por ejemplo, "artificialmente" agregando una restricción que evita la enseñanza de algunas materias en algunos días de la semana (si este es un horario semanal ...); Este tipo de restricciones da como resultado reducir el problema/espacios de solución, sin, típicamente, excluyendo un número significativo de buenos candidatos. - Asegurar que algunas de las restricciones del problema se puedan calcular rápidamente. Esto a menudo se asocia con la elección del modelo de datos utilizado para representar el problema; La idea es poder optar rápidamente por (o podar) algunas de las opciones.
- Redefinir el problema y permitir que algunas de las restricciones se rompan, algunas veces (típicamente hacia los nodos finales del gráfico). La idea aquí es eliminar alguno de restricciones para llenar las últimas ranuras en el horario, o para que el programa de generador de horario automático sea impedido a completar todo el horario, en lugar de proporcionarnos una lista de una docena de candidatos plausibles. Un humano a menudo está en una mejor posición para completar el rompecabezas, como se indica, posiblemente rompiendo algunas de las entradas, utilizando información que generalmente no se comparte con la lógica automatizada (por ejemplo, "no hay matemáticas en la tarde" que se puede romper en ocasiones en ocasiones para la clase de "matemáticas y física avanzadas"; o "Es mejor romper uno de los requisitos de Mr Jones que uno de la Sra. Smith ... ;-))
Al revisar esta respuesta, me doy cuenta de que es bastante tímido de proporcionar una respuesta definitiva, pero no es menos llena de sugerencias prácticas. Espero que esta ayuda, con lo que es, después de todo, un "problema difícil".
Otros consejos
Es un lío.un real desastre.Para añadir a las respuestas, ya muy completa, quiero señalar mi experiencia de la familia.Mi madre era maestra y se utiliza para ser involucrados en el proceso.
Resulta que tener una computadora para hacerlo no es sólo difícil de código per se, también es difícil porque hay condiciones que son difíciles de especificar a un pre-horneados programa de ordenador.Ejemplos:
- un maestro enseña, tanto en su escuela y en el otro instituto.Claramente, si él termina la lección no a las 10.30, se puede iniciar en sus instalaciones a las 10.30, porque él necesita algo de tiempo para viajar entre los institutos.
- dos maestros están casados.En general, se considera una buena práctica el no tener una pareja de profesores en la misma clase.Estos dos maestros por lo tanto debe tener dos clases diferentes
- dos profesores se casó, y su hijo asiste a la misma escuela.De nuevo, usted tiene que evitar los dos maestros para enseñar en la clase específica de dónde están sus hijos.
- la escuela tiene instalaciones separadas, como un día la clase en un instituto, y otro día la clase es en otro.
- la escuela dispone de laboratorios compartidos, pero estos laboratorios están disponibles sólo en determinados días de la semana (por razones de seguridad, por ejemplo, donde el personal adicional es requerido).
- algunos maestros tienen preferencias para el libre día:algunos prefieren el lunes, algunos de los viernes, algunos miércoles.Algunos prefieren venir temprano en la mañana, algunos prefieren venir más tarde.
- usted no debe situaciones donde usted tiene una lección de decir, la historia en la primera hora, luego de tres horas de matemáticas, después de una hora de la historia.No tiene sentido para los estudiantes, ni para el profesor.
- debe difundir los argumentos de manera uniforme.No tiene sentido tener los primeros días en la semana de la matemática, y luego el resto de la semana sólo en la literatura.
- usted debe dar a algunos profesores de dos horas consecutivas para hacer pruebas de evaluación.
Como se puede ver, el problema no es NP-completo, es NP-demente.
Así que lo que hacen es que tienen una gran mesa con pequeñas inserciones de plástico, y se mueven a los márgenes de hasta un satisfactorio resultado se obtiene.Nunca comenzar desde cero:normalmente se inicio desde el año anterior calendario y hacer ajustes.
los Competencia de horario internacional 2007 Tenía una pista de programación de lecciones y pista de programación de exámenes. Muchos investigadores participaron en esa competencia. Se probaron mucha heurística y metaheurística, pero al final la metaheurística de búsqueda local (como la búsqueda tabú y el recocido simulado) claramente superan otros algoritmos (como algoritmos genéticos).
Eche un vistazo a los 2 marcos de código abierto utilizados por algunos de los finalistas:
- JBoss Optaplanner (Java, código abierto)
- Unidad (Java, código abierto) - Más para las universidades
Una de mis tareas de mitad de período fue una generación de mesa escolar de algoritmo genético.
Toda la mesa es un "organismo". Hubo algunos cambios y advertencias para el enfoque genérico de algoritmos:
Se hicieron reglas para "mesas ilegales": dos clases en el mismo salón de clases, un maestro que enseñaba dos grupos al mismo tiempo, etc. Estas mutaciones se consideraron letales de inmediato y se brotó un nuevo "organismo" en lugar de los "fallecidos" de inmediato. El inicial fue generado por una serie de intentos aleatorios para obtener uno legal (aunque sin sentido). La mutación letal no se contó para el recuento de mutaciones en la iteración.
Las mutaciones de "intercambio" eran mucho más comunes que las mutaciones "modificar". Los cambios fueron solo entre partes del gen que tenían sentido, sin sustituir a un maestro con un aula.
Se asignaron pequeñas bonificaciones para agrupar ciertas 2 horas juntos, para asignar el mismo aula genérica en secuencia para el mismo grupo, para mantener continuas las horas de trabajo de los maestros y la carga de clase. Se asignaron bonos moderados para dar aulas correctas para sujetos dados, mantener las horas de clase dentro de los lazos (mañana o tarde), y tal. Las grandes bonificaciones fueron para asignar el número correcto de asignaturas dadas, la carga de trabajo dada para un maestro, etc.
Los maestros podrían crear sus horarios de carga de trabajo de "querer trabajar entonces", "bien para trabajar entonces", "no le gusta trabajar entonces", "no puede trabajar entonces", con los pesos adecuados asignados. Las 24 horas enteras eran horarios de trabajo legales, excepto que la noche no era muy deseada.
La función de peso ... oh sí. La función de peso era un producto enorme y monstruoso (como en la multiplicación) de pesos asignados a características y propiedades seleccionadas. Era extremadamente empinado, una propiedad fácil de cambiarla por un orden de magnitud hacia arriba o hacia abajo, y había cientos o miles de propiedades en un organismo. Esto dio como resultado números absolutamente enormes, ya que los pesos, y como resultado directo, deben usar una biblioteca Bignum (GMP) para realizar los cálculos. Para una pequeña prueba de prueba de unos 10 grupos, 10 maestros y 10 aulas, el conjunto inicial comenzó con una nota de 10^-200 de tantos años y se terminó con 10^+300 mim. Era totalmente ineficiente cuando era más plano. Además, los valores crecieron una distancia mucho más amplia con "escuelas" más grandes.
En cuanto al tiempo de cálculo, hubo poca diferencia entre una pequeña población (100) durante mucho tiempo y una gran población (10k+) en menos generaciones. El cálculo durante el mismo tiempo se produjo aproximadamente la misma calidad.
El cálculo (en una CPU de 1 GHz) tomaría unos 1H para estabilizarse cerca de 10^+300, generando horarios que se veían bastante bien, para dicho caso de prueba de 10x10x10.
El problema es fácilmente paralelizable al proporcionar una instalación de red que intercambiaría las mejores muestras entre las computadoras que ejecutan el cálculo.
El programa resultante nunca vio la luz del día afuera haciéndome una buena calificación para el semestre. Mostró algo de promesa, pero nunca tuve suficiente motivación para agregar ninguna GUI y hacerlo utilizable para el público en general.
Este problema es más difícil de lo que parece.
Como otros han aludido, este es un problema completo de NP, pero analicemos lo que eso significa.
Básicamente, significa que tienes que mirar todas las combinaciones posibles.
Pero "Mira" no te dice mucho lo que debes hacer.
Generar todas las combinaciones posibles es fácil. Puede producir una gran cantidad de datos, pero no debería tener muchos problemas para comprender los conceptos de esta parte del problema.
El segundo problema es juzgar si una posible combinación dada es buena, mala o mejor que la solución "buena" anterior.
Para esto, necesitas más que "¿Es una posible solución"?
Por ejemplo, ¿el mismo maestro está trabajando 5 días a la semana durante x semanas seguidas? Incluso si esa es una solución de funcionamiento, podría no ser una mejor solución que alternarse entre dos personas para que cada maestro haga una semana cada uno. Oh, ¿no pensaste en eso? Recuerde, estas son personas con las que está tratando, no solo un problema de asignación de recursos.
Incluso si un maestro pudiera trabajar a tiempo completo durante 16 semanas seguidas, esa podría ser una solución subóptima en comparación con una solución en la que intenta alternar entre los maestros, y este tipo de equilibrio es muy difícil de construir en el software.
Resumir, producir una buena solución a este problema valdrá mucho, para muchas personas. Por lo tanto, no es un problema fácil de romper y resolver. Esté preparado para replantear algunos objetivos que no son 100% y los llamen "lo suficientemente buenos".
ACTUALIZACIÓN: De los comentarios ... ¡también debería tener heurísticas!
Iría con Prolog ... luego use Ruby o Perl o algo para limpiar su solución en una forma más bonita.
teaches(Jill,math).
teaches(Joe,history).
involves(MA101,math).
involves(SS104,history).
myHeuristic(D,A,B) :- [test_case]->D='<';D='>'.
createSchedule :- findall(Class,involves(Class,Subject),Classes),
predsort(myHeuristic,Classes,ClassesNew),
createSchedule(ClassesNew,[]).
createSchedule(Classes,Scheduled) :- [the actual recursive algorithm].
Estoy (aún) en el proceso de hacer algo similar a este problema, pero usando la misma ruta que acabo de mencionar. Prolog (como lenguaje funcional) realmente facilita la resolución de los problemas np más fácil.
Los algoritmos genéticos a menudo se usan para dicha programación.
Fundar Este ejemplo (hacer un horario de clases usando algoritmo genético) que coincide con su requisito bastante bien.
Aquí hay algunos enlaces que encontré:
Horario escolar - Enumera algunos problemas involucrados
Mi algoritmo de tiempo de tiempo, implementado en FET (software de horario gratuito, http://lalescu.ro/liviu/fet/ , una aplicación exitosa):
El algoritmo es heurístico. Lo llamé "intercambio recursivo".
Entrada: un conjunto de actividades a_1 ... a_n y las restricciones.
Salida: un conjunto de veces ta_1 ... ta_n (la ranura de tiempo de cada actividad. Las habitaciones se excluyen aquí, por simplicidad). El algoritmo debe poner cada actividad en una ranura de tiempo, respetando las restricciones. Cada ta_i está entre 0 (t_1) y max_time_slots-1 (t_m).
Restricciones:
C1) Básico: una lista de pares de actividades que no pueden ser simultáneas (por ejemplo, A_1 y A_2, porque tienen el mismo maestro o los mismos estudiantes);
C2) Muchas otras restricciones (excluidas aquí, por simplicidad).
El algoritmo de Timetable (que llamé "intercambio recursivo"):
- Actividades de clasificación, lo más difícil primero. No es un paso crítico, pero acelera el algoritmo tal vez 10 veces o más.
Intente colocar cada actividad (A_i) en una intervalencia de tiempo permitida, siguiendo el orden anterior, una a la vez. Busque una ranura disponible (T_J) para A_i, en la que esta actividad se puede colocar respetando las restricciones. Si hay más ranuras disponibles, elija una aleatoria. Si no hay ninguno disponible, haga intercambio recursivo:
a. Para cada ranura de tiempo T_J, considere qué sucede si pone a_i en t_j. Habrá una lista de otras actividades que no están de acuerdo con este movimiento (por ejemplo, la actividad A_K está en la misma ranura T_J y tiene el mismo maestro o el mismo alumno que A_I). Mantenga una lista de actividades conflictivas para cada ranura de tiempo T_J.
b. Elija una ranura (T_J) con el menor número de actividades conflictivas. Digamos que la lista de actividades en esta ranura contiene 3 actividades: A_P, A_Q, A_R.
C. Coloque a_i en t_j y haga a_p, a_q, a_r no asignado.
d. Intente recursivamente colocar A_P, A_Q, A_R (si el nivel de recursión no es demasiado grande, digamos 14, y si el número total de llamadas recursivas contadas desde el paso 2) en A_i comenzó no es demasiado grande, digamos 2*n), como en el paso 2).
mi. Si se coloca con éxito A_P, A_Q, A_R, regrese con éxito, de lo contrario intente otras ranuras de tiempo (vaya al paso 2 b) y elija la siguiente ranura de mejor tiempo).
F. Si todos (o un número razonable de) ranuras de tiempo se intentaron sin éxito, regrese sin éxito.
gramo. Si estamos en el nivel 0, y no tuvimos éxito en colocar A_i, colóquelo como en los pasos 2 b) y 2 c), pero sin recursión. Ahora tenemos 3 - 1 = 2 actividades más para ubicar. Vaya al paso 2) (aquí se utilizan algunos métodos para evitar el ciclismo).
He diseñado algoritmos comerciales para el horario de clases y el horario de examen. Por el primero utilicé la programación entera; Para el segundo, una heurística basada en maximizar una función objetivo al elegir swaps de ranuras, muy similar al proceso manual original que había evolucionado. Las cosas principales para obtener tales soluciones aceptadas son la capacidad de representar todas las limitaciones del mundo real; y para que los horarios humanos no puedan ver formas de mejorar la solución. Al final, la parte algorítmica fue bastante directa y fácil de implementar en comparación con la preparación de las bases de datos, la interfaz de usuario, la capacidad de informar sobre estadísticas como la utilización de la habitación, la educación del usuario, etc.
Este documento describe el problema del horario escolar y su enfoque del algoritmo bastante bien: "El desarrollo del plan de estudios: un programador interactivo basado en restricciones para escuelas y colegios.[PDF
El autor me informa que el software del programa todavía se está utilizando/desarrollando aquí: http://www.scientia.com/uk/
Trabajo en un motor de programación ampliamente utilizado que hace exactamente esto. Sí, es NP-COMPLETO; Los mejores enfoques buscan aproximar una solución óptima. Y, por supuesto, hay muchas formas diferentes de decir cuál es la "mejor" solución: ¿es más importante que sus maestros estén contentos con sus horarios o que los estudiantes ingresen a todas sus clases, por ejemplo?
La pregunta más importante que necesita resolver desde el principio es ¿Qué hace una forma de programar este sistema mejor que otro?? Es decir, si tengo un horario con la Sra. Jones enseñando matemáticas a los 8 y el Sr. Smith enseñando matemáticas a los 9, ¿es mejor o peor que uno con ambos enseñando matemáticas a los 10? ¿Es mejor o peor que uno con la Sra. Jones enseñando a los 8 y al Sr. Jones enseñando a los 2? ¿Por qué?
El consejo principal que daría aquí es dividir el problema tanto como sea posible, tal vez por supuesto, tal vez maestro por maestro, tal vez espacio por habitación, y trabajar primero para resolver el subproblema. Allí debe terminar con múltiples soluciones para elegir, y debe elegir una como la más probable. Luego, el trabajo para hacer que los subproblemas "anteriores" tengan en cuenta las necesidades de los subproblemas posteriores en la puntuación de sus posibles soluciones. Luego, tal vez trabaje en cómo salir de las situaciones pintadas en la esquina (suponiendo que no pueda anticipar esas situaciones en subproblemas anteriores) cuando llega a un estado de "soluciones no válidas".
Un pase de optimización de búsqueda local a menudo se usa para "pulir" la respuesta final para obtener mejores resultados.
Tenga en cuenta que generalmente estamos tratando con sistemas altamente limitados por recursos en la programación escolar. Las escuelas no pasan por el año con muchas habitaciones vacías o maestros sentados en el salón el 75% del día. Los enfoques que funcionan mejor en entornos ricos en soluciones no son necesariamente aplicables en la programación escolar.
En general, la programación de restricciones es un buen enfoque para este tipo de problema de programación. Una búsqueda sobre "programación de restricciones" y programación o "programación basada en restricciones" tanto dentro de Stack Overflow como en Google generará algunas buenas referencias. No es imposible: es un poco difícil pensar cuando se utilizan métodos de optimización tradicionales como la optimización lineal o entera. Una salida sería: ¿existe un horario que satisfaga todos los requisitos? Eso, en sí mismo, es obviamente útil.
Buena suerte !
Puedes tomarlo con algoritmos genéticos, sí. Pero no deberías :). Puede ser demasiado lento y el ajuste de los parámetros puede ser demasiado tiempo de tiempo, etc.
Hay otros enfoques exitosos. Todos implementados en proyectos de código abierto:
- Enfoque basado en restricciones
- Implementado en Unidad (no es realmente para las escuelas)
- También podría ir más allá y usar la programación entera. Hecho con éxito en Universidad de Udine y también en University Bayreuth (estaba involucrado allí) utilizando el software comercial (ILog Cplex)
- Enfoque basado en reglas con Heuristisc - ver Planificador de babeo
- Diferentes heurísticas - Fet y mío
Ver aquí para un Lista de software de horario
Creo que deberías usar algoritmo genético porque:
- Es el más adecuado para grandes instancias problemáticas.
- Produce una complejidad de tiempo reducida en el precio de la respuesta inexacta (no es lo mejor)
- Puede especificar restricciones y preferencias fácilmente ajustando los castigos de aptitud para los no cumplidos.
- Puede especificar el límite de tiempo para la ejecución del programa.
La calidad de la solución depende de cuánto tiempo tenga la intención de pasar resolviendo el programa.
Definición de algoritmos genéticos
También eche un vistazo:Una pregunta similar y otro
No sé que nadie estará de acuerdo con este código, pero desarrollé este código con la ayuda de mi propio algoritmo y está trabajando para mí en Ruby. Espero que les ayude a los que lo están buscando en el siguiente código el PeriodFlag, DayFlag Sujemflag y Maestroflag son el hash con la identificación correspondiente y el valor de la bandera que es booleano. Cualquier problema contácteme ... (-_-)
Periodflag. cada do | K2, V2 |
if(TimetableDefinition.find(k2).period.to_i != 0)
subjectflag.each do |k3,v3|
if (v3 == 0)
if(getflag_period(periodflag,k2))
@teachers=EmployeesSubject.where(subject_name: @subjects.find(k3).name, division_id: division.id).pluck(:employee_id)
@teacherlists=Employee.find(@teachers)
teacherflag=Hash[teacher_flag(@teacherlists,teacherflag,flag).to_a.shuffle]
teacherflag.each do |k4,v4|
if(v4 == 0)
if(getflag_subject(subjectflag,k3))
subjectperiod=TimetableAssign.where("timetable_definition_id = ? AND subject_id = ?",k2,k3)
if subjectperiod.blank?
issubjectpresent=TimetableAssign.where("section_id = ? AND subject_id = ?",section.id,k3)
if issubjectpresent.blank?
isteacherpresent=TimetableAssign.where("section_id = ? AND employee_id = ?",section.id,k4)
if isteacherpresent.blank?
@finaltt=TimetableAssign.new
@finaltt.timetable_struct_id=@timetable_struct.id
@finaltt.employee_id=k4
@finaltt.section_id=section.id
@finaltt.standard_id=standard.id
@finaltt.division_id=division.id
@finaltt.subject_id=k3
@finaltt.timetable_definition_id=k2
@finaltt.timetable_day_id=k1
set_school_id(@finaltt,current_user)
if(@finaltt.save)
setflag_sub(subjectflag,k3,1)
setflag_period(periodflag,k2,1)
setflag_teacher(teacherflag,k4,1)
end
end
else
@subjectdetail=TimetableAssign.find_by_section_id_and_subject_id(@section.id,k3)
@finaltt=TimetableAssign.new
@finaltt.timetable_struct_id=@subjectdetail.timetable_struct_id
@finaltt.employee_id=@subjectdetail.employee_id
@finaltt.section_id=section.id
@finaltt.standard_id=standard.id
@finaltt.division_id=division.id
@finaltt.subject_id=@subjectdetail.subject_id
@finaltt.timetable_definition_id=k2
@finaltt.timetable_day_id=k1
set_school_id(@finaltt,current_user)
if(@finaltt.save)
setflag_sub(subjectflag,k3,1)
setflag_period(periodflag,k2,1)
setflag_teacher(teacherflag,k4,1)
end
end
end
end
end
end
end
end
end
end
end
