Che materia stai cercando?

Appunti delle lezioni - Programmazione e controllo della produzione, Gisario

Il file contiene gli appunti di tutte le lezioni di Programmazione e controllo della produzione della professoressa Gisario da settembre a dicembre 2017. Consiglio (se possibile) di stamparli a colori. Appunti basati su appunti personali del publisher presi alle lezioni del prof.

Esame di Programmazione e controllo della produzione docente Prof. A. Gisario

Anteprima

ESTRATTO DOCUMENTO

CSZ sett 5 o C = r + W + p

i i i i

 FLOW TIME tempo di flusso F

i

 LATENESS ritardo o anticipo che vado a realizzare per un dato job L

i

Obiettivi della schedulazione

 Massimizzare l’utilizzo delle risorse

o Andare ad impegnare in maniera efficiente le macchine senza creare tempi morti, saturare il più

possibile le macchine (esigenza di essere efficienti in ambito produttivo)

 Massimizzare il livello di servizio

o Andare a soddisfare il più possibile le richieste, quindi essere efficaci nei confronti dei clienti

(rispettare date di consegna, quantità da produrre)

 Minimizzare l’immobilizzo delle scorte

o Ridurre i tempi di attesa della lavorazione, il WIP si svolge in un tempo più contenuto, mi vado a

liberare di quelle scorte che non posso vendere, vado ad essere un po’ più economico (criterio di

economicità)

Devo raggiungere almeno uno di questi. Dobbiamo fare riferimento a degli indici di prestazione, questi sono tutti

parametri dipendenti dalla schedulazione sulla base dell’obiettivo che si vuole raggiungere.

Indicatori:

W C F L numero di jobs in ritardo (ci sono delle situazioni in cui i job sono tanti e non riusciamo a completarli tutti

i i i i

entro le date di consegna richieste, andiamo a rendere minimo il numero di job in modo da poter scegliere di far fare

la lavorazione a terzi e andare quindi a sostenere il livello di servizio, pur andando ad aumentare i costi interni)

Algoritmi di schedulazione

Iniziamo con algoritmi che fanno riferimento ad un’unica macchina (cioè una macchina sola che deve svolgere più

job). In questo esempio ogni job è costituito da una sola

operazione. Ogni job viene indicato con una casella

(tanto più grande quanto più grande è il tempo di

processamento).

Possiamo considerare dalla somma dei tempi di

processamento quello che sarà il tempo totale in cui

deve lavorare la macchina per completare tutte le

operazioni.

Se vado a sommare il tempo di completamento di ogni

singolo job devo sommare il suo tempo di

processamento più i tempi di quelli precedenti.

7

CSZ sett 5

26/10

Ogni volta che vogliamo schedulare le attività produttive dobbiamo porci degli obiettivi, in genere di 3 tipi:

 Efficienza del sistema produttivo

 Corretta risposta al cliente

 Ridurre il tempo delle scorte wip, ridurre il tempo di flusso

(Slide di sopra)

Algoritmi di schedulazione

Schedulare attività produttive di una sola macchina

Tutti i job faranno richiesta di essere processati da questa macchina. Il job è da considerarsi come un’unica

operazione (o più operazioni, ma come primo esempio prendiamo un’unica operazione). Le operazioni sono

caratterizzate da un tempo di processamento. Ipotizziamo di schedulare senza un criterio specifico, come arrivano le

inviamo alla macchina. I tempi di processamento sono differenti, dobbiamo considerare che il primo job entra nella

macchina, occorrerà un tempo tecnico che è p (tempo complessivo del lotto), completeremo il job all’istante c , poi

1 1

p che avrà un tempo di attesa (di processamento di p ) e così via

2 1

C somma di tutti I tempi di processamento.

m

Se dividiamo per il numero di job abbiamo il tempo medio per ogni job

Algoritmo shortest process time Sequenziamo le attività

considerando che la sequenza

deve rispettare il criterio dal più

piccolo al più grande.

Questo algoritmo si pone

l’obiettivo di andare a rendere

minimo il tempo di

completamento medio.

Ipotizziamo di avere il job 1 che ha un tempo di

processamento uguale a 4 ore, il job due pari a 2 ore.

8

CSZ sett 5

Con questa tecnica posso raggiungere diversi obiettivi:

 Riduzione del flow time per via della riduzione del tempo di attesa

 Riduzione di C medio

 Viene ridotto anche il Ritardo di consegna (LATENESS) Andiamo ad intervenire sempre sul tempo

di completamento medio.

Altro problema di schedulazione: cercare di ridurre il ritardo massimo

Se ad esempio una macchina mi ha generato un

ritardo devo trovare un modo per recuperare.

EARLIEST DUE DATE

Si fa riferimento alla data di consegna, vado a

sequenziare inviandoli dalla data più vicina a

quella più lontana. Il primo job che si farà sarà

quello con la data più imminente.

Potrebbe essere interessante applicare questo

algoritmo anche nel caso in cui tutti i job

verranno ad essere realizzati con un certo

anticipo, ma in quel caso ho come obiettivo

realizzare il minimo anticipo, cioè faccio partire

l’attività in modo tale da avere meno scorte

possibile.

Obiettivo principale di questo metodo è

consegnare il più possibile in tempo,

criterio di efficacia, ma può avere dei

risvolti economici (se visto in termini di

anticipo).

9

CSZ sett 5

Esempio:

Facciamo delle simulazioni per individuare la sequenza ottima per rendere minimo il tempo di completamento, poi

per rendere minimo il ritardo di consegna. Analizzo i dati:

 Ho il tempo di

processamento e la

scadenza, vado a calcolare il

tempo di completamento

(di flusso), perché il tempo

di rilascio è zero quindi

assumono lo stesso valore.

 12+6 =19 ecc ecc

 Il make span totale

sarà pari a 45 giorni (tempo

di processamento), tempo

di flusso totale 138 giorni

 Vado a vedere il

ritardo di consegna

 Confrontando le

due date con il tempo di

flusso valuto se c’è un ritardo o meno

o devo consegnare tra 8 giorni, lo completo in 3 giorni quindi ritardo zero

o Per il job B tra 18 giorni, lo completo a 13 ritardo zero

o per il job C realizzo 13 giorni di ritardo, calcolo tutti i ritardi, li sommo, considero i valori medi

Tempo di completamento

medio 20 giorni, prima era 23

Earliest due date ho una

sequenza diversa.

Ritardo massimo 44 giorni

complessivi anziché 50

10

CSZ sett 5 Regola del rapporto critico

(mette a rapporto la data di

consegna sul tempo di

processamento).

Quindi si mettono in ordine

di rapporto di criticità,

quanto più è piccolo il

rapporto tanto più è critico.

(Non è un algoritmo che noi

utilizzeremo, viene usato

solo come algoritmo di

confronto)

Algoritmo di MOORE

Fa riferimento sempre ad una sola macchina, ha come scopo quello di rendere minimo il numero di job in ritardo.

Se abbiamo job in ritardo e

dobbiamo pagare una penale forse

conviene far produrre all’esterno pur

di non avere ritardo.

La sequenza ottenuta va verificata,

potrebbe essere una sequenza

ottima ma dobbiamo verificare,

appena troviamo un job in ritardo ci

fermiamo, guardiamo i tempi di

processamento tutti i job sequenziati

compreso il primo che realizza

ritardo, osserviamo il tempo di

processamento, individuando quello

più lungo lo scartiamo, perché

questo è quello che genera ritardi su

tutti gli altri. Otteniamo quindi una nuova sequenza, anche questa va controllata, ci fermiamo al primo job in ritardo

e togliamo quello che ha il tempo di processamento più lungo.

Algoritmo iterativo finché non si trova una sequenza con nessun job in ritardo.

Esercizio di MOORE

Primo passo dell’algoritmo sequenziare secondo Earliest due date e calcolo i tempi di completamento, poi controllo

guardando i ritardi, mi accorgo che il secondo job è già in ritardo, allora lo elimino (perché fino a lì ha il tempo più

lungo)

Allora la mia sequenza ottima è 5,2,4

Sequenza job in ritardo 3,1 11

CSZ sett 5

Algoritmo di LAWLER Ci possono essere delle relazioni di

precedenza tra i diversi job. Fare ritardo

per un job può essere magari più grave che

farlo su altri. Quindi definiamo una

funzione gamma che dipende dal tempo di

completamento.

Dobbiamo rendere minimo il massimo di

questa funzione.

Passi dell’algoritmo:

 Definiamo la sequenza vedendo prima quelli che non hanno successori, li colloco (funzione obiettivo deve

avere minore valore) poi posiziono gli altri  Osservo il grafo delle

precedenze e calcolo il tempo

totale di completamento di tutti i

job  Mi costruisco un

sottoinsieme V di job che non

hanno relazioni di successione, per

questi job calcolo i valori della

funzione gamma e vedo quelli più

piccoli, li metto per ultimi, aggiorno

