Modello Macchina Singola
 Minimizzazione Makespan ossia Tempi di Set-up
 Metodo Euristico: Modello di Karg e Thompson
 Ipotesi del Modello:
 N job indipendenti
 date di consegna non rilevanti
 non è ammessa preemption
 tempi di set-up dipendenti dalla sequenza dei jobs
Modello Macchina Singola
Modello di Karg e Thompson
 Passi dell’Algoritmo:
 Step 1. Selezionare Casualmente due jobs.
 Step 2. Selezionare un nuovo job e provare a disporlo
nella sequenza corrente
 Step 3. Per ogni posizione provata calcolare il set-up
complessivo
 Step 4. Allocare il job nella posizione che garantisce i più
bassi tempi di set-up
 Step 5. Se vi sono ancora job da allocare vai al passo 2.
Altrimenti fine.
Esempio Algoritmo Euristico di Karg e
Thompson
Siano dati 7 Jobs: J1, J2, J3, J4, J5, J6, J7, con i tempi di set-up:
1
2
3
4
5
6
7
1
0
3
2
2
2
1
3
2
2
0
4
2
5
2
2
3
3
1
0
3
1
2
1
4
2
2
2
0
1
1
2
5
3
2
4
3
0
1
1
6
5
2
2
1
1
0
1
7
6
3
2
2
2
2
0
Step 1. Si sceglie casualmente la sequenza (J2,J3). Set-up=1
Step 2. Si sceglie J5 e si prova a disporlo:
(J5, J2, J3)->Set-up=5+1=6
(J2, J5, J3)-> Set-up=2+1=3
(J2, J3, J5)-> Set-up=1+4=5
Step 3. Si sceglie la sequenza (J2,J5,J3)
Modello Macchina Singola
Modello di Karg e Thompson
 Complessità computazionale bassa:
N  ( N  1)
i
 N!

2
i 1
N
 Limite: Soluzione dipendente dalla scelta della
coppia iniziale di job e dall'ordine con cui vengono
inseriti gli altri job.
 Soluzione: E’ possibile rieseguirlo più volte a partire
da coppie di jobs diverse
Modello Macchina Singola
 Minimizzazione del numero di Job in Ritardo
 Metodo Euristico: Modello di Hodgson
 Ipotesi del Modello:
 N job indipendenti
 date di consegna sono note e sono rilevanti
 non è ammessa preemption
 tempi di set-up nulli o indipendenti dalla sequenza e
quindi inclusi nei tempi di lavorazione
Modello Macchina Singola
Modello di Hodgson
 Dati dell’Algoritmo:
 Input: Tempi di lavorazione dei job, Date di Consegna
 Outputs:
E={Sequencing dei jobs non in ritardo}
L={l'insieme dei job in ritardo, da sequenziare in
qualsiasi ordine dopo i jobs relativi all'insieme E}
 Variabili Intermedie: E*, L*
Modello Macchina Singola
Modello di Hodgson
 Passi dell’Algoritmo:
 Step 1. Creare l'insieme E*={elenco dei job per data di
consegna crescente}, L*={}
 Step 2. In base all'ordine di sequenziamento individuato in
E*, determinare i tempi di completamento di ciascun job,
ed individuare i job in ritardo
 Step 3. Se in E* non vi sono job in ritardo allora E= E* e
L=L*. STOP.
 Se in E* vi è almeno un job in ritardo, sia k il primo job in
ritardo nella sequenza.
 Step 4. Identificare il job con tempo di lavorazione più
alto entro i primi k job (job k compreso) della sequenza
E*. Rimuovere questo job e metterlo in L*. GOTO Step 2.
Esempio dell'Algoritmo Euristico di Hodgson
Job
tj
dj
1
1
2
2
5
7
3
3
8
4
9
13
5
7
11
 Step 1. E*={1,2,3,5,4}, L*={}
 Prima Iterazione:
 Step 2. Job 1 (1), Job 2 (6), Job 3 (9), Job 5 (16), Job 4 (25)
 Step 3. Primo job in ritardo, Job k=3
 Step 4. E*={1,3,5,4}, L*={2}
 Seconda Iterazione:
 Step 2. Job 1 (1), Job 3 (4), Job 5 (10), Job 4 (19).
 Step 3. Primo job in ritardo, Job k=4
 Step 4. E*={1, 3, 5}, L*={2, 4}
