¿Qué hace que la programación escolar sea tan difícil? Un recorrido amable por un problema poco amable

Los horarios escolares pertenecen a una familia de problemas que los informáticos clasifican formalmente como muy difíciles. He aquí por qué su subdirector merece más simpatía y, de todos modos, cómo los solucionadores modernos lo descifran

Hay un momento familiar para todos los que han creado un horario escolar a mano. La red está llena en un 90%. Hay semanas de trabajo en juego. Y las últimas clases no van a ser adecuadas, no porque hayas cometido un error, sino porque una colocación que hiciste en la primera hora del primer día, hace semanas, hizo que este callejón sin salida fuera inevitable.

Ese momento no trae mala suerte. Es la naturaleza matemática del problema que se anuncia.

Tomemos un ejemplo deliberadamente pequeño: 10 profesores, 8 grupos de clase, 30 clases de una hora a la semana por grupo, 25 franjas horarias por semana.

Incluso en esta escuela de juguetes, la cantidad de formas de organizar las lecciones se reduce a números con docenas de dígitos. Una escuela secundaria real (50 profesores, 25 grupos, aulas especializadas, contratos a tiempo parcial, bloques de opciones) tiene un espacio de búsqueda que supera con creces la cantidad de átomos del universo observable

planificación de horarios pertenece a la clase de problemas en los que verificar una solución es fácil (comprobar si hay conflictos en una cuadrícula terminada es rápido), pero encontrar una solución puede resultar astronómicamente caro, porque el único método garantizado es, en el peor de los casos, intentar un número impensable de combinaciones. Este es el territorio que los científicos informáticos llaman NP-Hard, y los horarios escolares son un elemento que lleva cartas

La consecuencia práctica: ninguna cantidad de experiencia hace que el enfoque manual sea escalable. La experiencia hace que un planificador humano sea mejor para evitar las trampas obvias, pero las trampas que duelen nunca son las obvias.

Muchas industrias programan las cosas. Lo que hace que las escuelas sean especiales es la densidad de restricciones interrelacionadas

Todo se comparte. El horario de turnos de un hospital limita principalmente un tipo de recurso (personal). El horario de una escuela tiene un límite simultáneo de tres (profesores, aulas y grupos de estudiantes) y cada lección consume uno de cada uno. Al colocar una sola lección, se eliminan las opciones en tres dimensiones a la vez.

Las restricciones duras y blandas coexisten. Algunas reglas son físicas: un profesor no puede estar en dos aulas a la vez. Otras son preferencias: la Sra. Ortiz prefiere enseñar por las mañanas. Un buen horario debe satisfacer a todos los del primer tipo y al mayor número posible del segundo, y esos dos objetivos se pelean constantemente.

La estructura vive dentro de la estructura. Los períodos dobles deben ocupar franjas horarias consecutivas y, a menudo, no deben coincidir con la pausa para comer. Los bloques de opciones requieren que cuatro lecciones diferentes, impartidas por cuatro profesores en cuatro aulas, se impartan simultáneamente para que los estudiantes puedan combinar las opciones de asignaturas. Las sesiones de laboratorio necesitan aulas específicas. Las reuniones de personal necesitan liberar a grupos particulares de personas a la misma hora. Cada una de estas es una restricción sobre los grupos de ubicaciones, que es mucho más difícil que las restricciones sobre las ubicaciones individuales

Los datos son humanos. Contratos a tiempo parcial, profesores compartidos que dividen su semana entre dos escuelas, un entrenador que se marcha temprano los días de partido. Las verdaderas escuelas son un conjunto de excepciones, y un horario que las ignora no es un horario, es una sugerencia

software moderno de programación de horarios no utiliza la fuerza bruta en el universo de las combinaciones y no utiliza magia. Utiliza una familia de técnicas, desde la satisfacción de restricciones hasta la optimización combinatoria, que son realmente hermosas una vez que ves su forma

Propagación: deja que cada ubicación te enseñe algo. Cuando el solucionador coloca una lección, propaga inmediatamente las consecuencias: este profesor está ocupado el martes 2, esta aula está ocupada, este grupo está ocupado. Todas las opciones que acaban de volverse imposibles son eliminadas de la consideración en todos los demás lugares. El espacio de búsqueda se derrumba en órdenes de magnitud con cada paso seguro

Falla rápido, retrocede de forma inteligente. En lugar de descubrir un callejón sin salida después de semanas, como hace un humano, un solucionador detecta en cuestión de milisegundos que una rama de la búsqueda no puede tener éxito (en alguna lección futura ya no le quedan franjas horarias legales) y la abandona al instante. También puede identificar qué decisión anterior causó el callejón sin salida y volver exactamente a ese punto.

Heurística: coloca primero las cosas más difíciles. Los planificadores humanos experimentados lo hacen instintivamente (programa los bloques de opciones y los que trabajan a tiempo parcial con anticipación, llena los sencillos fáciles al final). Los solucionadores lo hacen de manera sistemática, clasificando cada lección no colocada según lo limitada que sea en

Repara y mejora. Conseguir un horario factible es solo la mitad del trabajo. Luego, los solucionadores lo mejoran, cambiando e intercambiando cadenas de lecciones para reducir las brechas entre los maestros, respetar más preferencias y equilibrar la carga, sin romper nunca una restricción estricta. Aquí es donde «válido» se convierte en «bueno».

El resultado, en una herramienta como Arignote Timetable, es que en cuestión de minutos se obtiene un horario completo y libre de conflictos para una escuela real: cada restricción estricta se verifica por una máquina y las más flexibles se optimizan mucho más allá del punto en el que un humano, el día catorce, se habría dado por vencido, comprensiblemente.

Esta es la parte que sorprende a la gente: la automatización hace que el rol humano sea más importante, no menos.

El solucionador es tan bueno como el modelo de la escuela que se le da. Decidir que los períodos dobles no deben abarcar el almuerzo, que el nuevo maestro necesita un primer trimestre tranquilo, que el jueves por la tarde es sagrado para las reuniones del departamento: eso es liderazgo escolar, codificado. El trabajo del software es asegurarse de que, una vez que lo hayas dicho, sea cierto en todas partes, siempre, de una manera que ningún humano que trabaje solo pueda garantizar.

Y cuando recuperas el horario generado, lo revisas como un editor, no como un mecanógrafo: ajusta una ubicación aquí, fija una lección allí (con cada edición verificada en vivo por conflictos) y regenera el resto en función de tus decisiones.

Semanas de trabajo mecánico se convierten en minutos de cómputos más horas de juicio. El juicio siempre fue la parte valiosa.