il tempo totale di completamento,

aggiornare l’insieme V (perché

alcuni job li ho già sistemati),

calcolo gamma per l’insieme

rimasto ecc ecc fin quando non ho

collocato tutti i job

12

CSZ sett 5

Esercizio algoritmo di LAWLER Calcolo t = 15

k

Vado a vedere i job senza successori, 5 e 6

Calcolo la funzione gamma e gamma

5 6

Altro esempio 13

CSZ sett 6

31/10

Algoritmo di Johnson

1. Numero di macchine =2

2. Job indipendenti tra loro (non ci sono relazioni di precedenza)

3. Schema di lavoro fisso M1 M2

4. Tempi di lavoro dei jobs su M1 e M2 noti e costanti

Indicheremo come A i tempi dei vari job sulla macchina 1 e con B i tempi dei vari job sulla macchina 2. Andiamo ad

individuare tra i due insiemi il valore più piccolo dei tempi

Esercizio Sott = DAECFB

Job M1 M2 Sott= DECFDB

A 5 5

B 4 3

C 8 9 M1 = [37, 51]

D 2 7 M2 = [0,2], [31,33]

E 6 8

F 12 15

D E C F A B M1 = [37, 51]

M1 2 6 8 12 5 4 M2 = [0,2], [31,33]

Cm1 2 8 16 28 33 37

M2 7 8 9 15 5 3

Cm2 9 17 26 43 48 51

Valutare quale sequenza fa in modo che le macchine operino con minor tempo di inattività.

Esercizio D= obiettivo che si vuole realizzare

Lo schema sarà per EDD n/1/F/L ;

max

Lo schema sarà per MOORE n/F/numero jobs in ritardo min;

Lo schema sarà per JOHNSON n/2/F/makespan complessivo min.

Abbiamo in questo caso 5 jobs, 3 macchine sistema flow shop con obiettivo makespan complessivo minimo

Avendo lo schema fisso vuol dire che avrò la seguente sequenza:

M1 M2 M3

L’ipotesi di partenza è che le macchine sono due: come ci muoviamo se aggiungiamo una macchina al processo di

schedulazione? La soluzione che andremo a trovare è un certo numero di sequenze, tra le quali si troverà quella

avente il makespan complessivo minore. 1

CSZ sett 6

Applichiamo Johnson: nel nostro problema abbiamo tre macchine, e io Johnson lo posso applicare solo a due

macchine. Ma posso considerare due casi:

1. Escludo gli effetti di M2 e applico Johnson a M1 e M3; mi vado a costruire la sequenza che non è più ottima,

considerando i tempi di M1 e di M3:

[M1 M3] S1 = ... J5 (J5 in ultima posizione), continuando avrò

S1= 34125

S2= 43125

2. L’altra soluzione è andare a considerare un sistema costruito da M macchine:

[M1+M2, M2+M3]; vado a valutare se la somma dei tempi di processamento M1+M2 è piccola la colloco a

monte, altrimenti a valle. Esamino in questo modo l’effetto congiunto. Mi devo costruire una seconda

tabella: M1+M2 8 10 12 10 10

M2+M3 6 4 11 9 5

S3=

[M1+M2, M2+M3] 34152

So per certo ora che una delle tre sequenze ha il tempo più piccolo

Mi vado a fare i calcoli

3 4 1 2 5 M1 = [35, 40]

M1 7 7 6 9 6 M2 = [0,7], [12,14], [17,20], [22, 29], [30, 35] [39, 40]

Cm1 7 14 20 29 35 M3 = [0, 12], [28, 30] [33, 39]

M2 5 3 2 1 4

Cm2 12 17 22 30 39

M3 6 6 4 3 1

Cm3 18 24 28 33 40 Riporto tutti i tempi di inattività come fatto sopra.

3 4 1 5 2

M1 7 7 6 6 9

Cm1 7 14 20 26 35

M2 5 3 2 4 1

Cm2 12 17 22 30 36

M3 6 6 4 1 3

Cm3 18 24 28 31 39

Nel caso ci siano più di due macchine, occorre trovare e fissare una procedura, poiché la precedente ci fa perdere la

sequenza ottima.

Ipotizziamo che le macchine siano ad esempio 5.

(n/5/F/Makespan)

Andremo ad analizzare la sequenza per le macchine:

S1 = M1, …, M5

S2 =M1+M2, M4+M5

S3 = M1+M2+M3, M3+M4+M5

Sono certo anche che all’interno di una di queste sequenze ci sia il tempo minimo.

S1 = M1, …, M4

S2 = M1+M2, M3+M4

S3 = M1+M2+M3, M2+M3+M4

Al compito bisogna applicare la procedura completa, considerando tutte le macro macchine pur sapendo che una

macchina può escludere un’altra.

Spostiamo l’attenzione in un sistema di produzione flow shop

2

CSZ sett 6 2 macchine e 4 jobs:

Tutti i jobs di tipo A necessitano di

essere processati solo alla macchina

M1, i jobs di tipo B necessitano di

essere lavorati solo da M2, ecc.

Facciamo prima l’esempio e poi

analizziamolo.

Scomponiamo il problema in

sottoproblemi: andiamo a prendere i

jobs che richiedono prima A e poi B.

A B

Questo è un problema di tipo flow shop (A B) con due

macchine quindi applico Johnson;

B A anche problema flow shop con due macchine,

quindi applico Johnson

A e B invece ho solo una macchina

Mi costruisco le sequenze:

per A B abbiamo che il tempo più piccolo ce l’ha la

macchina 5, lo tolgo dall’analisi e lo inserisco in ultima

posizione.

S ab ott = 6 3 1 5

Faccio la stessa analisi per B A

Devo collocare il job otto in prima posizione, quindi a seguire il più piccolo è il tre, ecc.

S ab ott = 8 12 7 11

S A ott = 2 10

S B ott = 9 4

Come sequenzio quindi le attività?

Su A ci mando Sab ott, Sa ott, Sba ott = 6,3,1,5,2,10,8,12,7,11

Su B ci mando Sba ott, Sb ott, Sab ott = 8,12,7,11,9,4,6,3,1,5

3

CSZ sett 6 Dobbiamo dare un inizio: ad

esempio decidiamo di partire

dalla sequenza J1, J2: dobbiamo

allora lavorare il J3, se lo colloco

tra J1 e J2 o tra J2 e J1 dove mi

va a pesare di meno (tempo di

setup).

Quindi il punto di partenza lo

stabiliamo noi, tutti i vari job si

vanno a collocare o a destra o a

sinistra e poi si va a scegliere la

sequenza finale più piccola (in

termini di tempo).

Questo problema di

schedulazione ha sempre

bisogno di andare a definire il

punto di partenza. Poi si

collocano i restanti jobs.

In questo modo si va a valutare la sequenza ottima.

Cominciamo ad affrontare un algoritmo che ci permette di realizzare il flow shop

Ipotizzando di tracciare i percorsi

Ciclo di lavorazione 

J1: M1 M3 M2 OUT

J1 M1(7) M3(8) 

J2: M2 M1 M3 OUT

M2(10) 

J3: M1 M2 M3 OUT

J2 M2(6) M1(4) (disegna grafico dei percorsi schematico facoltativo)

M3(12) Come andiamo a schedulare tale schema?

J3 M1(8) M2(8) M3(7) Facciamo un’analisi con il diagramma di Gantt

(vedi sopra già fatto uno simile)

2/11 Shifting bottleneck

Ci concentriamo sul collo di bottiglia, dobbiamo prima di

tutto identificarlo. Collo di bottiglia: macchina

sovraccaricata rispetto alle altre.

Iniziamo a calcolare il carico di lavoro per ogni macchina:

M1 = 7 + 4 + 8 = 19

M2 = 10 + 6 + 8 = 24

M3 = 8 + 12 + 7 = 27

Il collo di bottiglia è M3, su di essa grava il maggior carico di lavoro (ammesso che non ci siano attese).

Una volta identificato il collo di bottiglia dobbiamo concentrare l’attenzione solo su questa macchina e scheduliamo

le attività produttive, cioè la sequenza di lavoro da inviarle. Organizzato il lavoro per M3 dobbiamo preoccuparci

delle macchine restanti, ora il collo di bottiglia è M2, shifting vuol dire che spostiamo l’attenzione sul collo di

bottiglia, la nostra attenzione si concentra poi sul nuovo collo di bottiglia. Tutte le macchine diventano collo di

bottiglia ma in ordine decrescente di carichi di lavoro.

Applico quindi l’algoritmo in questo ordine: M3 M2 M1

Ci manca un’informazione: dobbiamo sapere i vari job quante ore necessitano per completare la lavorazione.

Per ogni job dobbiamo calcolare le ore di lavoro necessarie

4

CSZ sett 6

J1 = 7 + 8 + 10 = 25

J2 = 6 + 4 + 12 = 22

J3 = 8 + 8 + 7 = 23

