Operatori ed Operazioni
Salve ragazzi,
ho necessità di un aiuto per risolvere un problema apparentemente semplice ma che purtroppo mi sta facendo passare notti insonni per trovare un approccio di calcolo per trovare la soluzione.
Il problema è il seguente:
Devo pianificare una turnazione settimanale di n operatori che hanno dato disponibilità per attività svolte sia in sede che continuative fuori sede da un minimo di 1gg ad un massimo di 4gg.
Ogni dipendente ha dato disponibilità per le attività sia in sede che fuorisede, naturalmente non tutti hanno dato la stessa disponibilità.
Il problema che mi sono posta è in quanti modi possibili si possono disporre le attività su base settimanale soddisfacendo le esigenze di ogni dipendente.
Faccio uno schema tipo:
Durata attività
A1:3gg; A2:3gg;A3:3gg;A4:3gg;
A5:4gg;
A6:1gg;A7:1gg;A8:1gg;A9:1gg;A10:1gg;A11:1gg;A12:1gg;A13:1gg;
I dipendenti che nella tabella hanno rispetto al giorno della settimana nessuna attività assegnata significa che in quella giornata non hanno dato disponibiltà ad attività.
In quanti modi possibili posso disporre le attività assumendo che questa non sia l'unica Possibile.
Mi aiutate a risolvere questo rompicapo o per la soluzione esiste solo un metodo iterativo?
H3st3r1na
ho necessità di un aiuto per risolvere un problema apparentemente semplice ma che purtroppo mi sta facendo passare notti insonni per trovare un approccio di calcolo per trovare la soluzione.
Il problema è il seguente:
Devo pianificare una turnazione settimanale di n operatori che hanno dato disponibilità per attività svolte sia in sede che continuative fuori sede da un minimo di 1gg ad un massimo di 4gg.
Ogni dipendente ha dato disponibilità per le attività sia in sede che fuorisede, naturalmente non tutti hanno dato la stessa disponibilità.
Il problema che mi sono posta è in quanti modi possibili si possono disporre le attività su base settimanale soddisfacendo le esigenze di ogni dipendente.
Faccio uno schema tipo:
Durata attività
A1:3gg; A2:3gg;A3:3gg;A4:3gg;
A5:4gg;
A6:1gg;A7:1gg;A8:1gg;A9:1gg;A10:1gg;A11:1gg;A12:1gg;A13:1gg;
I dipendenti che nella tabella hanno rispetto al giorno della settimana nessuna attività assegnata significa che in quella giornata non hanno dato disponibiltà ad attività.
| Operatori | Lunedì | Martedi | Mercoledì | Giovedì | Venerdi | Sabato |
|---|---|---|---|---|---|---|
| A1 | A1 | A1 | A6 | Op2 | ||
| A5 | A5 | A5 | A5 | Op3 | A8 | |
| A2 | A2 | A9 | A10 | Op4 | A3 | |
| A3 | A11 | A12 | Op5 | A13 | A4 | A4 |
In quanti modi possibili posso disporre le attività assumendo che questa non sia l'unica Possibile.
Mi aiutate a risolvere questo rompicapo o per la soluzione esiste solo un metodo iterativo?
H3st3r1na
Risposte
Hai guardato Knuth? L'assegnazione di blocchi di memoria?
Magari per un informatico è facile.
Magari per un informatico è facile.
Voglio essere strasicuro di aver capito i parametri del problema, perché volendo scrivere un programma per contare le soluzioni devo contare le cose giuste.
Abbiamo un elenco di attività. O meglio, abbiamo un elenco delle _durate_ di alcune attività. La stessa attività non può essere fatta simultaneamente da più persone. Deve essere fatta in un unico blocco di tempo di lunghezza uguale alla durata dell'attività. Non può essere fatta in due blocchi di tempo distinti dalla stessa persona con un buco in mezzo.
Abbiamo un elenco $a$ i cui contentuti sono $a_1, a_2, ...$ in ordine noncrescente per comodità. Se l'elenco non è ordinato, ordiarlo così è la prima cosa che facciamo.
Abbiamo un elenco della lunghezza dei blocchi di tempo nei quali ogni operatore è disponibile.
Ai fini del problema non importa, in realtà, quale blocco appartiene ad quale operatore.
Anche qui, comunque siano presentate le lunghezze dei blocchi di tempo di disponibilità degli operatori, li mettiamo in ordine non-crescente.
L'elenco si chiama $o$ e i suoi contenuti sono $o_1, o_2, ..$.
Per trovare _un_ modo per farlo possiamo decidere che non metteremo MAI un valore di $a$ in mezzo ad uno spazio $o$ troppo lungo, solo all'inizio o alla fine. E tanto vale usare sempre l'inizio. Non ci sarebbe mai alcun vantaggio nel creare due sottospazi. Mettendo un valore $a$ all'inizio o alla fine di uno spazio $o$ se lo spazio è troppo lungo ci lascia un solo spazietto invece di due e uno spazietto un po' più lungo potrebbe essere utile in un'occasione dove due spazietti più piccoli ci lascerebbero senza soluzione.
Ma se vogliamo contare TUTTE le soluzioni dobbiamo permetterci di creare due spazietti in questi casi, perché potrebbe portare ad una soluzione in più.
Algoritmo/pseudocodice:
Guardiamo $a_1$. Se è maggiore di $o_1$ diciamo "0 soluzioni"
Se $a_1=o_1$ .... qualcosa.
Altrimenti: creiamo nuove versioni della lista dove $a_1$ non c'è più e $o_1$ è stato sosituito con varie cose diverse. Per esempio $o_1-a_1, 1$ o $1, o_1-a_1, o_1-a_1-1$ o .. ecc. poi... qualcosa ricorsione.
No, no, no...
Così non distinguiamo nemmeno fra $a_1, 1$ e $1,a1$ come sostituti di $o_1$. Ok devo pensarci.
Ma ... ho capito le restrizioni?
Secondo me gli informatici lo trovano banale e anche i matematici che programmano più di me. Che saranno in tanti. Volevo mostrare di averci pensato anche se i miei risultati fanno pena per ora.
Abbiamo un elenco di attività. O meglio, abbiamo un elenco delle _durate_ di alcune attività. La stessa attività non può essere fatta simultaneamente da più persone. Deve essere fatta in un unico blocco di tempo di lunghezza uguale alla durata dell'attività. Non può essere fatta in due blocchi di tempo distinti dalla stessa persona con un buco in mezzo.
Abbiamo un elenco $a$ i cui contentuti sono $a_1, a_2, ...$ in ordine noncrescente per comodità. Se l'elenco non è ordinato, ordiarlo così è la prima cosa che facciamo.
Abbiamo un elenco della lunghezza dei blocchi di tempo nei quali ogni operatore è disponibile.
Ai fini del problema non importa, in realtà, quale blocco appartiene ad quale operatore.
Anche qui, comunque siano presentate le lunghezze dei blocchi di tempo di disponibilità degli operatori, li mettiamo in ordine non-crescente.
L'elenco si chiama $o$ e i suoi contenuti sono $o_1, o_2, ..$.
Per trovare _un_ modo per farlo possiamo decidere che non metteremo MAI un valore di $a$ in mezzo ad uno spazio $o$ troppo lungo, solo all'inizio o alla fine. E tanto vale usare sempre l'inizio. Non ci sarebbe mai alcun vantaggio nel creare due sottospazi. Mettendo un valore $a$ all'inizio o alla fine di uno spazio $o$ se lo spazio è troppo lungo ci lascia un solo spazietto invece di due e uno spazietto un po' più lungo potrebbe essere utile in un'occasione dove due spazietti più piccoli ci lascerebbero senza soluzione.
Ma se vogliamo contare TUTTE le soluzioni dobbiamo permetterci di creare due spazietti in questi casi, perché potrebbe portare ad una soluzione in più.
Algoritmo/pseudocodice:
Guardiamo $a_1$. Se è maggiore di $o_1$ diciamo "0 soluzioni"
Se $a_1=o_1$ .... qualcosa.
Altrimenti: creiamo nuove versioni della lista dove $a_1$ non c'è più e $o_1$ è stato sosituito con varie cose diverse. Per esempio $o_1-a_1, 1$ o $1, o_1-a_1, o_1-a_1-1$ o .. ecc. poi... qualcosa ricorsione.
No, no, no...
Così non distinguiamo nemmeno fra $a_1, 1$ e $1,a1$ come sostituti di $o_1$. Ok devo pensarci.
Ma ... ho capito le restrizioni?
Secondo me gli informatici lo trovano banale e anche i matematici che programmano più di me. Che saranno in tanti. Volevo mostrare di averci pensato anche se i miei risultati fanno pena per ora.
Ho chiesto aiuto in informatico. A questo punto voglio vedere come si fa.
Penso di aver risolto questo rompicapo senza l'ausilio dell'informatica, ricapitolando:
Si consideri il seguente problema di assegnamento: abbiamo 5 operatori, ciascuno con una disponibilità lavorativa settimanale specificata, e un insieme di attività da svolgere, suddivise in attività continue di 3 giorni e attività singole di 1 giorno. L'obiettivo è determinare il numero totale di modi diversi in cui è possibile assegnare le attività agli operatori, rispettando i vincoli di disponibilità.
Modello matematico:
Definiamo:
n1: numero di operatori disponibili 6 giorni
n2: numero di operatori disponibili 4 giorni
a3: numero di attività da 3 giorni
a1: numero di attività da 1 giorno
Le attività da 3gg da assegnare sono 5 le attività da da 1gg sono 13 ogni. Ogni operatore deve avere tutta la settimana impegnata in base alle disponibilità date.
Ogni operatore deve avere settimanalmente un attività di 3gg contigui.
Soluzione:
Assegnamento delle attività da 3 giorni:
Gli operatori con disponibilità di 6 giorni hanno 4 possibili posizionamenti per un'attività da 3 giorni.
L'unico operatore con disponibilità di 4 giorni ha 2 possibili posizionamenti.
Utilizzando le disposizioni con ripetizione, otteniamo:
(4^n1) * (2^n2) modi di assegnare le attività da 3 giorni.
Permutazioni delle attività:
Le a3 attività da 3 giorni possono essere permutate in a3! modi diversi.
Le a1 attività da 1 giorno possono essere permutate in a1! modi diversi.
Soluzione finale:
Il numero totale di configurazioni possibili è dato dal prodotto delle permutazioni delle attività e dei modi di assegnare le attività da 3 giorni:
N = (4^n1) * (2^n2) * a3! * a1!
Spero di aver ragionato bene!
Se c'è qualche matematico che può venirmi in soccorso è molto gradito.
H3st3r1na
Si consideri il seguente problema di assegnamento: abbiamo 5 operatori, ciascuno con una disponibilità lavorativa settimanale specificata, e un insieme di attività da svolgere, suddivise in attività continue di 3 giorni e attività singole di 1 giorno. L'obiettivo è determinare il numero totale di modi diversi in cui è possibile assegnare le attività agli operatori, rispettando i vincoli di disponibilità.
Modello matematico:
Definiamo:
n1: numero di operatori disponibili 6 giorni
n2: numero di operatori disponibili 4 giorni
a3: numero di attività da 3 giorni
a1: numero di attività da 1 giorno
Le attività da 3gg da assegnare sono 5 le attività da da 1gg sono 13 ogni. Ogni operatore deve avere tutta la settimana impegnata in base alle disponibilità date.
Ogni operatore deve avere settimanalmente un attività di 3gg contigui.
Soluzione:
Assegnamento delle attività da 3 giorni:
Gli operatori con disponibilità di 6 giorni hanno 4 possibili posizionamenti per un'attività da 3 giorni.
L'unico operatore con disponibilità di 4 giorni ha 2 possibili posizionamenti.
Utilizzando le disposizioni con ripetizione, otteniamo:
(4^n1) * (2^n2) modi di assegnare le attività da 3 giorni.
Permutazioni delle attività:
Le a3 attività da 3 giorni possono essere permutate in a3! modi diversi.
Le a1 attività da 1 giorno possono essere permutate in a1! modi diversi.
Soluzione finale:
Il numero totale di configurazioni possibili è dato dal prodotto delle permutazioni delle attività e dei modi di assegnare le attività da 3 giorni:
N = (4^n1) * (2^n2) * a3! * a1!
Spero di aver ragionato bene!
Se c'è qualche matematico che può venirmi in soccorso è molto gradito.
H3st3r1na
Pensavo fosse un problema da risolvere in più occasioni. E quindi abbiamo bisogno di un metodo generale.
Se vuoi conoscere il numero di possibilità in questo caso e basta, certo.
Allora non ho capito assolutamente nulla fin dall'inizio e sono servo a nulla. Mi ritiro. Il problema generale non mi dispiace ormai ma a te non importa nulla del problema in generale.
Se vuoi conoscere il numero di possibilità in questo caso e basta, certo.
Allora non ho capito assolutamente nulla fin dall'inizio e sono servo a nulla. Mi ritiro. Il problema generale non mi dispiace ormai ma a te non importa nulla del problema in generale.
No, certo questo è solo un caso della molteplicità dei casi disponibili però l'approccio è matematico non informatico.
Se c'è qualcuno che si apprccia in maniera diversa e dia il suo contributo è sicuramente ben accetto.
Se c'è qualcuno che si apprccia in maniera diversa e dia il suo contributo è sicuramente ben accetto.
Gantt?
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo