Algoritmo SPT

ago
2010
11

scritto da | on | Nessun commento

Nella schedulazione di attività esistono diversi algoritmi che hanno come risultato finale l’ordinamento delle attività da eseguire in base alle esigenze di ottimizzazione dell’azienda. In questo post consideriamo l’algoritmo più elementare ovvero il Shortest Processing Time che ha come obiettivo il tempo medio di completamento delle operazioni. Consideriamo per il nostro esempio n ordini di produzione che devono essere evasi nella settimana successiva (hanno tutti data di consegna successiva alla settimana) ognuno dei quali ha un tempo ciclo differente T. L’algoritmo SPT consiste nell’ordinare gli ordini di produzione in base al tempo ciclo in maniera crescete. Consideriamo i seguenti ordini:

Ordine Minuti
A 235
B 175
C 210
D 140
E 160
F 165
G 130
H 125
I 155

Procediamo al calcolo del tempo medio di completamento in questo modo

Ordine Minuti cumulato
H 125 125
G 130 255
D 140 395
I 155 550
E 160 710
F 165 875
B 175 1050
C 210 1260
A 235 1495
Tempo medio 9 6715 746,11

In questo caso abbiamo supposto che i tempi ciclo siano deterministici, in realtà è molto probabile che i tempi reali siano vicini a quelli ciclo ma per calcolare il tempo medio di completamento è opportuno utilizzare delle variabili normali che hanno come media il tempo ciclo ed come deviazione standard le variazioni osservate nelle precedenti lavorazioni. Anche utilizzando variabili casuali normali per i tempi ciclo l’algoritmo SPT garantisce il tempo medio di completamento minore.

Lascia un Commento

News