L'orario - FET: come garantire che al più solo classi parallele facciano educazione fisica contemporaneamente...

... cioè prime al più con altre prime, seconde al più con altre seconde, terze al più con altre terze, etc... Più in generale garantire che al più solo classi parallele facciano una stessa lezione contemporaneamente.

Lo scenario è il seguente: dopo aver spiegato in questo articolo come  fare in modo che al più due classi facciano educazione fisica contemporaneamente, ora vogliamo imporre che le due classi che fanno educazione fisica contemporaneamente siano al più due prime, due seconde, etc... Al più vuol dire (sì, lo so, è ovvio) che o solo una classe fa educazione fisica o due classi dello stesso anno.

Purtroppo mi sembra non ci sia un metodo immediato. Ho trovato solo due tecniche che, pur funzionando bene, presentano dei limiti nell'implementazione (ma come dicevo non nei risultati: funzionano bene e fanno quel che promettono). L'unico vincolo che possiamo usare è quello che ci permette di imporre che alcune attività non siano concomitanti. Per spiegare le due tecniche partiamo da un esempio concreto. Siamo in una scuola media con sei sezioni complete (tre classi per sezione), abbiamo due professori di educazione fisica, uno per le sezioni A, B, C; l'altro per le sezioni D, E, F. Ogni professore di educazione fisica fa due ore in ogni classe.

1. La prima tecnica è la seguente: aggiungere tanti vincoli del tipo Tempo > Attività > Un insieme di (sub) attività non sono concomitanti per tutte le coppie di attività che non possono essere concomitanti. Il problema è valutare quante siano queste coppie. Proviamo a contarle, cominciamo dai vincoli che mi garantiscono che la 1A non faccia lezione con classi di anni diversi: (1A, 2D), (1A, 2E), (1A, 2F), (1A, 3D), (1A, 3E), (1A, 2F). Ovviamente non serve imporre un vincolo sulla coppia (1A, 2A), ed in generale (1A, 2 o 3 del professore delle sezioni A, B, C) perché quel professore o ha la 1A o la 2A, non è possibile che le due attività si svolgano contemporaneamente. Sembrerebbe quindi che abbiamo trovato 6 vincoli, ma non è così. Bisogna moltiplicare per 4, perché per ogni coppia dobbiamo lavorare sulle singole sub attività. Mi spiego: abbiamo due sub attività da un ora di educazione fisica per la 1A (chiamiamole 1Aa e 1Ab) e due per la 1D (chiamiamole 1Da e 1Db). Le coppie possibili sono 4: (1Aa, 1Da),  (1Aa, 1Db), (1Ab, 1Da), (1Ab, 1Db). In definitiva per imporre che la 1A non faccia educazione fisica contemporaneamente con classi di anni diversi mi servono 24 vincoli. Le prime in tutto sono sei, quindi per garantire le prime non facciano lezione con seconde o terze mo servono 6*24= 144 vincoli. Ora devo imporre che seconde e terze non facciano educazione fisica contemporaneamente, i vincoli sono solo 4*3*6 = 72 vincoli (fidatevi sulla parola). In definitiva dovremmo imporre 216 vincoli del tipo Un insieme di (sub) attività non sono concomitanti. Che decollerebbero se le sezioni fossero 9 o le classi per sezione 5.
   
   • Pro di questa tecnica: non inseriamo vincoli ridondanti
   • Contro di questa tecnica: elevato numero di vincoli da inserire, talmente elevato da rendere, a mio parere, la tecnica inutilizzabile
     
     
2. La seconda tecnica consiste sempre nell'inserire vincoli del tipo Tempo  >Attività > Un insieme di (sub) attività non sono concomitanti ma ora non lavoriamo solo su coppie, bensì su insiemi più ampi di sub attività (il vincolo lo permette). Possiamo garantire inserendo un solo vincolo che tutte le prime del professore delle sezioni A, B e C non facciano educazione fisica con le seconde o le terze dell'altro professore. Il vincolo coinvolge le seguenti sub attività: (1Aa, 1Ab, 1Ba, 1Bb, 1Ca, 1Cb, 2Da, 2Db, 2Ea, 2Eb, 2Fa, 2Fb, 3Da, 3Db, 3Ea, 3Eb, 3Fa, 3Fb). A questo aggiungiamo un vincolo simile per le tre prime del secondo professore e altri due vincoli che mi garantiscono che seconde e terze non facciano educazione fisica contemporaneamente. In tutte me la cavo con 4 vincoli, che per quanto richiedano di inserire più sub attività l'uno, sono comunque nel complesso molto più semplici dell'inserire i 216 vincoli della tecnica precedente. Dove sta la fregatura, vi chiederete? Troppo bello per essere vero. In realtà c'è un problema. Questa tecnica funziona e nemmeno eliminiamo soluzioni valide perché vincoliamo troppo. Però inseriamo tutta una serie di vincoli ridondanti. Analizziamo il vincolo che coinvolge le seguenti attività: (1Aa, 1Ab, 1Ba, 1Bb, 1Ca, 1Cb, 2Da, 2Db, 2Ea, 2Eb, 2Fa, 2Fb, 3Da, 3Db, 3Ea, 3Eb, 3Fa, 3Fb). Questo vincolo impedisce anche che le prime del primo professore non possano fare educazione fisica contemporaneamente, ma questo è già garantito da altri vincoli (il professore è uno, non ha il dono dell'ubiquità); e lo stesso vale per tutte le seconde e le terze del secondo professore: è già impossibile che facciano lezione contemporaneamente. Così facendo aggiungiamo quindi tanti vincoli inutili, come se scrivessimo le seguenti disequazioni: x>5, 2x>10, 3x>15... ne basta una per definire il problema, le altre due sono ridondanti. Ci sarebbe da chiedersi quanto l'algoritmo di calcolo della soluzione dell'orario sia influenzato dall'aggiunta di vincoli ridondanti. In teoria sì, in pratica non lo so perché non so come funziona. Per conludere:
   
   • Pro di questa tecnica: numero di vincoli da inserire limitato
   • Contro di questa tecnica: aggiungiamo tutta una serie di vincoli ridondanti che potrebbero influenzare la velocità del software.

Io ho utilizzato la seconda tecnica.

Con questo avrei concluso, voi che ne pensate? Avete utilizzato altre tecniche? Esiste un modo immediato per ottenere il risultato desiderato che mi è sfuggito? Aspetto vostri commenti.

Per come scaricare FET clicca sul seguente collegamento.