secundaria programacion programa personalizado para horarios horario hacer gratis generar escolares creativo crea como clases algoritmo algorithm language-agnostic np

algorithm - programacion - programa para hacer horarios de clases gratis



Algoritmo para crear un horario escolar (16)

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

Me gustaría ir con Prolog ... luego usar Ruby o Perl o algo para limpiar tu 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 usando el mismo camino que acabo de mencionar. Prolog (como lenguaje funcional) realmente facilita la resolución de problemas NP-Hard.

Me he estado preguntando si hay soluciones conocidas para el algoritmo de crear un horario escolar. Básicamente, se trata de optimizar la "dispersión de horas" (tanto en el caso de profesores como de clases) para asociaciones de clase-asignatura-docente. Podemos suponer que tenemos conjuntos de clases, asignaturas y profesores asociados entre sí en la entrada y que el horario debe caber entre las 8 AM y las 4 PM.

Supongo que probablemente no haya un algoritmo preciso para eso, pero tal vez alguien conozca una buena aproximación o pistas para desarrollarla.

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

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

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 del desbordamiento de la pila como en Google generará algunas buenas referencias. No es imposible, es un poco difícil pensar cuando se usan métodos de optimización tradicionales como optimización lineal o entera. Una salida sería: ¿existe un cronograma que satisfaga todos los requisitos? Eso, en sí mismo, es obviamente útil.

Buena suerte !

Es un desastre. un lío real. Para agregar 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 precocido. Ejemplos:

  • un maestro enseña tanto en tu escuela como en otro instituto. Claramente, si finaliza la lección allí a las 10.30, no puede comenzar en sus instalaciones a las 10.30, porque necesita tiempo para viajar entre los institutos.
  • dos profesores están casados En general, se considera una buena práctica no tener dos maestros casados ​​en la misma clase. Estos dos profesores deben tener dos clases diferentes
  • dos maestros están casados, y su hijo asiste a la misma escuela. Nuevamente, debe evitar que los dos maestros enseñen en la clase específica donde se encuentra su hijo.
  • la escuela tiene instalaciones separadas, como que un día la clase está en un instituto, y otro día la clase está en otro.
  • la escuela tiene laboratorios compartidos, pero estos laboratorios están disponibles solo en ciertos días de la semana (por razones de seguridad, por ejemplo, donde se requiere personal adicional).
  • algunos maestros tienen preferencias para el día libre: algunos prefieren el lunes, algunos el viernes y algunos el miércoles. Algunos prefieren venir temprano en la mañana, algunos prefieren venir más tarde.
  • no debería haber situaciones en las que tenga una lección de, por ejemplo, historia en la primera hora, luego tres horas de matemática, y luego otra hora de historia. No tiene sentido para los estudiantes, ni para el maestro.
  • deberías difundir los argumentos de manera uniforme. No tiene sentido tener los primeros días de la semana solo en matemáticas, y luego el resto de la semana solo literatura.
  • debe darles a los maestros dos horas consecutivas para que realicen los exámenes de evaluación.

Como puede ver, el problema no es NP-completo, es NP-insano.

Entonces, lo que hacen es que tienen una gran mesa con pequeños insertos de plástico, y mueven las inserciones hasta obtener un resultado satisfactorio. Nunca comienzan de cero: normalmente comienzan a partir del calendario del año anterior y hacen ajustes.

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 debes mirar todas las combinaciones posibles.

Pero "mira" no te dice mucho lo que tienes que 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 el de juzgar si una posible combinación dada es buena, mala o mejor que la solución anterior "buena".

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

Por ejemplo, ¿el mismo docente 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 solución mejor que alternar entre dos personas para que cada maestro haga una semana cada una. Oh, ¿no pensaste en eso? Recuerde, esta es la gente con la que está lidiando, no solo un problema de asignación de recursos.

Incluso si un maestro puede 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 intentas alternar entre profesores, y este tipo de equilibrio es muy difícil de incorporar al software.

En resumen, producir una buena solución a este problema valdrá mucho para muchas personas. Por lo tanto, no es un problema fácil de analizar y resolver. Prepárese para replantear algunas metas que no son 100% y llamarlas "lo suficientemente buenas".

He diseñado algoritmos comerciales para el horario de clase y el horario de examen. Para la primera vez que utilicé la programación entera; para el segundo, una heurística basada en maximizar una función objetiva eligiendo rangos de intercambio, muy similar al proceso manual original que se había desarrollado. Lo principal para lograr que se acepten tales soluciones es la capacidad de representar todas las limitaciones del mundo real; y para que los programadores humanos no puedan ver formas de mejorar la solución. 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.

La Competencia Internacional de Calendario de 2007 tuvo una pista de programación de lecciones y una pista de programación de exámenes. Muchos investigadores participaron en esa competencia. Se probaron muchas heurísticas y metaheurísticas, pero al final las metaheurísticas de búsqueda local (como Tabu Search y Simulated Annealing) superaron claramente a otros algoritmos (como los algoritmos genéticos).

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

