Appunti Automazione Industriale Modulo 2 con Esercizi

Sistemi ad eventi discreti

SISTEMA: Modello matematico descrittivo di un fenomeno, naturale o artificiale (macchina, robot, impianto produttivo)

SISTEMI AD AVANZAMENTO TEMPORALE (o SISTEMI AD EVENTI DISCRETI (o pilotati dagli

pilotati dal tempo): eventi)

Le grandezze che ne descrivono le condizioni di

funzionamento variano nel tempo secondo leggi Definizione di evento

dettate dalle equazioni differenziali (nel

continuo) o le equazioni alle differenze (nel

discreto). Un evento è un accadimento, in genere

istantaneo, che modifica le condizioni di

funzionamento di un sistema.

In entrambe le tipologie di sistema il concetto di STATO è fondamentale.

Sistemi ad eventi discreti

STATO DI UN SISTEMA: Insieme di variabili che rappresentano una fotografia del sistema, la quale può variare al

trascorrere del tempo (sistemi ad avanzamento temporale) oppure al verificarsi di eventi (sistemi ad eventi discreti).

ESEMPI di SISTEMI AD EVENTI DISCRETI:

Coda negli uffici pubblici:

STATO: numero di utenti in coda e in servizio

EVENTI: arrivo di un utente, partenza di un utente che ha terminato il servizio

Sistema manifatturiero:

STATO: numero di pezzi in transito nei buffer e in lavorazione nelle macchine

EVENTI: Inizio lavorazione, completamento lavorazione, scarico di un pezzo nel buffer,

guasto di una macchina, ecc.

Altri tipi di DES (Discrete Event Systems): Sistemi di comunicazione, sistemi hardware-

software (risorse allocate in un job).

Esistono anche i SISTEMI IBRIDI in cui le variabili possono modificarsi sia nel tempo che all’occorrenza di eventi.

Sistemi ad eventi discreti

CLASSIFICAZIONE DEI SISTEMI AD EVENTI DISCRETI:

Logici:

Si è interessati allo studio della successione di stati ed eventi, senza soffermarsi sulla durata di ciascun stato (tempo in cui

si permane in quello stato) o al tempo che caratterizza ogni transizione.

Temporizzati:

Si è interessati sia alla successione di stati ed eventi che alla durata di ciascun stato (tempo in cui si permane in quello

stato) o al tempo che caratterizza ogni transizione.

Ci sono vari modelli per rappresentare un sistema ad eventi discreti logico:

- AUTOMA

- RETI DI PETRI

- RETI DI PETRI COLORATE

Oppure sistemi ad eventi discreti temporizzati

- SIMULAZIONE

- RETI DI CODE

- RETI DI PETRI TEMPORIZZATE Sistemi ad eventi discreti

Tornando all’esempio della coda negli uffici pubblici, possiamo rappresentare tutte le sequenze possibili di stato e di eventi

:

mediante il seguente GRAFO ORIENTATO

FIGURA 1

= = = ⋯ = = = = ⋯ =p

rappresenta l’arrivo di un utente, mentre rappresenta la partenza

0 1 2 0 1 2

dell’utente dopo aver completato il servizio.

0,1,2,3,… rappresenta il numero di utenti in coda (STATO DEL SISTEMA)

I nodi sono gli stati e gli archi gli eventi del sistema. Nota che dallo stato 1 è possibile la sequenza pa, mentre la stessa

sequenza non è possibile dallo stato 0 (in quanto dallo stato 0 l’unico evento possibile è l’arrivo di un utente).

Il modello rappresentato in Figura 1 è denominato AUTOMA.

Sistemi ad eventi discreti

RETI DI PETRI: Grafi bipartiti in cui ci sono nodi (denominati POSTI), barre (denominate TRANSIZIONI) e archi. Gli archi

possono connettere esclusivamente posti e transizioni.

L’insieme dei posti, rappresentato da un vettore (denominato MARCATURA) è lo stato del sistema, mentre le transizioni

sono gli eventi.

Per chiarire il concetto di RETE DI PETRI riportiamo la seguente rete che modella una macchina:

Eventi:

t1 inizio lavorazione

token t2 fine lavorazione

t3 insorgere di un guasto

t4 riparazione del guasto

MARCATURA (STATO):

Un token (gettone) in P1 indica l’inattività della macchina;

Un token in P2 modella la macchina in lavorazione

Un token in P3 rappresenta un guasto della macchina

Sistemi ad eventi discreti

° " " verificarsi

