Individuazione delle possibili soluzioni

Figura 11: Macchina a stati finiti per l'identificazione degli intervalli da esaminare per la ricerca delle soluzioni rilevanti.

Le soluzioni, ovvero gli intervalli in grado di soddisfare alla richiesta, vengono individuate tramite una macchina a stati finiti (riportata in figura 11) che attualmente è costituita da tre fasi di ricerca di soluzioni:

1. si tengono in considerazione gli impegni di tutti gli utenti invitati: viene costruita una lista costituita dagli intervalli temporali in cui tutti gli utenti invitati risultano liberi da impegni;
2. in caso di fallimento si passa a considerare solo gli impegni di tutti gli utenti invitati come partecipanti necessari: viene costruita una lista costituita da intervalli temporali in cui tutti gli invitati necessari risultano liberi da impegni;
3. se anche lo stadio $2$ si conclude con un fallimento si cerca una soluzione considerando solo gli impegni dell'iniziatore e le riunioni che coinvolgono i partecipanti necessari: viene costruita una lista costituita dagli intervalli temporali in cui l'iniziatore risulta libero da qualsiasi impegno e gli invitati necessari risultano liberi da altre riunioni in cui la loro presenza sia necessaria.
4. nel caso in cui non si riesca a definire alcun possibile intervallo in cui pianificare la riunione, il procedimento termina avvertendo del fallimento l'iniziatore, il quale potrà eventualmente modificare la richiesta ridefinendone i vincoli temporali.

Nel caso in cui tutte le fasi falliscano la macchina termina in uno stato di fallimento e la richiesta non viene soddisfatta. In caso contrario, la lista $L$ degli intervalli che sono stati individuati e le funzioni obiettivo $d(t)$ e $p(t)$ vengono utilizzati per costruire un insieme di istanti rilevanti da utilizzare per identificare le possibili soluzioni.

Definizione 7.4   Chiamiamo $T$ l'insieme degli istanti rilevanti. Un istante $t_k$ è rilevante se

• $t_k$ coincide con l'istante iniziale o finale di uno degli intervalli contenuti in $L$,
• $t_k$ coincide con un punto di salto di almeno una delle funzioni obiettivo $d(t)$ e $p(t)$.²

Figura: Algoritmo per l'identificazione delle soluzioni. I pedici $start$ e $end$ indicano rispettivamente l'istante iniziale e finale di un intervallo. La funzione $next(T, t)$ restituisce il primo istante temporale successivo a $t$ tra quelli contenuti in $T$.

La lista di intervalli $L$ e l'insieme $T$ degli istanti rilevanti, vengono analizzati dall'Algoritmo di Identificazione delle Soluzioni Rilevanti (figura 12) allo scopo di estrarne un insieme di possibili soluzioni. Tale algoritmo rappresenta un elemento di novità rispetto alle soluzioni proposte in [5,7,9,11]. Anzichè discretizzare il tempo in intervalli predefiniti l'algoritmo individua degli intervalli che sono rilevanti al fine di ottimizzare la collocazione di una riunione rispetto alle funzioni obiettivo. Vengono considerati tutti e soli gli intervalli temporali che sono candidati a rappresentare dei massimi locali per gli indici $\alpha$ e $\beta$. Questo permette di ottenere un numero finito di possibili soluzioni con il vantaggio di una maggiore flessibilità.

Figura 13: Esempio di individuazione delle soluzioni rilevanti all'interno di uno dei possibili intervalli da esaminare. La soluzione indicata dalla freccia è quella individuata al passo $10$ dell'algoritmo.

Esempio: Nella situazione riportata in figura 13 si ha un intervallo da analizzare e tre istanti temporali rilevanti $t_0$, $t_1$ e $t_2$, di cui $t_0$ e $t_2$ rappresentano l'istante iniziale e finale dell'intervallo da analizzare, mentre $t_1$ rappresenta un punto di salto di una delle funzioni obiettivo. L'algorimo di individuazione delle soluzioni inizia individuando una soluzione di lunghezza minima posizionata a partire dall'istante $t_0$. Successivamente l'algoritmo espande la durata, individuando una soluzione che inizia in $t_0$ e termina in $t_1$. Cercando nuovamente di espandere la durata della soluzione non è possibile individuare altri istanti rilevanti che precedano $t_3$, il quale rappresenta l'istante finale della soluzione a durata massima con inizio in $t_0$. Dopo aver memorizzato la soluzione compresa tra $t_0$ e $t_3$ si procede cercando di spostare l'istante iniziale. Esso viene posizionato in $t_1$, e l'algoritmo riparte considerando la soluzione di durata minima e cercando di espanderla sino alla durata massima. Infine l'istante iniziale viene posizionato in $t_4$, calcolato in modo da poter espandere la durata della soluzione sino al massimo valore possibile restando nei limiti imposti dall'intervallo analizzato (la soluzione a durata massima con istante iniziale in $t_4$ termina in $t_2$, ultimo istante utile nell'intervallo a cui ci si è vincolati).

Figura 14: Possibili soluzioni presentate all'utente iniziatore.

Tutte le soluzioni individuate vengono valutate, ordinate e comunicate all'agente GA dell'iniziatore, che le presenta all'utente (figura 14) il quale ne può selezionare una da assegnare definitivamente alla nuova riunione. Tale scelta potrà essere effettuata esaminando le caratteristiche di ciascuna soluzione (qualità stimata, massimo numero di utenti non disponibili, identità di tali utenti e percentuale di utenti disponibili in media). L'intervallo selezionato sarà quindi assegnato alla riunione che potrà essere notificata agli utenti invitati e memorizzata nel database.³