Esempio dell'Algoritmo Euristico di Hodgson
Job
tj
dj
1
1
2
2
5
7
3
3
8
4
9
13
5
7
11
 Terza Iterazione:
 Step 2. Job 1 (1), Job 3 (4), Job 5 (10)
 Step 3. Nessun Job in ritardo. STOP
 Soluzione di Schedulazione E={1,3,5}, L={2,4}
 Possibili schedulazioni: 1,3,5,2,4 o 1,3,5,4,2
Modello Macchina Singola
 Minimizzazione del Flowtime Medio
 Ipotesi del Modello
 N job indipendenti
 date di consegna non rilevanti
 non è ammessa preemption
 tempi di set-up sono nulli od indipendenti dalla sequenza
 Metodo di Ottimizzazione Algoritmica
 I jobs vengono ordinati in ordine crescente in base ai
tempi di lavorazione (complessità O(N2))
 Soluzione Ottima
 Regola di Carico per i Job Shop
Modello Macchine Parallele Identiche
 Minimizzazione Makespan
 Metodo di Ottimizzazione Algoritmica: Modello di
Mc Naughton
 Ipotesi del Modello:
 M macchine identiche parallele
 N job indipendenti
 date di consegna non sono rilevanti
 è ammessa preemption
 tempi di set-up nulli o indipendenti dalla sequenza e
quindi inclusi nei tempi di lavorazione
 un job non può essere lavorato contemporaneamente su
più macchine
Modello Macchine Parallele Identiche
Modello di Mc Naughton
 Risultato teorico su cui si basa la soluzione
algoritmica:
 sotto le ipotesi del modello, il minimo makespan è:
N
tj
M*  max{
j1
M
, max{ t j}}
 Caratteristiche dell'Algoritmo:
 L'algoritmo ammette più di una soluzione
 In ogni caso la soluzione fornita è ottima
Modello Macchine Parallele Identiche
Modello di Mc Naughton
 J1(5), J2(6), J3(4), J4(3)
N
M*  max{
M1
M2 J2
t
j1
M
j
, max{ t j}}  max{ 9,6}  9
J2
J3
J1
J4
9
Modello Macchine Parallele Identiche
Modello di Mc Naughton
 J1(2), J2(11), J3(4), J4(3)
N
M*  max{
M1
J3
M2
J2
t
j1
M
j
, max{ t j}}  max{10,11}  11
J2
J1
J4
11
Modello Macchine Parallele Identiche
Modello di Mc Naughton
 Passi dell'Algoritmo:
 Step 1. Selezionare un job da iniziare sulla macchina 1 al
tempo 0
 Step 2. Se la macchina corrente è occupata per un tempo
pari a M*, allora terminare la schedulazione sulla
macchina, e GOTO Step 3. In caso contrario, alla fine
della lavorazione corrente, segliere uno tra i job rimasti e
schedularlo sulla stessa macchina, senza lasciare tempi
morti. GOTO Step 2.
 Step 3. Se tutti i job sono stati schedulati, ossia non vi
sono più macchine, allora STOP. Altrimenti, asegnare il
tempo di processo rimanente del job su cui si è operata la
preemption, alla macchina successiva a partire dall'istante
0.
Esempio dell'Algoritmo di Mc Naughton
 J1(5), J2(6), J3(4), J4(3)
 due Macchine
 Una soluzione fornita dall'algoritmo:
