Què fa que la programació escolar sigui tan difícil? Un recorregut suau per un problema poc suau

L'horari escolar pertany a una família de problemes que els informàtics classifiquen formalment com a molt durs. Heus aquí per què el seu cap adjunt mereix més simpatia —i com els solvers moderns ho esquerden de totes maneres

Hi ha un moment familiar per a tothom que alguna vegada ha construït un horari escolar a mà. La xarxa està plena al 90%. Queden setmanes de treball a la junta. I les últimes lliçons no encaixaran —no perquè hagis comès un error, sinó perquè una col·locació que vas fer a primera hora del primer dia, setmanes enrere, feia tranquil·lament inevitable aquest carreró sense sortida.

Aquest moment no és mala sort. És la naturalesa matemàtica del problema que s'anuncia a si mateix.

Preneu un exemple deliberadament minúscul: 10 professors, 8 grups classe, 30 lliçons d'una hora a la setmana per grup, 25 franges horàries docents a la setmana.

Fins i tot en aquesta escola de joguines, el nombre de maneres d'organitzar les lliçons es topa amb números amb desenes de dígits. Una escola secundària real —50 professors, 25 grups, aules especialitzades, contractes a temps parcial, blocs d'opcions— té un espai de cerca que supera còmodament el nombre d'àtoms de l'univers observable

Timeting pertany a la classe de problemes on veri ficar una solució és fàcil (comprovar una quadrícula acabada per als xocs és ràpid) però trobar -ne una pot resultar astronòmicament car, perquè l'únic mètode garantit és, en el pitjor dels casos, provar un nombre impensable de combinacions. Aquest és el territori informàtics anomenen NP-dur, i l'horari escolar és un membre portador de targetes

La conseqüència pràctica: cap quantitat d'experiència fa que l'enfocament manual s' escala. L'experiència fa que un planificador humà sigui millor per evitar trampes òbvies, però les trampes que fan mal mai són les òbvies.

Moltes indústries programen coses. El que fa especials les escoles és la densitat de restriccions d'enclavament

Tot comparteix. Un horari de torns hospitalaris restringeix majoritàriament un tipus de recurs (personal). Un horari escolar restringeix simultàniament tres —professors, aules i grups d'estudiants— i cada lliçó consumeix un de cadascun. La col·locació d'una sola lliçó elimina les opcions en tres dimensions alhora.

Algunes regles són de física: un professor no pot estar en dues aules alhora. Altres són preferències: la senyora Ortiz preferiria ensenyar matins. Un bon horari ha de satisfer tots els de primera mena i tants com sigui possible del segon —i aquells dos gols es barallen constantment.

L'estructura viu dins l'estructura. Els períodes dobles han d'ocupar franges horàries consecutives —i, sovint, no han d'enfilar la pausa per dinar. Els blocs d'opcions requereixen quatre lliçons diferents, impartides per quatre professors en quatre aules, per executar simultàniament perquè els estudiants puguin barrejar opcions de temes. Les sessions de laboratori necessiten aules específiques. Les reunions de personal necessiten conjunts particulars de persones alliberar a la mateixa hora. Cadascun d'aquests és una restricció sobre grups de col·locacions, que és molt més difícil que les restriccions sobre els únics.

Les dades són humanes. Contractes a temps parcial, professors compartits que es reparteixen la setmana entre dues escoles, un entrenador que surt ben d'hora els dies de partit. Les escoles reals són feixos d'excepcions, i un horari que les ignora no és un horari, és un suggeriment

programari modern d'horaris no obliga brutament l'univers de combinacions, i no utilitza màgia. Utilitza una família de tècniques des de la satisfacció de constrenyiment i l'optimització combinatòria que són genuïnament belles una vegada que es veu la forma d'ells:

Propagació: deixeu que cada col·locació us ensenyi alguna cosa. Quan el solucionador col·loca una lliçó, en propaga immediatament les conseqüències — aquest professor ara està ocupat dimarts-període-2, aquesta aula és presa, aquest grup està ocupat. Tota opció que acaba d'esdevenir impossible s' elimina de la consideració a tot arreu. L'espai de cerca es col·lapsa per ordres de magnitud amb cada pas confiat

Falla ràpid, retrocés intel·ligent. En lloc de descobrir un carreró sense sortida després de setmanes com fa un humà, un solucionador detecta en qüestió de mil·lisegons que una branca de la recerca no pot tenir èxit —alguna lliçó futura ja li queden zero franges horàries legals— i l'abandona a l'instant. També pot identificar quina decisió anterior va causar el carreró sense sortida i saltar de nou a exactament allà.

Heurística: col·loca primer les coses més difícils. Planificadors humans experimentats ho fan instintivament (programar els blocs d'opcions i els temps parcial abans d'hora, omplir els senzills fàcils darrera). Els solucionadors ho fan de manera sistemàtica, classificant cada lliçó no col·locada per la restricció que està a

Reparar i millorar. Acon seguir un horari factible és només la meitat de la feina. A continuació, els solucionadors la milloren —canviant i intercanviant cadenes de lliçons per reduir les llacunes dels professors, honorar més preferències i equilibrar la càrrega— mentre no trenquen mai una restricció dura. Aquí és on el “vàlid” es converteix en “bo”.

El resultat, en una eina com Arignote Timetable, és que un horari complet, alliberar de conflictes per a una escola real emergeix en qüestió de minuts - amb cada restricció dura màquina verificada, i els suaus optimitzats molt passat el punt en què un humà, el dia catorzè, hauria entès comprensiblement per vençut.

Heus aquí la part que sorprèn a la gent: l'automatització fa que el paper humà sigui més important, no menys.

El solucionador només és tan bo com el model de l'escola que es dóna. Decidir que els períodes dobles no haurien de fer el dinar, que el nou professor necessita un primer mandat suau, que dijous a la tarda és sagrat per a les reunions del departament — això és el lideratge escolar, codificat. La feina del programari és assegurar-se que un cop ho has dit, és cert a tot arreu, sempre, d'una manera que cap humà que treballa sol pot garantir.

I quan el horari generat torna, ho revises com un editor, no un tipògraf: ajusteu una col·locació aquí, hi fixeu una lliçó —amb cada conflicte d'edició comprovat en directe— i regenereu la resta al voltant de les vostres decisions.

Les setmanes de treball mecànic es converteixen en minuts de còmput més hores de judici. La sentència sempre va ser la part valuosa.