L’algoritmo EDD

ott
2010
15

scritto da | on | Nessun commento

L’algoritmo earliest due date ha l’obiettivo di minimizzare il ritardo nella consegna che possiamo considerare come il ritardo massimo o come il numero minimo di lavori in ritardo, a seconda dei casi utilizzeremo una versione differente dell’algoritmo. Per poter utilizzare questo algoritmo è necessario considerare per ogni lavorazione il suo tempo di lavorazione e la sua data di consegna. Consideriamo ad esempio di avere in data 01/10/2010 le seguenti lavorazioni con i loro tempi e le loro date:

LAVORAZIONE DURATA DATA CONSEGNA
A

34

21/11/2010
B

42

06/10/2010
C

50

24/10/2010
D

40

20/11/2010
E

36

02/11/2010
F

52

12/11/2010
G

45

18/10/2010

Consideriamo adesso la data di consegna espressa in ore lavorative a partire dal 01/10/2010 ovvero se la data di consegna è il 04/10/2010 le ore lavorative sono 8, se la data è il 05/10/2010 le ore sono 16 e così via, ordinando per data di consegna espressa in ore in maniera crescente, in questo modo avremo minimizzato il ritardo massimo.

LAVORAZIONE DURATA DATA CONSEGNA ORE LAVORATIVE DAL 01/10/2010 cumulato lavorazioni ritardo
B 42 06/10/2010 32 42 10
G 45 18/10/2010 96 87 -9
C 50 24/10/2010 128 137 9
E 36 02/11/2010 176 173 -3
F 52 12/11/2010 240 225 -15
A 34 21/11/2010 280 259 -21
D 40 20/11/2010 280 299 19

Infatti se ordinassimo per durata crescente avremo un ritardo massimo di 59

LAVORAZIONE DURATA DATA CONSEGNA ORE LAVORATIVE DAL 01/10/2010 cumulato lavorazioni ritardo
A 34 21/11/2010 280 34 -246
E 36 02/11/2010 176 70 -106
D 40 20/11/2010 280 110 -170
B 42 06/10/2010 32 152 120
G 45 18/10/2010 96 197 101
C 50 24/10/2010 128 247 119
F 52 12/11/2010 240 299 59

Nel caso si voglia minimizzare il numero di lavorazioni in ritardo si utilizzerà il seguente algoritmo:

  1. Ordinare le lavorazioni secondo la regola EDD
  2. Calcolare i tempi di fine lavoro per ogni lavorazione fino a quando non di verifica un ritardo, se non vi sono ritardi passare alla fase 4 altrimenti si sposta lavorazione in un elenco a parte
  3. Si toglie dalla sequenza la lavorazione dell’elenco il cui tempo di processo è più lungo e si torna alla fase 2
  4. La sequenza ottimale di ottiene ponendo prima le lavorazioni rimaste nella sequenza EDD, quindi quelli in ritardo, che possono essere ordinati secondo una sequenza qualsiasi.

Lascia un Commento

News