Earliest Due Date
# Earliest Due Date

Il teorema noto come dei Tempi di Consegna il prima possibile o Earliest Due Date elaborato nella Teoria della schedulazione afferma che il massimo ritardo tra i lotti-maximum job tardiness è minimizzato sequenziando i lotti in ordine tale che:

$d_{[1]}\leq \ d_{[2]}\leq \$ $...\leq \ d_{[n]}$.

dove $d_{[i]}$ è la data di consegna del lotto che verrà lavorato in posizione i-esima.

L'ambiente produttivo cui si riferisce il risultato sopra esposto è un reparto assimilabile ad una macchina singola che deve lavorare n lotti cui sono assegnate le date di consegna..

Nel seguito per indicare la posizione assegnata ad un generico lotto k-esimo in una sequenza ordinata di lotti si adotta la seguente convenzione di scrittura: si utilizzeranno le parentesi quadre per denotare la posizione scelta nella sequenza. Ad esempio il simbolo [7]=5 significa che il lotto numero 5 è assegnato alla posizione 7 nella sequenza; così come $p_{[k]}$ indicherà il tempo di lavorazione del lotto che occupa la posizione k-esima nella sequenza.

Si consideri una sequenza S di lotti che non sono stati ordinati con la regola delle date di consegna crescenti, ciò significa che esiste una qualche posizione i per cui si ha $d_{[i]}>\ d_{[i+1]}$.

Ora si consideri un'altra sequenza S' che differisce dalla sequenza S per il fatto che è stata ottenuta scambiando la posizione dei due lotti $L_{[i]}$ ed $L_{[i+1]}$. La nuova sequenza S' presenta gli stessi lotti della S nelle prime i-1 posizioni e nelle n-i-1 posizioni, sicché questi n-2 lotti iniziano e terminano la lavorazione nello stesso momento. Ricordando che la Lateness di un lotto j, in simboli $L_{j}$, è la differenza tra il tempo di completamento e la data di consegna, $L_{j}=C_{j}-d_{j}$, è chiaro che la lateness degli n-2 lotti in esame è la stessa sia per la sequenza S che per S', $L=L'$.

Ciò per cui differiscono S ed S' sono le lateness dei due lotti i e i+1 che sono stati scambiati. Si vuole verificare che la massima latenenss $L_{max}=max\left\{L;L_{[i]};L_{[i+1]}\right\}$ per la sequenza S è non inferiore alla massima lateness $L_{max}'=max\left\{L';L_{[i]}';L_{[i+1]}'\right\}$ per la sequenza S'. Se infatti si dimostra vera la tesi per cui

$L_{max}\geq \ L_{max}'$

significa che per ogni sequenza S scelta esiste un potenziale miglioramento scambiando coppie adiacenti di lotti secondo l'ordine naturale delle date di consegna. In altri termini, qualsiasi sequenza può essere sempre riordinata secondo date di consegna crescenti senza peggiorare la massima lateness.

Indicato per brevità di notazione $t=\sum _{j=1}^{i-1}p_{[j]}$ sia per S che per S', si avrà come lateness per i primi i lotti della sequenza S

$L_{[i]}=t+p_{[i]}-d_{[i]}$ e come lateness per i primi i+1 lotti della sequenza S

$L_{[i+1]}=t+p_{[i]}+p_{[i+1]}-d_{[i+1]}$.

Per S' invece sarà:

$L_{[i+1]}'=t+p_{[i+1]}-d_{[i+1]}$ e

$L_{[i]}'=t+p_{[i+1]}+p_{[i]}-d_{[i]}$.

Poiché $d_{[i]}>\ d_{[i+1]}$ si deduce per confronto che $L_{[i+1]}>L_{[i]}'$, inoltre poiché $p_{j}>0$ è vero che $L_{[i+1]}>L_{[i+1]}'$.

Pertanto le due disequazioni appena scritte portano a concludere che certamente si ha

$L_{[i+1]}>max\left\{L_{[i]}';L_{[i+1]}'\right\}$.

Ora per definizione di massimo è sempre vera a priori la seguente catena di disuguaglianze

$L_{max}=max\left\{L;L_{[i]};L_{[i+1]}\right\}\geq \ max\left\{L_{[i]};L_{[i+1]}\right\}\geq \ L_{[i+1]}$.

Poiché in precedenza si è evidenziato che $L_{[i+1]}>max\left\{L_{[i]}';L_{[i+1]}'\right\}$ è lecito scrivere per la proprietà transitiva della relazione d'ordine che

$L_{max}\geq \ max\left\{L_{[i]}';L_{[i+1]}'\right\}$.

Nuovamente si ha

$max\left\{L_{[i]}';L_{[i+1]}'\right\}\geq \ max\left\{L;L_{[i]}';L_{[i+1]}'\right\}$.

Inoltre ricordando che $L=L'$ si può scrivere

$max\left\{L;L_{[i]}';L_{[i+1]}'\right\}=\ max\left\{L';L_{[i]}';L_{[i+1]}'\right\}=L_{max}'$

ne consegue che

$L_{max}\geq \ L_{max}'$

e dunque rimane dimostrata la tesi.

La minimizzazione della massima tardiness è conseguenza diretta della definizione di lateness: $T_{max}=max\left\{0;L_{max}\right\}$.