J2
J3
J2
J1
J4
9
Modello Macchine Parallele Identiche
 Minimizzazione Makespan in assenza di preemption
 Metodo di Ottimizzazione Analitico
 Ipotesi del Modello:
 M macchine identiche parallele
 N job indipendenti
 date di consegna non sono rilevanti
 non è ammessa preemption
 tempi di set-up nulli o indipendenti dalla sequenza e
quindi inclusi nei tempi di lavorazione
Modello Macchine Parallele Identiche
 Soluzione: Programmazione Lineare Intera:
Assenza di
preemption
N

 y   t j  x ji  0
j1

 M
 x ji  1
 i 1
minimizzar e ( y)


1 i  M
1 j N
dove:
y=Makespan
xji=1 se il job j è assegnato alla macchina i, xji=0 altrimenti
tj=tempo di lavorazione del job j.
M+N vincoli
M*N+1 variabili
Flow Shop
 Minimizzazione del Makespan
 Metodo Euristico: Algoritmo Euristico di Campbell,
Dudek e Smith
 Si basa sull’algoritmo di ottimizzazione di Johnson
 Metodo di Ottimizzazione Algoritmico Specifico
Flow Shop
Modello di Johnson
 Il sistema è un flow shop con:
 2 macchine
 N job
 date di consegna non rilevanti
 non è ammessa preemption dei job
 tempi di set-up nulli o indipendenti dalla sequenza e
dunque inglobati nei tempi di lavorazione
 non sono ammessi sorpassi
 Obiettivo: Minimizzazione del Makespan
 Metodo di Ottimizzazione Algoritmico: basata su
Teorema di Johnson
Teorema di Johnson
 Ipotesi: Dato un Routing fisso:
 Macchina1, Macchina2
 Teorema: Il job X precede il job Y in una sequenza
ottima se viene verificata la condizione:
min{tX1,tY2}min{tX2,tY1}
 tji= tempo di lavorazione del job j sulla macchina i
Esempio Teorema Johnson
J1=(M1(1),M2(2))
J2=(M1(3),M2(6))
M1 J1
M2
M1
J2
J1
M2
J2
J2
J1
J2
J1
10
11
min{t11,t22}=min{1,6}=1
min{t21,t12}=min{3,2}=2
min{t12,t21}=min{2,3}=2
min{t22,t11}=min{6,1}=1
min{tX1,tY2}min{tX2,tY1}
min{tX1,tY2}min{tX2,tY1}
min{t11,t22}<min{t12,t21}
min{t21,t12}>min{t22,t11}
Esempio Teorema Johnson
J1=(M1(8),M2(2))
J2=(M1(5),M2(1))
M1
M2
M1
J2
J1
J1
J2
14
M2
J2
J1
J2
J1
15
min{t11,t22}=min{8,1}=1
min{t21,t12}=min{5,2}=2
min{t12,t21}=min{2,5}=2
min{t22,t11}=min{1,8}=1
min{tX1,tY2}min{tX2,tY1}
min{tX1,tY2}min{tX2,tY1}
min{t11,t22}<min{t12,t21}
min{t21,t12}>min{t22,t11}
Algoritmo di Ottimizzazione di Johnson
 Step 0. Considerare un insieme S contenente tutti i job non
ancora schedulati. Inizialmente la sequenza di schedulazione è
SP={}
 Step 1. Trovare il minj {tj1,tj2} tra tutti i Job j di S (j=1,..,N)
 Step 2. Se il minimo tempo è sulla macchina 1, allora inserire
il relativo job j nella prima posizione disponibile della
sequenza di schedulazione SP. Goto 4
 Step 3. Se il minimo tempo è sulla macchina 2, allora inserire
il job j nell’ultima posizione disponibile della sequenza di
schedulazione SP
 Step 4. Rimuovere il job j da S. Se S non è vuoto goto 1.
Altrimenti fine.
 Le situazioni di parità vengono sempre gestite in modo
casuale
 L‘algoritmo fornisce sempre la soluzione ottima
Esempio Algoritmo di Johnson









J1=(M1(3),M2(6))
J2=(M1(5),M2(2))
J3=(M1(1),M2(2))
J4=(M1(6),M2(6))
J5=(M1(7),M2(5))
Step 0. S={J1,J2,J3,J4,J5}, SP={}
Step.1 minj {tj1,tj2}=t31 tra tutti i job j di S
Step.2. Il job 3 viene inserito nella prima posizione disponibile di SP={J3}
Step 3. S={J1,J2,J4,J5)
Step 4. minj {tj1,tj2}=t22
Step 5. Il job 2 viene inserito nell’ultima posizione disponibile di SP={J3,
…..,J2}
Step 6. S={J1,J4,J5)
Step 7. minj {tj1,tj2}=t12
Step 8. Il job 1 viene inserito nella prima posizione disponibile di SP={J3,
J1,……..,J2}
Esempio Algoritmo di Johnson
 Step 9. S={J4,J5)
 Step 10. minj {tj1,tj2}=t52
 Step.11. Il job 5 viene inserito nell’ultima posizione disponibile di SP={J3,
J1,……,J5,J2}
 Step 12. S={J4)
 Step 13. minj {tj1,tj2}=t41
 Step.11. Il job 4 viene inserito nella prima posizione disponibile di SP={J3,
J1,J4,J5,J2}
 Soluzione Finale: Makespan 24
M1
J1
J4
J5
J1
J4
J2
J3
M2
J3
J5
J2
Algoritmo Euristico di Campbell, Dudek e
Smith
 Il sistema è un flow shop con:
 M macchine
 N job
 date di consegna non rilevanti
 non è ammessa preemption dei job
 tempi di set-up nulli o indipendenti dalla sequenza
 non sono ammessi sorpassi
 Obiettivo: Minimizzazione del Makespan
Algoritmo Euristico di Campbell, Dudek e
Smith
 Si compone di L (L=1, 2,.., M-1) passi
 Ad ogni passo L, viene generata una schedulazione
completa per la quale viene calcolato il makespan
 Tra tutte le M-1 schedulazioni complete viene scelta
quella con il makespan migliore
Algoritmo Euristico di Campbell, Dudek e
Smith
 Calcolo della Schedulazione Completa al passo L:
 Applicazione dell’algoritmo di Johnson a N job e 2
macchine fittizie. I tempi di processamento dei job j
(j=1,..,N) sulle due macchine fittizie sono dati da:
L
t ' j1   t jk
k 1
L
t ' j2   t jM  k 1
k 1
j=1,..,N
Esempio Algoritmo Euristico di Campbell,
Dudek e Smith
J1=(M1(3),M2(9),M3(4))
J2=(M1(5),M2(8),M3(8))
J3=(M1(9),M2(3),M3(7))
J4=(M1(7),M2(5),M3(6))
J5=(M1(4),M2(12),M3(6))
 M=3, Numero di Passi L=1,2
Esempio Algoritmo Euristico di Campbell,
Dudek e Smith
 Passo L=1
1
t '11   t1k  3
k 1
1
t '21   t 2 k  5
k 1
1
1
t '12   t1M  k 1   t1 3 k 1  t1 3  4
k 1
k 1
1
t '12   t 2 3 k 1  t 2 3  8
k 1
t’31=9, t’32=7
t’41=7, t’42=6
t’51=4, t’52=6
 Applicando l’algoritmo di Johnson si ottiene:
 {J1, J5, J2, J3, J4}
 Makespan=53

Esempio Algoritmo Euristico di Campbell,
Dudek
e
Smith
Passo L=2
2
2
k 1
k 1
t '11   t1k  t11  t12  12 t '12   t1M  k 1  t13  t12  13
t’21=13, t’22=16
t’31=12, t’32=10
t’41=12, t’42=11
t’51=16, t’52=18
 Applicando l’algoritmo di Johnson si ottiene:
 { J1 , J2 , J5 , J4 , J3 }
 Makespan=51 M1 J1 J2 J5 J4
