Algoritmo para crear un horario escolar

Es un desastre. un desastre real. Para añadir a las respuestas, ya muy completas, quiero señalar mi experiencia familiar. Mi madre era maestra y solía participar en el proceso.

Resulta que tener una computadora para hacerlo no solo es difícil de codificar per-se, también es difícil porque hay condiciones que son difíciles de especificar para un programa de computadora pre-horneado. Ejemplos:

• un maestro enseña tanto en su escuela como en otro instituto. Claramente, si él termina la lección allí a las 10.30, no puede comenzar en sus instalaciones a las 10.30, porque necesita algo de tiempo para viajar entre los institutos.
• dos maestros están casados. En general, se considera una buena práctica no tener dos profesores casados en la misma clase. Por lo tanto, estos dos profesores deben tener dos clases diferentes
• dos maestros están casados, y su hijo asiste a la misma escuela. Una vez más, usted tiene que evitar que los dos maestros para enseñar en la clase específica donde su hijo ser.
• 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 tiene laboratorios compartidos, pero estos laboratorios solo están disponibles en ciertos días laborables (por razones de seguridad, por ejemplo, cuando se requiere personal adicional).
• algunos profesores tienen preferencias para el día libre: algunos prefieren el lunes, otros el viernes, otros el miércoles. Algunos prefieren venir temprano en la mañana, algunos prefieren venir tarde.
• no deberías tener situaciones en las que tengas una lección de, digamos, historia a la primera hora, luego tres horas de matemáticas, luego otra hora de historia. No tiene sentido para los estudiantes, ni para el profesor.
• debe distribuir los argumentos de manera uniforme. No tiene sentido tener los primeros días de la semana solo matemáticas, y luego el resto de la semana solo literatura.
• debe dar a algunos maestros dos horas consecutivas para hacer las pruebas de evaluación.

As pueden ver, el problema no es NP-completo, es NP-loco.

Así que lo que hacen es que tienen una mesa grande con pequeñas inserciones de plástico, y mueven las inserciones alrededor hasta que se obtiene un resultado satisfactorio. Nunca comienzan desde cero: normalmente comienzan a partir del calendario del año anterior y hacen ajustes.

El Concurso Internacional de Horarios 2007 tenía una pista de programación de lecciones y una pista de programación de exámenes. Muchos investigadores participaron en ese concurso. Se probaron muchas heurísticas y metaheurísticas, pero al final las metaheurísticas de búsqueda local (como la Búsqueda Tabu y el Recocido Simulado) claramente vencieron a otros algoritmos (como los algoritmos genéticos).

Eche un vistazo a los 2 frameworks de código abierto utilizados por algunos de los finalistas:

• JBoss OptaPlanner (Java, open source)
• Unitime (Java, open source) - más para universidades

Una de mis asignaciones de medio término fue una generación de tablas escolares con algoritmos genéticos.

Toda la tabla es un "organismo". Hubo algunos cambios y advertencias al enfoque de algoritmos genéticos genéricos:

• Se establecieron reglas para las "mesas ilegales": dos clases en el mismo aula, un maestro enseñando a dos grupos al mismo tiempo, etc. Estas mutaciones fueron consideradas letales inmediatamente y un nuevo" organismo "brotó en lugar del" fallecido " inmediatamente. La inicial fue generado por una serie de intentos aleatorios para obtener uno legal (si no tiene sentido). La mutación letal no se contó para el recuento de mutaciones en iteración.

• "Las mutaciones de intercambio eran mucho más comunes que las mutaciones de Modificación. Los cambios eran solo entre partes del gen que tenían sentido, sin sustituir a un maestro por un aula.

• Se asignaron pequeñas bonificaciones por agrupar ciertas 2 horas juntas, por asignar el mismo aula genérica en secuencia para el mismo grupo, para mantener las horas de trabajo del profesor y la carga de clase continua. Se asignaron bonificaciones moderadas por dar aulas correctas para una asignatura determinada, mantener las horas de clase dentro de los bonos (por la mañana o por la tarde), y cosas así. Las primas grandes eran para asignar el número correcto de materia dada, carga de trabajo dada para un profesor etc.

• Los maestros podrían crear sus horarios de carga de trabajo de "quiere trabajar entonces", "está bien para trabajar entonces", "no le gusta trabajar entonces", "no puede trabajar entonces", con los pesos apropiados asignados. Las 24 horas eran horas de trabajo legales, excepto que la noche era muy indeseada.

