\chapter{Definizione del problema}\label{chapDefinizioneProblema}

La generazione dell'orario consiste nel ricavare una soluzione che permetta di svolgere le varie lezioni nell'arco della settimana tenendo conto della disponibilità di risorse limitata di risorse a disposizione in termini di numero di Aule, disponibilità dei Docenti a fare lezione, necessità di garantire agli studenti la possibilità di seguire determinati Insegnamenti lo stesso semestre (che quindi non potranno essere erogati contemporaneamente in aule differenti) e più in generale di soddisfare vari vincoli di natura diversa che verranno trattati in seguito nel dettaglio.

\section{Esempi introduttivi}
Vengono ora mostrati due esempi per entrare maggiormente nell'ottica del problema:
\begin{example}\label{esSoddisfacibilita}
{\footnotesize 
\begin{enumerate}
    \item\say{si hanno 8 lezioni di 1,5h ciascuna che vanno erogate il Lunedì mattina a partire dalle 8:30 e devono concludersi entro le ore 16:00}
    \item\say{vi sono 2 Aule distinte}
    \item\say{le lezioni sono così ripartite tra tre diversi Insegnamenti: 3 lezioni (da qui in avanti chiamate Slot) sono di Geografia, 2 Slot (3 ore) sono di Storia e i rimanenti 3 Slot (4,5 ore) sono di Italiano}
    \item\say{gli studenti che seguono il corso di Storia devono poter seguire anche il corso di Italiano}
    \item\say{il Docente del Corso di Storia è il medesimo di quello del corso di Geografia}
    \item\say{è noto che la soglia di attenzione degli studenti cali notevolmente dopo 3 ore di lezione della stessa materia}.
\end{enumerate}
Dai requisiti sopra esposti è possibile dedurre l'impossibilità di pianificare l'erogazione di tutti e tre gli Insegnamenti contemporaneamente (vi è un limite di due aule), non è valido un orario in cui le ore di Italiano e Storia vengano erogate in parallelo (gli studenti devono poter seguire entrambi gli Insegnamenti), discorso analogo anche per la coppia Storia e Geografia (il Docente che tiene le lezioni è il medesimo); infine le 4,5 ore di lezione di Geografia andranno divise poichè non è possibile avere più di 3 ore consecutive della stessa materia.
}
\end{example}