J3
 Soluzione Finale:
J1
J5
J2
M2
M3
J1
J2
J4 J3
J5
J4
J3
51
Job Shop
 Problema estremamente complesso
 Regole di Carico: Scegliere il job da caricare su una
macchina (quando si libera) tra quelli in attesa di
essere lavorati
 Differenza con i precedenti approcci: la regola di
carico non implica necessariamente un sequencing,
ma solo il dispatching del job con priorità più bassa o
più alta.
Job Shop
 Vantaggi dell’Approccio basato sulle Regole di
Carico:
 può essere applicato a qualunque impianto, con qualunque numero di
job, di macchine e qualunque tipo di routing
 può essere esteso anche ad altri modelli (flow shop, open shop, e
macchine singole/parallele)
 è semplice
 permette di personalizzare la valutazione delle priorità
 Svantaggi dell’Approccio basato sulle Regole di
Carico:
 difficoltà nella scelta delle priorità in relazione alla funzione da
minimizzare
 non è possibile avere una stima sugli istanti di completamento dei job
Regole di Carico
 Modalità Operative:
 Regole Statiche. I parametri su cui la regola opera
(assegnazione della priorità) non variano nel tempo
 Regole Dinamiche. Hanno senso solo in impianti
monitorati da calcolatore
 Visibilità
 Regole Locali. Utilizza informazioni relative unicamente
alla macchina su cui fare il dispatching
 Regole Globali. Utilizzano informazioni relative ad altre
macchine dell'impianto (lunghezza delle code di attesa,
tempo di processamento rimanente, etc.)
Regole di Carico
 Regole che considerano il tempo di lavorazione o il
tempo di set-up
 Regola SPT (Shortest Processing Time): viene caricato il
job che ha tempo di lavorazione più breve sulla macchina.
 Regola TSPT (Truncated SPT): viene applicata la regola
SPT, ma quando un job rimane in attesa in coda per un
tempo superiore di una soglia, esso viene caricato.
 Regole che considerano la data di consegna
 Regola EDD (Earliest Due Date): viene caricato il job che
ha data di consegna più vicina.
Regole di Carico
 Regole che considerano il tempo di accesso e la data
di consegna
 Regola S/OPN (Slack per Operation): viene caricato il job
che ha il minimo valore del rapporto:
data consegna  istante attuale - tempo lavorazion e rimanente
numero operazioni rimanenti
slack= data consegna - istante attuale - tempo lavorazione rimanente
 Regola SPTEX (SPT with Expediting): i job sono distinti
in due classi di priorità. Nella prima classe sono inclusi i
job soggetti ad anticipo di consegna o già in ritardo.
Vengono schedulati (con la regola SPT) tutti i job della
prima classe, e solo in assenza di essi, la regola SPT viene
applicata ai job della seconda classe.
Regole di Carico
 Regole che considerano la situazione dell'impianto
 Regola NINQ (Number In Next QUEUE): viene caricato
il job che ha la lavorazione successiva sulla macchina con
il minor numero di job in coda.
 Regola WINQ (Work In Next QUEUE): viene caricato il
job che ha la lavorazione successiva sulla macchina con la
coda di attesa più breve in termini di carico di lavoro (non
come numero di job !).
Regole di Carico
 Regole che considerano la situazione dei job
 Regola FIFO
 Regola LIFO
 Regola FROP (Fewest Remaining Operations): viene
caricato il job con il minor numero di operazioni ancora da
eseguire (più vicino al completamento).
 Regola MROP (Most Remaining Operations): viene
caricato il job con il maggior numero di operazioni ancora
da eseguire.
 Regole che considerano fattori economici
 Regola COVERT: viene caricato il job che ha il massimo
valore del rapporto:(costo di ritardo)/(tempo rimanente).
Regole di Carico
 Combinazioni Lineari di Regole di Carico
 L'impiego di regole composte è di scarsa rilevanza pratica:
 è necessario tarare i coefficienti nella combinazione