Mi algoritmo de establecimiento de horarios, implementado en FET (Free Timetabling Software, 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 (el intervalo de tiempo de cada actividad. Las salas se excluyen aquí, por simplicidad). El algoritmo debe colocar 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) 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 profesor o los mismos estudiantes);

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

El algoritmo de creación de horarios (que denominé "intercambio recursivo"):

  1. Clasificar actividades, lo más difícil primero. No es un paso crítico, pero acelera el algoritmo quizás 10 veces o más.

  2. Intente colocar cada actividad (A_i) en un intervalo de tiempo permitido, siguiendo el orden anterior, de a una por vez. Busque una ranura disponible (T_j) para A_i, en la que esta actividad se puede realizar respetando las restricciones. Si hay más espacios disponibles, elija uno aleatorio. Si no hay ninguno disponible, realice un 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 concuerdan con este movimiento (por ejemplo, la actividad A_k está en el mismo espacio T_j y tiene el mismo profesor o los mismos estudiantes que A_i). Mantenga una lista de actividades en conflicto para cada intervalo de tiempo T_j.

    b . Elija una ranura (T_j) con el menor número de actividades conflictivas. Supongamos que la lista de actividades en este espacio 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 intente 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).

    e . Si se coloca con éxito A_p, A_q, A_r, regresa con éxito, de lo contrario prueba con otros intervalos de tiempo (ve al paso 2 b) y elige el siguiente mejor intervalo de tiempo).

    f . Si todos (o un número razonable de) intervalos de tiempo fueron probados sin éxito, regresen sin éxito.

    g . 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 recurrencia. Ahora tenemos 3 - 1 = 2 actividades más para colocar. Vaya al paso 2) (algunos métodos para evitar el ciclismo se usan aquí).

No sé si alguien estará de acuerdo con este código, pero desarrollé este código con la ayuda de mi propio algoritmo y me está funcionando en ruby. Espero que les ayude a los que lo buscan en el siguiente código the periodflag, dayflag subjectflag y teacherflag son el hash con el id correspondiente y el valor del indicador que es booleano. Cualquier problema contáctame ....... (-_-)

periodflag.each 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

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

Hay otros enfoques exitosos. Todo implementado en proyectos de código abierto:

  • Enfoque basado en restricciones
    • Implementado en Unitime (no realmente para escuelas)
    • También puede ir más allá y usar la programación entera. Hecho con éxito en la universidad de Udine y también en la Universidad Bayreuth (participé allí) utilizando el software comercial (ILOG CPLEX)
    • Enfoque basado en reglas con heuristisc - Ver el planificador Drools
  • Heurística diferente - FET y mi propio

Vea aquí para obtener una lista de software de horarios

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 maneras diferentes de decir cuál es la "mejor" solución: ¿es más importante que tus profesores estén contentos con sus horarios o que los alumnos participen en todas sus clases, por ejemplo?

La pregunta más importante que necesita resolver desde el principio es ¿qué hace que una forma de programar este sistema sea mejor que otra ? 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 el Sr. Jones enseñando a los 2? ¿Por qué?

El principal consejo que daría aquí es dividir el problema tanto como sea posible - tal vez curso por curso, tal vez maestro por maestro, tal vez cuarto por cuarto - 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 óptima posible. Luego, trabaje en hacer que los sub-problemas "anteriores" tomen en cuenta las necesidades de sub-problemas posteriores para calificar sus posibles soluciones. Luego, tal vez trabaje en cómo salirse de situaciones pintadas en la esquina (suponiendo que no puede anticipar esas situaciones en sub-problemas anteriores) cuando llega a un estado de "soluciones no válidas".

Un pase de optimización de búsqueda local a menudo se utiliza para "pulir" la respuesta final para obtener mejores resultados.

Tenga en cuenta que, por lo general, estamos lidiando con sistemas de alta restricción de recursos en la programación escolar. Las escuelas no pasan el año con muchas salas 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.

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

