La regola Shortest Processing Time (SPT), tradotta come dei tempi di lavorazione più brevi, è un teorema elaborato nell'ambito della teoria della schedulazione per i problemi di sequenziamento della produzione. Applicata a un sistema costituito da una macchina singola, la regola afferma che il tempo di attraversamento medio dei lotti (mean flow time) è minimizzato sequenziando i lotti da lavorare in ordine non decrescente dei rispettivi tempi di lavorazione:

Tempo di attraversamento e tempo medio di attraversamento Nei problemi di sequenziamento, dato un insieme di n lotti da lavorare all'interno di un reparto produttivo, si utilizzano le seguenti grandezze: : il generico lotto k-esimo estratto dall'insieme degli n lotti da lavorare; : l'istante in cui il lotto k-esimo è disponibile in reparto per la lavorazione; : il tempo di attesa del lotto k-esimo tra l'ultimazione della lavorazione i-1 e l'inizio della lavorazione successiva i; se le lavorazioni da effettuarsi sul lotto sono in numero m, il tempo di attesa totale è pari alla somma dei tempi di attesa delle m operazioni:

: il tempo necessario per la lavorazione i-esima sul lotto k-esimo, comprensivo, generalmente, sia del tempo di attrezzaggio sia del tempo di movimentazione del lotto verso la macchina che dovrà effettuare la lavorazione i.

Si definisce flow time (o tempo di attraversamento), , del generico lotto l'intervallo di tempo intercorrente tra l'istante in cui il lotto k-esimo è pronto a ricevere la prima lavorazione e l'istante in cui termina la sua ultima lavorazione:

dove è il tempo di completamento del lotto k, o completion time.

Assegnati n lotti da lavorare all'interno del sistema produttivo in esame, si definisce mean flow time (tempo di attraversamento medio, o average flow time), , la media aritmetica dei tempi di attraversamento dei singoli lotti:

Dimostrazione Dati n lotti da lavorare all'interno di un sistema produttivo costituito da una macchina singola, per un'assegnata sequenza di questi n lotti il mean flow time si può esprimere come:

Osservando che è costante per qualsiasi ordinamento della sequenza adottata, per minimizzare è necessario minimizzare : scegliendo una sequenza tale da rendere il più piccolo possibile, anche la loro somma verrà minimizzata.

Per indicare la posizione assegnata a un generico lotto k-esimo in una sequenza ordinata si adotta la seguente convenzione: le parentesi quadre denotano la posizione nella sequenza (ad esempio, =5 significa che il lotto numero 5 è assegnato alla posizione 7), mentre indica il tempo di lavorazione del lotto che occupa la posizione k-esima.

Poiché il primo lotto inizia subito, si pone . Il lotto in seconda posizione dovrà attendere che il lotto precedente venga lavorato: . Scegliendo come lotto in posizione quello con il tempo di lavorazione più breve, si minimizza . Nella posizione si ha , ovvero il terzo lotto dovrà attendere che e vengano lavorati: la scelta al passo precedente resta ottimale, mentre come secondo lotto si sceglierà quello con il tempo di lavorazione più breve tra quelli rimanenti.

Procedendo in questo modo si costruisce una sequenza in cui il lotto da lavorare in posizione [i] presenta il tempo di lavorazione più breve tra quelli ancora da lavorare. La sequenza così ottenuta, detta SPT (Shortest Processing Time), minimizza .

Note

Bibliografia

Categoria:Ricerca operativa Categoria:Ottimizzazione