Da questo quadro complessivo delle macchine e dei job vado a derivare l’informazione che è il makespan

complessivo minimo, cioè il limite inferiore è il più grande tra tutti, se per le macchine vale l’ipotesi che non ci siano

attese allora per ogni job e per ogni macchina so che non impiegherò meno di 27 ore, è un valore che può

aumentare se ci sono attese. Una volta effettuate tutte le lavorazioni dei job otterrò non meno di 27 ore. Mi segno il

dato

MakeSpan complessivo minimo = 27

Poi vado a costruirmi il grafo disgiuntivo (che mi aiuterà nei vari calcoli da fare). Il grafo disgiuntivo è un grafo che da

per ogni job l’ordine di lavorazione, però non vi è l’indicazione di qual è l’ordine che devono seguire le macchine.

Devo schedulare le attività produttive cumulando il

valor medio di makespan, identifico altri archi tra le

singole macchine, lo faccio una macchina alla volta

partendo dal collo di bottiglia.

Dobbiamo analizzare le attività presenti sulla macchina 3:

Riportiamo sulla tabella riferita a M3 per i 3 job i dati: tempo di processamento, data di rilascio (che dipende dalla

posizione dell’operazione), poi riporto anche la due date (27 è il valore minimo), se 27 è il valore di riferimento e

l’operazione sulla macchina M3 del J1 la M3 è presente in

seconda operazione, quindi per completare tutto a 27 io devo

dare il tempo all’ultima operazione di essere svolta, quindi

completo la lavorazione M3 J1 al tempo 17, così poi aggiunte le

10 ore il job 1 lo completo alla 27° ora.

Ora per la M3

Dalle due tabelle ho che completo il J1 a 17 ore ma lo faccio a 15,

J2 lo completo a 27 ritardo zero, J3 lo completo a 34 invece lo

dovrei dare a 27, allora vado a realizzare in questo caso un

ritardo che è pari a 7 (prima tabella)

Seconda tabella completo a 15, completo a 23 ecc ecc ma il

ritardo è 8 ore, più grande di prima.

Quindi se sequenzio come nella prima tabella il makespan non è

più 27 ma 34

Devo esplorare tutte e 6 le opzioni, ma faccio un’osservazione preliminare, se io ho disposto J1 per primo perché è

quello con la che date più piccola, se io lo disponessi più in là avrei sicuramente un ritardo più grande, allora non

serve che io esplori tutte le opzioni, ne esploro solo alcune.

5

CSZ sett 6

Esempio: Ho 20 giorni di ritardo. Quindi metto sempre i job in ordine di due

date crescente, così esploro solo alcune delle opzioni.

Il ritardo più grande ce l’ho ovviamente sul J1 con 13 giorni.

In generale se la differenza tra dati è evidente esploriamo solo

alcune opzioni. In altri casi i risultati potrebbero essere simili pertanto dovrei tenere in considerazione più opzioni.

M3 fisso la sequenza J1 J2 J3 che mi permette di realizzare un ritardo di 7 ore, quindi il makespan complessivo

minimo è 27 + 7 = 34

Per M3 devo riportare la sequenza sul grafo disgiuntivo

Ora dobbiamo prendere in considerazione il seguente collo di

bottiglia.

Sei possibili opzioni, ma delle 6 esploro solo quelle che mettono J2 in

prima posizione.

CT, J1 avrei dovuto fare 15+10 ma siccome 16 è più grande allora

sommo 16+10.

Calcolo i ritardi, nel primo caso 6 nel secondo 0.

Quindi ho organizzato anche l’attività produttiva per M2.

M2 fisso la sequenza J2 J3 J1. L = 0. Makespan = 34

max

Attivo gli archi: 6

CSZ sett 6

Facciamo ora la stessa cosa per M1: Fisso la sequenza su M1: J1 J2 J3

Lmax = 3

Makespan = 37

Risultato finale dell’esercizio:

Esercizio da fare a casa:

Shifting bottle neck 7

CSZ sett 7

7/11

Esercizio M1 = 5+10+5=20

M2 = 8+2+7=17

M3=4+5+4=13

Ordine: M1, M2, M3

J1=5+8+4=17

J2=5+10+2=17

J3=7+4+5=16

Nessun job risulta superiore a 20, makespan = 20

Andrò ad analizzare 12>10 quindi faccio 12+10

L = 4

max

M1 -> J3 J1 J2

Occorre tracciare il diagramma di Gantt 1

CSZ sett 7

Scaricare software LEKIN

Riepilogo: come risolvere esercizi di questa tipologia

1) Determinare carichi di lavoro alle macchine

a. Tracciare la Sequenza dei colli di bottiglia

2) Calcolo del makespan minimo

a. Carico di lavoro di ciascun job

b. Rapportarlo con le macchine e scegliere il più grande

3) Tracciare grafico disgiuntivo

4) Procedere con schedulazione delle macchine, nell’ordine stabilito al primo step

5) Grafico Gantt 2

CSZ sett 7

Esercizio

J1=10+8+4=22

J2=8+3+5+6=22

J3=4+7+3=14

M1=10+3+4=17

M2=8+3+7=23

M3=4+6=10

M4=5+3=8

Makespan=23

M2 -> M1 -> M3 -> M4 (diagramma di Gantt)

3

CSZ sett 7

Password per le esercitazioni corsopcp1415

Reti di Petri Questo strumento si colloca

parallelamente a ciò che abbiamo visto,

lo usiamo per modellare il sistema

produttivo. La rete di Petri si usa per

Sistemi ad eventi discreti.

Il modello di Petri viene utilizzato per la

sistemazione degli elementi dinamici,

cioè che evolvono. Non si considera

t=tempo ma comunque si considera un

numero finito di eventi in successione,

(ecco perché sistemi discreti).

Esistono particolari processi produttivi

che hanno più fasi che devono essere

svolte non contemporaneamente ma

nello stesso periodo a monte di un’ultima

fase. Questo non viene

considerato nei diagrammi di

flusso. La rete di Petri permette

la rappresentazione di fasi che

devono essere svolte nello

stesso periodo.

Grazie alla rete di Petri

possiamo sapere lo stato delle

fasi.

Le reti di Petri hanno infiniti

stati.

Gli eventi non sono vincolati ad

accodarsi in linea definita. Il

livello di dettaglio lo stabiliamo

noi in base al peso che

vogliamo dare alle fasi. Gli

eventi a flusso vengono

rappresentati

spontaneamente.

4

CSZ sett 7

9/11

Reti di Petri

Insieme di più elementi, possiamo

considerarle costituite da 4 gruppi di

elementi

Nelle slide c’è un errore, P è da considerarsi

N che sta per Petri Net

P 1. Posti

a. Schematizzati con dei

cerchietti, posti della rete

che rappresentano degli

Stati, la rete di Petri è un

sistema ad eventi discreti

(definito tale in quanto

descrive una successione di

stati)

2. Transizioni

a. Schematizzate con dei

rettangolini pieni, eventi che si verificano, in funzione di questi si passa da uno stato precedente ad

uno successivo. I modi in cui cambiano questi stati lo stabilisco con le relazioni di flusso:

3. Relazioni di flusso

a. Archi orientati, i due stati precedenti (i due cerchi) verranno persi e verrà acquisito lo stato che è a

valle della transizione

4. Marcatura iniziale

a. Ci permette di comprendere in un dato momento dove ci troviamo, cioè in quale stato ci troviamo.

Se io trovo la presenza di questi pallini (o gettoni) nei cerchi vuol dire che questo è uno stato

corrente, cioè abbiamo completato le fasi che dovevamo

Per tutte le reti di petri valgono le 3 principali proprietà di definizione della rete (che mi permettono di definire

correttamente una rete)

1. L’insieme dei posti intersecato alle transizioni mi dà l’insieme vuoto, cioè sono sempre insiemi separati

 P ∩ T = Ø

2. La seconda proprietà insieme dei posti unito alle transizioni dà un insieme non vuoto, cioè per avere una

rete di petri devo avere almeno uno stato e una transizione, ci devono essere sia posti che transizioni (senza

transizioni non avrei evoluzione)

 P U T ≠ Ø

3. Le relazioni di flusso indicate con F sono relazioni che legano posti a transizioni e viceversa, ma non ci sono

relazioni che legano due posti tra di loro o due transizioni tra di loro.

Ipotizziamo un sistema di pressofusione

Fondiamo il metallo, lo mettiamo in un crogiolo, mentre solidifica applichiamo pressione, ci assicuriamo che assuma

la forma dello stampo, quindi otteniamo un oggetto che ricorda la cavità dello stampo.

Vengono schematizzate alcune fasi

 Posizionare lo stampo sotto la pressa

 Lo stampo deve essere caldo per evitare solidificazione precoce

 Dobbiamo mettere il metallo nel forno, si fonde poi lo coliamo nello stampo

 Accendiamo la pressa, selezioniamo i parametri fondamentali

 Quando lo stampo ha raggiunto la temperatura voluta la macchina è pronta

 Avvio la pressofusione

 Estraggo il metallo dal crogiolo e lo metto nello stampo, aziono la pressa ed estraggo il metallo.

