Algoritmo per riparto tempi tra lavorazioni contemporanee
Ciao a tutti.
Sto ragionando sul problema che segue, senza riuscire a generalizzarlo. Spero riusciate a darmi una mano. In pratica, si tratta di suddividere dei tempi di lavorazione tra il numero di lavorazioni contemporanee effettuate.
Se, ad esempio, inizio 3 lavorazioni alle 9.00 della mattina e le termino contemporaneamente alle 15.00, avrò effettuato 3 lavorazioni in 6 ore. Pertanto il tempo di ogni singola lavorazione corrisponderà a 6/3=2h. Fin qui è abbastanza semplice, il problema sorge nel momento in cui le lavorazioni sono sovrapposte, ma i loro tempi di inizio e fine lavorazione non coincidono. Mi spiego con un esempio.
La prima lavorazione inizia alle ore 10.00 e termina alle 12.00. La seconda inizia alle 11.00 e termina alle 13.30. La terza inizia alle 11.30 e termina alle 12.00. Schematizzando:
[img]http://www.matematicamente.it/forum/download/file.php?id=8[/img]
Ora, la soluzione in questo caso specifico consiste nel suddividere il tempo totale, dalle 10.00 alle 13.30, in 4 intervalli:
1) 10.00-11.00;
2) 11.00-11.30;
3) 11.30-12.00;
4) 12.00-13.30.
Nell'intervallo 1) viene assegnata 1h alla lavorazione 1. Nell'intervallo 2) viene assegnata (0.5/2)h alle lavorazioni 1 e 2. Nell'intervallo 3) viene assegnata (0.5/3)h alle lavorazioni 1, 2 e 3. Nell'intervallo 4) viene assegnata 1.5h alla lavorazione 2.
Quindi in definitiva i tempi di lavorazione sono i seguenti:
Lavorazione 1= (1 + 0.5/2 + 0.5/3)h
Lavorazione 2= (0.5/2 + 0.5/3 + 1.5)h
Lavorazione 3= (0.5/3)h
Ora, mi piacerebbe sapere:
- In che categoria di problemi ricade il suddetto?
- Come si chiama il problema specifico?
- Esiste una formulazione matematica del problema?
- Esiste una formula/algoritmo risolutivo?
Grazie mille per l'attenzione e la disponibilità.
Sto ragionando sul problema che segue, senza riuscire a generalizzarlo. Spero riusciate a darmi una mano. In pratica, si tratta di suddividere dei tempi di lavorazione tra il numero di lavorazioni contemporanee effettuate.
Se, ad esempio, inizio 3 lavorazioni alle 9.00 della mattina e le termino contemporaneamente alle 15.00, avrò effettuato 3 lavorazioni in 6 ore. Pertanto il tempo di ogni singola lavorazione corrisponderà a 6/3=2h. Fin qui è abbastanza semplice, il problema sorge nel momento in cui le lavorazioni sono sovrapposte, ma i loro tempi di inizio e fine lavorazione non coincidono. Mi spiego con un esempio.
La prima lavorazione inizia alle ore 10.00 e termina alle 12.00. La seconda inizia alle 11.00 e termina alle 13.30. La terza inizia alle 11.30 e termina alle 12.00. Schematizzando:
[img]http://www.matematicamente.it/forum/download/file.php?id=8[/img]
Ora, la soluzione in questo caso specifico consiste nel suddividere il tempo totale, dalle 10.00 alle 13.30, in 4 intervalli:
1) 10.00-11.00;
2) 11.00-11.30;
3) 11.30-12.00;
4) 12.00-13.30.
Nell'intervallo 1) viene assegnata 1h alla lavorazione 1. Nell'intervallo 2) viene assegnata (0.5/2)h alle lavorazioni 1 e 2. Nell'intervallo 3) viene assegnata (0.5/3)h alle lavorazioni 1, 2 e 3. Nell'intervallo 4) viene assegnata 1.5h alla lavorazione 2.
Quindi in definitiva i tempi di lavorazione sono i seguenti:
Lavorazione 1= (1 + 0.5/2 + 0.5/3)h
Lavorazione 2= (0.5/2 + 0.5/3 + 1.5)h
Lavorazione 3= (0.5/3)h
Ora, mi piacerebbe sapere:
- In che categoria di problemi ricade il suddetto?
- Come si chiama il problema specifico?
- Esiste una formulazione matematica del problema?
- Esiste una formula/algoritmo risolutivo?
Grazie mille per l'attenzione e la disponibilità.
Risposte
Ti linko un consiglio sui possibili poco vantaggi nel postare domande da scaricare.
viewtopic.php?f=15&t=118257
viewtopic.php?f=15&t=118257
Quale è il tuo obbiettivo? Qual è il problema da risolvere?
Zaino reale (oppure qualche somiglianza con sheduling di programma, ma direi di no).
Se il tempo L1 + L2 + L3 > TOT tempo, che fai? Un lavoro lo interrompi? Oppure vuoi massimizzare la partizione di tempo dei lavori possibili nel totale?
Se il tempo L1 + L2 + L3 > TOT tempo, che fai? Un lavoro lo interrompi? Oppure vuoi massimizzare la partizione di tempo dei lavori possibili nel totale?
Sposto qui in ricerca operativa, che mi pare essere la sezione più adatta.
"hamming_burst":
Zaino reale (oppure qualche somiglianza con sheduling di programma, ma direi di no).
Se il tempo L1 + L2 + L3 > TOT tempo, che fai? Un lavoro lo interrompi? Oppure vuoi massimizzare la partizione di tempo dei lavori possibili nel totale?
Ciao. Grazie per avermi risposto. Io temo che il mio problema non abbia molto a che fare con la ricerca operativa, in quanto non ho l'obiettivo di massimizzare alcuna variabile. E' più un problema aritmetico...
Il mio obiettivo è consuntivare i tempi di lavorazione di un operatore PER OGNI SINGOLA LAVORAZIONE, quando esso si dedica a più attività contemporaneamente (sto sviluppando l'algoritmo all'interno di un software gestionale). Non esistono vincoli del tipo L1 + L2 + L3 <= TOT, anzi, nella normalità accade spesso che la somma dei tempi di lavorazione è maggiore al tempo di lavoro complessivo. Proprio per "risolvere" questa situazione non reale si ripartisce il tempo tra le lavorazioni, in modo che la somma dei tempi di lavorazione sia uguale al tempo totale! Per fare un altro esempio, se io lavoro 2 ore su 2 diversi oggetti contemporaneamente, non ho lavorato per 4 ore!!! La domanda cui l'algoritmo deve rispondere è: se in 2 ore ho lavorato 2 oggetti, quanto tempo ho dedicato ad ogni lavorazione? La risposta è, ovviamente, 1 ora a lavorazione. Questo è però vero solo se inizio e finisco le due lavorazioni nel medesimo istante. Se invece inizio prima una lavorazione (L1) e solo dopo un'ora inizio l'altra (L2), non è possibile pensare che io abbia dedicato un'ora ad ogni lavorazione... Di fatto ho dedicato 1h intera ad L1 ed un'1h a L1 ed L2. Quindi, avrò dedicato 1,5h ad L1 e 0,5h ad L2. Spero di essere stato chiaro, non saprei come chiarire ulteriormente...
Io ho già improntato un algoritmo risolutivo, ma vorrei sapere in che caso ricade ciò che sto facendo (per semplice curiosità) e quali sono gli algoritmi più efficienti che sono stati sviluppati (per sapere in che modo ottimizzare, eventualmente, il mio). Comunque appena l'avrò implementato e testato, condividerò l'algoritmo con voi!
"Luca97":
Ti linko un consiglio sui possibili poco vantaggi nel postare domande da scaricare.
viewtopic.php?f=15&t=118257
Grazie per il consiglio. Tuttavia terrei a precisare che:
1) Non è necessario scaricare lo schema per comprendere la domanda, è solo un chiarimento ulteriore (l'esposizione testuale è di per sé autoesplicativa).
2) L'allegato consiste in un'immagine, quindi viene aperta direttamente nel browser e non è necessario "scaricare" nel senso comune del termine.
3) Si tratta di un file .png, non .rar, .exe o simili, quindi non esiste la possibilità di contrarre virus sul computer.
4) L'account tinypic di matematicamente, per aggiungere direttamente immagini ai post, è stato bannato per violazione dei termini di utilizzo, quindi non avevo altra alternativa se non quella di utilizzare la funzione "invia allegato".
Detto questo, ora provo ad inserire direttamente l'immagine nel post... Oppure spiegatemi come fare usando le funzioni del forum! Grazie. Ciao.
EDIT: ecco fatto, ci sono riuscito
! Ora potete vedere direttamente l'immagine nel post! Grazie.
"ufo":
[quote="Luca97"]Ti linko un consiglio sui possibili poco vantaggi nel postare domande da scaricare.
viewtopic.php?f=15&t=118257
Grazie per il consiglio. Tuttavia terrei a precisare che:
1) Non è necessario scaricare lo schema per comprendere la domanda, è solo un chiarimento ulteriore (l'esposizione testuale è di per sé autoesplicativa).
2) L'allegato consiste in un'immagine, quindi viene aperta direttamente nel browser e non è necessario "scaricare" nel senso comune del termine.
3) Si tratta di un file .png, non .rar, .exe o simili, quindi non esiste la possibilità di contrarre virus sul computer.
4) L'account tinypic di matematicamente, per aggiungere direttamente immagini ai post, è stato bannato per violazione dei termini di utilizzo, quindi non avevo altra alternativa se non quella di utilizzare la funzione "invia allegato".
Detto questo, ora provo ad inserire direttamente l'immagine nel post... Oppure spiegatemi come fare usando le funzioni del forum! Grazie. Ciao.
EDIT: ecco fatto, ci sono riuscito
! Ora potete vedere direttamente l'immagine nel post! Grazie.[/quote]Il mio non voleva essere un rimprovero: ci mancherebbe, e poi chi sono io?
Era solo per evitare un tuo possibile svantaggio
Nell'intervallo 1) viene assegnata 1h alla lavorazione 1. Nell'intervallo 2) viene assegnata (0.5/2)h alle lavorazioni 1 e 2. Nell'intervallo 3) viene assegnata (0.5/3)h alle lavorazioni 1, 2 e 3. Nell'intervallo 4) viene assegnata 1.5h alla lavorazione 2.
secondo questa suddivione puoi fare più lavorazioni contemporaneamente.
nell'intervallo 2) inizi la lavorazione 2 e finisci la lavorazione 1. Il mio assunto era che avevi un solo macchinario e dovevi suddividere il lavoro per massimizzare il tempo di lavorazione per ogni oggetto.
quindi deduco tu abbia più macchinari a disposizione che lavorano in parallelo su tutti gli oggetti.
Quanti macchinari hai a disposizione? perchè se no la logica di suddivisione è illogica se possiedi una macchina solamente.
"Luca97":
Il mio non voleva essere un rimprovero: ci mancherebbe, e poi chi sono io?
Era solo per evitare un tuo possibile svantaggio
Certo, nessun problema. Anzi, effettivamente con l'immagine nel post è più semplice capire la domanda.
"hamming_burst":
Quindi deduco tu abbia più macchinari a disposizione che lavorano in parallelo su tutti gli oggetti.
Infatti, il succo del discorso è che io non devo dividere il lavoro su un macchinario. Devo solo "ricalcolare" i tempi di lavoro.
Un caso pratico potrebbe essere il seguente:
- Un operaio inizia la lavorazione "verniciatura sportello automobile" alle 10.00. Prende lo sportello, lo carteggia e alle 11.00 lo mette sotto un braccio meccanico che esegue la verniciatura in automatico, mentre l'operaio deve tornare di tanto in tanto a verificare lo stato e impartire determinati ordini al macchinario. La verniciatura finisce alle 12.00. L'operaio rifinisce le ultime cose e alle 12.30 la lavorazione risulta conclusa.
- Mentre lo sportello viene verniciato in automatico, alle ore 11.00 inizia la lavorazione "lucidatura cerchioni automobile". Quindi prende un cerchio ed inizia a lucidarlo a mano, fermandosi di tanto in tanto per andare al macchinario della verniciatura per verificare lo stato e impartire determinati ordini. La lucidatura finisce alle ore 12.00.
Ora, è chiaro che non si può affermare che l'operaio ha lavorato 2 ore e 30 minuti alla verniciatura e 1 ora alla lucidatura. Altrimenti avrebbe lavorato 3 ore e 30 minuti in un intervallo di 2 ore e 30 minuti!!! Pertanto, quando vi sono lavorazioni in contemporanea, si sceglie di suddividere il tempo trascorso per il numero di lavorazioni. Quindi prendiamo l'intervallo dalle 11.00 alle 12.00, mentre l'operaio verniciava, lucidava anche. Quindi avrà impiegato (in "media") 30 minuti per la lucidatura e 30 minuti per la verniciatura. In questo modo risulta che ha verniciato per 2 ore totali ed ha lucidato per 30 minuti, cioè per un totale di 2 ore e 30 minuti, proprio come la durata dell'intervallo considerato!
ooh ok, ora è chiaro.
La questione è un po' più complessa. In questo caso lo zaino reale è solo un piccolo sottoproblema.
La risoluzione algoritmica è possibile, ma bisogna trovare la riduzione del problema corretto. Forse flusso massimo, visto la distinzione tra lavoro umano e lavoro macchina (con flusso massimo si possono inserire delle condizioni widget ad-hoc), ma ci provo [strike]in serata[/strike] quando ho un po' di tempo, è un problema interessante.
La questione è un po' più complessa. In questo caso lo zaino reale è solo un piccolo sottoproblema.
La risoluzione algoritmica è possibile, ma bisogna trovare la riduzione del problema corretto. Forse flusso massimo, visto la distinzione tra lavoro umano e lavoro macchina (con flusso massimo si possono inserire delle condizioni widget ad-hoc), ma ci provo [strike]in serata[/strike] quando ho un po' di tempo, è un problema interessante.
Ti ringrazio anticipatamente!
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo