Sintesi programmazione e controllo della produzione

WIP.

Algoritmo SPT Shortest process time (minimo completamento medio):

Per semplicità si considerano n operazioni con tempo di processamento pari a e ogni job include una sola

operazione. L’algoritmo di SPT ha come obiettivo quello di ridurre al minimo il tempo di completamento

medio: : = min

Il minimo tempo di completamento medio rispetto a tutte le sequenze S realizzabili è quello dato dalla

sequenza SPT ottenibile ordinando i lavori per tempi di processamento crescenti. Con questo algoritmo si

diminuiscono le attese, dunque il vantaggio principale è economico. Minimizzare il tempo di

, e

completamento medio implica la minimizzazione del flusso medio dell’attesa media del ritardo

medio dal momento che

= + + = + + = +

Se il tempo di rilascio è 0, minimizzare C significa minimizzare Wi dal momento che il tempo di

processamento è un valore fisso dipendente dalla schedulazione.

1 1 1

=1 =1 =1

∑ ∑ ∑

= − = = ( − ) = −

(con r si indica il ritardo)

Dove d è un valore costante dunque minimizzare C medio significa

anche minimizzare L medio, con L che può avere segno positivo o

negativo a seconda se è un anticipo o un ritardo

Algoritmo EDD: Earlest due date

Ora l’obiettivo della schedulazione è effettuare il sequenziamento in modo tale che tra tutti i lavori, quello

più in ritardo è il minimo possibile

= max =

r

: min = min max

r

L’obiettivo principale dunque è quello di effettuare le consegne più possibile in tempo. È un criterio di

efficacia ma con l’anticipo diventa anche un vantaggio economico. Si ordinano i lavori in funzione della data

di scadenza, metto prima i lavori con data anticipata, indipendentemente dalla loro lunghezza. Rendere

minimo il massimo ritardo equivale a dire massimizzare il minimo anticipo.

Algoritmo FCFS: First come first served

I job vengono lavorati secondo l’ordine di arrivo al centro di lavoro

Algoritmo CR: critical ratio

I job vengono lavorati secondo il rapporto CR= data di consegna/tempo di lavorazione, dal più piccolo al più

grande.

Algoritmo di moore:

L’obiettivo di questo algoritmo è rendere minimo il numero di job in ritardo. Si decide dunque di svolgere

internamente i lavori per cui non si realizza ritardo e esternalizzare quei job che non si riesce a concludere

entro la data di scadenza e per cui si preferisce quindi pagare un prezzo maggiore per il loro svolgimento

piuttosto di pagare la penale per il ritardo di consegna. Sequenza operazioni algoritmo:

1. Si ordinano i job secondo l’algoritmo EDD (cioè in ordine di due date) ottenendo una prima

sequenza 1

2. Si individua il primo lavoro in ritardo nella sequenza corrente definita

()

3. Si analizzano tutti i tempi di processamento dei job dai non in ritardo al primo in ritardo e si

individua quello più lungo ()

4. Si definisce una nuova sequenza escludendo e si ritorna al passo 2. Se non esiste nessun

+1 ()

lavoro in ritardo mi fermo cioè continuo in maniera iterativa finché non si arriva a generare ritardo

0.

Esempio:

JOB

JOB

JOB

5 2 3 2 0 5 2 3 2 0

1 5 10 3 6 7 8 1 2 3 8 5 0

2 3 8 2 3 8 11 4 4 9 9 0

3 6 7 4 4 9 15 1 5 10 14 4

4 4 9 1 5 10 20

5 2 3

= 5,2,4. Mentre 3,1 li esternalizzo

Algoritmo di Lawer: generalizzazione metodo EDD

In verità i vari job non sempre sono svincolati ma possono avere delle relazioni di precedenza. Finora i job

sono stati sempre considerati indipendenti. Per poter schedulare lavorazioni con vincoli di precedenza si

può far uso dell’algoritmo di Lawer che ha come obiettivo quello di minimizzare la massima penalità.

Individuate le relazioni di precedenza, si procede prima a fissare quei job svincolati. A tal fine si introduce la

funzione: = ∙

Funzione non decrescente dei completamenti , definita come prodotto tra attesa del job iesimo per la

tardness, differenza tra la somma totale dei tempi di processamento dei job, di cui ancora non è stata

definita la posizione, e la data prevista di consegna del job i-esimo.

= ∑ = −

=1

( )

min max à

Creo poi un insieme di lavori che non hanno successori e ne calcolo il valore assunto dalla funzione ,

quello che assume valore della funzione minore viene fissato come ultimo.

=1

∑

=

1. Calcolo della

2. Individuo i lavori senza successori e calcolo il valore della per questi lavori

3. Fisso in ultima posizione il lavoro che ha valore minimo di , ciò dà minima penalità

4. Aggiorno il tempo di completamento T sottraendo al valore precedenza calcolato il tempo di

processamento del lavoro fissato in ultima posizione

5. Si ritorna al punto 2 e si continua in maniera iterativa fino a fissare tutti i job

Esempio: =1

∑

JOB = = 15

1)

(15

= = 4 − 12) = 12

1 8 4 2 5 5 5

{5,6 }

→ {

2)

2 12 3 1 = = 3(15 − 13) = 6 ← à

6 6 6

3 8 2 2 3) 6 =1

∑

= = 15 − 1 = 14

4 8 4 1 4)

5 12 1 4 (14

= = 4 − 12) = 8

5 5 5

6 13 1 3 {5,3,4} = = 2(14 − 8) = 12

→ {

5) 3 3 3

= = 1(14 − 8) = 6 ← à

4 4 4

Si continua così in maniera iterativa fino a fissare tutti i job.

Algoritmo di Jhonson:

Questo algoritmo viene implementato quando si devono effettuare lavorazioni su più macchine. Finora

infatti la macchina era unica ora si definiscono le seguenti ipotesi di partenza:

 Numero macchine=2

 Job indipendenti tra loro, non ci sono relazioni di precedenza

 →

Schema di lavorazione fisso

1 2

 Tempi di lavorazione dei job indipendenti e costanti

Si definiscono le seguenti grandezze:

= =

1 2

Si costruisce il sequenziamento delle attività partendo dalle posizioni esterne e muovendosi verso il centro.

Il sequenziamento viene fatto con l’obiettivo di ridurre le attese a monte e a valle, cioè rendere l’attesa

media più piccola possibile. Data la tabella dei JOB, si individua di volta in volta il tempo di lavorazione più

piccolo e se questo corrisponde allora il Job viene posto in testa, se corrisponde a viene posto in

1 2

coda. Esempio:

< >

JOB

1 2 1

5 5

< >

4 3 2

8 9

2 7

6 8

12 15

Con il diagramma di Gantt verifico le finestre temporali in cui ho inattività ( lì ad esempio si può inserire

manutenzione) e si può determinare il makespan complessivo:

Alle stesse conclusioni si può giungere in forma tabellare, si sviluppa la forma tabellare per le

sottosequenze:

D A E C F B D E C F A B

2 5 6 8 12 4 2 6 8 12 5 4

1 1

2 7 13 21 33 37 2 8 16 28 33 37

1 1

7 5 8 9 15 3 7 8 9 15 5 3

2 2

9 14 22 31 48 51 9 17 26 43 48 51

2 2

Stringa per descrivere il tipo di schedulazione: ///

° /° ℎ/ /

: /1// ; : /1//, , , ; : /1//° ;

: /1// ; : /2//

Se le macchine su cui lavorano i job sono 3 si utilizza Jhonson che permetterà di selezionare tra le sequenze

possibili quella avente makespan minore. Si ci riconduce a due macchine individuando la macchina con

tempi di processamento minore e utilizzando l’algoritmo di Jhonson sulle macchine rimanenti oppure

sommando i tempi di processamento di una macchina alle altre due e calcolando l’effetto congiunto.

Esempio: = 3, 4, 1, 2, 5

1

[ ]:

; {

JOB 1 3

1 2 3 4 5 = 4, 3, 1, 2, 5

2

6 9 7 7 6

JOB

1 1 2 3 4 5

2 1 5 3 4 + 8 10 12 10 10

2 1 2

[ ]:

+ ; = 3,4,1,5,2

1 2 3 3 + 6 4 11 9 5

4 3 6 6 1 3 2

3

Si va poi a verificare qual è la sequenza a t minore, confrontando il makespan totale e i tempi morti tra le

operazioni, in questo esempio si evidenzia come s3 termini prima e abbia meno tempi morti:

S3 3 4 1 2 5

S1 3 4 1 2 5 7 7 6 9 6

7 7 6 9 6 1

1 7 14 20 29 35

7 14 20 29 35

1

1 5 3 2 4 1

5 3 2 1 4 2

2 12 17 22 30 36

12 17 22 30 39

2

2 6 6 4 1 3

6 6 4 3 1 3

3 18 24 28 31 39

18 24 28 33 40

3

3

Schedulazione per Job shop:

Se si devono process