Dobbiamo costruire la rete di petri. 5

CSZ sett 7

Possiamo costruire un’infinità di reti di

petri, a seconda del livello di dettaglio

che vogliamo.

Il primo stato è quello delle macchine,

ci servono le macchine pronte (pressa,

forno e stampo, che non è una

macchina ma attrezzatura). 3 fasi

operative che sono parallele, devono

avvenire in un arco temporale e al

termine di esse posso effettuare una

successiva operazione

1. Scaldare il forno per fondere il

metallo

a. Accendo il forno e

setto la temperatura

di fusione necessaria

b. Stato del forno: forno

alla temperatura desiderata, lo apro, ci metto il crogiolo con il metallo da fondere, la fase successiva

sarà fondere il materiale, che si conclude con uno stato materiale fuso

2. Settare la pressa

3. Riscaldare lo stampo

a. L’evento che deve realizzarsi cambia lo stato, mi trovo in una situazione in cui lo stampo è

posizionato

b. Nuovo stato: stampo riscaldato

Svolgo queste 3 fasi, solo allora potrò fare la colata. Non importa se parto con lo stampo, il forno o la pressa, l’ordine

è indifferente, l’importante è raggiungere questi 3 stati.

Poi avrò materiale colato caldo posizionato sotto la pressa. Materiale colato bisogna applicare la pressione, la pressa

è già pronta, attivo solo il pistone. Applicata la pressione ho il materiale in pressione, quindi devo aspettare che tutto

solidifichi, materiale solidificato lo estraiamo e quindi otteniamo il prodotto finito.

Vediamo i cerchi con i pallini dentro, ci troviamo nello stato in cui lo stampo ha raggiunto la temperatura, abbiamo

posizionato e abbiamo tutto pronto l’unica fase che manca è la pressatura.

La marcatura è quella che dà la possibilità vera di seguire l’evoluzione. La rete di petri la osserveremo attraverso la

marcatura. 6

CSZ sett 7

Archi di input collegano i posti

con le transizioni, identificano

gli Stati precedenti

Gli archi di output identificano

gli Stati successivi.

Se ho una rete di petri così

semplice come nella slide il

posto a monte della transizione

identifica la presenza di un

pezzo sulla macchina, la

transizione indica che avendo

posto il pezzo sulla macchina

posso processarlo, operazione

sulla macchina del pezzo 1.

Conclusa questa avrò

operazione sul pezzo terminata

quindi pezzo pronto.

Quindi comprendiamo lo stato della rete in funzione di dove si trova la marcatura. Un posto senza gettone non è uno

stato corrente, invece un posto con gettoni (pallini dentro) definisce uno stato corrente.

Le transizioni con la marcatura permettono di rappresentare la parte attiva della rete di petri.

Dobbiamo capire quando le transizioni si verificano. Abbiamo due reti apparentemente uguali (stessa struttura, due

posti a monte e solo uno a valle), abbiamo due gettoni sul posto a sinistra 4 su quello a destra, mentre nell’altro caso

solo due gettoni per posto. Gli archi orientati in realtà li abbiamo visti sempre senza numeretto (quando non c’è

numeretto intendiamo il peso unitario) se invece c’è un numeretto vuol dire che l’informazione che porta questo

arco è che occorrono quel numero di marche. L’altro arco porta come valore 3, l’evento si può realizzare se la

transizione è abilitata a scattare.

La regola dello scarto vuole che la transizione è abilitata se il numero di marchi nel posto a monte è almeno uguale a

quello sull’arco orientato. Devo avere per gli archi di input almeno quel numero di marche nel posto a monte.

Siccome sono connessi entrambi i due posti alla transizione, perché questa sia abilitata deve essere valida la

condizione per entrambi i posti a

monte.

La prima transizione quindi è

abilitata allo scatto, quella

accanto no.

La prima scatta, lo scatto lo vedo

sotto. 2+3=5 non fa 4, non c’è

connessione tra quello che

succede a monte e quello che

succede a valle, tutto è regolato

dalle relazioni di flusso.

Tornando allo schema di petri

della pressofusione, abbiamo 3

stati con i token (pallini),

transizione abilitata allo scatto,

perdo le marche in quei posti e la

ritrovo sotto, non c’è connessione tra monte e valle, tutto stabilito dalle relazioni di flusso.

7

CSZ sett 7 Abbiamo una macchina, pezzi poggiati su un pallet che porta

i pezzi. Questi vengono posizionati in prossimità della

macchina sulla piattaforma girevole, abbiamo un doppio

piatto collegato dall’albero, questo piatto può ruotare. I

pezzi sono movimentati su un sistema di trasporto a nastro,

sono grigi quando sono grezzi, una volta lavorati sono gialli. I

pezzi lavorati vengono direzionati verso l’uscita.

Consideriamo la rete 4 posti e transizioni.

 Il primo posto identifica la presenza del grezzo sulla

macchina

 La transizione è inizio operazione

 Una volta avviata l’operazione il pezzo è in lavorazione,

 Fine operazione, il pezzo è in attesa

 Quando ruota il piatto tira fuori quello lavorato e ne mette un altro a lavorare

 Avvenuto lo scambio avrò pezzo in uscita

Marcato ho un pezzo in lavorazione, 3 pezzi in uscita (quindi 3 gettoni)

Gli eventi avvengono se le transizioni sono abilitate allo scatto. La transizione abilitata allo scatto è T1, un gettone, il

posto è marcato con un gettone, quindi è abilitata. Il secondo posto non ha gettoni quindi la transizione non è

abilitata allo scatto, nemmeno quella sotto.

Ora T2 è abilitata allo scatto, può succedere solo che può

terminare l’operazione. Termina l’operazione e andiamo a far

scattare la transizione

8

CSZ sett 8

14/11

In virtù della marcatura possiamo capire come evolve la rete, abbiamo

visto quando una transizione è abilitata allo scatto (quando ha nei posti

in input un numero di pallini almeno uguale al valore riportato dalla

relazione di flusso).

Per seguire l’evoluzione abbiamo visto di volta in volta la transizione

abilitata allo scatto. Dividiamo le relazioni in:

 relazioni di flusso che precedono la transizione

 relazioni di flusso che seguono la transizione

Andiamo a prepararci per l’analisi matriciale, possibile per le reti di Petri. Andiamo ad esprimere l’insieme dei posti

attraverso un vettore colonna che ha dimensione pari al numero dei posti.

Il processo produttivo è lo stesso che abbiamo analizzato nella scorsa lezione, ma ora lo miglioriamo.

P1 rappresenta la condizione di macchina disponibile.

T1 significa inizio operazione, ma per iniziare il pezzo grezzo deve essere già sulla macchina e la macchina deve

essere pronta.

Fine operazione, quando finisce

dobbiamo avere un pezzo lavorato

in attesa, posto p4.

L’insieme dei posti può essere rappresentato con un vettore colonna che ha dimensione pari al numero di posti. Le

transizioni sono un vettore riga con dimensione pari al numero delle transizioni. La marcatura è costituita dal

numero di pallini presenti nei posti, andiamo a specificare

quanti pallini sono presenti nei posti. Il vettore marcatura è

un vettore colonna con la stessa dimensione del vettore dei

posti.

1

CSZ sett 8 La stessa cosa dobbiamo fare per le relazioni di flusso distinguendo tra input

e output alle transizioni.

Per ogni posto porto i valori dell’arco unitario. Per t1 i posti a monte sono

solo P1 e P2 con valori degli archi unitari, tutti gli altri zero. Faccio lo stesso

per t2 e t3.

Ora ci ricaviamo le matrici: Abbiamo costruito in forma matriciale le relazioni di flusso distinguendole

tra pre e post.

Andiamo ad analizzare l’evoluzione di questa rete di petri:

Affinché possa evolvere dobbiamo analizzare le transizioni abilitate allo scatto (quando si verifica la condizione)

La marcatura iniziale M è 110013, se devo fotografare questa

0

situazione iniziale e quindi il vettore marcatura iniziale (stessa

dimensione dei posti) riporto in ogni posto il valore dei pallini

presenti.

Le transizioni abilitate allo scatto sono:

 T1 è verificata

 T2 no

 T3 non abbiamo una marca in p4

Quindi l’unica abilitata allo scatto è t1, scatterà sicuramente

questa

2

CSZ sett 8

Una volta che scatta t1 Il grafo di stato è un grafo che va a descrivere a partire da uno stato

come la rete può evolvere. Lo stato iniziale è rappresentato da M ,

0

poi è scattata t , attraverso quello evolvo nello stato rappresentato

1

da M .

1

Ora le transizioni abilitate allo scatto sono:

 T1 no

 T2 può scattare

 T3 no perché c’è un gettone in p5 e niente in p4

