ricerca operativa e programmazione: gestione turni!

Messaggioda zenit16 » 12/09/2011, 10:33

Ciao a tutti!
vi spiego subito il mio grosso problema: voglio creare un'applicazione che gestisca i turni di alcuni lavoratori.
Non ci sono particolari vincoli e i turni sono solo due, mattino e pomeriggio.

Ho pensato di utilizzare le mie, scarse, conoscenze di ricerca operativa e usare quindi un normale algoritmo di gestione turni.
Si ma, tra l'ottenere una funzione obiettivo con dei vincoli e la 'traduzione' in linguaggio di programmazione mi sembra ci sia un oceano di distanza! :?:
Avete avuto modo di incontrare problemi simili? Potete aiutarmi gentilemente? :-D

ciao!
zenit16
Starting Member
Starting Member
 
Messaggio: 1 di 6
Iscritto il: 12/09/2011, 10:18

Re: ricerca operativa e programmazione: gestione turni!

Messaggioda hamming_burst » 12/09/2011, 11:11

Ciao,
sbagliato sezione mi sa :)

Comunque manca una cosa fondamentale, cosa devi fare? ottimizzare o decidere i turni, il personale, il guadagno... Specifica meglio :-)
hamming_burst
Cannot live without
Cannot live without
 
Messaggio: 1169 di 8058
Iscritto il: 04/07/2009, 10:53

Re: ricerca operativa e programmazione: gestione turni!

Messaggioda Deckard » 12/09/2011, 17:12

zenit16 ha scritto:Si ma, tra l'ottenere una funzione obiettivo con dei vincoli e la 'traduzione' in linguaggio di programmazione mi sembra ci sia un oceano di distanza!

Un oceano di distanza detto algoritmo del simplesso. Ti conviene utilizzare un solutore già implementato. Ci sono dei solver per AMPL gratuiti piuttosto efficienti (lpsolve ad esempio).
http://www.mathcomp.leeds.ac.uk/turing2012/

Hilbert space is a big place.
Deckard
Average Member
Average Member
 
Messaggio: 168 di 503
Iscritto il: 17/08/2010, 08:58

Re: ricerca operativa e programmazione: gestione turni!

Messaggioda zenit16 » 13/09/2011, 08:56

ham_burst ha scritto:Ciao,
sbagliato sezione mi sa :)

Comunque manca una cosa fondamentale, cosa devi fare? ottimizzare o decidere i turni, il personale, il guadagno... Specifica meglio :-)


.. devo decidere i turni.
Le persone sono dei volontari quindi danno la loro disponibilità, cioè quanti turni possono fare.
Ogni turno deve essere di due persone.
Quindi il mio problema è questo: come incastro i turni di questi volontari? :|
help me! :roll:
zenit16
Starting Member
Starting Member
 
Messaggio: 2 di 6
Iscritto il: 12/09/2011, 10:18

Re: ricerca operativa e programmazione: gestione turni!

Messaggioda hamming_burst » 15/09/2011, 21:49

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:
Immagine

Versione più grande: http://i56.tinypic.com/2md59i8.png

Spiegazione:
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.
hamming_burst
Cannot live without
Cannot live without
 
Messaggio: 1179 di 8058
Iscritto il: 04/07/2009, 10:53

Re: ricerca operativa e programmazione: gestione turni!

Messaggioda zenit16 » 28/09/2011, 09:13

Scusa tanto per il ritardo...
Leggo ora il tutto, e mi sembra veramente quello che cercavo! :-D
La pianificazione è mensile comunque.
Provo subito ad implementare... Grazie tante per l'eccellente risposta! :-)
ciao!
zenit16
Starting Member
Starting Member
 
Messaggio: 3 di 6
Iscritto il: 12/09/2011, 10:18

Re: ricerca operativa e programmazione: gestione turni!

Messaggioda hamming_burst » 28/09/2011, 14:02

di nulla :-)
se è mensile basta semplicemente sostituire $G=7$ con $G=28,30,31$ :-)
hamming_burst
Cannot live without
Cannot live without
 
Messaggio: 1229 di 8058
Iscritto il: 04/07/2009, 10:53

Re: ricerca operativa e programmazione: gestione turni!

Messaggioda Raptorista » 25/04/2018, 09:12

Moderatore: Raptorista

Sposto da Generale.
Un matematico ha scritto:... come mia nonna che vuole da anni il sistema per vincere al lotto e crede che io, in quanto matematico, sia fallito perché non glielo trovo


Immagine
Avatar utente
Raptorista
Moderatore
Moderatore
 
Messaggio: 4899 di 9616
Iscritto il: 28/09/2008, 19:58


Torna a Analisi Numerica e Ricerca Operativa

Chi c’è in linea

Visitano il forum: Nessuno e 1 ospite