• 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 empinada, una propiedad fácilmente capaz de cambiarla por un orden de magnitud hacia arriba o hacia abajo - y había cientos o miles de propiedades en un organismo. Esto resultó en números absolutamente enormes como los pesos, y como resultado directo, necesidad de utilizar una biblioteca bignum (gmp) para realizar los cálculos. Para un pequeño caso de prueba de unos 10 grupos, 10 profesores y 10 aulas, el conjunto inicial comenzó con una nota de 10^-200something y terminó con 10^+300something. Era totalmente ineficiente cuando era más plano. Además, los valores crecieron mucho más lejos con "escuelas" más grandes.

• En cuanto al tiempo de cálculo, había poca diferencia entre una población pequeña (100) durante mucho tiempo y una población grande (10k+) durante menos generaciones. El cálculo durante el mismo tiempo produjo aproximadamente la misma calidad.

• El cálculo (en una CPU de 1GHz) tardaría 1h en estabilizarse cerca de 10^+300, generando programas 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 fuera de hacerme una buena calificación para el semestre. Mostró algo de promesa, pero nunca tuve la motivación suficiente para agregar cualquier 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 NP-completo, 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 necesitas hacer.

Generar todas las combinaciones posibles es fácil. Podría 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 el de juzgar si una combinación posible dada es buena, mala o mejor que la solución "buena" anterior.

Para esto necesita algo más que "¿es una posible solución?".

Por ejemplo, ¿el mismo maestro trabaja 5 días a la semana durante X semanas seguidas? Incluso si esa es una solución de trabajo, podría no ser una mejor solución que alternar entre dos personas para que cada maestro haga una semana cada uno. ¿No pensaste en eso? Recuerde, se trata de personas con las que está tratando, no solo un problema de asignación de recursos.

Incluso si un profesor 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 se intenta alternar entre profesores, y este tipo de equilibrio es muy difícil de incorporar en el software.

Para resumir, producir una buena solución a este problema valdrá mucho, para muchas muchas personas. Por lo tanto, no es un problema fácil de descomponer y resolver. Ser preparado para plantear algunas metas que no son 100% y llamarlas "lo suficientemente buenas".

ACTUALIZACIÓN: de los comentarios ... debería tener heurística también!

Yo 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 (todavía) en el proceso de hacer algo similar a este problema, pero utilizando el mismo camino que acabo de mencionar. Prolog (como lenguaje funcional) realmente facilita la resolución de problemas NP-Hard.

Los algoritmos genéticos se utilizan a menudo para dicha programación.

Encontrado este ejemplo (Hacer 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

Un Algoritmo Genético Híbrido para la Programación Escolar

Utilidades y herramientas de programación

Mi algoritmo de programación, implementado en FET (Free Timetabling Software, http://lalescu.ro/liviu/fet / , una solicitud aceptada):

El algoritmo es heurístico. Lo llamé "intercambio recursivo".

Input: un conjunto de actividades A_1...A_n y las restricciones.

Salida: un conjunto de veces TA_1...TA_n (la franja horaria de cada actividad. Las habitaciones están excluidas aquí, por simplicidad). El algoritmo debe poner cada actividad en un intervalo de tiempo, respetando las restricciones. Cada TA_i está entre 0 (T_1) y max_time_slots-1 (T_m).

Restricciones:

C1) Basic: una lista de pares de actividades que no pueden ser simultáneas (por ejemplo, A_1 y A_2, porque tienen el mismo profesor o los mismos estudiantes);

C2) Muchas otras restricciones (excluidas aquí, por simplicidad).

El algoritmo de programación de horarios (al que llamé "intercambio recursivo"):

1. Ordena las actividades, primero las más difíciles. No paso crítico, pero acelera el algoritmo tal vez 10 veces o más.

2. Intente colocar cada actividad (A_i) en un intervalo de tiempo permitido, siguiendo el orden anterior, uno a la vez. Busque un espacio disponible (T_j) para A_i, en el que esta actividad se puede colocar respetando las restricciones. Si hay más ranuras disponibles, elija una al azar. Si no hay ninguno disponible, haga intercambio recursivo:

   A. Para cada intervalo de tiempo T_j, considere lo que sucede si coloca 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 profesor o los mismos estudiantes que A_i). Mantenga una lista de actividades conflictivas para cada franja horaria 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 sin asignar.

   D . Recursivamente tratar de 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 que comenzó el paso 2) en A_i no es demasiado grande, digamos 2*n), como en el paso 2).

   E . Si se coloca con éxito A_p, A_q, A_r, regrese con éxito, de lo contrario intente con otros intervalos de tiempo (vaya al paso 2 b) y elija el siguiente mejor intervalo de tiempo).

   F . Si todas las franjas horarias (o un número razonable de ellas) se intentaron sin éxito, vuelva sin éxito.

   G . Si somos 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 colocar. Vaya al paso 2) (algunos métodos para evitar el ciclismo se utilizan aquí).

