demo técnica · horarios escolares
El horario del instituto, resuelto con un optimizador gratuito y examinado en público
Cogimos el archivo público con el que la investigación académica lleva más de una década midiéndose en horarios de instituto (XHSTT, mantenido por la Universidad de Twente): 25 institutos reales de 12 países, cada uno con sus normas y con la mejor solución conocida publicada, con autor y fecha. Uno de ellos es un instituto español: 66 profesores, 21 grupos y 225 clases que colocar en 35 franjas semanales.
Cada septiembre, en miles de centros, ese encaje se hace a mano: el jefe de estudios, una plantilla y semanas de ajustar guardias, desdobles y huecos hasta que todo cuadra. Nosotros se lo dimos a CP-SAT, el optimizador de código abierto de Google, gratuito: se le describen las normas del centro y busca el mejor encaje posible. En el instituto español encontró un horario que cumple todas las normas obligatorias en 0,2 segundos, en un portátil.
No hemos encontrado ningún resultado publicado de CP-SAT sobre este archivo, y lo hemos buscado a conciencia: los de esta página son, que nos conste, los primeros públicos de este solver aquí. El examen se mide contra soluciones que equipos especializados han ido afinando durante años, y la tabla de abajo recoge lo que salió: óptimos certificados en varios institutos y una derrota clara en Finlandia.
el examen · 20 minutos por instituto
Mismo presupuesto para todos: 20 minutos y 12 hilos por instituto, en un portátil, una sola pasada. Cada resultado son dos números, infracciones graves / molestias: primero las normas obligatorias incumplidas (un profesor en dos sitios a la vez), después los puntos de molestia (huecos, sesiones mal repartidas). La columna "mejor conocida" es la mejor solución publicada por la investigación para ese instituto, y el gap, a cuántos puntos nos quedamos de ella. Óptimo certificado significa que el optimizador además demostró que no existe solución mejor.
12 institutos examinados: óptimo certificado en 4. En el español, horario válido en 0,2 s.
Cargando la tabla del examen…
"n/d": sin referencia transcrita en el piloto, el gap no se calcula. Los números salen de un JSON público y se actualizan al terminar cada tanda.
El instituto español, de cerca
La instancia ES-SS-08 es una escuela real (los días del fichero vienen en catalán: Dilluns, Dimarts...) con 66 profesores, 21 grupos, 4 pistas y gimnasios compartidos y 225 clases que colocar. Sus normas van de las obligatorias, nadie puede estar en dos sitios a la vez, a las de convivencia: separar las sesiones de una misma asignatura en días no consecutivos, respetar las horas en que cada profesor no está disponible.
La fase difícil, encontrar un horario que cumpla todas las normas obligatorias, costó 0,2 segundos. Los 20 minutos restantes se fueron en limar molestias: el examen terminó en 0/437, cero infracciones y 437 puntos de molestia. La mejor solución publicada, de un equipo danés con programación entera, deja 335, y la cota inferior publicada (el suelo matemático: nadie puede bajar de ahí) es 334. Quedamos a 102 puntos de una solución que ha tenido años de trabajo dedicado detrás.
La lectura práctica no es el gap, es la escala: lo que un centro resuelve en semanas de plantilla, un optimizador gratuito lo deja válido en menos de un segundo y decente en minutos. Y las molestias restantes se negocian con quien conoce el centro, que es como se afina un horario.
La ronda larga: sin límite de 20 minutos
Los 20 minutos son la línea base comparable: el mismo tiempo para todos. La segunda ronda quita ese tope con una regla de parada declarada por adelantado: cada instituto no cerrado al óptimo sigue hasta el óptimo certificado o hasta dos horas sin encontrar mejora, lo que llegue antes. Se publica la trayectoria completa: cada mejora con su minuto, el criterio por el que paró y el tiempo total. La ronda corta se queda como está: las dos tablas conviven.
La ronda larga está en marcha. Cada instituto aparecerá aquí al terminar, con su gráfica: el coste bajando a medida que el optimizador encuentra horarios mejores, dibujada sobre la propia cuadrícula del cuaderno.
La trayectoria registra el objetivo interno del optimizador en cada mejora. El número final de cada instituto es siempre el del evaluador calibrado, y en todo el examen ambos coincidieron.
Cómo se comprueba
- El protocolo se selló antes de ejecutar: modelo, presupuesto de tiempo, máquina y métrica quedaron por escrito antes de lanzar el examen, y los dos titulares posibles, el bueno y el malo, estaban redactados de antemano.
- El juez es un evaluador calibrado: antes de resolver nada, nuestro evaluador de costes tuvo que reproducir exactamente las 46 soluciones con coste publicado de 9 institutos de 8 países, incluido el 335 del caso español. Clavó las 46, y se contrastó además contra KHE, el motor del autor de la especificación XHSTT, compilado aparte: mismos 46 costes.
- Cualquiera puede repetirlo: los datos y las mejores soluciones son públicos en el archivo XHSTT de la Universidad de Twente, que además acepta envíos de soluciones nuevas y los publica con nombre y fecha.
Los límites de este examen
La cobertura es de 12 de los 25 institutos. El modelo cubre los tipos de norma del caso español y sus vecinos; los 13 restantes usan mecanismos aún sin modelar (reparto de carga docente, troceo libre de clases largas, asignación de aulas a gran escala) y quedan declarados fuera, no aproximados a ojo.
Comparamos contra años de investigación dedicada. Las mejores soluciones del archivo vienen de equipos que viven de esto, con días de cómputo y afinado a medida. Que un optimizador de serie iguale varias en 20 minutos es la noticia, no que no las bata todas.
Y el examen es de laboratorio. Un colegio real trae restricciones que no están en ningún archivo público: medias jornadas, profesores compartidos entre centros, preferencias que nadie escribe. El benchmark, el examen estándar público de la especialidad, demuestra el motor; el traje se corta con las normas de cada centro.
Los 13 institutos fuera de cobertura, con su motivo
Datos: archivo XHSTT-2014 (Universidad de Twente, Gerhard Post y colaboradores), sin afiliación. Resultados de esta página: JSON público, generado desde los registros del examen.
¿Y en tu empresa?
Lo del horario no va de institutos: va de encajar recursos escasos bajo normas que se pisan entre sí. Turnos de enfermería, cuadrantes de tienda, aulas y exámenes de una universidad, la planificación semanal de una fábrica. El mismo motor, con tus normas.
Si tienes un cuadrante que se hace a mano cada mes y nadie se atreve a tocar, escríbenos. Un primer trabajo corto lo dice pronto y con criterio de aceptación medible, como el de esta página. Sin rollo: te decimos si se puede o no.