Abbiamo di nuovo una sola transizione che può scattare

Se scatta t2 avremo M2 Ora l’unica che può scattare è t3, avrò una marcatura M3

Ora è abilitata t1, ad M3 farò seguire l’evoluzione attraverso t1 e otterrò la marcatura M4

Ora è abilitata di nuovo t2

3

CSZ sett 8 Ora:  t1 non può scattare perché manca il pezzo grezzo in

lavorazione

 t2 non può scattare perché è terminata l’operazione

quindi abbiamo il pezzo in attesa ma non abbiamo più un pezzo

grezzo sul piattello

La rete non evolve più, allora la miglioriamo ancora, la

complichiamo, andiamo a modificare delle cose.

Abbiamo che:

 P1 e p2 rimangono invariati

 T1 ha lo stesso significato di prima

 P3 è il pezzo in lavorazione a cui segue t2 fine operazione

 Pezzo in attesa

 Aggiunge una transizione pezzo attivo in uscita, a cui

seguirà lo scambio, una volta avvenuto lo scambio ci sarà il pezzo

in uscita ed effettuata l’uscita il pezzo rientra tra quelli fuori. Si è

aggiunto un passaggio in cui il pezzo è in attesa dello scambio ma

una volta avvenuto lo scambio è un pezzo in uscita, per lasciare

lo spazio al pezzo grezzo.

 Se scatta t4 il pezzo lavorato si toglierà dal piattello, il

piattello è libero per far posizionare un nuovo pezzo grezzo che sta arrivando dal nastro trasportatore.

 Ora abbiamo 8 posti, quindi vettore marcatura 8 righe, con le marche riportate in ciascuno degli 8 posti

Rifacciamo l’analisi delle transizioni abilitate allo scatto a

partire da M0 poi M1 ecc

T1 abilitata allo scatto, ma anche t4

Quale delle due scatta prima?

 Se scatta t1 mi troverò in uno stato successivo in cui

invece di avere una marca in P1 e una in p2 avrò una marca in

p3 (M1)

 Se scatta t4 si verifica la condizione che con lo scatto di

t4 mi troverò in M2 in cui t4 ha a monte una marca, a valle 2

marche (pezzi fuori) 0 marche (dove vista come forcella).

Abbiamo che la forcella se è marcata è libera, se non c’è il pallino la forcella non è libera

Quindi non posso fare il ragionamento quale scatta prima, le reti di petri non dipendono dal tempo ma vanno solo

analizzate secondo la successione degli eventi, devo analizzare tutte le possibili evoluzioni. Ho 2 transizioni

concorrenti, ragiono su se scatta questa in che direzione evolvo e viceversa.

Il grafo di stato, mentre prima era tutto in sequenza perché scattava una transizione alla volta, ora mi trovo in una

situazione di concorrenza Può scattare prima t1 o prima t4, ma se scatta prima t4 nulla vieta che poi scatti t1, così

come nulla vieta se scatta t1 che poi scatti t4, mi troverò in una situazione in cui ho uno

stato con entrambi gli scatti, stato M4 sono già scattate sia t1 che t4

4

CSZ sett 8

Arrivata a M4 possono scattare t2 e t5, quindi ho di nuovo una situazione di concorrenza

Se scatta t2 perdo la marca nel pezzo di lavorazione e la

acquisisco nel pezzo attivo in uscita, arrivo a M8.

Da M8 è abilitata solo t3, posso andare in una direzione

sola Se da M0 voglio arrivare a M8 ho

diversi percorsi

Dobbiamo considerare anche la

sequenza in rosso, prima non

l’avevamo messa, la consideriamo

perché una volta arrivati a M1

tramite t1 è abilitata anche t2 quindi

posso avere anche quel percorso