può

non ,

,

poi in

, p non

,

token

ci sono

^

ASSEMBLAGGIO

iss

☐ verificarsi

'

( token puo

diviso

viene non

un ,

token ) '

poiche

due in P

in non

,

Una transizione per poter essere abilitata e accendersi ha yo ,

, ,

,

g. ,

,

bisogno di un numero di token sufficiente nei posti a

monte della transizione stessa.

E’ possibile inserire dei pesi sugli archi che indicano il

numero di token che si muovono da un posto all’altro

Sistemi ad eventi discreti

RETI DI PETRI COLORATE:

Le condizioni di scatto

possono variare a

seconda del colore del

token.

Le condizioni di scatto

per questo motivo sono

più complesse. Sistemi ad eventi discreti

Tra i sistemi TEMPORIZZATI si distinguono i MODELLI DI SIMULAZIONE: riproduzione delle dinamiche di un sistema nella

sua evoluzione temporale.

Esempio: Conoscere per quanto tempo un impiegato è utilizzato allo sportello.

Naturalmente non è opportuno in questi casi far uso di modelli logici a eventi discreti poiché non forniscono una

percezione dei tempi di permanenza in ciascun stato.

Un modello di simulazione può considerare e rappresentare la variabile n(t) indicando con essa il numero di utenti in coda e

in servizio al variare del tempo. Gli eventi sono indicati con tj e rappresentano l’arrivo e partenza degli utenti.

stato

n(t) Definire l’indice di performance: in questo

T caso l’utilizzazione dell’impiegato.

2 3 − 1 + (5 − 4)

à

= =

1

t3 t

t2 t5

t4

t1 Sistemi ad eventi discreti

Il coefficiente di utilizzazione può essere considerato anche nel caso più complesso di sistemi di produzione. Un valore

eccessivo dell’indice di performance può essere segnale di un centro di lavorazione per troppo tempo occupato. Tale

centro di lavorazione può rappresentare un collo di bottiglia per tutto il sistema. sistema

del

alto

utilizzazione

coefficiente monte

troppo

neanche

buono

' di

Non avete un a

e

In fase di simulazione, conoscere tale coefficiente è utile per la costruzione del sistema di produzione al fine di evitare

riduzioni del throughput del sistema (pezzi prodotti per unità di tempo).

Altri indici di performance:

- Numero medio degli utenti in coda

- Numero totale di utenti nel sistema C- lo

ex a attira

=

. utente

- Throughput del sistema sempre un ,

E via

Va

20 sempre

- ecc. z :

utente

un ^

La simulazione può essere eseguita considerando gli istanti d occorrenza degli eventi e la durata dei servizi deterministici o

stocastici. partenze

gli le

attivi e

> deterministiche

esausti non

comunque

o

sono

Svantaggi: software apposito

- complessa descrizione del funzionamento del sistema; di

sviluppo un

>

- difficile comprensione dell’osservazione;

- tempo richiesto per un’analisi accurata.

Sistemi ad eventi discreti

RETI DI CODE: Sono rappresentate tramite un CENTRO DI SERVIZIO e una CODA IN SENSO STRETTO in cui gli utenti

attendono di essere serviti.

In questo modello STOCASTICO è necessario specificare per una singola coda:

TEMPI DI INTERRARIVO: tempo che trascorre tra l’arrivo di un utente e il successivo (secondo legge deterministica o

stocastica)

TEMPI DI SERVIZIO: Tempo necessario per espletare il servizio (nella maggior parte dei casi sono estrazioni di una

distribuzione probabilistica)

NUMERO DI SERVENTI: numero di agenti umani o artificiali che danno il servizio

DISCIPLINA DI SERVIZIO: regola con cui si stabilisce l’ordine di servizio sulla base di varie informazioni, tra cui l’ordine di

arrivo (esempio: FIFO il primo ad arrivare è il primo ad essere servito, LIFO l’ultimo ad arrivare è il primo ad essere servito,

eec.) coda centro di servizio

Sistemi ad eventi discreti

RETI DI CODE: E’ un insieme di code legate in modo che gli utenti uscenti da una coda possano entrare in un’altra coda o

uscire dal sistema.

Quindi in una RETI DI CODE vanno specificate anche le probabilità di ROUTING degli utenti sia verso l’esterno che verso

qualsiasi coda.

E’ possibile studiare il comportamento delle RETI DI CODE a regime e dedurre importanti informazioni come il throughput,

