Perché due motori
🧰 FET è il programma classico, gratuito, installato sul tuo computer. Gestisce moltissimi tipi di regole e dà ai vincoli un «peso». Per un orario complicato servono di solito 5-20 minuti.
⚡ OR-Tools CP-SAT è un solutore matematico (software libero, licenza Apache 2.0), già dentro ProntOrario. Lavora nel tuo browser, senza installare nulla. Nelle prove su una scuola vera: 676 attività collocate in circa 10 secondi (con 4 processi in parallelo).
In breve: CP-SAT è molto più veloce a trovare un orario valido; FET conosce più regole «morbide». Per questo oggi si usano insieme, e nel pannello di controllo ogni regola mostra quale motore la considera.
Il confronto
| FET | OR-Tools CP-SAT | |
|---|---|---|
| Dove calcola | Programma sul tuo PC | Dentro il browser, sul tuo PC |
| Da installare | Sì (gratuito) | No |
| Tempo tipico | 5-20 minuti (indicazione ufficiale per i casi complessi) | Secondi o pochi minuti; l'orario valido arriva per primo |
| Regole rigide (sovrapposizioni, aule, buchi degli studenti) | Sì | Sì |
| Ore buche dei docenti, ore al giorno, giorni di presenza, cambi di sede | Sì, con peso | Sì: massimo/minimo ore e sedi come regole rigide; buche, giorni e le materie spezzate in due momenti dello stesso giorno da ridurre al minimo |
| Aule preferite «con peso» | Sì | Non ancora |
| Più orari da confrontare | Sì | Sì (altri 9 orari con tabella di confronto) |
| Se non esiste un orario | Messaggi tecnici | Pulsante «Spiega perché»: indica i gruppi di regole responsabili |
| Privacy | Tutto sul tuo PC | Tutto sul tuo PC (nomi pseudonimizzati) |
Le icone nel pannello di controllo
Accanto a ogni regola del pannello trovi l'icona del motore che la usa. FET + CP-SAT: la regola è rispettata da entrambi. Solo FET: la regola vale solo se calcoli con FET. «parz.»: CP-SAT la considera in parte (ad esempio le ore buche: cerca di ridurle, ma non scende mai sotto il limite, così resta almeno un'ora libera per il ricevimento).
I vincoli si impostano da soli
🎚️ Scegli un livello, e basta. Con i livelli non devi regolare a mano decine di vincoli: ogni livello compila in automatico tutte le regole, sia per CP-SAT sia per FET, con i valori giusti per quel livello. L'unica cosa che decidi è quanto tempo vuoi aspettare. Con 10 minuti, su una scuola di circa 35 classi e 650 attività, l'autore ha ottenuto un orario ottimizzato di altissimo livello. Se cambi un valore a mano puoi farlo, ma esci dai valori previsti: i tempi non sono più prevedibili e l'orario potrebbe non chiudersi.
I quattro livelli di CP-SAT
Livello 1 – Rapido. Solo le regole di base. Sulla scuola di prova: circa 17 secondi.
Livello 2 – Equilibrato. In più ore al giorno dei docenti, sedi e spostamenti. Circa 34 secondi.
Livello 3 – Curato. In più riduce ore buche, giorni di presenza e le materie spezzate in due momenti dello stesso giorno. Circa 70 secondi.
Livello 4 – Massimo. Lavora fino al tempo massimo per ridurre ancora. Più tempo dai, meglio va, ma non c'è garanzia di arrivare a zero.
Nel pannello di controllo le due colonne (CP-SAT e FET) si compilano da sole con i valori del livello scelto. I tempi sono misure su una scuola con 676 attività e 2 processi in parallelo: sul tuo computer cambiano, e il pannello corregge la stima dopo il primo calcolo.
Il calcolo in parallelo: perché CP-SAT è veloce
⚙️ Tanti calcoli insieme. Un computer moderno ha più «cervelli» (i processori, o core). CP-SAT li usa tutti nello stesso momento: lancia più ricerche diverse in parallelo, ognuna con una strategia propria. Se una trova una buona strada, le altre ne approfittano; chi arriva prima all'orario vince. È come far cercare una soluzione a quattro persone che provano strade diverse e si passano i risultati, invece di una persona sola che prova una strada dopo l'altra.
📏 Una misura. Sulla scuola di prova (676 attività) lo stesso calcolo del livello 1 ha richiesto 83 secondi con un solo calcolo e 17 secondi con due in parallelo. È una sola prova, non una regola: il guadagno non cresce sempre in proporzione ai processori.
🖥️ Metodo moderno, computer moderni. Il calcolo in parallelo è una delle ragioni principali della rapidità, insieme al modo in cui CP-SAT ragiona (vedi sotto). Per questo rende di più su un PC recente. Su un PC con pochi processori funziona, ma è più lento.
Due modi diversi di ragionare
🔵 FET: come farebbe una persona. FET è un algoritmo euristico, cioè un procedimento a tentativi che imita il lavoro a mano. Mette le attività in ordine di difficoltà, le più difficili per prime. Ne colloca una in un posto libero; se non ce n'è, la mette dove dà meno fastidio, toglie le attività che si scontrano e prova a ricollocare quelle. L'autore lo chiama «scambio ricorsivo» (recursive swapping). È un procedimento a passi successivi, uno dopo l'altro.
🟣 CP-SAT: scrive il problema come regole matematiche. Ogni regola (nessuno in due posti, un'aula per volta, massimo di ore al giorno…) diventa una condizione che un lavoro di calcolo deve rispettare. Poi cerca con tecniche di ricerca matematica, ispirate ai solutori «SAT», che imparano dai vicoli ciechi per non ripeterli. Sa anche dimostrare che un orario non esiste, ed è per questo che il pulsante «Spiega perché» funziona.
Un procedimento a tentativi come quello di FET parte subito e va benissimo in tantissimi casi, ma per sua natura non può dire «non esiste» né «questo è il meglio possibile». Un solutore matematico può farlo, ma richiede più memoria e più processori.
Un po' di storia del calcolo dell'orario
- Il problema è difficile per natura. Nel 1976 Even, Itai e Shamir dimostrarono che costruire un orario scolastico è un problema «NP-completo»: non si conosce un metodo che garantisca il risultato rapidamente in ogni caso. Da allora si cercano buoni metodi a tentativi e metodi esatti.
- Anni 1990 e 2000: i metodi ispirati alla natura. Si provano algoritmi genetici (che «fanno evolvere» gli orari come una selezione naturale), tempra simulata, ricerca tabu. FET nasce nel 2002 con un algoritmo genetico: il nome significa «Free Evolutionary Timetabling».
- 2007: FET cambia strada. Il suo autore sostituisce l'algoritmo genetico, lento e adatto solo agli orari facili, con lo «scambio ricorsivo», dalla versione 5.0.0. Il nome resta, l'algoritmo non è più evolutivo.
- Le gare internazionali. Le comunità di ricerca organizzano competizioni tra programmi. L'International Timetabling Competition del 2011 (la terza) era dedicata proprio agli orari delle scuole superiori, con dati veri.
- Oggi: solutori matematici generali. Strumenti come OR-Tools, nati per problemi di ottimizzazione di ogni genere, trovano e migliorano orari in tempi brevi, sfruttando i processori del computer.
Riconoscimenti
🏅 OR-Tools CP-SAT. La MiniZinc Challenge è la gara internazionale annuale tra solutori. Nel 2013 OR-Tools ottenne due medaglie d'oro proprio nelle categorie «parallelo» e «portfolio». Nel 2024 CP-SAT ha vinto l'oro in quattro categorie (fisso, libero, parallelo, aperto), e la sua variante con ricerca locale l'oro nella categoria ricerca locale.
🎓 FET. FET è usato anche in lavori universitari: esistono articoli scientifici che raccontano la sua applicazione a orari di università, di college e di scuole (alcuni titoli saranno citati nel libro).
Approfondimenti, con le fonti e la storia completa, saranno nel libro «Manuale ProntOrario». Fonti di questa pagina: descrizione dell'algoritmo di FET · MiniZinc Challenge 2024 · MiniZinc Challenge 2013 (fonte) · International Timetabling Competition 2011.
Quale PC serve
🟣 CP-SAT lavora nel browser. Ti serve un browser aggiornato (Chrome o Edge) e un computer non troppo datato. Indicazione prudente: almeno 4 processori e 8 GB di RAM. Con meno, il calcolo funziona ma è più lento: scegli il livello 1 o 2.
🔵 FET si installa sul PC. È un programma vero e proprio: non ha i limiti di memoria del browser. Con un computer modesto resta la strada più sicura, anche se il calcolo può durare più a lungo.
Un limite che non dipende dalla RAM. Il browser concede ai programmi di questo tipo al massimo 2 GB di memoria, anche se il computer ne ha 16. In una prova su una scuola da 676 attività il livello 3 ha raggiunto questo limite: per questo il motore usa pochi calcoli in parallelo e, se la memoria finisce, riprova con meno. L'orario valido già trovato non si perde.
Perché due strade. Le scuole non hanno sempre computer adeguati. ProntOrario offre due motori perché chi lo ha ideato conosce molto bene la realtà del settore scolastico e cerca soluzioni adatte ai bisogni reali delle scuole, non solo a quelle con il computer migliore.
Le indicazioni sul computer sono prudenti: finora il motore è stato provato su un computer con 16 GB di RAM e in un ambiente di prova con 2 processori. Se lo usi su un PC molto diverso, ti sarà utile sapere com'è andata.
Quale usare
🏆 Con un PC di buone prestazioni, scegli CP-SAT. Provato dall'autore su una scuola di circa 35 classi e 650 attività: con 10 minuti di calcolo (livello 4) l'orario esce ottimizzato ad altissimo livello, con soli 4 casi oltre i limiti (giorni di presenza dei docenti). È il risultato di una scuola reale: sulla tua i numeri potranno essere diversi, ma l'ordine di grandezza dei tempi è questo.
- PC recente (Chrome o Edge aggiornati, almeno 4 processori e 8 GB di RAM): usa CP-SAT. Parti dal livello 3 o 4 e dì solo quanto tempo vuoi aspettare.
- PC datato: usa CP-SAT al livello 1 o 2, per sapere subito se l'orario esiste, oppure calcola con FET.
- Hai regole che solo FET conosce (aule preferite con peso, regole molto particolari)? Calcola con FET.
- Vuoi scegliere: calcola con entrambi e confronta gli orari.
Cosa dicono le fonti
CP-SAT è tra i solutori più forti nelle gare internazionali di ottimizzazione (le MiniZinc Challenge) e gli studi sul problema dell'orario scolastico lo indicano come molto efficace. Attenzione: sono prove generali, non un confronto diretto su orari scolastici italiani. Il dato che conta per te è quello misurato sui tuoi dati: per questo FET resta disponibile.
FET è di Liviu Lalescu e collaboratori (licenza GNU AGPL v3); OR-Tools è software libero (licenza Apache 2.0). ProntOrario non è collegato ai loro autori.