(Slide che ha saltato perché ha fatto alla lavagna, ma sembrano diverse da quello che ha fatto

5

CSZ sett 8 Se voglio ottenere M2 lo ottengo o andando ad analizzare dallo

stato iniziale (considerare ordine t1 t2), oppure parto dalla

relazione in cui conosco lo stato immediatamente precedente

e uso M1 più la matrice di incidenza per il vettore di

occorrenza.

Il problema di questa equazione di stato è che possiamo

applicarla su tutto anche quando le sequenze di

transizione non sono possibili. La sequenza 125 non è

corretta, ci viene un risultato ma non è ammissibile.

Dobbiamo sempre tracciare il grafo di stato e poi

applicare questa equazione.

6

CSZ sett 8

Approfondimenti sulle reti di petri Principio di non determinismo, non so

esattamente quale scatterà per prima ma so per

certo quali scatteranno, appena scatta una

transizione devo analizzare la situazione con la

marcatura.

Nel momento in cui abbiamo due o più

transizioni abilitate allo scatto le faremo

scattare a caso ma ogni volta che scatta una di

esse dobbiamo analizzare localmente quello che

avviene. Potrebbe essere che scattando una

l’altra è ancora abilitata allo scatto oppure no,

bisogna fare una valutazione. Andiamo a svincolare le reti di petri dal tempo. La rete di petri qui accanto identifica

un sistema produttivo che è costituito

da una sottorete di produttori e due

sottoreti di consumatori. La sottorete

di produttori costituita da p1 e p2,

transizioni t1, t2

 T1 rappresenta l’assegnazione

di materie prime

 T2 produzione di oggetti

 Posso avviare produzione

degli oggetti

 Quando scatta t2 trasformo le

materie prime in prodotti finiti

T1 non può scattare, t2 può scattare, allora produco oggetti, le due materie prime verranno trasformate. Se scatta t1

ci troviamo nella situazione in cui abbiamo una materia prima da trasformare e p7

e p2 verranno riempiti di un pallino (p7 con due pallini)

Se vado da p7 a t3, questa può scattare, allora devo cancellare entrambe le marche di p7 e ne acquisto una in p4. Un

consumatore si è visto assegnare i prodotti finiti richiesti, ora c’è l’esigenza di andare a soddisfare il consumo, poi ci

sarà nuovamente il cliente che vuole vedersi assegnare il prodotto finito. Nella sottorete costituita da p3 p4 ci sono

due soggetti che possono consumare.

I 3 cicli sono continuativi. 7

CSZ sett 8 Due transizioni si dicono in

sequenza se sono disposte in

maniera successiva e lo scatto

di una abilita l’altra. Ci

possono essere anche due

transizioni in conflitto: quando

si condividono un posto,

quindi abbiamo una situazione

come quella nella slide

accanto, io ho che sono

abilitate sia t1 che t2 però se

scatta t1 t2 non è più abilitata

e viceversa.

Conflitto strutturale lo osservo dalla tipologia, un posto in comune, l’effettivo lo vedo dalle marche. Se in p1 e p2 ho

tante marche non è detto che il conflitto sia strutturale ed effettivo.

8

CSZ sett 8

16/11

 In concorrenza: non si condividono nessun posto e sono abilitate a scattare

o Principio di non determinismo

 Principio di concorrenza

 Concorrenza strutturale è sempre effettiva

 Inizio concorrenza: smontaggio

 Sincronizzazione: montaggio

Proprietà di definizione delle reti di Petri

(proprietà già viste in precedenza) Home state non è una proprietà

ma uno stato

9

CSZ sett 8 Limitatezza: non c’è eccedenza di

marche (overflow)

10

CSZ sett 8

Se c’è un posto che ha accumulo di marche allora non è limitata. Una rete è limitata se tutti i posti della rete sono

limitati. Arrivati al punto t1 t2 t3 volendo si

può far scattare infinite volte t4,

così facendo però P5 accumula

marche. Se abbiamo però un

magazzino che può essere

riempito fino ad un certo punto

allora aggiungo un posto

complementare e poi controllo.

Una transizione viva è una transizione abilitata allo scatto.

Se giro e ho la transizione abilitata allo scatto allora la rete è viva.

11

CSZ sett 8

 RLV rete reversibile limitata viva

 RLV rete non reversibile limitata viva

 RLV

3

2 possibili combinazioni

Esempi 12

CSZ sett 9

21/11 Questa analisi diventa

impegnativa quando la rete

cresce allora si passa all’analisi

matriciale, abbiamo visto che

una rete di petri può essere

rappresentata in forma

matriciale.

Con l’analisi matriciale siamo in grado di qualificare una rete di Petri dal punto di vista comportamentale nei riguardi

dell’evoluzione, cioè sulla limitatezza, reversibilità e vivezza.

Ci sono dei risultati molto forti, e altre analisi che non danno una reale garanzia. Di base ci sono 4 caratteristiche

statiche che non variano con la marcatura ma

guardando la topologia della struttura, analizzare

la rete di Petri dal punto di vista topologico mi

porta a derivare queste proprietà.

 Invarianti

o Mantengono costante qualcosa

 Tipo P (sui posti)

 Tipo T (sulle transizioni

 Quantità che variano

o I sifoni Alcuni posti possono

perdere le marche, se li perde

progressivamente non sarà più in

grado di abilitare le transizioni,

o Le trappole al contrario attirano

tutte le marche 1

CSZ sett 9 Negli insiemi di posti quello che

si conserva è la somma delle

marche, somma pesata delle

marche, ci sono delle relazioni di

flusso che possono non essere

unitarie, se fossero tutte

unitarie allora sarebbe la somma

delle marche, se consideriamo

anche non unitarie allora si parla

di somma pesata delle marche.

T

X’ è un X vettore X trasposto

Dall’equazione di stato (equilibrio che ci permetteva di determinare una qualsiasi marcatura a partire da quella

iniziale) andiamo a sommare il prodotto matrice di incidenza per il vettore degli stati.

Il nostro obiettivo per trovare P-varianti

è trovare la soluzione più piccola in

grado di trovare anche le altre

soluzioni.

2

CSZ sett 9

Andiamo a fare un procedimento analogo per la rete accanto

3

CSZ sett 9

Analizziamo ora la terza rete della slide All’inizio l’unica

transizione abilitata è t2,

nel momento in cui scatta

mi troverò i posti in p3 e

in p4. La parte a sinistra

rappresenta un insieme di

posti in cui la marca si

conserva, la parte destra

rappresenta un insieme di

posti in cui la marca si

conserva, quindi il P-

invariante dice che ho una

marca a destra e una a

sinistra.

Gli invarianti di tipo p si trovano con

quelle due equazioni.

I supporti X1 e X2 trovati in precedenza

come due P invarianti dovrei prendere

1 1, entrambi sono supporti minimi,

ma i posti non nulli dell’uno sono

diversi dall’altro. X1 e X2 sono due

supporti minimi canonici

4

CSZ sett 9 Se la rete è conservativa posso dire

che è limitata.

Determino la matrice di incidenza ecc

ecc trovo le soluzioni, queste vanno

osservate, mi interessano le minime

canoniche ecc ecc quindi non mi

serve il grafo.

Una rete limitata non

necessariamente è conservativa. Se è

conservativa è limitata, ma non è

detto il contrario.

Gli invarianti di tipo T li

sfruttiamo per andare a

ragionare sulla reversibilità.

Andiamo a considerare come

vettore degli invarianti di tipo T

il vettore Y. È un T-invariante se

e solo se soluzione

dell’equazione nella slide.

5

CSZ sett 9

La reversibilità dipende quindi dalla struttura della rete ma anche dalla marcatura iniziale.

Ipotizziamo di avere trovato un

T

vettore Y=[ 1 2 0 1] ho 4 transazioni,

devono scattare una volta la prima,

due volte la seconda e una volta la

quarta per poter tornare nella

situazione iniziale. L’invariante di

tipo T dice una possibile sequenza di

scatti che va verificata per la

marcatura della rete in esame. Se

per tornare alla prima non sfrutto

mai la terza devo verificare che

questa non sia mai abilitata allo

scatto perché altrimenti potrebbe

scattare anche quella.

I sifoni sono un gruppo di posti che

complessivamente tendono a

perdere marche, fino ad arrivare

ad un certo punto con nessuna

transizione che può scattare,

allora la rete non è viva.

Il PRE di X è un insieme con la

transizione che è l’input al posto.

Pre di X significa che per ogni

posto devo vedere le transizioni in

ingresso a tutti i posti dell’insieme

X.

Quando parlo del post di X vado.

Considerare tutte le transizioni in

uscita al posto.

6

CSZ sett 9 P3 p4 è un sifone

Ho una marca in p1 e in p4

T3 è abilitata, l’evoluzione può

avvenire in quella direzione, ora

abbiamo marche in p1 e p3 e p2. Ora

le possibili evoluzioni sono nella

direzione t2 o t4. Se vado in t4

percorro il ciclo, se vado in t2

succede che le marche vanno in p2,,

questo ha generato che la rete

procede in direzione t1 ma la rete, le

due marche vanno in P1, ho solo 2

marche in p1 quindi ho perso una marca, questa rete non è viva.

S’ è un sifone più grande di S perché contiene una transizione in più.

23/11

Riassunto delle cose viste la scorsa volta:

Abbiamo analizzato le reti di Petri dal punto di vista comportamentale, cosa già affrontata dal punto di vista grafico.

A volte analizzare dal punto di vista visivo può essere difficoltoso, possiamo fare l’analisi strutturale della rete di Petri

tramite l’impiego di matrici, ci interessa la amatrice di incidenza, che tira in ballo tutte le relazioni di ingresso e

uscita. Ci sono 4 caratteristiche statiche della rete di Petri

 P-invarianti

o Si trovano nella matrice, si conserva la somma pesata delle marche se la rete è viva. Se esistono P-

invarianti e questi sono tali da comprendere al loro interno tutti i posti della rete allora possiamo

dire che la rete è coperta, conservativa, quindi è limitata

 T-invarianti

o Si trovano in maniera simile a quelli di tipo P. Con questi andiamo a verificare se nella rete si

conserva la proprietà di reversibilità, abbiamo anche specificato che quando andiamo a trovare gli

invarianti guardiamo solo la struttura della rete (non anche le marche). Nel caso del tipo T senza

guardare le marche non siamo sicuri della reversibilità, quindi bisogna controllare se per quella

marcatura abbiamo il t-invariante.

o Identifica un certo valore per ogni transizione. Se 0 la transizione non partecipa alla reversibilità, se 1

partecipa una volta sola, se 2 partecipa 2 volte ecc

o Per raggiungere una certa reversibilità, ipotizziamo di avere 5 transizioni nella rete devo far scattare

le transizioni del t-invariante in qualsiasi ordine, però le devo far scattare tutte

7

CSZ sett 9

 Sifoni

o Sono da intendersi un insieme di posti nei quali si vengono a perdere marche progressivamente, si

arriva ad un certo punto in cui non si hanno più marche, andiamo ad indagare sulla non vivezza,

dobbiamo vedere per quale percorso ad un certo punto la marcatura è morta.

o Il sifone è minimo se e solo se è contenuto in un altro sifone.

o Se siamo giunti (prendiamo esempio l’ultima slide dell’altra lezione), il sifone S con lo scatto di T3 e

t2 si era smarcato, qualsiasi marcatura raggiungibile da quella in cui si è smarcato avrà sempre i posti

smarcati?

In presenza di un sifone non marcato tutte le transizioni del posto sono morte, la rete non è viva. Se troviamo un

sifone non marcato siamo sicuri di avere una condizione di non vivezza.

 Trappole

o Accumula marche

complessivamente

o Pre e post, ci sono

dei pre da cui

arrivano marche e

dei post da cui non

escono.

o Devo verificare la

condizione che

definisce una

trappola,

nell’esempio di

prima le transizioni

in uscita 8

CSZ sett 9 La seconda trappola contiene in sé un sifone.

Se studiamo l’uguaglianza un P-

invariante acquista e perde

marche quindi nell’evoluzione

rimane costante

Con quest’ultima proprietà possiamo verificare subito il sifone. Possiamo avere un sifone che

contiene una trappola, allora

il sifone si rialimenta da

quella trappola, ma non è

detto che la rete sia viva perché se il sifone è smarcato lì ci saranno delle transizioni che non sono mai abilitate allo

scatto. 9

CSZ sett 9

Due libri, quello viola riguarda la parte di teoria delle reti di Petri, quello azzurro esercizi sulle reti di Petri

Esercizio 1 del capitolo analisi strutturale (libro blu)

10

CSZ sett 9

Prendiamo il primo T, se scatta t1 la marcatura va in p1, può scattare t2, che può andare in due direzioni, tolgo la

marca da p1 e in p6 e la porto in p5, poi la marcatura la sposto ecc ecc, torno alla marcatura iniziale

T1 t3 t5 t7 torno alla marcatura iniziale, quindi reversibile secondo questo percorso (l’ordine delle transizioni non

deve necessariamente essere quello).

Verifichiamo il secondo T

T2 non può scattare, t4 non può scattare, può scattare solo t6, la marca va da p6 a p7. Poi tolgo marche in p2 e p7 e

la metto in p3, poi scatta e la marca la riporto in p2, quindi anche qui reversibile perché sono di nuovo nella

situazione iniziale.

Rete reversibile a due vie.

Ora l’esercizio richiede di verificare cosa sono gli insiemi di posti scritti sopra

La rete è viva 11

CSZ sett 10

28/11 La macchina a stati è una rete

definita dalla condizione che

per ogni transizione

appartenente all’insieme delle

transizioni si verifica che il pre

ed il post di una qualunque

transizione valgono 1.

Automa (riesce a seguire un

flusso in maniera ordinata)

Un esempio di macchina a stati può essere ad esempio: Rete strettamente

conservativa: ipotizziamo di

avere un’unica marca, vuol dire

che questa di conserverà (se

conservativa è anche limitata),

esempio a sinistra con quella

marca posso andare o a destra

o a sinistra, posso decidere se percorrere un ciclo o l’altro, ma resterà sempre e comunque una sola marca.

Sappiamo già che è viva e limitata, dobbiamo sapere solo se è reversibile,

dobbiamo quindi verificare se è totalmente connessa, perché se non lo è allora

non è reversibile.

Abbiamo detto che è un particolare tipo di rete perché deduciamo subito delle

proprietà. 1

CSZ sett 10

Grafo marcato Per ogni posto appartenente

all’insieme dei posti il pre dei posti

è 1 così come il post del posto vale

1.

Nella macchina a stati potevamo avere dei conflitti tra le

transizioni, li modelliamo. Nel grafo marcato non si

possono modellare i conflitti. Modella allora situazioni di

sincronizzazione, (due posti connessi ad una transizione),

situazioni di inizio concorrenza.

Perché sia viva ogni ciclo deve avere almeno un posto

marcato. Un grafo marcato totalmente connesso che realizza la condizione che almeno un posto di ogni ciclo sia

marcato allora rappresenta una rete viva. 2

CSZ sett 10 Si dice che è a scelta libera se per ogni

transizione e per ogni posto il pre di T è

uguale al post, anche per i posti vale lo

stesso.

Ciò significa che: Non ammettono che ci sia contemporaneamente un conflitto ed

una sincronizzazione. O c’è solo il conflitto o solo la

sincronizzazione.

3

CSZ sett 10

Modellazione di sistemi produttivi

• Approccio fisico

o sistema produttivo complessivo costituito dalla somma di tutti i suoi sottosistemi (sistemi fisici

elementari)

o Andiamo a schematizzare ciascun sottosistema mediante una rete di petri elementare

o Andiamo a fondere quelle transizioni che devono avvenire nello stesso istante

• Approccio funzionale

o Identificare le varie tappe logiche (produttive, logistiche ecc) e sequenziarle opportunamente

o Allocare le risorse produttive 4

CSZ sett 10

Esempio

Quale dei due scegliere? Se i ragionamenti sono giusti dovrebbero portare allo stesso sistema, ma forse quello

funzionale ci permette di andare a modellare situazioni simili

5

CSZ sett 10

Immaginiamo ora che ci siano:

• Prodotto A

o Ottenuto mediante 3 operazioni 1,2,3

▪ 1,2 su M1

▪ 3 su M2

• Prodotto B

o Ottenuto mediante 3 operazioni 4,5,6

▪ 4,5 su M2

▪ 6 su M1

Utilizzo l’approccio funzionale, quindi ragiono per tappe logiche:

Abbiamo qui le ricette per il Job 1 e per il Job 2 6

CSZ sett 10

C’ è un posto tra la prima e la seconda operazione che rappresenta una fase di attesa, è più corretto in generale

mettere tra due macchine una fase di attesa che può essere o un magazzino a capacità limitata o infinita (caso in cui

tra le due macchine c’è talmente tanto spazio da poterla considerare tale).

Il buffer è un posto limitato (magari è un nastro che collega le due cose), il robot (l’altra risorsa da allocare)

nell’attesa non lavora. Il robot carica il pezzo sulla macchina M1, pezzo in lavorazione, il robot prende il pezzo e lo

mette sul nastro.

Per il Job 2 è tutto uguale tranne il robot per carico e scarico.

7

CSZ sett 10

30/11 Il processo in esame è costituito

da due centri di lavoro, oltre a

questi due robot (per carico e

scarico) e due nastri

trasportatori (uno per i pezzi da

lavorare su cui al massimo ci

possono essere 2 pezzi alla

volta, l’altro per pallet vuoti).

Il tipo di rete tracciata è stata

ottenuta con i metodi visti la

scorsa volta.

Tutti i pezzi vengono lavorati nel centro1, poi nel centro di lavoro2, sistema flow shop per tutti i pezzi. Dobbiamo

eseguire l’operazione su M1, poi disporlo sul nastro, poi eseguire l’operazione 2 su M2, poi dobbiamo rilasciare i

pezzi lavorati. Abbiamo detto che ogni operazione viene fatta con l’ausilio del robot che monta i pezzi sul pallet, alla

fine dobbiamo rilasciare i pallet.

Abbiamo 3 pallet disponibili, devo allocare le risorse.

Le risorse sono la macchina disponibile per l’operazione 1 e la macchina disponibile per l’operazione 2. L’altra risorsa

da allocare è il robot, ne abbiamo due, si occupano delle fasi di carico e scarico, il robot inizia a lavorare quando il

pallet è disponibile, ci mette il pezzo sopra (se la macchina è disponibile) e rimane impegnato finché non scarica il

pallet dopo la lavorazione. Dobbiamo imporre che il nastro al massimo può contenere due pezzi, dobbiamo quindi

limitare i posti sul nastro. Abbiamo usato l’approccio funzionale, prima le fasi principali e poi le risorse.

8

CSZ sett 10 Trova un unico T-invariante, vi è

un percorso di evoluzione che

comprende tutte e 4 le

transizioni col quale torno alla

condizione iniziale, non importa

in che ordine. Abbiamo

analizzato un solo percorso, non

tutti i percorsi quindi non

sappiamo se è sempre

reversibile, andrebbero

controllati tutti i percorsi

possibili.

9

CSZ sett 10 Ora possiamo dire se è reversibile.

Vediamo che possiamo sempre tornare

alla rete iniziale, quindi la rete è

reversibile.

Osservo che non ci sono marcature

morte, tutte le transizioni sono abilitate

allo scatto, tutte le marcature sono vive,

allora la rete è viva. Questa rete però

riusciamo ad analizzarla bene solo col

grafo di raggiungibilità e questo è

oneroso.

Ci accorgiamo che questo grafo

è marcato, avevamo detto che la

condizione di vivezza vale se

ogni suo ciclo è marcato.

I cicli sono:

• Macchina m1

o P2 e P5

• Robot

o P2 P8

• Buffer limitato (nastro)

• M2 o P4 P7

• R2 o P4 P9

• Poi c’è un ciclo che è quello dei pallet sul nastro N1(2)

o P3 P6

• Ciclo N2(3)

o P1 P2 P3 P4

Questi P sono i P-invarianti

Tutti i cicli sono marcati, la rete è viva, anche senza fare il grafo di raggiungibilità.

Quando risolveremo il sistema vedremo che avremo 4 equazioni in 9 incognite, non riusciremo quindi a risolvere il

sistema in maniera semplice. 10

CSZ sett 10

Esempio preso da un articolo (file case study sulla pagina sua)

Due job

• Job 1 consiste in:

o Stampa

o Taglio

o Confezionamento

• Job 2:

o Fogli

o Bustina

Calcolo dei P-invarianti

Come obiettivo si pone quello di annullare passo passo le colonne della matrice di incidenza dalla prima all’ultima. Le

annulla esprimendo le righe come combinazioni lineari tali che la loro somma produca zero sugli elementi della

prima colonna, poi sulla seconda ecc ecc iterativo. Termina quando ha annullato tutte le colonne possibili. In

corrispondenza delle colonne annullate troviamo i P-invarianti.

11

CSZ sett 10

La rete di petri di cui vogliamo i P-invarianti con questo algoritmo è schematizzata in basso, 5 posti

Algoritmo:

1. Calcolare matrice di incidenza

2. Costruire la matrice identità con dimensioni pari al numero dei posti con elementi unitari sulla diagonale

3. Obiettivo: annullare le colonne della matrice di incidenza

La prima colonna riporta -1 alla prima riga, 1 alla seconda, vado ad esprimere la riga di p1 e quella di p2 in maniera

opportuna, in questo caso p1+p2=0, si copia tutto il resto della matrice sotto, sotto riporta la combinazione lineare

p1+p2

Priorità delle transizioni L’ordine delle

transizioni lo

decidiamo noi.

12

CSZ sett 10

Archi inibitori

Sono archi che contengono un pallino alla fine della connessione.

Nel momento in cui abbiamo un arco di questo tipo la condizione

affinché possa scattare la transizione è che non ci siano marche

nel posto ad esso connesso.

Senza marche invece nessuna delle due transizioni sarebbe

abilitata.

Reti temporizzate

Ipotizziamo che ci siano una serie di operazioni che devono essere completate per poter avviare l’altra fase.

Solitamente vengono inseriti due valori numerici (a,b) che assumono il significato:

• Giunti ad a la transizione può scattare

• Entro b deve scattare Si tratta di

un

intervallo di

tempo in cui

deve

scattare

13

CSZ sett 11

5/12

Funzionamento del software per analizzare le reti di Petri

Il file è pipev4.3 lo possiamo scaricare e installare sia su Mac che Windows. Apriamo la cartella, c’è un esecutivo che

va lanciato e apre una finestra, non va installato.

Dobbiamo creare una rete, avremo la possibilità di selezionare la posizione dei posti, inserisco i posti, parte da P ,

0

scelgo di nominarlo P poi ne posso aggiungere altri (c’è un pulsante sulla barra degli strumenti in alto fatto a

1

cerchio), poi mettiamo le transizioni e poi gli archi orientati.

Ora dobbiamo analizzarla, a sinistra abbiamo ad esempio l’analisi degli invarianti, il software calcola t e p invarianti,

da lì possiamo trarre le nostre conclusioni.

Generiamo il grafo di raggiungibilità, dobbiamo marcarlo, inserisco la marcatura con tasto destro sul posto – edit.

Posso andare su animate e vedere le possibili evoluzioni, mi indica in rosso le transizioni abilitate allo scatto, posso

vedere poi come evolve la rete, la direzione la scegliamo noi.

Per l’esercitazione dobbiamo usare questo.

Analisi dei flussi in un sistema produttivo Il nostro obiettivo è valutare la capacità produttiva

del sistema. Andiamo a sfruttare per questo

obiettivo una teoria delle code.

Consideriamo dei clienti, questi chiederanno ad

una o più macchine l’esecuzione di un servizio,

ricevuto questo usciranno dal sistema produttivo.

Dobbiamo valutare la macchina che è in grado di

erogare questo servizio che capacità produttiva

ha. Considerando questa analisi per tutte le

macchine del sistema produttivo come dato finale

dobbiamo tirare fuori la capacità complessiva di

tutto il sistema.

Teoria delle code Si usa laddove esistono fenomeni

di attesa, si può applicare non

solo alle macchine ma a tutti i

posti dove ci sono delle attese.

Nel nostro caso si tratta di un

servizio produttivo, sia chi chiede

(non è detto che entrino tutti con

una cadenza sempre uguale) che

chi eroga il servizio (non è detto

che lo eroghi in maniera

costante).

Dobbiamo considerare un insieme

di servitori non vuoto, dobbiamo

considerare un’area di attesa, un

buffer dove accogliere i clienti, si

fa riferimento a clienti che

chiedono tutti lo stesso servizio,

andiamo a considerare una certa disciplina di servizio per erogarli: possiamo considerare la possibilità di erogare il

servizio in ordine di arrivo, ma ci sono anche altri contesti in cui non è così, nei servizi ospedalieri si va in base alla

1

CSZ sett 11

gravità. Nei magazzini l’ultimo arrivato è il primo ad essere prelevato. Faremo riferimento alla disciplina first in first

out (o server).

Dobbiamo considerare il processo di arrivo dei clienti e quello realizzato dai servitori che andranno ad erogare il loro

servizio. Tutti i pezzi che varcheranno la soglia del

sistema produttivo formeranno la nostra

coda, si disporranno in fila, 3 macchine

(eseguitori) che eseguiranno l’operazione

richiesta da quei pezzi, poi questi pezzi

verranno caricati dalla macchina in un’area e

verranno portati fuori dal sistema

produttivo.

Per andare ad identificare una coda

dobbiamo presentare i suoi elementi

costitutivi:

 Popolazione dei clienti

 Processo d’arrivo

 Coda

 Servitori (uno o più, con la stessa velocità o velocità diverse)

 Processo di servizio in senso di parametri

 Disciplina di servizio Abbiamo 3 macchine in grado di erogare

il servizio.

Per quanto riguarda la popolazione questa può essere:

 Clienti dello stesso tipo, cioè che richiedono una stessa lavorazione

o Popolazione finita

o Infinita (lotto molto molto grande) 2

CSZ sett 11 Il processo di arrivo dei clienti nel

sistema produttivo è qualificato

attraverso il tempo che intercorre

tra un ingresso e il successivo,

tempo di interarrivo. Solitamente

consideriamo questo tempo pari a

1/λ , dove λ è la velocità con cui i

pezzi arrivano nel sistema

produttivo.

Il processo di arrivo è aleatorio, caratteristiche dovute al caso, ma noi ci porremo sempre in una particolare

condizione (di stazionarietà), ci porremo in una condizione in cui le caratteristiche statistiche non variano nel tempo.

Se abbiamo un buffer limitato ad

un certo punto quando sarà pieno

le altre unità in arrivo verranno

rigettate.

Andremo a considerare una

velocità equivalente dei servitori.

μ è la velocità di servizio

Nel nostro sistema produttivo noi

andremo a ragionare sempre nel

modo: il primo che arriva è il

primo ad essere servito.

3

CSZ sett 11 Schema di definizione

I primi due elementi fanno

riferimento al processo di

arrivo e a quello di servizio,

sono identificati secondo le

loro specifiche distribuzioni.

Con C andiamo a specificare

il numero dei servitori, uno

o più. Con k intendiamo la

capacità massima del

sistema (la coda più lunga).

Con m la dimensione della

popolazione, Z disciplina di

servizio.

Se abbiamo una coda che è rappresentata con MM INF INF FCFS avremo un unico servitore, capacità del sistema

infinita, popolazione infinita, disciplina di servizio FCFS. Solitamente si può andare ad identificare questo tipo di coda

con le prime 3 lettere, questo perché si intende per default inf inf e firs in first served.

Questi sono parametri

prestazionali.

Esempio di coda

Distribuzione degli arrivi costante, dei servizi idem, unico servitore, popolazione infinita, capacità infinita, first in first

out Gli arrivi sono costanti e noti a

priori

Immaginiamo che:

a(1) = 8

a(2) = 8.02

…intervallo di arrivo 0.02 fino

ad a(5)

Ipotizziamo tempo di servizio

pari a 3 minuti

s(1) = 3

s(2) = 3

4

CSZ sett 11

s(3)=3

…ecc

Ci chiede l’istante di uscita del cliente i-esimo Possiamo calcolare

per ogni istante

quante persone ci

sono nel sistema.

Andiamo a considerare la distribuzione esponenziale Richiede 3 ipotesi fondamentali

1. Ipotesi di uniformità: La

probabilità che un evento si

verifichi è maggiore quanto

maggiore è l’intervallo di tempo

considerato

2. Ipotesi che non si

possono avere più di un evento

nello stesso istante di tempo

3. Indipendenza degli

eventi

Con poisson consideriamo un

processo di arrivo esponenziale,

possiamo calcolare per un certo

istante il numero di clienti nel

sistema produttivo

Consideriamo ora processo di nascita (entrata di un cliente) e morte (uscita di un cliente)

5

CSZ sett 11 Ipotizziamo in un istante

iniziale popolazione = 0, in un

successivo istante popolazione

= 1, potrà verificarsi poi o

un’altra nascita o una morte.

In un istante generico mi posso

trovare in una situazione in cui

la popolazione è pari ad n,

posso trovarmi in n+1

attraverso un tasso di nascita

oppure nello stato adiacente

n-1 per effetto di una morte.

Nell’intervallo di tempo

considerato può succedere

anche che non ci sia nessuna

evoluzione.

Tre situazioni: La probabilità di avere n clienti in fila al

tempo t è la somma di questi 3 eventi.

Abbiamo un sistema di equazioni differenziali, la risoluzione sarebbe molto complessa, ci mettiamo in una situazione

semplificata: in un tempo infinito deve succedere che il tasso delle uscite superi il tasso delle nascite, se questo non

si verificasse la coda esploderebbe. Per un tempo sufficientemente grande il tasso delle morti deve superare quello

delle nascite in modo tale che la coda possa essere risolvibile.

Ci mettiamo nella condizione in cui verificata questa situazione mi trovo in una coda stabile: tanti ne entrano quanti

ne escono, condizione di stazionarietà.

Consideriamo allora le proprietà indipendenti dal tempo:

Significa fare un equilibrio al nodo, cioè flusso entrante uguale a flusso uscente.

6


ACQUISTATO

3 volte

PAGINE

144

PESO

40.61 MB

AUTORE

CSY

PUBBLICATO

8 mesi fa


DETTAGLI
Corso di laurea: Corso di laurea in ingegneria gestionale
SSD:
A.A.: 2018-2019

I contenuti di questa pagina costituiscono rielaborazioni personali del Publisher CSY di informazioni apprese con la frequenza delle lezioni di Programmazione e controllo della produzione e studio autonomo di eventuali libri di riferimento in preparazione dell'esame finale o della tesi. Non devono intendersi come materiale ufficiale dell'università La Sapienza - Uniroma1 o del prof Gisario Annamaria.

Acquista con carta o conto PayPal

Scarica il file tutte le volte che vuoi

Paga con un conto PayPal per usufruire della garanzia Soddisfatto o rimborsato

Recensioni
Ti è piaciuto questo appunto? Valutalo!

Altri appunti di Programmazione e controllo della produzione

Sintesi programmazione e controllo della produzione
Appunto
Tecnologia dei processi produttivi - tpp
Appunto
Fondamenti di Automatica, Analisi
Appunto
Elettronica - gestionale prof. Balucani
Appunto