Earliest Due Date
Il teorema noto come dei Tempi di Consegna il prima possibile o Earliest Due Date[1] elaborato nella Teoria della schedulazione afferma che il massimo ritardo tra i lotti-maximum job tardiness è minimizzato sequenziando i lotti in ordine tale che:
.
![{\displaystyle d_{[1]}\leq \ d_{[2]}\leq \ }](https://wikimedia.org/api/rest_v1/media/math/render/svg/383d9909a21d03435e4b8384ec92e66a6c58c9ec)
![{\displaystyle ...\leq \ d_{[n]}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ce4a8b41ba8a223bc6ad078760a3240382265e27)
dove è la data di consegna del lotto che verrà lavorato in posizione i-esima.
![{\displaystyle d_{[i]}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d6fd6d007569b79a08e3d8c1f21dfbca699ede92)
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.[Nota 1].
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 indicherà il tempo di lavorazione del lotto che occupa la posizione k-esima nella sequenza.
![{\displaystyle p_{[k]}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3de4040fe4aab804be8734f77da390fb2be4ee27)
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 .
![{\displaystyle d_{[i]}>\ d_{[i+1]}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5cc39dfd1f93dbbe624de5637f00820cbe50bcee)
Ora si consideri un'altra sequenza S' che differisce dalla sequenza S per il fatto che è stata ottenuta scambiando la posizione dei due lotti ed . 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 , è la differenza tra il tempo di completamento e la data di consegna, , è chiaro che la lateness degli n-2 lotti in esame è la stessa sia per la sequenza S che per S', .
![{\displaystyle L_{[i]}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/04b985bb4130fa941caf62c689b0a16ea75a1f7a)
![{\displaystyle L_{[i+1]}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e03d664a9c33495a4e177b8bdca3bbfd0fb782ea)
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 per la sequenza S è non inferiore alla massima lateness per la sequenza S'. Se infatti si dimostra vera la tesi per cui
![{\displaystyle L_{max}=max\left\{L;L_{[i]};L_{[i+1]}\right\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1acd8720e9878e8829a90579a9aeb7cc09aca1af)
![{\displaystyle L_{max}'=max\left\{L';L_{[i]}';L_{[i+1]}'\right\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/852bcee33b7abfe3f2d8a7fc9b813d5a8a0b3833)
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 sia per S che per S', si avrà come lateness per i primi i lotti della sequenza S
![{\displaystyle t=\sum _{j=1}^{i-1}p_{[j]}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/51913e0a746cc467358045cd0f0bfcefe3b9d115)
e come lateness per i primi i+1 lotti della sequenza S
![{\displaystyle L_{[i]}=t+p_{[i]}-d_{[i]}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/29a41ed7a7d0278f8bbcbdd2fe4eab3913987ab9)
.
![{\displaystyle L_{[i+1]}=t+p_{[i]}+p_{[i+1]}-d_{[i+1]}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/902cd69f9093075628c7d5dddf9b78f586d80055)
Per S' invece sarà:
e
![{\displaystyle L_{[i+1]}'=t+p_{[i+1]}-d_{[i+1]}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9805a4d1b0f8b76ac7eee4352c3de8354aee0503)
.
![{\displaystyle L_{[i]}'=t+p_{[i+1]}+p_{[i]}-d_{[i]}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/89f63c33ce4b723893d2c240c5d6a2c16bcc64ed)
Poiché si deduce per confronto che , inoltre poiché è vero che .
![{\displaystyle L_{[i+1]}>L_{[i]}'}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d4ffb4ca00c4e6ec56f38108b4156a172d8b5abb)
![{\displaystyle L_{[i+1]}>L_{[i+1]}'}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4c46c9ab27ef20116fbb59dae57e657a9bfeee9a)
Pertanto le due disequazioni appena scritte portano a concludere che certamente si ha
.
![{\displaystyle L_{[i+1]}>max\left\{L_{[i]}';L_{[i+1]}'\right\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d572961b6e148e06389f9dc863e74302183f64e5)
Ora per definizione di massimo è sempre vera a priori la seguente catena di disuguaglianze
.
![{\displaystyle L_{max}=max\left\{L;L_{[i]};L_{[i+1]}\right\}\geq \ max\left\{L_{[i]};L_{[i+1]}\right\}\geq \ L_{[i+1]}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a05fa236c160fcc2f851fac0b51fd2a3a534b2d5)
Poiché in precedenza si è evidenziato che è lecito scrivere per la proprietà transitiva della relazione d'ordine [Nota 2] che
.
![{\displaystyle L_{max}\geq \ max\left\{L_{[i]}';L_{[i+1]}'\right\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9dcb53a666608dc24d001e9d36d9f58a74a6d76c)
Nuovamente [Nota 3] si ha
.
![{\displaystyle max\left\{L_{[i]}';L_{[i+1]}'\right\}\geq \ max\left\{L;L_{[i]}';L_{[i+1]}'\right\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/020f83fa60a5d524ac0983cf43ddb06ddd073eee)
Inoltre ricordando che si può scrivere
![{\displaystyle max\left\{L;L_{[i]}';L_{[i+1]}'\right\}=\ max\left\{L';L_{[i]}';L_{[i+1]}'\right\}=L_{max}'}](https://wikimedia.org/api/rest_v1/media/math/render/svg/eb2ccadfb7e02daaae4f0c571a5e2882e68f9da1)
ne consegue che
e dunque rimane dimostrata la tesi.
La minimizzazione della massima tardiness è conseguenza diretta della definizione di lateness: .
Note modifica
- ^ Il problema di sequenziamento per una macchina singola consiste nel determinare l'ordine con cui gli n lotti devono essere lavorati in modo tale da soddisfare il più possibile i tempi di consegna promessi. Tra i vari criteri di prestazione adottabili, il criterio di valutazione della maximum job tardiness, è quello che meglio si presta a valutare la bontà di una sequenza.
- ^ La proprietà transitiva di un relazione d'ordine > è la seguente: se A > B e B > C allora A > C.
- ^ Si osservi infatti che in S' è .
![{\displaystyle L<L_{[i]}'<L_{[i+1]}'}](https://wikimedia.org/api/rest_v1/media/math/render/svg/96c1d87bcf2278264b36efd55191e27ce9945c4e)
Riferimenti modifica
Bibliografia modifica
- (EN) Richard W. Conway, William L. Maxwell e Louis W. Miller, Theory of scheduling, USA: Dover Publications, 2003.
- (EN) J.R. Jackson, Scheduling a Production Line to Minimize Maximum Tardiness, in Management Sciences Research Project, Research Report n. 43, UCLA, gennaio 1955.
