Shortest Processing Time

Si tratta del Teorema noto come dei Tempi di Lavorazione più brevi / Shortest Processing Time elaborato nella Teoria della schedulazione che afferma che il tempo di attraversamento medio-average flow time, ${\bar {F}}\$, è minimizzato sequenziando i lotti in ordine non decrescente dei tempi di lavorazione $p_{[1]}\leq \ p_{[2]}\leq \$ $...\leq \ p_{[n]}$.

Dati n lotti da lavorare all'interno del sistema produttivo costituito da una macchina singola, per un'assegnata particolare sequenza di questi n lotti si ha come mean flowtime: ${\bar {F}}\ ={\frac {1}{n}}\sum _{i=1}^{n}F_{i}=C_{k}={\frac {1}{n}}\sum _{i=1}^{n}\left(A_{k}+p_{k}\right)={\frac {1}{n}}\sum _{i=1}^{n}A_{k}+{\frac {1}{n}}\sum _{i=1}^{n}p_{k}$

Osservando che $\sum _{i=1}^{n}p_{k}$ è costante per qualsiasi ordinamento della sequenza adottata, si deduce che per minimizzare ${\bar {F}}\$ è necessario minimizzare $\sum _{i=1}^{n}A_{k}$. È chiaro che se si sceglie una sequenza tale da rendere $A_{k}$ il più piccolo valore possibile allora anche la loro somma verrà minimizzata.

Nel seguito per indicare la posizione assegnata ad un generico lotto k-esimo $L_{k}$ 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.

Poiché per il primo lotto $L_{[1]}$ incomincia subito, si può porre $A_{[1]}=0$.

Poiché il lotto nella seconda posizione della sequenza $L_{[2]}$ dovrà attendere che il lotto che lo precede venga lavorato, si ha $A_{[2]}=p_{[1]}$. Se si sceglie come lotto in posizione [1] il lotto che presenta il più breve tempo di lavorazione allora si minimizzerà $A_{[2]}$.

Nella posizione [3] si ha $A_{[3]}=p_{[1]}+p_{[2]}$, ovvero il terzo lotto $L_{[3]}$ dovrà attendere che $L_{[1]}$ e $L_{[2]}$ vengano lavorati. Per minimizzare $A_{[3]}$ si sceglieranno i lotti che presentano il più breve tempo di lavorazione: dunque il lotto scelto al passo precedente è ottimale, mentre come secondo lotto si sceglierà quello che presenta il tempo di lavorazione più breve tra quelli rimanenti.

Procedendo in questo modo si costruisce una sequenza di lotti in cui il lotto da lavorare in posizione [i] presenta il tempo più breve di lavorazione tra quelli ancora da lavorare. Come risultato la sequenza scelta SPT – Shortest Processing Time minimizza ${\bar {F}}\$.

Bibliografia

• Simon French, Sequencing and scheduling: an introduction to the Mathematics of the Job-Shop, Great Britain: Ellis Horwood Limited, 1987