lineare
 i coefficienti potrebbero non essere costanti ma dipendere
da alcune caratteristiche del job
 diversi studi hanno dimostrato che i benefici ottenibili
dall'uso delle combinazioni lineari tra le regole di carico
sono molto ridotti.
Programmazione della Produzione
Just in Time (JIT)
 Caratteristiche Principali:
 Sviluppato dalla Toyota Motor Corporation
 Gestione di Produzione di tipo “Pull”
 Ordini di Produzione a “Valle” del Sistema Produttivo
 Riduzione delle scorte (si spostano verso i fornitori)
Programmazione della Produzione
Just in Time (JIT)
Pianificazione di Lungo Periodo
Programma di Produzione Annuale
Livellamento Mensile della Produzione
Programma di Produzione Mensile
Calcolo della Produzione Livellata
Piano di Produzione Media Giornaliera
R1
R2
kanban
Rn-1
Rn
kanban
Descrizione di un Sistema Kanban
a 2 Cartellini
2
1
4
7
5
3
6
cassetta di raccolta
R
i-1
Ri
Descrizione di un Sistema Kanban
a
2
Cartellini
Cartellino (Kanban) di Produzione

 Cartellino (Kanban) di Prelievo
 Passi Operativi:
 Nel reparto Ri si e’ verificata la necessità di un prodotto fornito dal reparto Ri-1
 Un kanban di Prelievo indica il prodotto richiesto.
 Un contenitore vuoto con associato il kanban di Prelievo viene inoltrato al magazzino
del reparto Ri-1 a monte (1).
 Viene cercato un contenitore pieno con cartellino di produzione corrispondente al
kanban di prelievo (2). Il cartellino di produzione viene staccato e sostituito con quello
di prelievo.
 il kanban di produzione viene posto in una cassetta di raccolta (3), secondo una certa
priorità.
 il contenitore vuoto viene lasciato in una apposita area (4).
 il contenitore pieno viene trasferito al reparto Ri a valle che ha fatto richiesta (5)
 i kanban di produzione vengono prelevati secondo una certa priorità dal cassetto di
raccolta. Essi costituiscono gli ordini di produzione del reparto Ri-1 (6)
 i prodotti completati dal reparto Ri-1 vengono messi nei contenitori vuoti in attesa di
essere prelevati (7)
Programmazione della Produzione JIT
 Vantaggi del Sistema JIT
 Assenza di Schedulazione di Breve Periodo
 Produzione del Numero di Prodotti Richiesto
 Nessun Accumulo (WIP). Le scorte sono ridotte al
minimo sufficiente a garantire le richieste dei reparti a
valle.
 Nessuna Contesa sulle Risorse
 Il meccanismo kanban permette di far fronte a piccole
variazioni delle richieste di produzione.
 Imprese giapponesi che usano il JIT da più di 5 anni hanno
osservato:
incremento della produttività del 30 %
riduzione degli investimenti in scorte del 60 %
riduzione dello spazio occupato del 15 %
Programmazione della Produzione JIT
 Limiti dei Sistemi Kanban (JIT)
 Necessità di Livellamento della Produzione (non sono
ammessi flussi produttivi irregolari)
 Vicinanza dei Fornitori (Reparti a Monte)
 Criticità del Sistema di Trasporto
 Tempi di Regime Elevati (5-10 anni)
 Rigidità della produzione e dei ritmi produttivi (Il
meccanismo kanban non è in grado di far fronte a forti
variazioni di richieste di produzione)
Programmazione della Produzione JIT
 Applicazioni di Sistemi Kanban:
 Toyota Motor Corporation (ideatori e primi utilizzatori)
 General Motors (riduzione delle giacenze da 8 a 2 miliardi
$ per anno)
 Kawasaki (Nebraska). Successo del kanban system dal
1980.
 Yamaha (Giappone) (riduzione del tempo di produzione
da 20 a 10 giorni)