il tempo di permanenza in coda, il numero medio di utenti in coda, l’ergodicità (simile al concetto colli di bottiglia).

Tali modelli sono largamente utilizzati nell’ambito delle telecomunicazioni, dell’informatica (reti di calcolatori) e

automobilistico. Sistemi ad eventi discreti

RETI DI PETRI TEMPORIZZATE: Lo scatto di una transizione può avvenire dopo un tempo finito dalla sua abilitazione. In

dettaglio, una volta che le condizioni di abilitazione di una transizione sono verificate, dopo un tempo la transizione

(rappresentata da un rettangolo) scatta muovendo i token tra i posti di ingresso e uscita. Il tempo può essere

deterministico, oppure un’estrazione da una distribuzione probabilistica.

AUTOMI – Linguaggi formali

Abbiamo visto che ad ogni evento è associato un simbolo. Per questa ragione ad una sequenza di eventi è associata una

sequenza di simboli. E’ quindi necessario definire formalmente un linguaggio generato da un sistema ad eventi discreti.

Definizione di PAROLA

Una parola (o stringa) w definita sull’alfabeto E è una sequenza di simboli di E, che consente anche le

ripetizioni.

Il numero di simboli, comprese le ripetizioni, che formano la sequenza w è chiamata LUNGHEZZA della parola

w, e si indica con |w|.

∈

Analogamente indica il numero di volte in cui compare nella stringa w.

Definizione di PAROLA VUOTA , = 0)

La parola vuota, indicata con il simbolo è una parola di lunghezza zero ( definita su qualunque

alfabeto. AUTOMI – Linguaggi formali

Indichiamo con E* l’insieme di tutte le parole costruibili con i simboli di E, indipendentemente dal significato e dalla

lunghezza. ∗ ∗

∈ = +∞

e

Adesso soffermiamoci sulle OPERAZIONI TRA STRINGHE:

Concatenazione di parole

∗ ∗ ∗

∈ ∈ ∋ =

Date due parole e , la concatenazione di w e w è una parola ottenuta facendo seguire

1 2 1 2

1 2

alla stringa w la parola w .

1 2

∗

∀ ∈ : = = .

Nota che ex . 1=266 ÒC

al

> Wiwa

WI abrazo

:

= <

>

=

W Zac

:

)

Proiezione ത ∗

⊆ ∈

Dato un alfabeto E e un sottoinsieme di esso e considerata una parola (parola w definita su E), la proiezione

ത ത ത

, ↑ , .

di su indicata con è la parola ottenuta eliminando da tutti i simboli non appartenenti a

ത ത

↑ ={aaca}.

Esempio: E={a,b,c}, ={a,c} , w=aabcbba,

AUTOMI – Linguaggi formali

OPERAZIONI TRA STRINGHE:

Prefisso, Substringa, Suffisso

∗ ∗

∋ = , , ∈ ≼

Data una parola con , ( ) è detto prefisso (suffisso) di e si indica con (

1 2 3 1 2 3 1 3 1 3

≽ , , .

), mentre le tre parole sono substringhe di

1 2 3

Un prefisso (suffisso) di può essere ottenuto eliminando da simboli da destra (sinistra).

AUTOMI – Linguaggi formali

LINGUAGGIO DI UN SISTEMA

Un linguaggio L definito su un alfabeto E è un sottoinsieme di E*. Indichiamo con |L| la cardinalità del linguaggio L.

Esempio

Se E è l’alfabeto italiano, allora un linguaggio potrebbe essere dato dall’insieme delle parole della lingua italiana.

Poiché il linguaggio L è un insieme, esso è soggetto a tutte le operazioni tra insiemi come l’unione e l’intersezione.

Esempio di linguaggi i j k z

E={a,b,c} , L1={a,b,c} , L2={aba, bacca, bca}, L3={b a b,b ,a } , con i,j,k,z=0,1,… , L4={a,ab,ac} , L5={} , L6=∅

Nota che |L5|=1, mentre la |L6|=0.

Operazioni con i LINGUAGGI contenuto

Concatenazione di Linguaggi a

∗ ∗

⊆ ⊆ =

Dati due linguaggi e (costruiti sull’alfabeto E), la concatenazione di L e L è il linguaggio formato

1 2 1 2

1 2

dall’insieme di tutte le parole ottenute concatenando (nell’ordine) ciascuna parola di L con tutte le parole di L .

1 2

∗

L = = ∈ , ∈ } , ⊆

In modo formale: con

1 2 1 1 2 2 1 1

AUTOMI – Linguaggi formali

