Concetti
Come funziona davvero la generazione automatica
Senza retorica commerciale. Che cosa fa il motore, perché il problema è difficile e perché la qualità dei vincoli conta più dell'ingegnosità dell'algoritmo.
Il problema, esposto con chiarezza
Si dispone di un insieme di lezioni. Ognuna richiede una fascia oraria, un'aula e un docente. Alcune risorse sono condivise, alcune lezioni non devono sovrapporsi, e un lungo elenco di regole vincola quali combinazioni siano ammissibili. Occorre trovare un'assegnazione che non violi alcuna regola rigida e violi il minor numero possibile di preferenze.
Si tratta di un problema di soddisfacimento di vincoli, e la programmazione dell'orario universitario ne è un caso difficile molto studiato. Il numero di assegnazioni possibili cresce in modo esplosivo con il numero di lezioni: la ricerca esaustiva non è semplicemente lenta, è astronomicamente impraticabile anche per una facoltà di modeste dimensioni.
Per questo nessun sistema pratico procede con una ricerca esaustiva. Utilizzano euristiche — strategie informate per decidere che cosa collocare per primo e che cosa fare quando ci si blocca — per trovare rapidamente una buona soluzione anziché, prima o poi, una soluzione dimostrabilmente ottimale.
Che cosa fa realmente il motore
- Ordinamento. Decidere quali lezioni collocare per prime. Le lezioni molto vincolate — una coorte numerosa che richiede un laboratorio specifico con un solo tecnico qualificato — vengono di solito collocate presto, perché collocarle per ultime significa disfare tutto il resto.
- Collocazione. Assegnare una lezione a una combinazione ammissibile di fascia oraria, aula e docente che non violi alcun vincolo rigido.
- Backtracking. Annullare decisioni precedenti quando una lezione non ha più alcuna collocazione ammissibile. È qui che se ne va la maggior parte del tempo di esecuzione.
- Valutazione. Stimare quanto bene la soluzione parziale corrente soddisfi le preferenze flessibili, così che la ricerca possa privilegiare le regioni migliori dello spazio.
- Miglioramento. Una volta ottenuta una soluzione ammissibile completa, apportare modifiche locali che migliorano il punteggio senza compromettere nulla.
Perché i vincoli contano più dell'algoritmo
Questa è la parte che i fornitori sono meno inclini a dire. Dato un insieme di vincoli ben specificato, la maggior parte dei motori competenti produce risultati paragonabili. Dato uno specificato male, nessun motore produce nulla di utile.
Il fallimento più comune non è algoritmico. È un insieme di vincoli in cui le preferenze sono state dichiarate inviolabili, per cui non esiste alcuna soluzione ammissibile e il motore segnala correttamente un gran numero di lezioni non collocabili. Il secondo più comune è costituito da dati di input obsoleti o errati — capienze delle aule che nessuno controlla dall'ultima ristrutturazione, disponibilità raccolte sei settimane prima.
Ecco perché la domanda utile da porre a un fornitore non è "che algoritmo utilizzate" ma "come mi aiutate a definire correttamente vincoli e disponibilità".
Come si presenta un buon sistema nella pratica
Un sistema utilizzabile genera abbastanza in fretta da rendere la rigenerazione una routine anziché un lavoro notturno — Wise Timetable rigenera anche orari di grandi dimensioni in meno di un minuto, il che significa che si sperimenta invece di impegnarsi su una sola esecuzione.
Segnala che cosa non è riuscito a collocare, e perché, invece di violare silenziosamente una regola per produrre qualcosa che sembri finito. Rispetta le lezioni che avete bloccato, così che lavoro automatico e manuale possano convivere. E produce più varianti, così da poterle confrontare anziché accettarne una.
Desiderate vederlo in funzione?
Prenotate una presentazione online di 45 minuti e la illustreremo sul problema di programmazione del Vostro ateneo.