Cosa rende così difficile la pianificazione scolastica? Una panoramica delicata di un problema poco delicato

L'orario scolastico appartiene a una famiglia di problemi che gli informatici classificano formalmente come molto difficili. Ecco perché il tuo vice capo merita più simpatia e comunque come i risolutori moderni lo risolvono.

C'è un momento familiare a chiunque abbia mai costruito a mano un orario scolastico. La griglia è piena al 90%. Settimane di lavoro sono previste. E le ultime lezioni non ti andranno bene, non perché hai commesso un errore, ma perché un piazzamento che hai fatto nella prima ora del primo giorno, settimane fa, ha reso silenziosamente inevitabile questo vicolo cieco

Quel momento non porta sfortuna. È la natura matematica del problema che si annuncia

Prendiamo un esempio volutamente piccolo: 10 insegnanti, 8 gruppi di classe, 30 lezioni di un'ora a settimana per gruppo, 25 fasce orarie di insegnamento a settimana.

Anche in questa scuola di giocattoli, il numero di modi per organizzare le lezioni è numerato da decine di cifre. Una vera scuola secondaria (50 insegnanti, 25 gruppi, aule specializzate, contratti part-time, blocchi di opzioni) ha uno spazio di ricerca che supera di gran lunga il numero di atomi nell'

La tempistica appartiene alla classe di problemi per cui verificare una soluzione è facile (controllare la presenza di interferenze su una griglia finita è veloce) ma trovarne una può essere incredibilmente costoso, perché l'unico metodo garantito è, nel peggiore dei casi, provare un numero impensabile di combinazioni. Questo è il territorio che gli informatici chiamano NP-Hard e l'orario scolastico è un membro titolare della tessera

La conseguenza pratica: nessuna esperienza rende scalabile l'approccio manuale. L'esperienza rende un pianificatore umano più bravo a evitare trappole evidenti, ma le trappole che fanno male non sono mai quelle

Molte industrie programmano le cose. Ciò che rende speciali le scuole è la densità di vincoli ad incastro

Tutto è condiviso. Un programma di turni ospedalieri limita principalmente un tipo di risorsa (personale). Un orario scolastico ne limita contemporaneamente tre: insegnanti, aule e gruppi di studenti, e ogni lezione ne consuma uno per lezione. L'inserimento di una singola lezione rimuove le opzioni in tre dimensioni contemporaneamente.

Vincoli rigidi e morbidi coesistono. Alcune regole sono fisiche: un insegnante non può stare in due aule contemporaneamente. Altre sono preferenze: la signora Ortiz preferirebbe insegnare la mattina. Un buon orario deve soddisfare tutti i tipi della prima e il maggior numero possibile della seconda, e questi due obiettivi si combattono costantemente

La struttura vive all'interno della struttura. I periodi doppi devono occupare fasce orarie consecutive e spesso non devono coincidere con la pausa pranzo. I blocchi opzionali richiedono che quattro lezioni diverse, tenute da quattro insegnanti in quattro aule, si svolgano contemporaneamente in modo che gli studenti possano scegliere diverse materie. Le sessioni di laboratorio richiedono aule specifiche. Gli incontri con il personale richiedono una certa presenza di persone libere alla stessa ora. Ognuno di questi è un vincolo relativo ai gruppi di collocamenti, che è molto più difficile dei vincoli relativi

I dati sono umani. Contratti a tempo parziale, insegnanti condivisi che dividono la settimana tra due scuole, un allenatore che parte presto nei giorni delle partite. Le vere scuole sono un insieme di eccezioni e un orario che le ignori non è un orario, è un suggerimento

I moderni software di cronometraggio non usano la forza bruta nell'universo delle combinazioni e non usano la magia. Utilizza una famiglia di tecniche di soddisfazione dei vincoli e ottimizzazione combinatoria che sono davvero belle una volta vista

Propagazione: lascia che ogni collocazione ti insegni qualcosa. Quando il risolutore inserisce una lezione, ne propaga immediatamente le conseguenze: questo insegnante è occupato martedì secondo periodo, questa aula è occupata, questo gruppo è occupato. Ogni opzione che è appena diventata impossibile viene rimossa dalla considerazione ovunque. Lo spazio di ricerca crolla di ordini di grandezza ad ogni passo sicuro

Fallisci velocemente, torna indietro in modo intelligente. Invece di scoprire un vicolo cieco dopo settimane come fa un umano, un risolutore rileva in pochi millisecondi che un ramo della ricerca non può avere successo (qualche lezione futura ha già zero fasce orarie legali rimaste) e lo abbandona all'istante. Può anche identificare quale decisione precedente ha causato il vicolo cieco e tornare esattamente a quel punto.

Euristica: metti al primo posto le cose più difficili. I pianificatori umani esperti lo fanno istintivamente (pianifica in anticipo i blocchi di opzioni e i part-time, riempi i single facili per ultimi). I risolutori lo fanno sistematicamente, classificando ogni lezione non effettuata in base a quanto sia limitata

Ripara e migliora. Ottenere un orario fattibile è solo metà del lavoro. I risolutori quindi lo migliorano, spostando e scambiando le catene di lezioni per ridurre le lacune tra gli insegnanti, rispettare più preferenze e bilanciare il carico, senza mai infrangere un vincolo rigido. È qui che «valido» diventa «buono».

Il risultato, con uno strumento come Arignote Timetable, è che un programma completo e privo di conflitti per una vera scuola emerge in pochi minuti, con tutti i vincoli rigidi verificati meccanicamente e quelli morbidi ottimizzati ben oltre il punto in cui un essere umano, il quattordicesimo giorno, avrebbe comprensibilmente rinunciato.

Ecco la parte che sorprende le persone: l'automazione rende il ruolo umano più importante, non meno importante.

Il risolutore è valido solo quanto il modello della scuola che gli viene dato. Decidere che le due mestruazioni non debbano coincidere con il pranzo, che il nuovo insegnante abbia bisogno di un primo semestre delicato, che il giovedì pomeriggio è sacro per gli incontri di dipartimento: questa è la leadership scolastica, in codice. Il compito del software è assicurarsi che, una volta detto, sia vero ovunque, sempre, in un modo che nessun essere umano che lavora da solo può garantire.

E quando ritorna l'orario generato, lo rivedi come un editor, non come un dattilografo: modifica un posizionamento qui, aggiungi una lezione lì, con ogni modifica verificata in tempo reale, e rigenera il resto in base alle tue decisioni.

Settimane di lavoro meccanico diventano minuti di calcolo più ore di giudizio. Il giudizio era sempre la parte preziosa.