He diseñado algoritmos comerciales tanto para la programación de clases como para la programación de exámenes. Para el primero utilicé programación entera; para el segundo una heurística basada en maximizar una función objetiva eligiendo swaps de ranura, muy similar al proceso manual original que había sido desarrollado. Lo principal para conseguir que se acepten estas soluciones es la capacidad de representar todas las restricciones del mundo real; y que los cronometradores humanos no sean capaces de ver formas de mejorar la solución. En al final, la parte algorítmica fue bastante sencilla 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 sala, la educación del usuario, etc.

Este documento describe el problema del horario escolar y su enfoque del algoritmo bastante bien: "El Desarrollo de SYLLABUS-Un Programador Interactivo, Basado en Restricciones para Escuelas y Universidades."[PDF]

El autor me informa que el software del PLAN de ESTUDIOS 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 aproximarse a una solución óptima. Y, por supuesto, hay muchas maneras 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 absoluta más importante que debe resolver desde el principio es lo que hace que 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 las 8 y el Sr. Jones enseñando a las 2? ¿Por qué?

El consejo principal que daría aquí es dividir el problema tanto como sea posible-tal vez curso por curso, tal vez maestro por maestro, tal vez habitación por habitación - y trabajar en resolver el sub-problema primero. Allí debe terminar con múltiples soluciones para elegir, y debe elegir una como la más probable óptima. Luego, trabaje en hacer que los subproblemas "anteriores" tengan en cuenta las necesidades de los subproblemas posteriores para calificar sus posibles soluciones. Entonces, tal vez trabajar en cómo salir de situaciones pintadas en la esquina (suponiendo que no se puede anticipar esas situaciones en sub-problemas anteriores) cuando se llega a un estado de "no soluciones válidas".

A local-search optimization pass se utiliza a menudo para" pulir " la respuesta final para obtener mejores resultados.

Tenga en cuenta que normalmente estamos tratando con sistemas muy limitados de recursos en la programación escolar. Las escuelas no pasan 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.

Generalmente, la programación con restricciones es un buen enfoque para este tipo de problema de programación. Una búsqueda en " 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 solo un poco difícil de pensar cuando se utilizan métodos de optimización tradicionales como la optimización lineal o entera. Una salida sería - ¿existe un programa que satisfaga todos los requisitos? Que, en sí mismo, es obviamente útil.

¡Buena suerte !

Se puede tomar con algoritmos genéticos, sí. Pero no deberías:). Puede ser demasiado lento y el ajuste de parámetros puede consumir demasiado tiempo, etc.

Existen otros enfoques exitosos. Todos implementados en proyectos de código abierto:

• Enfoque basado en restricciones
  • Implementado en UniTime (no realmente para las escuelas)
  • También podría ir más allá y usar la programación de enteros. Realizado con éxito en universidad de Udine y también en la Universidad de Bayreuth (Estuve involucrado allí) usando el software comercial (ILOG CPLEX)
  • Enfoque basado en reglas con heuristisc-Ver Drools planner
• Diferentes heurísticas - FET y mi propio

Vea aquí una lista de programas de programación

Creo que deberías usar el algoritmo genético porque:

• Es el más adecuado para grandes instancias de problemas.
• Produce una complejidad de tiempo reducida en el precio de la respuesta inexacta (No la mejor)
• Puede especificar restricciones y preferencias fácilmente ajustando los castigos de aptitud física para los que no se cumplen.
• Puede especificar el límite de tiempo para la ejecución del programa.

• La calidad de la solución depende de cuánto tiempo tiene la intención de pasar resolviendo el programa..

  Definición de Algoritmos genéticos

  Tutorial de Algoritmos genéticos

  Proyecto de programación de clases con GA

También echa un vistazo a: una pregunta similar y otra

No creo que nadie esté de acuerdo con este código, pero he desarrollado 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, periodflag, dayflag subjectflag y teacherflag son el hash con el id correspondiente y el valor de flag que es booleano. Cualquier problema en contacto conmigo.......(-_-)

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
                                                @[email protected]_struct_id
                                                @[email protected]_id
                                                @finaltt.section_id=section.id
                                                @finaltt.standard_id=standard.id
                                                @finaltt.division_id=division.id
                                                @[email protected]_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