L'Esempio \ref{esSoddisfacibilita} corrisponde ad un problema di soddisfacilità che dovrà essere implementato su un dataset con una cardinalità dell'ordine di 600 Slot di lezione, 250 differenti Docenti, 20 Orientamenti composti da differenti Insegnamenti che non potranno essere erogati contemporaneamente (gli studenti che scelgono un Orientamento devono poterlo seguire interamente) tenendo conto dei limiti dettati dalle Aule messe a disposizione nonchè della loro capienza (risulta evidente l'impossibilità di erogare un Insegnamento con 300 studenti iscritti in un Aula con 50 postazioni).

Si introduce ora un problema di ottimizzazione:
\begin{example}
{\footnotesize
\begin{enumerate}\label{esOttimizzazione}
    \item\say{Il Docente del corso di Storia e Geografia preferisce terminare le sue lezioni con Storia perchè la ritiene meno impegnativa per i suoi studenti}
    \item\say{Gli studenti del corso di Geografia principalmente non vivono vicino alla scuola e quindi potrebbero avere difficoltà ad essere puntuali alle 8:30}.
\end{enumerate}
}
\end{example}
L'Esempio \ref{esOttimizzazione} consente di ricavare differenti pianificazioni delle lezioni rispettando tutti i vincoli dell'Esempio \ref{esSoddisfacibilita}, ma non tutte saranno ottime.


\section{Requisiti}
I requisiti costituiscono le asserzioni e le deduzioni di alto livello dedotti a seguito di interviste con i responsabili dell'orario necessari alla progettazione del modello:\\
\begin{enumerate}
    \item\say{Vi sono Corsi di Laurea, Orientamenti, Insegnamenti, Slot\footnote{Si intende la singola lezione indivisibile erogabile e può occupare 1.5 ore o un suo multiplo.}, Fasce Orarie, Giorni, Locali, Docenti}.
    \item\say{I Corsi di Laurea sono di tipo Magistrale o Triennale}.
    \item\say{Un Corso di Laurea prevede diversi Orientamenti\footnote{Per ogni Corso di Laurea vi sono più Orientamenti.}}.
    \item\say{Un Orientamento propone diversi Insegnamenti\footnote{Un Insegnamento può essere presente in Orientamenti differenti.}}.
    \item\say{Un Orientamento è costituito da più anni: tre per gli Orientamenti di Corsi di Laurea Triennali e due per quelli Magistrali}.
    \item\say{Un Orientamento ha \textit{Insegnamenti obbligatori}, \textit{Insegnamenti suggeriti}\index{Insegnamento suggerito}, \textit{Insegnamenti a Scelta}\index{Insegnamento a scelta} molto correlati, a media correlazione e poco correlati per ogni anno\footnote{I vari Insegnamenti all'interno di un Orientamento non hanno la medesima importanza, in quanto non tutti sono obbligatori al conseguimento del titilo, inoltre alcuni di essi sono obbligatori ma in mutua esclusione tra loro. Si veda la Tabella \ref{table:tabPenalitaInsInOrient} per una descrizione rigorosa della correlazione tra Insegnamenti all'interno di un determinato Orientamento}}.
    % \todo[inline]{spiegare cosa vuol dire correlazione}
    \item\say{Un Orientamento contiene alcuni Insegnamenti che devono essere considerati per la consecutività\footnote{Viene introdotto un limite sul numero massimo di ore di lezione giornaliere allocabili a tali Insegnamenti; l'appartenenza di un Insegnamento a tale gruppo dipende dall'\textit{intensità} della relazione Orientamento-Insegnamento.}}.
    \item\say{Un Insegnamento si tiene in uno o più semestri ed è associato ad un anno per ogni Orientamento}. 
    \item\say{Un Insegnamento è composto da uno o più Slot}.
    \item\say{Per ogni Insegnamento viene definito un Template Orario\footnote{Rappresenta la suddivisione desiderata dei vari Slot all'interno della settimana, specificando per ognuno di essi le risorse necessarie per la sua allocazione.}}.
    \item\say{Un Insegnamento è associato a uno o più Docenti e uno di essi è titolare di esso\footnote{Il Docente titolare non deve necessariamente essere presente in tutti gli Slot dell'Insegnamento; la sua figura è importante in quanto si occupa di definire il Template Orario per l'Insegnamento.}}.
    \item\say{Un Insegnamento è frequentato da un certo numero di studenti}.
    \item\say{Un Insegnamento ha un piano di allocazione settimanale fisso per l'intera durate del semestre}.
    \item\say{Un Insegnamento fa riferimento ad un Collegio}.
    \item\say{Uno Slot può essere una \textit{Lezione}, un'\textit{Esercitazione in Aula} o un'\textit{Esercitazione in Laboratorio}}. 
    \item\say{I Locali possono essere \textit{Aule} e \textit{Laboratori}. Le Aule si suddividono a loro volta in \textit{Aule attrezzate CA2}, \textit{Aule attrezzate CA}, \textit{Aule TableBox}, \textit{Aule WallBox} e \textit{Aula 5T}; mentre i laboratori sono: \textit{LABINF}, \textit{LAIB}, \textit{LADISPE}, \textit{LED}, \textit{LED1}, \textit{LED2}, \textit{ACSLAB}}.
    \item\say{Gli Slot vanno allocati in un tipo di Locale specifico}.
    \item\say{Un Insegnamento può prevedere Slot in cui gli studenti sono divisi in squadre; quindi potranno essere allocati anche in parallelo}.
    \item\say{Ad ogni Slot sono associati uno o più Docenti}.
     \item\say{I Docenti possono fornire informazioni in merito al fatto che le loro lezioni all'interno di un Insegnamento sono limitate in un periodo specifico del semestre}.
    \item\say{Ogni Slot si svolge in un giorno\index{Giorno} della settimana: dal Lunedì al Venerdì ed eventualmente il Sabato}.
    \item\say{Ogni Slot dura 1,5 ore e si svolge in una fascia oraria\index{FasciaOraria}: dalle 8:30 alle 19:00}.
    \item\say{Le Aule hanno una \textit{capienza} massima}. Fatto strettamente in relazione con il numero di studenti frequentanti un Insegnamento.
    \item\say{Uno Slot è assegnato ad un \textit{Locale}}.
    \item\say{I Docenti assegnano \textit{preferenze} circa gli slot orari in cui desiderano a fare lezione su una scala discreta di 3/5 valori differenti\footnote{Informazioni non vincolanti al fine di trovare una soluzione valida.}}.
    \item\say{I Docenti possono indicare un numero limitato di slot orari in cui sono impossibilitati a tenere una lezione\footnote{Informazioni vincolanti.}}.
    \item\say{I Docenti potrebbero avere ulteriori incompatibilità dovute a Insegnamenti erogati all'interno di altri Collegi}.
    \item\say{Per ogni Insegnamento viene definito un \textit{Piano di Allocazione settimanale}}.
    \item\say{Due Aule si trovano ad una certa distanza}. % TODO le metto?
    \item\say{Gli studenti scelgono un Orientamento e un piano di studi}.
    \item\say{Due Insegnamenti possono essere in conflitto in modo vincolante o non vincolante}.
    \item\say{Un Piano di Allocazione\index{Piano Allocazione} corrisponde all'orario settimanale di tutti gli Insegnamenti contenente tutti gli Slot che li costituiscono con le relative informazioni circa il Giorno, la Fascia oraria, i Docenti e il Locale assegnati per ognuno di essi}.
    \item\say{Esistono dei vincoli tra Slot appartenenti allo stesso Insegnameto}.
    \item\say{Esiste il piano di allocazione dell'anno precedente}.
    \item\say{I Docenti possono esprimere una valutazione di gradimento dell'allocazione dell'anno precedente}.
    \item\say{I Docenti titolari di un Insegnamento definiscono l'allocazione ideale degli Slot durante la settimana}.
\end{enumerate}

\section{Analisi dei requisiti}
Dopo un'accurata analisi dei requisiti sopra esposti è stata fatta un'estrazione dei vincoli caratterizzanti il problema andandoli a suddividere in due macro categorie:
\begin{itemize}
    \item\textit{Hard Contraint}\index{Hard constraint}: ne fanno parte tutti i vincoli il cui rispetto è obbligatorio al fine di ottenere una soluzione valida
    \item\textit{Soft Constraint}\index{Soft constraint}: ne fanno parte tutti i vincoli che non è obbligatorio rispettare per ottenere una soluzione valida; tuttavia l'osservazione o meno di questi permette di valutare la bontà di una soluzione mediante l'introduzione di penalità/bonus. La somma algebrica di tali punteggi consente di stabilire un criterio di ordinamento tra le soluzioni, consentendo di trovare la \textit{soluzione ottima}\index{soluzione ottima}.
\end{itemize}
\subsection{Hard Constraint}
Segue ora una caratterizzazione formale di tutti gli Hard Constraint introdotti nel modello.
\begin{itemize}
    \item\textit{Slot allocabili} solo in prefissati slot orari\footnote{Singola unità di tempo allocabile e corrisponde a 1 ora e mezza.}: dal Lunedì al Venerdì dalle 8:30 alle 19:00 e opzionalmente il Sabato mattina dalle 8:30 alle 13:00.
    \item\textit{Locali}: 
    \begin{itemize}
        \item Uno Slot va allocato in un Locale di capienza congrua alla cardinalità degli studenti frequentanti\footnote{Negli anni passati si è osservato come una parte degli studenti seppur sia iscritta all'Insegnamento non ne frequenta le lezioni; si considera una buona approssimazione assumere come numero di studenti frequentanti il numero di essi iscritto all'Insegnamento per la prima volta.} l'Insegnamento.
        \item Uno Slot va allocato in un Locale del \textit{tipo} richiesto.
    \end{itemize}
    \item\textit{Slot}:
    \begin{itemize}
        \item Per un determinato Insegnamento è possibile raggruppare all'interno dello stesso giorno un limite di 2 entità Slot\footnote{Singola entry nel Template Orario di un dato Insegnamento.} consecutive.
        \item Alcuni Slot che devono essere allocati in un predeterminato slot orario.
        \item Possono essere definite delle relazioni binarie Slot: \textit{almenoUnGiornoDopo}, \textit{subitoDopo}, \textit{stessoGiorno}, \textit{giornoDiverso} e \textit{parallelo}.
    \end{itemize}
    \item\textit{Slot} di uno o più Insegnamenti all'interno dello stesso Orientamento:
    \begin{itemize}
        \item Gli Slot di Insegnamenti obbligatori non devono mai essere allocati nello stesso slot orario.
        \item Gli Slot di Insegnamenti suggeriti dello stesso Orientamento non devono mai essere allocati nello stesso slot settimanale.
        \item Uno Slot di un Insegnamento suggerito e uno Slot di un Insegnamento obbligatorio non devono mai essere allocati nello stesso slot settimanale.
        \item Se un Insegnamento ha più di uno Slot allocato lo stesso giorno, nel caso i Docenti che svolgono lezione in tali Slot siano anche solo parzialmente in comune\footnote{Ad uno Slot possono essere associati più Docenti.} e nel caso tali Slot abbiano come tipologia \textit{"lezione"} allora necessariamente essi saranno allocati in maniera contigua.
    \end{itemize}
    \item\textit{Docente}:
    \begin{itemize}
        \item Lo stesso Docente non può essere assegnato contemporaneamente a due Insegnamenti differenti (salvo richieste esplicite del Docente).
        \item Un Docente non può avere allocati più di 4 Slot in un dato giorno (salvo limiti differenti da considerare puntualmente per docenti con molti slot da allocare).
        \item Non è possibile allocare uno Slot tenuto da un Docente in uno slot settimanale in cui ha indicato incompatibilità.
        \item Un Docente può esprimere una distanza minima/massima in termini di slot orari tra Slot a lui collegati ma appartenenti a Insegnamenti diversi.
        \item Un Docente può richiedere l'uso dell'Orario dell'anno precedente.
        \item Un Docente può non voler avere allocati in un medesimo giorno Slot appartenenti ad Insegnamenti differenti.
    \end{itemize}
    \item\textit{Studente} iscritto ad un Orientamento:
    \begin{itemize}
        \item Non deve avere più di 5 slot orari consecutivi allocati in un determinato giorno tra gli Insegnamenti definiti obbligatori, suggeriti o obbligatori a scelta\footnote{In un Orientamento è prassi comune offrire gruppi di Insegnamenti tra cui scegliere in mutua esclusione che risultano essere obbligatori; si pensi ad esempio al caso di un Insegnamento erogato in inglese e italiana.} per il suo Orientamento.
        \item Non deve avere più di 6 slot orari allocati in un determinato giorno tra gli Insegnamenti definiti obbligatori, suggeriti o obbligatori a scelta.
    \end{itemize}
\end{itemize}
\subsection{Soft Constraint}
Di seguito una caratterizzazione formale di tutti i Soft Constraint introdotti nel modello.

\begin{itemize}
    \item\textit{Slot}:
    \begin{itemize}
        \item Possono essere definite delle relazioni binarie Slot: \textit{almenoUnGiornoDopo}, \textit{subitoDopo}, \textit{stessoGiorno}, \textit{giornoDiverso} e \textit{parallelo}.
    \end{itemize}
    \item\textit{Slot} di uno o più Insegnamenti all'interno dello stesso Orientamento:
    \begin{itemize}
        \item La sovrapposizione di Slot appartenenti a Insegnamenti differenti non trattata come hard constraint è soggetta a penalità variabili secondo la Tabella \ref{table:tabPenalitaInsInOrient}:
        
        \begin{table}[tb]
        \centering
        \begin{adjustbox}{width=1\textwidth}
            \begin{tabular}{|p{6em}||p{6em}|p{6em}|p{5em}|p{4em}|p{4em}|}
                 \hline
                 & Obbligatorio& Obbligatorio a scelta& Suggerito& Tabella a scelta& Credito libero\\
                 \hline\hline
                 Obbligatorio & hard const. & hard const. & hard const. & LV_4*k & LV_3*k \\
                 \hline
                 Obbligatorio a scelta & hard const. & hard const. & hard const. & LV_4*k & LV_3*k\\
                 \hline
                 Suggerito & hard const. & hard const. & LV_4*k & LV_3*k & LV_2*k \\
                 \hline
                 Tabella a scelta & LV_4*k & LV_4*k & LV_3*k & LV_2*k & LV_1*k\\
                 \hline
                 Credito libero & LV_3*k & LV_3*k & LV_2*k & LV_1*k & LV_0\\
                 \hline
            \end{tabular}
            \end{adjustbox}
            \caption{tipologia Insegnamenti in Orientamento.}
            \label{table:tabPenalitaInsInOrient}
        \end{table}
        
        Il calcolo della penalità deve tenere conto del fatto che due Insegnamenti possono essere presenti in molteplici Orientamenti e che la loro sovrapposizione può causare un disagio ad una popolazione più o meno vasta di studenti a seconda del numero di questi frequentanti gli Insegnamenti coinvolti.\\
        Viene quindi introdotta la seguente formula per calcolare le penalità derivanti dalla sovrapposizione di Slot di Insegnamenti
        presenti nello stesso Orientamento:
        
        \begin{equation*}
        \begin{gathered}
             penalty = \mathrm{MAX}(\text{penalty\_sovr})+\mathrm{SUM}(penalty\_sovr*delta\footnote{Per limitare l'effetto della stessa penalità all'interno di molteplici Orientamenti.}),\\
            delta=0.1
        \end{gathered}
        \end{equation*}
        
        \item In certi Orientamenti sono presenti coppie o terne di Insegnamenti tra cui lo studente deve scegliere solo uno di questi Insegnamenti e questi vanno considerati di tipo obbligatorio all'interno dell'Orientamento. Considerare puntualmente gli Insegnamenti appartenenti ai singoli gruppi permette di allocare eventualmente in parallelo gli Insegnamenti appartenenti allo stesso gruppo.
        
    \end{itemize}
    \item\textit{Docente}:
    \begin{itemize}
        \item Un Docente può esprimere parere favorevole o contrario circa la possibilità di fare lezione in uno slot settimanale.
        \item Un Docente può esprimere una distanza minima/massima in termini di slot orari tra Slot a lui collegati ma appartenenti a Insegnamenti diversi nello stesso giorno.
        \item Un Docente può esprimere la preferenza a mantenere l'Orario dell'anno precedente.
        \item Un Docente può indicare di preferire di non aver allocati lo stesso giorno Slot appartenenti ad Insegnament differenti.
        \item \'E necessario un meccanismo di bilanciamento per evitare di assecondare soltanto le richieste di alcuni Docenti a scapito di altri.
    \end{itemize}
    \item\textit{Studente} iscritto ad un Orientamento:
    \begin{itemize}
    % TODO def Insegnamenti core Orientamento come obb, obb_a_scelta, suggeriti
        \item Se uno studente di un orientamento ha 4 slot orari di lezione consecutivi tra gli Insegnamenti definiti \textit{core}\index{Insegnamenti core} per l'Orientamento allora viene assegnata una penalità LV\_1 al Piano Allocazione.
        \item Se uno studente di un orientamento ha 5 slot orari di lezione consecutivi tra gli Insegnamenti definiti \textit{core}\index{Insegnamenti core} per  l'Orientamento allora viene assegnata una penalità LV\_2 al Piano Allocazione.
        \item Se nell'orario di uno studente di un orientamento nella stessa giornata è presente un intervallo di 2 slot orari tra Slot appartenenti ad Insegnamenti definiti \textit{core}\index{Insegnamenti core} per l'Orientamento allora viene assegnata una penalità LV\_1 al Piano Allocazione.
        \item Se nella stessa giornata è presente un intervallo di almeno 3 slot orari tra Slot appartenenti ad Insegnamenti
        definiti \textit{core}\index{Insegnamenti core} per l'Orientamento.
        \item Se nella stessa giornata sono presenti due intervalli tra Slot appartenenti ad Insegnamenti definiti \textit{core}\index{Insegnamenti core} per l'Orientamento allora viene assegnata una penalità LV\_6 al Piano Allocazione.
    \end{itemize}
\end{itemize}
