Il problema dell'orario scolastico

Il problema di preparare l'orario scolastico e' un tipico problema
di intelligenza artificiale.
Dato un certo numero di classi ed un corrispondente numero di
insegnanti il problema consiste nel suddividere le ore degli
insegnanti nei vari giorni in ciascuna classe.
Il problema non puo' essere risolto con metodi combinatoriali
classici, poiche' il numero di combinazioni cresce esponenzialmente
rispetto al numero di classi elaborate.
Inoltre l'algoritmo puo' fallire anche nel tentativo di sistemare
l'ultimo insegnante nell'ultima classe, il che significa che non
puo' essere un algoritmo di tipo incrementale e che e' necessaria
una strategia di back tracking.
Per non ricominciare tutte le volte da zero l'algoritmo deve tenere
una graduatoria di situazioni che possa portare alla soluzione in
un tempo ragionevole.
Un possibile approccio consiste nell'utilizzare la tecnica degli
algoritmi genetici.
Una popolazione di configurazioni che possa essere selezionata sulla
base di un obiettivo finale.
I criteri per un buon orario scolastico comprendono molti vincoli.
Alcuni di questi sono connaturati al problema come il numero di ore
per classe, altri sono di tipo aggiuntivo di tipo logistico come
le ore in cui un insegnante e' occupato altrove ovvero non e' disponibile.
Un buon algoritmo per la schedulazione dell'orario scolastico deve
prevedere un certo numero di vincoli per poter essere utilizzato nella
pratica: l'abbinamento di insegnanti, ovvero due insegnanti nella stessa
ora nella stessa classe, l'abbinamento di classi, ovvero due classi
per lo stesso insegnante, la disponibilita' delle aule, il giorno
libero previsto per gli insegnanti, il massimo numero di ore per ogni
insegnante, il bilinguismo, ore fisse relativamente alla disponibilita'
delle palestre, il numero minimo di ore consecutive, ecc.
Esiste una certa dose di sfiducia relativamente alle realizzazioni
di programmi per la schedulazione dell'orario scolastico proprio per
la difficolata' intrinseca del problema.
Un algoritmo efficiente per la schedulazione dell'orario scolastico
dovrebbe generare un orario equilibrato senza troppi "buchi" per
l'orario degli insegnanti e tenere conto della difficolta' delle
materie per non affaticare troppo gli studenti.
In sostanza si possono delineare alcuni passi logici relativi ad un
buon algoritmo di schedulazione:
1) riempimento delle ore disponibili in ogni classe
2) memorizzazione di un primo livello di back tracking
3) applicazione dei vincoli allo schema
4) In caso di fallimento back tracking iniziando lo scheduling
   dall'insegnante causa del fallimento stesso
5) cancellazione delle configurazioni che portano al fallimento
6) premiazione delle configurazioni con alta fitness
Naturalmente occorre un controllo preventivo della consistenza
delle richieste, per esempio che il numero di ore a disposizione
di un insegnante non sia superiore al numero di ore previste per
ogni classe.
Personalmente mi sono cimentato nella soluzione di questo problema
e modestamente credo di aver ottenuto un discreto risultato.
Chi e' interessato all'argomento puo' contattarmi via E-Mail
all'indirizzo obettelli@cesia.unibo.it
 

Scarica ORARIO - Schedulazione orario scolastico