Vediamo un po'.
Non hai specificato se vuoi pianificare uno scheduling settimanale, o altro.
Perciò assunzioni e generalizzazioni che faccio:
- 2 turni x giorno
- 2 persone per turno
- pianificazione settimanale, 7 giorni e 14 turni totali
- $n$ volontari
modificarli è banale
Ci sono diversi modi per modellare questo problema, uno è quello consigliato da Deckard, ma io ti propongo una variante che forse ti è più facile da modificare e modellare nei tuoi casi.
Visto che hai detto che conosci concetti di Ricerca Operativa, Io ti propongo di utilizzare la modellizzazione e la classe di problemi risolvibili con Ricerca Locale (una variante della RO), e in questo caso di utilizzare il problema di flusso massimo-taglio minimo. Utilizza i grafi, tutto ciò che devi modificare sono gli archi per la "disponibilità" dei volontari. Ovviamente è risolvibile con il simplesso, con opportune modifiche.
ti allego qua il disegno, non ho tempo di disegnartelo in vettoriale, penso si capisca comunque:
Versione più grande:
http://i56.tinypic.com/2md59i8.pngSpiegazione:
per ogni volontario $v_i$, aggiungiamo un nodo $V_i$. Per ogni turno $t_j$ aggiungiamo un nodo $T_{G.H}$, dove $G$ è il giorno della settimana e $H$ è il turno $M=\text{mattina} vv P=\text{pomeriggio}$. Per ogni coppia (volontario $V_i$, giorno $G$) aggiungiamo un nodo $W_{v.g}$. Infine, aggiungiamo la sorgente $S$ e il pozzo $T$. Poichè gni volontario può lavorare al massimo $14 $turni (non essendoci un massimo consideriamo quello settimanale), mettiamo il peso $14$ su tutti gli archi $(S,V_i)$. Poichè ogni dipendente può lavorare al massimo $2$ turni al giorno (essendoci massimo $2$ turni disponibili, se fossero $3$ mettiamo $3$), mettiamo il peso $2$ su tutti gli archi $(V_i,W_{v.g})$.
Le preferenze di disponibilità dei volontari sono rappresentate dagli archi $(W_{v.g},T_{g.h})$, tutti con peso $1$ ovviamente. Infine, si collegano i turni al nodo pozzo, con peso $2$ come di necessità scritta dal tuo problema.
Il costo dell'algoritmo con Ford–Fulkerson dovrebbe essere, se consideriamo come il flusso massimo $P=sum 2*T_{G.H} = 2*(7*2) = 28$ allora sarà $O(P(|N|+|E|))$.
$|N| = 8*|V| +16$ i nodi totali
$|E| in O(106*|V|+14)$ sono gli archi massimi. Perciò il costo totale sarà di $O(3192|V|)$.
Se si utilizza invece Edmonds–Karp, la complessità diviene $11236|V|^3+28|V|^2+ 196 in O(11236|V|^3)$ decisamente meglio F-F
.
i conti di complessità li ho solo messi per completezza
Ora gli algoritmi se cerchi sono già belli che implementati in $N$ verisioni in $M$ linguaggi differenti, cerca quello che preferisci te.
Il lavoro che devi fare è creare la struttura dati del grafo bipartito sopra nel tuo linguaggio, con i nodi fissi, i nodi dei volontari dipendenti dal numero che hai e le disponibilità che possono fare.
Ora se hai dubbi o domande (sempre che non abbia preso cantonate) chiedi pure
EDIT:
corretto piccolo errore.
Inviato: 12/09/2011, 10:33
