Sistemi a eventi discreti
Nell’Ottocento Babbage concepisce
il processo di trasformazione
manifatturiera come un
concatenarsi di eventi discreti cioè un
sistema a eventi discreti
C.Babbage Economy of manufacturers and
machinery,
1832, testo che precorre la moderna
impostazione sistemistica
Sistemi a eventi discreti
La visione
modellistica di
Babbage non
trova sviluppo
immediato per
i sistemi
manifatturieri
Quella visione
gli fa realizzare
la prima
macchina
calcolatrice
programmabile
Macchina analitica
Il ruolo dei modelli
Leonardo da Vinci (1452-1516)
I meccanismi devono imitare la
matematica
Controllo di sistemi a eventi discreti
Come si sono sviluppati i modelli
per la gestione e il controllo delle
operazioni ?
Valutazione e miglioramento
delle prestazioni con alta
numerosita’ degli eventi:
modelli "analitici" a "reti di
code"
Reti di code:
sistemi di produzione a grandi
lotti
Descrizione stocastica dei
fenomeni temporali e delle
interconnessioni
Rete di Petri:
concatenamento
degli eventi
sganciato dal
fluire del tempo
Reti di Petri
Descrizione deterministica o
stocastica dei fenomeni
temporali e delle
interconnessioni
Modelli di ottimizzazione
combinatoria
La struttura del grafo degli stati
discende dalla scelta della
funzione obiettivo
Spesso una struttura
modulare (e/o "nidificata”)
consente di semplificare
rappresentazione, analisi e
algoritmi di ottimizzazione
Oggetto dei due moduli
Procedure
di gestione e di controllo delle
operazioni
METODOLOGIE
Mod1: Reti di code, Reti di Petri,
Sequenziamento ottimo su una
macchina (o processore)
Mod2: Modelli di ottimizzazione per
“seq.-sincron.” (scheduling) su più
macchine (o processori)
Ambito applicativo principale:
Insiemi coordinati di macchine
manufatturiere
noti come:
- Celle, linee, FMS
- Sistemi integrati
di lavorazione
Nei sistemi integrati,
spesso il coordinamento
delle operazioni richiede
decisioni
Il controllo supervisore del
sistema coordina:
• le operazioni prescritte dal
processo tecnologico
• il sequenziamento dei
processi tecnologici (lavori)
e la condivisione delle
risorse necessarie
Si vogliono “ottimizzare”
le prestazioni del sistema
rispettando i vincoli tecnologici
prescritti dal processo produttivo
Analisi di sistemi di controllo
ad eventi discreti
con reti di Petri
2.1 Eventi, transizioni; condizioni,
posti, marche; marcatura iniziale
RETI DI PETRI
Rappresentazione di
sistemi ad eventi discreti
2
1
Eventi:
- operazione sul pezzo
- scambio del pezzo 1 con 2
1
2
Eventi:
- operazione sul pezzo
- scambio del pezzo 1 con 2
Ogni evento è rappresentato da una
transizione, simboleggiata da una
barretta
Ogni condizione necessaria per l’evento
è rappresentata da un posto (cerchietto)
collegato in input con un arco orientato
Ogni condizione creata da un evento è
rappresentata da un posto
collegato in output con un arco
orientato
TRANSIZIONI
operazione su 1
2
1
2
TRANSIZIONI
operazione su 1
scambio 1 con 2
1
2
2
1
POSTI
pezzo 1 sulla macchina
operazione su 1
scambio 1 con 2
11
2
POSTI
pezzo 1 sulla macchina
operazione su 1
operazione su 1 finita
scambio 1 con 2
11
2
POSTI
pezzo 1 sulla macchina
operazione su 1
operazione su 1 finita
scambio 1 con 2
scambio ultimato
2
2
1
Lo stato di una
condizione è
rappresentato da
marche nel
corrispondente posto
MARCHE
pezzo 1 grezzo sulla macchina
operazione su 1
operazione su 1 finita
1
MARCHE
pezzo 1 grezzo sulla macchina
operazione su 1
operazione su 1 finita
1
MARCHE MULTIPLE
grezzo sulla macchina
inizio operazione
pezzo in lavorazione
fine operazione
pezzo in attesa
scambio
pezzi in uscita
MARCHE MULTIPLE
grezzo sulla macchina
inizio operazione
pezzo in lavorazione
fine operazione
pezzo in attesa
scambio
pezzi in uscita
MARCHE MULTIPLE
grezzo sulla macchina
inizio operazione
pezzo in lavorazione
fine operazione
pezzo in attesa
scambio
pezzi in uscita
MARCHE MULTIPLE
grezzo sulla macchina
inizio operazione
pezzo in lavorazione
fine operazione
pezzo in attesa
scambio
pezzi in uscita
MARCHE MULTIPLE
grezzo sulla macchina
inizio operazione
pezzo in lavorazione
fine operazione
pezzo in attesa
scambio
pezzi in uscita
MARCHE MULTIPLE
grezzo sulla macchina
inizio operazione
pezzo in lavorazione
fine operazione
pezzo in attesa
scambio
pezzi in uscita
Una transizione è abilitata quando ci
sono sufficienti marche nei posti di input
Un evento si può verificare quando
esistono tutte le condizioni necessarie
Lo scatto di una transizione crea marche
nei posti di uscita
Quando un evento si verifica cambia lo
stato di alcune condizioni
SCATTO DELLE TRANSIZIONI
pezzo in ingresso
macchina disponibile
pezzo in attesa lav.
inizio operazione
pezzo in lavorazione
fine operazione
pezzo in attesa usc.
scambio
pezzi in uscita
SCATTO DELLE TRANSIZIONI
pezzo in ingresso
disponibilità della macchina
pezzo att. lav.
inizio operazione
pezzo in lavorazione
fine operazione
pezzo in attesa usc.
scambio
pezzi in uscita
SCATTO DELLE TRANSIZIONI
pezzo in ingr: disponibile
disponibilità della macchina
pezzo att. lav.
inizio operazione
pezzo in lavorazione
fine operazione
pezzo in att. usc.
scambio
pezzi in uscita
SCATTO DELLE TRANSIZIONI
pezzo in ingr: disponibile
macchina:disponibile
pezzo att. lav.
inizio operazione
pezzo in lavorazione
fine operazione
pezzo in att. usc.
scambio
pezzi in uscita
SCATTO DELLA TRANSIZIONI
pezzo in ingresso
macchina:disponibile
pezzo att. lav.
inizio operazione
pezzo in lavorazione
fine operazione
pezzo att. usc.
scambio
pezzi in uscita
MARCATURA INIZIALE
pezzo in ingresso
macchina disponibile
pezzo in attesa lav.
inizio operazione
pezzo in lavorazione
fine operazione
pezzo in attesa usc.
scambio
pezzi in uscita
2.2 Matrici Pre, Post, di incidenza;
grafo di stato; equazione di stato,
di transizione
Reti di Petri regolari: una transizione
è abilitata quando c’è almeno una
marca in ciacun posto di input
Reti di Petri regolari: lo scatto di
una transizione crea una sola marca
in ciacun posto di uscita
DEFINIZIONE FORMALE
T : insieme dei nodi transizione
P : insieme dei nodi posto
Pre : matrice delle marcature per
lo scatto
Post : matrice delle marcature
create dallo scatto
rete di Petri: N = (T, P, Pre, Post)
m1
p1 m2 p2
t1
P=
p1
p2
p3
p4
p5
p6
m5
m3
p3
T= t1 t2 t3
t2
p5
m4
p4
t3
m6
p6
marcatura: M=
1
1
0
0
1
3
m1
m2
m3
m4
m5
m6
p1
p2
t1
p3
t2
p5
p4
t3
Pret1=
1
1
0
0
0
0
p6
Pret2=
0
0
1
0
0
0
Pret3=
0
0
0
1
1
0
m1
m2
m3
m4
m5
m6
Pre=
Post =
1 0 0
1 0 0
0 1 0
0 0 1
0 0 1
0 0 0
t1 t2 t3
p1
p2
p3
p4
p5
p6
0 1 0
0 0 1
1 0 0
0 1 0
0 0 0
0 0 1
t1 t2 t3
p1
p2
p3
p4
p5
p6
p2
p1
t1
p3
p5
t2
p4
t3
p6
RETE DI PETRI N
p2
p1
t1
p5
p3
t2
p4
t3
p6
Scatto di t: M  Min(t) = Pre(t)
RETE DI PETRI MARCATA: (N, M0)
condizione
della macchina
pezzo in
ingresso p5
p1
p2
t1 inizio operazione
p3 pezzo in lavorazione
t2 operazione
pezzo in attesa
t3 scambio
p4
M 0=
1
1
0
0
1
3
m10
m20
m30
m40
m50
m60
p6
Grafo di stato della rete (N, M0)
p1
p2
inizio op.
M0=
1
1
0
0
1
3
M0
m10 p5
m20
m30
m40
m50
m60
t1
p3
t2 operazione
p4
t3 scambio
p6
Grafo di stato della rete (N, M0)
p1
p2
inizio op.
M1=
0
0
1
0
1
3
M0
m11 p5
m21
m31
m41
m51
m61
t1
M1
t1
p3
t2 operazione
p4
t3 scambio
p6
Grafo di stato della rete (N, M0)
p1
p2
inizio op.
M2=
1
0
0
1
1
3
M0
t1
p3
t2 operazione
m12 p5
m22
m32
m42
m52
m62
t1
M1
p4
t3 scambio
p6
t2
M2
Grafo di stato della rete (N, M0)
p1
p2
inizio op.
M3=
1
1
0
0
0
4
M0
t1
p3
t2 operazione
m13 p5
m23
m33
m43
m53
m63
t1
M1
p4
t3 scambio
p6
t2
M2
t3
M3
Grafo di stato della rete (N, M0)
p1
p2
inizio op.
M4=
0
0
1
0
0
4
M0
t1
p3
t2 operazione
m14 p5
m24
m34
m44
m54
m64
t1
M1
p4
t3 scambio
M4
p6
t1
t2
M2
t3
M3
Grafo di stato della rete (N, M0)
p1
p2
inizio op.
M5=
1
0
0
1
0
4
M0
t1
p3
t2 operazione
m15 p5
m25
m35
m45
m55
m65
t1
M1
p4
t2
t3 scambio
M4
p6
t1
t2
M2
M5
t3
M3
Interfaccia con il sistema di trasporto
forcella
libera
da p. in
uscita
pezzo in ingr.
condizione della
macchina: disp.
p. att. lav.
p. att.
ingr.
t1
p.
in
lav.
t5
op.
t2
t3
t4
p.att.usc.
scambio
p. in usc.
uscita
pezzi fuori
M0
Interfaccia con il sistema di trasporto
forcella
libera
da p. in
uscita
pezzo in ingr.
condizione della
macchina
p.att. lav.
p. att.
ingr.
t1
p.
in
lav.
t5
op.
t2
t3
t4
p.att.usc.
scambio
p.in usc.
uscita
pezzi fuori
M4
Interfaccia con il sistema di trasporto
forcella
libera
pezzo in ingr.
condizione della
macchina
p.att. lav.
p. att.
ingr.
t1
p.
in
lav.
t5
op.
t2
t3
t4
p.att.usc.
scambio
p.in usc.
uscita
pezzi fuori
M7
GRAFO DEGLI STATI
t1
M1
t4
M0
t4
M2
t1
M4
t1, t4 concorrenti
t5
M7
Interfaccia con il sistema di trasporto
forcella
libera
pezzo in ingr.
condizione della
macchina
p.att. lav.
p. att.
ingr.
t1
p.
in
lav.
t5
op.
t2
t3
t4
p.att.usc.
scambio
p.in usc.
uscita
pezzi fuori
M8
GRAFO DEGLI STATI
t1
t2
M1
M5
t4
M2
t1
M6
t2
t4
M0
t4
M4
t1,t4 in M0; t2,t4 in M1;
t2,t5 in M4 concorrenti
t5
M7
t5
t2
M8
Interfaccia con il sistema di trasporto
forcella
libera
pezzo in ingr.
condizione della
macchina
p.att. lav.
p. att.
ingr.
t1
p.
in
lav.
t5
op.
t2
t3
t4
p.att.usc.
scambio
p.in usc.
uscita
pezzi fuori
M9
GRAFO DEGLI STATI
t1
t2
M1
M5
t4
M2
t1
M6
t2
t4
M0
t4
M4
t1,t4 in M0; t2,t4 in M1;
t2,t5 in M4 concorrenti
t5
M7
t5
t2
M8
t3
M9
MATRICE DI INCIDENZA
p1
p2
t1
p5
p3
t2
Pre=
1 0 0
1 0 0
0 1 0
0 0 1
0 0 1
0 0 0
t1 t2 t3
p1
p2
p3
p4
p5
p6
p4
t3
p6
Post =
C = Post - Pre
0 1 0
0 0 1
1 0 0
0 1 0
0 0 0
0 0 1
t1 t2 t3
p1
p2
p3
p4
p5
p6
EQUAZIONE DI STATO
p2
p1
p5
t1
p3
t2
C=
p4
t3
p6
scatto di t1:
M1=
1
1
0
0
0
0
+
-1
-1
1
0
0
0
t1
-1
-1
1
0
0
0
1
0
-1
1
0
0
t2
1
0
-1
1
0
0
0
1
0
-1
-1
1
t3
0
1
0
-1
-1
1
p1
p2
p3
p4
p5
p6
1
0
0
= M0+C e1
EQUAZIONE DI TRANSIZIONE
p1
p5
p2
t1
p3
t2
Sequenza di scatti s12: t1 t2
Conteggio di scatti s12= e1 + e2
M2= M1+ C e2 = M0 + C s12
p4
M2= M0 + C s12
t3
p6
scatto di t2:
M2 =
0
0
1
0
0
0
+
-1
-1
1
0
0
0
1
0
-1
1
0
0
0
1
0
-1
-1
1
0
1
0
= M1+C e2
S143 : no
t1
t2
M1
M5
t4
M2
t1
M6
t2
t4
M0
t4
M4
t5
M7
t5
t2
M8
Sequenze ammissibili:
Corrispondono ad un percorso nel grafo degli stati
sono ammissibili S124 S412 S142
S1245 S4152
Transizioni: M6= M0+C s124
M8= M0+C s1245