Toda la mesa es un "organismo". Hubo algunos cambios y advertencias sobre el enfoque de los algoritmos genéticos genéricos:

  • Las reglas fueron hechas para "mesas ilegales": dos clases en el mismo salón de clases, un maestro enseñando dos grupos al mismo tiempo, etc. Estas mutaciones fueron consideradas letales inmediatamente y un nuevo "organismo" brotó en lugar del "fallecido" inmediatamente. 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" fueron mucho más comunes que las mutaciones de "modificación". Los cambios solo se daban entre las partes del gen que tenían sentido, no 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, por mantener las horas de trabajo del maestro y la carga continua de la clase. Se asignaron bonificaciones moderadas para dar aulas correctas para asignaturas determinadas, manteniendo las horas de clase dentro de los bonos (mañana o tarde), y demás. Grandes bonos fueron para asignar el número correcto de asignatura dada, la carga de trabajo dada para un profesor, etc.

  • Los docentes podrían crear sus cronogramas de carga de trabajo de "quiero trabajar en ese momento", "está bien para trabajar en ese momento", "no me gusta trabajar en ese momento", "no puedo trabajar en ese momento", con los pesos adecuados asignados. Las 24 horas enteras eran horas de trabajo legal, excepto que la noche era muy poco deseada.

  • La función de peso ... oh sí. La función de peso era enorme, producto monstruoso (como en la multiplicación) de los pesos asignados a las características y propiedades seleccionadas. Era extremadamente empinada, una propiedad podía cambiarla fácilmente en un orden de magnitud hacia arriba o hacia abajo, y había cientos o miles de propiedades en un organismo. Esto dio lugar a números absolutamente ENORMES como los pesos, y como resultado directo, necesidad de utilizar una biblioteca del bignum (gmp) para realizar los cálculos. Para una pequeña caja de prueba de unos 10 grupos, 10 maestros y 10 aulas, el conjunto inicial comenzó con una nota de 10 ^ -200 de algo y terminó con 10 ^ + 300 de algo. Fue totalmente ineficiente cuando era más plano. Además, los valores crecieron una distancia mucho más amplia con las "escuelas" más grandes.

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

  • El cálculo (en una CPU de 1 GHz) tardaría aproximadamente 1 h 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 intercambie las mejores muestras entre las computadoras que ejecutan el cálculo.

El programa resultante nunca vio la luz del día y obtuvo una buena calificación para el semestre. Me pareció algo prometedor, pero nunca tuve la motivación suficiente para agregar cualquier GUI y hacerla utilizable para el público en general.

Este problema es NP-Completo !
En pocas palabras, uno necesita explorar todas las combinaciones posibles para encontrar la lista de soluciones aceptables. Debido a las variaciones en las circunstancias en las que aparece el problema en varias escuelas (por ejemplo: ¿Existen limitaciones con respecto a las aulas? ¿Algunas de las clases se dividen en subgrupos alguna vez? ¿Es un horario semanal? etc.) no existe una clase de problema bien conocida que corresponda a todos los problemas de programación. Tal vez, el problema de Knapsack tiene muchos elementos de similitud con estos problemas en general.

Una confirmación de que este es un problema difícil y al que la gente siempre busca una solución, es verificar esta (larga) lista de herramientas de programación de software (principalmente comerciales)

Debido a la gran cantidad de variables involucradas, la mayor fuente de las cuales son, típicamente, los deseos de los miembros de la facultad; -) ..., no es práctico considerar enumerar todas las combinaciones posibles . En cambio, debemos elegir un enfoque que visite un subconjunto de los espacios problema / solución.
- Algoritmos genéticos , citados 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 los candidatos que se mantendrá para la próxima generación)
- Los enfoques de reescritura de gráficos también son útiles con este tipo de problemas de optimización combinatoria.

En lugar de centrarme en implementaciones particulares de un programa generador de cronograma automático, me gustaría sugerir algunas estrategias que pueden aplicarse, al nivel de la definición del problema .
El fundamento 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, expresas e implícitas: se satisfarán por completo. Por lo tanto, nos ayudamos a nosotros mismos por:

  • Definir y clasificar todas las restricciones conocidas
  • Reducir el espacio problema, de forma manual, proporcionando un conjunto de restricciones adicionales .
    Esto puede parecer contra-intuitivo, pero por ejemplo al proporcionar un cronograma inicial parcialmente lleno (digamos aproximadamente el 30% de los intervalos de tiempo), de una manera que satisface completamente todas las restricciones, y al considerar este cronograma parcial inmutable, reducimos significativamente la tiempo / espacio necesario para producir soluciones candidatas.
    Otra forma en que las limitaciones adicionales ayudan es, por ejemplo, agregar "artificialmente" una restricción que impide enseñar algunos temas algunos días de la semana (si se trata de un programa semanal ...); este tipo de restricciones resulta en la reducción de los espacios problema / solución, sin, típicamente, excluir un número significativo de buenos candidatos.
  • Asegurando que algunas de las restricciones del problema puedan ser rápidamente calculadas. Esto a menudo se asocia con la elección del modelo de datos utilizado para representar el problema; la idea es poder optar (o eliminar) rápidamente 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 algunas de las limitaciones para completar los últimos espacios en el cronograma, o hacer que el programa generador de cronogramas automático deje de completar todo el cronograma, en lugar de proporcionarnos una lista de una docena más o menos plausible. candidatos. A menudo, un humano está en una mejor posición para completar el rompecabezas, tal como se indica, posiblemente rompiendo algunas de las restricciones, utilizando información que no suele compartirse con la lógica automatizada (por ejemplo, la regla "No matemáticas en la tarde" puede romperse en ocasiones para la clase de "matemáticas avanzadas y física", o "Es mejor romper uno de los requisitos de Mr Jones que uno de la Sra. Smith ... ;-))

Al corregir esta respuesta, me doy cuenta de que es bastante tímido dar una respuesta definitiva, pero no obstante está llena de sugerencias prácticas. Espero que esta ayuda, con lo que es, después de todo, un "problema difícil".