Operazioni con i LINGUAGGI

Esempio di concatenazione:

∗ ∗ 2 2 2

⊇ = , , ⊇ = , , ⟹ L = = { , , , , , , , , }

E={a,b,c}; ,

1 2 1 2 K

E’ possibile concatenare un linguaggio L con se stesso K volte, utilizzando la notazione L .

Si assume L ={}

0

Chiusura di Kleen ∗

⊆

Dato un linguaggio , la chiusura di Kleen è il linguaggio L* definito come segue:

∞

∗ 0 2

= ڂ … =

ڂ ڂ ڂ =0

Chiusura dei prefissi ത

∗ ∗

⊆ ⊆

Dato un linguaggio , la chiusura dei prefissi di L è il linguaggio formato da tutti i prefissi di L, ed è

formalmente definito dalla seguente relazione:

ത ∗

= { ∈ |∃ ∈ ∶ ≼ } prefissi

i abc

tutti c' 4

sto

× a.

patois .

- , ,

AUTOMI – Linguaggi formali

Operazioni con i LINGUAGGI

Esempio di chiusura dei prefissi: vite

C- le parole

per

1

ത

∗ 3 3 2 3 3 2 3

⊇ = , , ⟹ = {, , , , , , , , , , }

E={a,b,c}; IE

- -

]

ÒI i

per

per >

ത ത

L ⊆ L =

In generale e se si dice che L è chiuso rispetto ai prefissi.

Complemento di un linguaggio

∗ ∗ ∗

⊆ ⊆

Dato un linguaggio , si dice COMPLEMENTO DI L RISPETTO A il linguaggio costituito da tutte

∗

le parole di che non appartengono a L.

∗

= { ∈ | ∉ }

Formalmente:

{ "

silo }

loc

↳ mik

i

= Io

, "

Pistola

te '

" J

→

it > .

>

me '

èè

" "

anni

↳ Koen

' ' ◦ ◦ } diversi

indici

b. :< devono

' : coopre

-2 e µ

, ≥

- , ,

n

:{ .

. ,

" ,

sì

la } .

~

io nik ≥

; o altrimenti imporranno

, kit che

↳ "

" stesso volte

'

si ripetono di

lo numero

0^15 " lo si

significa

ad esempio e

che

AUTOMI – Linguaggi formali

Operazioni con i LINGUAGGI

Composizione concorrente (o sincrona) di due linguaggi

1∗ 2∗

⊆ ⊆ = ڂ

Dati due linguaggi e , e posto l’alfabeto ,si dice COMPOSIZIONE CONCORRENTE (o

1 2 1 2

∗

∥ = { ∈ | ↑ ∈ , ↑ ∈ }

sincrona) di e il linguaggio , ossia l’insieme delle parole di

1 2 1 2 1 1 2 2

∗

le cui proiezioni su appartengono a e le cui proiezioni su appartengono a .

1 1 2 2

Esempio:

= {, }, = , ⟹ = ∪ = , ,

1 2 1 2

1∗ 2∗

⊆ ⊆

={ con n=0,1,…} , ={ con n=0,1,…}

1 2

Per calcolare la composizione concorrente si parte da uno dei due linguaggi e si impongono per ciascuna delle

sue parole i vincoli affinché le proiezioni sull’altro alfabeto appartengano all’altro linguaggio.

Scegliamo ={ con n=0,1,…} . Si nota subito che affinchè le proiezioni delle sue parole su appartengano

1 2

al linguaggio è necessario che;

2

1) n=2 ; 2) il simbolo c deve precedere la prima b ma può precedere o posporsi al simbolo a, dato che esso

… a … );

scompare dopo la proiezione ( , 3) tra le due b deve interporsi una c ripetuta n volte.

∥ = { ,

Pertanto, il linguaggio con n=0,1,….}

Partiamo dalla ' lunga

piu

m lo

b

( (

abm lom

prefisso di

deve

2 essere un

"

"

' "

' i i

;

^

^ , "

! "

.

.

:

a. =

Io molte

' posizioni in

messo

a essere

puo tos o

>

la ' nelle viola

in

posizioni

2 essere

non messo

puo AUTOMI – Linguaggi formali

Composizione concorrente (o sincrona) di due linguaggi

Si giunge allo stesso risultato partendo da :

2

= {, }, = , ⟹ = ∪ = , ,

1 2 1 2

1∗ 2∗

⊆ ⊆

={ con n=0,1,…} , ={ con n=0,1,&hellip