Análise de DesempenhoAnálise de Desempenho Analíticos
– Determinísticos Melhor e pior casos
– Probabilisticos Valores prováveis
Simulação Análise exaustiva
Implementação real– Medidas obtidas do sistema real– Benchmarks– Protótipos
Redes de PetriRedes de Petri
Espaço dosFormalismos
NíveisdeAbstração
Interpretações
Aut
ônom
o
Est
ocás
tico
Det
rem
inís
tico
Inte
rval
o
Pre
dica
dos
Lim
ites
Sin
ais
Ext
erno
s
Temporizado Dados Interpretados
Obj.RdP
Pr/T, CPN
P,T
CE, EN
Redes TemporizadasRedes Temporizadas
ExtensõesTemporizadas
Token-TimedPN
Transition-TimedPN
Place-TimedPN
StochasticPN
TimePN
……
TimedPN
Redes TemporizadasRedes Temporizadas
ExtensõesTemporizadas
Token-TimedPN
Transition-TimedPN
Place-TimedPN
StochasticPN
TimePN
……
TimedPN
Redes TemporizadasRedes Temporizadas
Ramchandani, 1973 - Transition Timed Ramchandani, 1973 - Transition Timed NetNet
Merlin, 1976 - Transition Time NetMerlin, 1976 - Transition Time Net Sifakis, 1977 - Place Timed NetSifakis, 1977 - Place Timed Net
Redes Temporizadas Redes Temporizadas EstocásticasEstocásticas
Natkin -1980Natkin -1980 Molloy - 1981Molloy - 1981 Marsan et al. - 1984Marsan et al. - 1984
É uma rede temporizada onde o É uma rede temporizada onde o delaydelay associado à transição é uma variável associado à transição é uma variável aleatória de distribuição exponencialaleatória de distribuição exponencial
Redes TemporizadasRedes Temporizadas Redes de Petri com Lugares Temporizados Redes de Petri com Lugares Temporizados
(PTPN) (Sifakis77)(PTPN) (Sifakis77) Definição: PTPN=(P,T,F,K,W,MDefinição: PTPN=(P,T,F,K,W,M00,,,,), onde ), onde
P é o conjunto de lugares,P é o conjunto de lugares,
T o conjunto de transições, T o conjunto de transições,
F F (P (P T) T) (T (T P) uma relação que representa os arcos P) uma relação que representa os arcos
WW – Valoração (peso dos arcos) - W: F – Valoração (peso dos arcos) - W: F N N
MM00- Marcação inicial - M- Marcação inicial - M00:P :P N N
={={11, , 22,…, ,…, ii,…} números reais denominada base de tempo.,…} números reais denominada base de tempo.
:P :P um mapeamato que um mapeamato que (p) = (p) = jj
Redes TemporizadasRedes Temporizadas - - PTPN -PTPN -
2
t0 p0 t1
Regra de DisparoRegra de Disparo
(p0) = 3(p0) = 3
p1
2
Redes TemporizadasRedes Temporizadas - - PTPN -PTPN -
2
t0 p0 t1
Regra de DisparoRegra de Disparo
Instante=0
p1
2
(p0) = 3(p0) = 3
Redes TemporizadasRedes Temporizadas - - PTPN -PTPN -
2
t0 p0 t1
Regra de DisparoRegra de Disparo
Instante=1
p1
2
(p0) = 3(p0) = 3
Redes TemporizadasRedes Temporizadas - - PTPN -PTPN -
2
t0 p0 t1
Regra de DisparoRegra de Disparo
Instante=2
p1
2
(p0) = 3(p0) = 3
Redes TemporizadasRedes Temporizadas - - PTPN -PTPN -
2
t0 p0 t1
Regra de DisparoRegra de Disparo
Instante=3
p1
2
(p0) = 3(p0) = 3
Redes de Petri Redes de Petri TemporizadasTemporizadas
- - Tempo Associado às Tempo Associado às TransiçõesTransições - -
Conceitos Básicos:Conceitos Básicos:– Duração (disparo em três fases)Duração (disparo em três fases)
Marcas são consumidas dos lugares de entradaMarcas são consumidas dos lugares de entrada Há uma duraçãoHá uma duração Marcas são geradas no lugares de saídaMarcas são geradas no lugares de saída
– Disparo atômicoDisparo atômico As marca permanecem nos lugares de entrada As marca permanecem nos lugares de entrada
pelo período igual ao pelo período igual ao delaydelay associada à transição. associada à transição. Após o Após o delaydelay as marcas são consumidas e as marcas são consumidas e geradas nos lugares de saída imediatamente.geradas nos lugares de saída imediatamente.
Redes de Petri Redes de Petri TemporizadasTemporizadas
- - Tempo Associado às Tempo Associado às TransiçõesTransições - -
Conceitos Básicos:Conceitos Básicos:– Duração (disparo em três fases)Duração (disparo em três fases)
Pode ser representada por uma rede com disparo Pode ser representada por uma rede com disparo atômicoatômico
Modelo mais compactoModelo mais compacto O estado é uma informação mais complexa do O estado é uma informação mais complexa do
que o modelo não-temporizadoque o modelo não-temporizado
– Disparo atômicoDisparo atômico Pode representar o modelo com duraçãoPode representar o modelo com duração O conjunto de marcações alcançáveis é um sub-O conjunto de marcações alcançáveis é um sub-
conjunto das marcações do modelo não-conjunto das marcações do modelo não-temporizado.temporizado.
Redes de Petri Redes de Petri TemporizadasTemporizadas
- - Tempo Associado às Tempo Associado às TransiçõesTransições - -
Conceitos Básicos:Conceitos Básicos:
– Regras de Seleção:Regras de Seleção: Pré-seleção:Pré-seleção: (duração e (duração e delaydelay))
– PrioridadePrioridade– ProbabilidadeProbabilidade
Race Race (corrida):(corrida): ( (delaydelay))– Transições habilitadas com menor Transições habilitadas com menor delaydelay são são
disparadasdisparadas
Redes de Petri Redes de Petri TemporizadasTemporizadas
- - Tempo Associado às Tempo Associado às TransiçõesTransições - -
Conceitos Básicos:Conceitos Básicos:– Quando uma das transições Quando uma das transições
conflitantes é desabilitada pelo conflitantes é desabilitada pelo disparo da outra, o que acontece disparo da outra, o que acontece com o com o timertimer da que ficou da que ficou desabilitada quando a mesma desabilitada quando a mesma tornar-se habilitada outra vez?tornar-se habilitada outra vez?
Redes de Petri Redes de Petri TemporizadasTemporizadas
- - Tempo Associado às Tempo Associado às TransiçõesTransições - -
Como fica a memorização Como fica a memorização do tempo de habilitação do tempo de habilitação anterior?anterior?
ContinueContinue– O O timertimer associado à transição associado à transição
mantem o valor atual e quando mantem o valor atual e quando a transição se tornar a transição se tornar novamente habilitada o valor novamente habilitada o valor do do timertimer iniciará daquele valor. iniciará daquele valor.
Restart– Quando a transição for
novamente habilitada o timer será re-iniciado.
ta tb
p0
p1 p2
dadb
Redes de Petri Redes de Petri TemporizadasTemporizadas
- - Tempo Associado às Tempo Associado às TransiçõesTransições - -
Conceitos Básicos:Conceitos Básicos:– O que acontece com o O que acontece com o timertimer das das
transições habilitadas após o transições habilitadas após o disparo de uma transição? disparo de uma transição?
Todas as transições. Não somente Todas as transições. Não somente as transições conflitantes.as transições conflitantes.
•Algumas políticas de memória podem ser construídas
Redes de Petri Redes de Petri TemporizadasTemporizadas
- - Tempo Associado às Tempo Associado às TransiçõesTransições - -
Conceitos Básicos:Conceitos Básicos:
– ResamplingResampling Após cada disparo os Após cada disparo os timers timers de de TODASTODAS as as
transições são re-iniciadotransições são re-iniciado ( (restartrestart)) Não há memóriaNão há memória Após descartar todos os Após descartar todos os timerstimers, os valores , os valores
iniciais são associados a todas as iniciais são associados a todas as transições que se tornarem habilitadas na transições que se tornarem habilitadas na nova marcaçãonova marcação..
Redes de Petri Redes de Petri TemporizadasTemporizadas
- - Tempo Associado às Tempo Associado às TransiçõesTransições - -
Conceitos Básicos:Conceitos Básicos:
– Enabling MemoryEnabling Memory Após cada disparo os Após cada disparo os timers timers das das
transições que ficaram desabilitadastransições que ficaram desabilitadas são re-iniciados (são re-iniciados (restartrestart))
As As transições que permaneceram transições que permaneceram habilitadashabilitadas com o disparo matêem com o disparo matêem seus valores presentes(seus valores presentes(continuecontinue))
Redes de Petri Redes de Petri TemporizadasTemporizadas
- - Tempo Associado às Tempo Associado às TransiçõesTransições - -
Conceitos Básicos:Conceitos Básicos:
– Age MemoryAge Memory Após cada disparo os Após cada disparo os timerstimers de de
todas todas as transições são mantidos as transições são mantidos em seus valores presentes em seus valores presentes ((continuecontinue))
Redes de Petri Redes de Petri TemporizadasTemporizadas
- - Tempo Associado às Tempo Associado às TransiçõesTransições - -
Conceitos Básicos:Conceitos Básicos:– Grau de Habilitação Grau de Habilitação
((Enabling Degree)Enabling Degree) É o número de vezes que É o número de vezes que
uma determinada uma determinada transição pode ser transição pode ser disparada, antes de se disparada, antes de se torna desabilitada.torna desabilitada.
Quando o grau de Quando o grau de habilitação é habilitação é maior que maior que umum, atenção especial à , atenção especial à semântica de semântica de temporização deve ser temporização deve ser considerada.considerada.
ta
p0
p1
p1
d
Redes de Petri Redes de Petri TemporizadasTemporizadas
- - Tempo Associado às Tempo Associado às TransiçõesTransições - -
Conceitos Básicos:Conceitos Básicos:– Semântica de TemporizaçãoSemântica de Temporização
Single-serverSingle-server firing semantics firing semantics
Infinite-serverInfinite-server firing semantics firing semantics
Multiple-serverMultiple-server firing semantics firing semantics– K é o máximo grau de paralelismo. Quando K é o máximo grau de paralelismo. Quando
kk , Multiple-server firing semantics , Multiple-server firing semantics é igual a é igual a infinite-server firing semantics.infinite-server firing semantics.
Redes de Petri Redes de Petri TemporizadasTemporizadas
- - Tempo Associado às Tempo Associado às TransiçõesTransições - -
Conceitos Básicos:Conceitos Básicos:– Single-serverSingle-server firing firing
semanticssemantics
ta
p0
p1
d=3 t=3 t=6 t=9 t
Redes de Petri Redes de Petri TemporizadasTemporizadas
- - Tempo Associado às Tempo Associado às TransiçõesTransições - -
Conceitos Básicos:Conceitos Básicos:– Infinite-serverInfinite-server firing firing
semanticssemantics
ta
p0
p1
d=3 t=3 t
Redes de Petri Redes de Petri TemporizadasTemporizadas
- - Tempo Associado às Tempo Associado às TransiçõesTransições - -
Conceitos Básicos:Conceitos Básicos:– Multiple-serverMultiple-server
firing semantics firing semantics k=2k=2
ta
p0
p1
d=3 tt=3 t=6
Redes TemporizadasRedes Temporizadascom Transições com Transições TemporizadasTemporizadas
Time Petri Nets Time Petri Nets (Merlin76)(Merlin76) Definição: TPN=(P,T,F, W,MDefinição: TPN=(P,T,F, W,M00,I), onde ,I), onde
P é o conjunto de lugares,P é o conjunto de lugares,
T o conjunto de transições, T o conjunto de transições,
F F (P (P T) T) (T (T P) uma relação que representa os arcos P) uma relação que representa os arcos
WW – Valoração (peso dos arcos) - W: F – Valoração (peso dos arcos) - W: F MM00- Marcação inicial - M- Marcação inicial - M00::PP
I:(DI:(Dminmin,D,Dmaxmax))
DDminmin: : ((+ + {0}) {0})TT , D , Dmaxmax:(:(+ + {0}) {0})TT, onde I(t, onde I(tii)=(d)=(diiminmin, d, dii
maxmax), ),
ddiimaxmax d dii
minmin
TC: T TC: T é uma função parcial que associa as transições um é uma função parcial que associa as transições um timer clocktimer clock
Redes TemporizadasRedes Temporizadascom Transições com Transições TemporizadasTemporizadas
Semântica de Disparo de TransiçãoSemântica de Disparo de Transição Uma transição Uma transição ttjj é é disparáveldisparável se estiver habilitadase estiver habilitada
– Regras de habilitaçãoRegras de habilitação M[tM[tjj > , M(pi) > , M(pi) pi, tpi, tjj)) pi pi PPdurantedurante o intervalo I(t o intervalo I(tjj)=(d)=(djj
minmin, d, djjmaxmax), ),
Ou seja,Ou seja, t tj j só será disparável só será disparável se tc(tse tc(tjj) ) d djjminmin
e terá e terá que disparar que disparar antes queantes que tc(ttc(tjj) > d) > djjmaxmax ((strong semanticsstrong semantics) )
ouou e poderá e poderá disparar disparar antes queantes que tc(ttc(tjj) > d) > djj
maxmax ((weak semanticsweak semantics) ) Resampling Resampling (Merlin76)/(Merlin76)/Enabling MemoryEnabling Memory(Starke87)(Starke87) Regras de disparoRegras de disparo Se M[tSe M[tjj >M’ >M’ M’(pi)=M0(pi) - I(pi, tM’(pi)=M0(pi) - I(pi, tjj)+O(pi, t)+O(pi, tjj), ), pi pi PP
Redes TemporizadasRedes Temporizadascom Transições com Transições TemporizadasTemporizadas
p0 t0 p1 t1 p2
[3,5] [1,3]
M0
tc(t0)=1tc(t1)= indefinido
Redes TemporizadasRedes Temporizadascom Transições com Transições TemporizadasTemporizadas
p0 t0 p1 t1 p2
[3,5] [1,3]
M0
tc(t0)=2tc(t1)= indefinido
Redes TemporizadasRedes Temporizadascom Transições com Transições TemporizadasTemporizadas
p0 t0 p1 t1 p2
[3,5] [1,3]
M0
tc(t0)=3tc(t1)= indefinido
t0 pode disparar
Redes TemporizadasRedes Temporizadascom Transições com Transições TemporizadasTemporizadas
p0 t0 p1 t1 p2
[3,5] [1,3]
M0
tc(t0)=4tc(t1)= indefinido
Redes TemporizadasRedes Temporizadascom Transições com Transições TemporizadasTemporizadas
p0 t0 p1 t1 p2
[3,5] [2,4]
M0
tc(t0)= indefinidotc(t1)=1
M1t0
Redes TemporizadasRedes Temporizadascom Transições com Transições TemporizadasTemporizadas
p0 t0 p1 t1 p2
[3,5] [2,4]
M0
tc(t0)= indefinidotc(t1)=2
M1t0
t1 pode disparar
M2t1
Redes TemporizadasRedes Temporizadascom Transições com Transições TemporizadasTemporizadas
p0 t0 p1 t1 p2
[3,5] [2,4]
M0
tc(t0)= indefinidotc(t1)= indefinido
M1t0
M2t1
Redes TemporizadasRedes Temporizadascom Transições com Transições TemporizadasTemporizadas
p0
t0
p1
t1t2
p2 p3
[2,3]
[2,3] [2,4]
M0 tc(t0)= 1tc(t1)= indefinidotc(t2)= indefinido
Redes TemporizadasRedes Temporizadascom Transições com Transições TemporizadasTemporizadas
p0
t0
p1
t1t2
p2 p3
[2,3]
[2,3] [2,4]
M0 tc(t0)= 2tc(t1)= indefinidotc(t2)= indefinido
Redes TemporizadasRedes Temporizadascom Transições com Transições TemporizadasTemporizadas
p0
t0
p1
t1t2
p2 p3
[2,3]
[2,3] [2,4]
M0 tc(t0)= indefinidotc(t1)= 1tc(t2)= 1
M1
t0
Redes TemporizadasRedes Temporizadascom Transições com Transições TemporizadasTemporizadas
p0
t0
p1
t1t2
p2 p3
[2,3]
[2,3] [2,4]
M0 tc(t0)= indefinidotc(t1)= 2tc(t2)= 2
M1
t0
Redes TemporizadasRedes Temporizadascom Transições com Transições TemporizadasTemporizadas
p0
t0
p1
t1t2
p2 p3
[2,3]
[2,3] [2,4]
M0 tc(t0)= 1tc(t1)= indefinidotc(t2)= indefinido
Redes TemporizadasRedes Temporizadascom Transições com Transições TemporizadasTemporizadas
p0
t0
p1
t1t2
p2 p3
[2,3]
[2,3] [2,4]
M0 tc(t0)= 2tc(t1)= indefinidotc(t2)= indefinido
Redes TemporizadasRedes Temporizadascom Transições com Transições TemporizadasTemporizadas
p0
t0
p1
t1t2
p2 p3
[2,3]
[2,3] [2,4]
M0 tc(t0)= 1tc(t1)= 1tc(t2)= 1
M1
t0
Redes TemporizadasRedes Temporizadascom Transições com Transições TemporizadasTemporizadas
p0
t0
p1
t1t2
p2 p3
[2,3]
[2,3] [2,4]
M0 tc(t0)= 2tc(t1)= 2tc(t2)= 2
M1
t0
Redes TemporizadasRedes Temporizadascom Transições com Transições TemporizadasTemporizadas
p0
t0
p1
t1t2
p2 p3
[2,3]
[2,3] [2,4]
M0 tc(t0)= 1tc(t1)= indefinidotc(t2)= indefinido
M1
t0
M2
t1
Redes TemporizadasRedes Temporizadascom Transições com Transições TemporizadasTemporizadas
p0
t0
p1
t1t2
p2 p3
[2,3]
[2,3] [2,4]
M0
M1
t0
M2
t1
M3
t2
tc(t0)= 1tc(t1)= indefinidotc(t2)= indefinido
Redes TemporizadasRedes Temporizadascom Transições com Transições TemporizadasTemporizadas
p0
t0
p1
t1t2
p2 p3
[2,3]
[2,3] [2,4]
M0
M1
t0
M2
t1
M3 M4
t2t0
tc(t0)= indefinidotc(t1)= 1tc(t2)= 1
Grafo de AlcançabilidadeGrafo de Alcançabilidade- - Untimed Model -Untimed Model -
Definição:Grafo de Alcançabilidade- seja Definição:Grafo de Alcançabilidade- seja uma rede marcada uma rede marcada N=(R,MN=(R,M00)). . RG(R, RG(R, MM00)=(RS,ARCS))=(RS,ARCS) define o grafo de define o grafo de alcançabilidade (alcançabilidade (Reachability GraphReachability Graph), onde ), onde RSRS é o conjunto de vértice e representa o é o conjunto de vértice e representa o conjunto de alcançabilidade. conjunto de alcançabilidade. ARCS ARCS RS RS T T RS RS é uma relação representando os arcos. é uma relação representando os arcos.
Redes TemporizadasRedes Temporizadascom Transições com Transições TemporizadasTemporizadas
Time Petri Nets Time Petri Nets Definição:Definição: Grafo de Alcançabilidade Grafo de Alcançabilidade
TemporizadoTemporizado- seja uma rede marcada - seja uma rede marcada TTN=(R,MN=(R,M00,I),I). . TRG(TN)=(S,ARCS)TRG(TN)=(S,ARCS) define o grafo define o grafo de alcançabilidade temporal (de alcançabilidade temporal (Time Reachability Time Reachability GraphGraph), onde ), onde SS é o conjunto de vértice e é o conjunto de vértice e representa o conjunto de alcançabilidade. representa o conjunto de alcançabilidade. ARCS ARCS S S S S é uma relação representando os arcos. é uma relação representando os arcos. S = (M,TC)S = (M,TC), onde , onde M: M: PP e e TC: T TC: T é uma é uma função parcial que associa as transições um função parcial que associa as transições um timer clock, timer clock, que representa o tempo passado que representa o tempo passado (desde a sua habilitação) até atingir-se (desde a sua habilitação) até atingir-se M.M.
S S RS RS
Redes TemporizadasRedes Temporizadascom Transições com Transições TemporizadasTemporizadas
Timed Petri Nets Timed Petri Nets (Ramchandani74,Zuberek87)(Ramchandani74,Zuberek87) Definição: TPN=(P,T,F, W,MDefinição: TPN=(P,T,F, W,M00,c,D), onde ,c,D), onde
P é o conjunto de lugares,P é o conjunto de lugares,
T o conjunto de transições, T o conjunto de transições,
F F (P (P T) T) (T (T P) uma relação que representa os arcos P) uma relação que representa os arcos
WW – Valoração (peso dos arcos) - W: F – Valoração (peso dos arcos) - W: F MM00- Marcação inicial - M- Marcação inicial - M00: P : P
D: T D: T + + {0} {0}
c:T c:T 0 01 função de probabilidade de escolha, tal que1 função de probabilidade de escolha, tal que
ttii c(t) = 1, c(t) = 1, TTiiFree(T), onde Free(T)={TFree(T), onde Free(T)={T11,..., T,..., Tnn} conjunto } conjunto de conjuntos de transições de conjuntos de transições free-choice.free-choice.
Redes TemporizadasRedes Temporizadascom Transições com Transições TemporizadasTemporizadas
TPN=(P,T,F, W,MTPN=(P,T,F, W,M00,c,D),,c,D),p0
p1
p2
p3
p4
p5
p6t0
t1
t2
t3
t4
t5
d0
d1
d2
d3
d4
d5
c0 c3
c1 c4
c2
c5
Redes TemporizadasRedes Temporizadascom Transições com Transições TemporizadasTemporizadas
Timed Petri Nets Timed Petri Nets Definição: Definição: Estado Estado - Seja - Seja TPN=(P,T,F, W,MTPN=(P,T,F, W,M00,c,D),c,D) uma uma Timed Petri Timed Petri
netnet. Um estado é definido por uma tupla . Um estado é definido por uma tupla s=(ms=(m11,m,m22,r),r), onde , onde MM11: P : P é a marcação é a marcação MM22: T : T é uma função que mapeia cada transição em é uma função que mapeia cada transição em natural, onde este natural representa o número de vezes que natural, onde este natural representa o número de vezes que aquela transição está sendo disparada naquele estado aquela transição está sendo disparada naquele estado SS..R: TR: Tk k + + {0} {0} se mse m22(t(tii) ) 0 0
indefinidaindefinida se mse m22(t(tii) = 0) = 0 onde onde k k é o número de vezes que é o número de vezes que ttii está sendo está sendo
disparada em disparada em SS ( (mm22(t(tii)= k)= k ) ) r(tr(tii): (): (+ + {0}) {0})kk é um vetor que associa a cada disparo de é um vetor que associa a cada disparo de ttii um número real que representa o um número real que representa o remaining firingremaining firing timetime de cada de cada disparo de disparo de ttii naquele estado naquele estado SS. . rrjj(t(tii) ) é j-ésimo componente de é j-ésimo componente de R(tR(tii))
Redes TemporizadasRedes Temporizadascom Transições com Transições TemporizadasTemporizadas
Timed Petri Nets Timed Petri Nets Definição: Definição: Regra de Habilitação e Disparo Regra de Habilitação e Disparo - Seja - Seja TPN=(P,T,F, TPN=(P,T,F,
W,MW,M00,c,D),c,D) uma uma Timed Petri net Timed Petri net e e s=(ms=(m11,m,m22,r),r) um estado em algum um estado em algum instante instante + + {0} {0}..Um Um step step st: T st: T está habilitado se está habilitado se
mm11(pi) (pi) ttTTst(t).W(pi,t), st(t).W(pi,t), pi pi PPSe um Se um stepstep stst está habilitado em um instante está habilitado em um instante (vamos tratar nos (vamos tratar nos )), dispara-se , dispara-se stst em em ..Em Em +1+1, tem-se: , tem-se: m’m’11(pi) (pi) m’m’1 1 - - ttC0C0st(t).W(pi,t)st(t).W(pi,t)
+ + ttC1C1st(t).W(t,pi) + st(t).W(t,pi) + ttC2C2 mm22(t).W(t,pi), (t).W(t,pi), pi pi PP, onde, ondeCC00={t ={t T | st(t) > 0} T | st(t) > 0}CC11={t ={t T | st(t) > 0 T | st(t) > 0 D(t) =1} D(t) =1}CC22={t ={t T | R T | Rjj(t) =1 (t) =1 t t st}, 0< j st}, 0< j K K m’m’22(t) = (t) = mm22(t) - (t) - m’m’2,2,+1+1(t), (t), m’m’2,2,+1+1(t) (t) representa que “sairam” da representa que “sairam” da transição no instantetransição no instante +1+1 r’r’jj(t)= r(t)= rjj(t)-1, t (t)-1, t m m22 t t st st (transições pertencentes ao (transições pertencentes ao stepstep stst ou ou as que já se encontravam “dentro” (as que já se encontravam “dentro” (mm22) das transições)) das transições)
Redes TemporizadasRedes Temporizadascom Transições com Transições TemporizadasTemporizadas
p0
t0
p2t2
p4
t3p5
p1
t1
p3
d0=2
d1=2d2=3
d4=3
Redes TemporizadasRedes Temporizadascom Transições com Transições TemporizadasTemporizadas
p0
t0
p2t2
p4
t3p5
p1
t1
p3
d0=2
d1=2d2=3
d4=3
No instante =1, r1(t0) = 1, m2(t0) = 1
Redes TemporizadasRedes Temporizadascom Transições com Transições TemporizadasTemporizadas
p0
t0
p2t2
p4
t3p5
p1
t1
p3
d0=2
d1=2d2=3
d4=3
•No instante =1, r1(t0) = 1, m2(t0) = 1•No instante =2, r(t1) = 2, m2(t1) = 1 r(t1) = 3, m2(t1) = 1
Redes TemporizadasRedes Temporizadascom Transições com Transições TemporizadasTemporizadas
p0
t0
p2t2
p4
t3p5
p1
t1
p3
d0=2
d1=2d2=3
d4=3
•No instante =1, r1(t0) = 1, m2(t0) = 1•No instante =2, r(t1) = 2, m2(t1) = 1 r(t2) = 3, m2(t2) = 1
Redes TemporizadasRedes Temporizadascom Transições com Transições TemporizadasTemporizadas
p0
t0
p2t2
p4
t3p5
p1
t1
p3
d0=2
d1=2d2=3
d4=3
•No instante =1, r1(t0) = 1, m2(t0) = 1•No instante =2, r(t1) = 2, m2(t1) = 1 r(t2) = 3, m2(t2) = 1•No instante =3, r(t1) = 1, m2(t1) = 1 r(t2) = 2, m2(t2) = 1
Redes TemporizadasRedes Temporizadascom Transições com Transições TemporizadasTemporizadas
p0
t0
p2t2
p4
t3p5
p1
t1
p3
d0=2
d1=2d2=3
d4=3
•No instante =1, r1(t0) = 1, m2(t0) = 1•No instante =2, r(t1) = 2, m2(t1) = 1 r(t2) = 3, m2(t2) = 1•No instante =3, r(t1) = 1, m2(t1) = 1 r(t2) = 2, m2(t2) = 1•No instante =4, r(t2) = 1, m2(t2) = 1
Redes TemporizadasRedes Temporizadascom Transições com Transições TemporizadasTemporizadas
p0
t0
p2t2
p4
t3p5
p1
t1
p3
d0=2
d1=2d2=3
d3=3
•No instante =1, r1(t0) = 1, m2(t0) = 1•No instante =2, r(t1) = 2, m2(t1) = 1 r(t2) = 3, m2(t2) = 1•No instante =3, r(t1) = 1, m2(t1) = 1 r(t2) = 2, m2(t2) = 1•No instante =4, r(t2) = 1, m2(t2) = 1•No instante =5, r(t3) = 3, m2(t3) = 1
Redes TemporizadasRedes Temporizadascom Transições com Transições TemporizadasTemporizadas
p0
t0
p2t2
p4
t3p5
p1
t1
p3
d0=2
d1=2d2=3
d3=3
•No instante =1, r1(t0) = 1, m2(t0) = 1•No instante =2, r(t1) = 2, m2(t1) = 1 r(t2) = 3, m2(t2) = 1•No instante =3, r(t1) = 1, m2(t1) = 1 r(t2) = 2, m2(t2) = 1•No instante =4, r(t2) = 1, m2(t2) = 1•No instante =5, r(t3) = 3, m2(t3) = 1
Redes TemporizadasRedes Temporizadascom Transições com Transições TemporizadasTemporizadas
p0
t0
p2t2
p4
t3p5
p1
t1
p3
d0=2
d1=2d2=3
d3=3
•No instante =1, r1(t0) = 1, m2(t0) = 1•No instante =2, r(t1) = 2, m2(t1) = 1 r(t2) = 3, m2(t2) = 1•No instante =3, r(t1) = 1, m2(t1) = 1 r(t2) = 2, m2(t2) = 1•No instante =4, r(t2) = 1, m2(t2) = 1•No instante =5, r(t3) = 3, m2(t3) = 1•No instante =8, m1(p5) = 1
Redes TemporizadasRedes Temporizadascom Transições com Transições TemporizadasTemporizadas
p0
t0 p2t2
p4
t3p5
p1
t1
p3
d0=2
d1=2d2=3
d4=3
d5=2t5
c(t2)=0.5 c(t5)=0.5
Redes TemporizadasRedes Temporizadascom Transições com Transições TemporizadasTemporizadas
p0
t0 p2t2
p4
t3p5
p1
t1
p3
d0=2
d1=2d2=3
d4=3
d5=2t5
c(t2)=0.5 c(t5)=0.5
•No instante =1, r1(t0) = 1, m2(t0) = 1
Redes TemporizadasRedes Temporizadascom Transições com Transições TemporizadasTemporizadas
p0
t0 p2t2
p4
t3p5
p1
t1
p3
d0=2
d1=2d2=3
d4=3
d5=2t5
c(t2)=0.5 c(t5)=0.5
•No instante =1, r1(t0) = 1, m2(t0) = 1•No instante =2,
Redes TemporizadasRedes Temporizadascom Transições com Transições TemporizadasTemporizadas
p0
t0 p2t2
p4
t3p5
p1
t1
p3
d0=2
d1=2d2=3
d4=3
d5=2t5
c(t2)=0.5 c(t5)=0.5
•No instante =1, r1(t0) = 1, m2(t0) = 1•No instante =2, r(t1) = 2, m2(t1) = 1 r(t2) = 3, m2(t2) = 1
Redes TemporizadasRedes Temporizadascom Transições com Transições TemporizadasTemporizadas
p0
t0 p2t2
p4
t3p5
p1
t1
p3
d0=2
d1=2d2=3
d4=3
d5=2t5
c(t2)=0.5 c(t5)=0.5
•No instante =1, r1(t0) = 1, m2(t0) = 1•No instante =2, r(t1) = 2, m2(t1) = 1 r(t2) = 3, m2(t2) = 1•No instante =3, r(t1) = 1, m2(t1) = 1 r(t2) = 2, m2(t2) = 1
Redes TemporizadasRedes Temporizadascom Transições com Transições TemporizadasTemporizadas
p0
t0 p2t2
p4
t3p5
p1
t1
p3
d0=2
d1=2d2=3
d4=3
d5=2t5
c(t2)=0.5 c(t5)=0.5
•No instante =1, r1(t0) = 1, m2(t0) = 1•No instante =2, r(t1) = 2, m2(t1) = 1 r(t2) = 3, m2(t2) = 1•No instante =3, r(t1) = 1, m2(t1) = 1 r(t2) = 2, m2(t2) = 1•No instante =4, r(t2) = 1, m2(t2) = 1
Redes TemporizadasRedes Temporizadascom Transições com Transições TemporizadasTemporizadas
p0
t0 p2t2
p4
t3p5
p1
t1
p3
d0=2
d1=2d2=3
d4=3
d5=2t5
c(t2)=0.5 c(t5)=0.5
•No instante =1, r1(t0) = 1, m2(t0) = 1•No instante =2, r(t1) = 2, m2(t1) = 1 r(t2) = 3, m2(t2) = 1•No instante =3, r(t1) = 1, m2(t1) = 1 r(t2) = 2, m2(t2) = 1•No instante =4, r(t2) = 1, m2(t2) = 1•No instante =5, r(t3) = 3, m2(t3) = 1
Redes TemporizadasRedes Temporizadascom Transições com Transições TemporizadasTemporizadas
p0
t0 p2t2
p4
t3p5
p1
t1
p3
d0=2
d1=2d2=3
d4=3
d5=2t5
c(t2)=0.5 c(t5)=0.5
•No instante =1, r1(t0) = 1, m2(t0) = 1•No instante =2, r(t1) = 2, m2(t1) = 1 r(t2) = 3, m2(t2) = 1•No instante =3, r(t1) = 1, m2(t1) = 1 r(t2) = 2, m2(t2) = 1•No instante =4, r(t2) = 1, m2(t2) = 1•No instante =5, r(t3) = 3, m2(t3) = 1
Redes TemporizadasRedes Temporizadascom Transições com Transições TemporizadasTemporizadas
Timed Petri Nets Timed Petri Nets
Definição:Definição: Grafo de Alcançabilidade Grafo de Alcançabilidade TemporizadoTemporizado- seja uma rede marcada - seja uma rede marcada TPN=(P,T,F, W,MTPN=(P,T,F, W,M00,c,D),c,D) . . TRG(TPN)=(S,D,h,q)TRG(TPN)=(S,D,h,q) define define o grafo de estados temporal (o grafo de estados temporal (Timed State Timed State GraphGraph), onde ), onde SS é o conjunto de vértice e é o conjunto de vértice e representa o conjunto de estados. representa o conjunto de estados. D D S S S S é é uma relação representando arcos dirigidos. uma relação representando arcos dirigidos. h : S h : S ++ {0} {0} é uma função que associa o é uma função que associa o holding holding timetime a cada estado a cada estado ssii=(m=(m11,m,m22,r),r), onde , onde h(sh(sii)=min)=minttT T
m2(t)>0 m2(t)>0 (r(rii(t)[1])(t)[1]) e e q : D q : D [0,1] [0,1] é uma função que é uma função que associa uma probabilidade aos arcos do grafo.associa uma probabilidade aos arcos do grafo.
Redes TemporizadasRedes Temporizadascom Transições com Transições TemporizadasTemporizadas
p1
t1d1=0
p2
p4
t5d=20
p5t6
d6=0
p3t3
d3=0
0,1
t4d=5
0,9
p6t7d7=0
p7
si M1 M2 h(si) M’2 sj q
1 p=0 t1=1 0 t2=t5=1 2 12 p=0 t2=t5=1 10 t4=1 3 0,9 t3=1 4 0,13 p=0 t4=t5=1 5 t1=1 5 14 p=0 t3=t5=1 0 t=0 6 15 p6=1 t1=t5=1 0 t2=t5=1 7 16 p=0 t5=1 10 t7=1 8 17 p6=1 t2=1,t5=2 5 t6=1 9 18 p=0 t7=1 0 t1=1 1 19 p=0 t2=t5= 0 t=0 10 1 t6=110 p=0 t2=t5=1 5 t4=1 3 0,9 t3=1 4 0,1
t2d2=10
t1d1=0
Redes TemporizadasRedes Temporizadascom Transições com Transições TemporizadasTemporizadas
p1
p2
p4
t5d=20
p5t6
d6=0
p3t3
d3=0
0,1
t4d=5
0,9
p6t7d7=0
p7
si M1 M2 h(si) M’2 sj q
1 p=0 t1=1 0 t2=t5=1 2 12 p=0 t2=t5=1 10 t4=1 3 0,9 t3=1 4 0,13 p=0 t4=t5=1 5 t1=1 5 14 p=0 t3=t5=1 0 t=0 6 15 p6=1 t1=t5=1 0 t2=t5=1 7 16 p=0 t5=1 10 t7=1 8 17 p6=1 t2=1,t5=2 5 t6=1 9 18 p=0 t7=1 0 t1=1 1 19 p=0 t2=t5= 0 t=0 10 1 t6=110 p=0 t2=t5=1 5 t4=1 3 0,9 t3=1 4 0,1
t2d2=10
Redes TemporizadasRedes Temporizadascom Transições com Transições TemporizadasTemporizadas
p1
t1d1=0
p2
p4
t5d=20
p5t6
d6=0
p3t3
d3=0
0,1
t4d=5
0,9
p6t7d7=0
p7
si M1 M2 h(si) M’2 sj q
1 p=0 t1=1 0 t2=t5=1 2 12 p=0 t2=t5=1 10 t4=1 3 0,9 t3=1 4 0,13 p=0 t4=t5=1 5 t1=1 5 14 p=0 t3=t5=1 0 t=0 6 15 p6=1 t1=t5=1 0 t2=t5=1 7 16 p=0 t5=1 10 t7=1 8 17 p6=1 t2=1,t5=2 5 t6=1 9 18 p=0 t7=1 0 t1=1 1 19 p=0 t2=t5= 0 t=0 10 1 t6=110 p=0 t2=t5=1 5 t4=1 3 0,9 t3=1 4 0,1
t2d2=10
Redes TemporizadasRedes Temporizadascom Transições com Transições TemporizadasTemporizadas
p1
t1d1=0
p2
p4
t5d=20
p5t6
d6=0
p3t3
d3=0
0,1
t4d=5
0,9
p6t7d7=0
p7
si M1 M2 h(si) M’2 sj q
1 p=0 t1=1 0 t2=t5=1 2 12 p=0 t2=t5=1 10 t4=1 3 0,9 t3=1 4 0,13 p=0 t4=t5=1 5 t1=1 5 14 p=0 t3=t5=1 0 t=0 6 15 p6=1 t1=t5=1 0 t2=t5=1 7 16 p=0 t5=1 10 t7=1 8 17 p6=1 t2=1,t5=2 5 t6=1 9 18 p=0 t7=1 0 t1=1 1 19 p=0 t2=t5= 0 t=0 10 1 t6=110 p=0 t2=t5=1 5 t4=1 3 0,9 t3=1 4 0,1
t2d2=10
Redes TemporizadasRedes Temporizadascom Transições com Transições TemporizadasTemporizadas
p1
t1d1=0
p2
p4
t5d=20
p5t6
d6=0
p3t3
d3=0
0,1
t4d=5
0,9
p6t7d7=0
p7
si M1 M2 h(si) M’2 sj q
1 p=0 t1=1 0 t2=t5=1 2 12 p=0 t2=t5=1 10 t4=1 3 0,9 t3=1 4 0,13 p=0 t4=t5=1 5 t1=1 5 14 p=0 t3=t5=1 0 t=0 6 15 p6=1 t1=t5=1 0 t2=t5=1 7 16 p=0 t5=1 10 t7=1 8 17 p6=1 t2=1,t5=2 5 t6=1 9 18 p=0 t7=1 0 t1=1 1 19 p=0 t2=t5= 0 t=0 10 1 t6=110 p=0 t2=t5=1 5 t4=1 3 0,9 t3=1 4 0,1
t2d2=10
Redes TemporizadasRedes Temporizadascom Transições com Transições TemporizadasTemporizadas
Tempo de ExecuçãoTempo de Execução
– Análise do grafo de estados + Algorítmo de Análise do grafo de estados + Algorítmo de Procura de CaminhosProcura de Caminhos (Redes Genéricas)(Redes Genéricas)
– Métodos EstruturalMétodos Estrutural (sub-classes: grafo-marcado)(sub-classes: grafo-marcado)
Redes TemporizadasRedes Temporizadascom Transições com Transições TemporizadasTemporizadas
p1
t1d1=0
p2
p4
t5d=20
p5t6
d6=0
p3t3
d3=0
0,1
t4d=5
0,9
p6t7d7=0
p7
si M1 M2 h(si) M’2 sj q
1 p=0 t1=1 0 t2=t5=1 2 12 p=0 t2=t5=1 10 t4=1 3 0,9 t3=1 4 0,13 p=0 t4=t5=1 5 t1=1 5 14 p=0 t3=t5=1 0 t=0 6 15 p6=1 t1=t5=1 0 t2=t5=1 7 1
...• D(s1,s5) = 0 + 10 + 5 + 0 = 15
t2d2=10
Redes TemporizadasRedes Temporizadascom Transições com Transições TemporizadasTemporizadas
Métodos Algébricos Aplicados aos Grafos Métodos Algébricos Aplicados aos Grafos MarcadosMarcados
– CCmm = max = maxkk {D {Dkk/N/Nkk} k=1,...,q} k=1,...,q
q q é o número de circuitosé o número de circuitos DDk k é a soma dos tempos associados às transições é a soma dos tempos associados às transições
do circuitodo circuito k k NNkk é o somatório de marcas no circuito é o somatório de marcas no circuito k k
Redes TemporizadasRedes Temporizadascom Transições com Transições TemporizadasTemporizadas
A B
t1 d1=5
C Dt2 t3d2=20 d3=4E F t4 d4=3
t5d=2
G
•P-minimum semiflows:SP1={A,C,E,G}SP2={A,D,F,G}SP3={B,C,E}SP4={B,D,F}
•Circuito:•c1={t1,t2,t4,t5}•c2={t1,t3,t4,t5}•c3={t1,t2,t4}•c4={t1,t3,t4}
Redes TemporizadasRedes Temporizadascom Transições com Transições TemporizadasTemporizadas
A B
t1 d1=5
C Dt2 t3d2=20 d3=4E F t4 d4=3
t5d=2
G
Cm = maxk {Dk/Nk} k=1,...,4
C1=(5+20+3+2)/2= 15
C2=(5+4+3+2)/1= 14
C3=(5+20+3)/2= 14
C4=(5+4+3)/1= 12
•Cm = maxk {15,14,14,12} = 15
Redes TemporizadasRedes Temporizadascom Transições com Transições TemporizadasTemporizadas
Estedendo o Método Anterior para Redes Estedendo o Método Anterior para Redes Free-Free-ChoiceChoice sem Compartilhamento de Recursos sem Compartilhamento de Recursos
Seja Seja N=(P,T,I,O,MN=(P,T,I,O,M00,D),D) uma rede e uma rede e SNSNii=(P=(PSNiSNi,T,TSNiSNi,I,ISNiSNi,O,OSNiSNi,M,M00
SNiSNi,D,DSNiSNi)) e uma rede e uma rede SNSNii NN obtida pelos obtida pelos p-minimum semiflowsp-minimum semiflows.. Seja Seja SNSNkk=(P=(PSNkSNk,T,TSNkSNk,I,ISNkSNk,O,OSNkSNk,M,M00
SNkSNk,D,DSNkSNk)) uma rede tal uma rede tal que que SNSNkk SN SNii onde onde TTSNkSNk pertence a um único pertence a um único t-t-minimum semiflowsminimum semiflows..
Redes TemporizadasRedes Temporizadascom Transições com Transições TemporizadasTemporizadas
Tempo do Caminho CríticoTempo do Caminho Crítico
– CTCTmm = max = maxkk {D {Dkk/N/Nkk} k=1,...,q} k=1,...,q q q é o número de sub-redes é o número de sub-redes SNSNkk
DDk k é a soma dos tempos associados às transições é a soma dos tempos associados às transições da sub-rededa sub-rede k. k.
NNkk é o somatório de marcas no circuito é o somatório de marcas no circuito k k
Redes TemporizadasRedes Temporizadascom Transições com Transições TemporizadasTemporizadas
Tempo MínimoTempo Mínimo
– MTMTmm = max = maxkk {min{D {min{Djj/N/Njj},D},Dii/N/Nii} i=1,...,q. } i=1,...,q. j=1,...,rj=1,...,r q q é o número de sub-redes é o número de sub-redes SNSNi i obtidas diretamente obtidas diretamente
dos dos p-minimum semiflowsp-minimum semiflows e cujos e cujos TTSNiSNi pertence a pertence a um único um único t-minimum semiflowst-minimum semiflows..
r r é o número de sub-redes é o número de sub-redes SNSNj j obtidas dos obtidas dos p-p-minimum semiflowsminimum semiflows e por sua decomposição tal e por sua decomposição tal que que TTSNjSNj pertence a um único pertence a um único t-minimum t-minimum semiflowssemiflows..
DDk k é a soma dos tempos associados às transições é a soma dos tempos associados às transições da sub-rededa sub-rede k. k.
NNkk é o somatório de marcas no circuito é o somatório de marcas no circuito k k
p
pp p
p p
p
p
p
p
p
p
p p
p p
pp
p
p
t
t t
t t
t t
t
t t
t t t
t t
t
t
t
t
p
0
1
2 3
0
4 5
6 8
7
16
119
10
13
14
12
19 20
15
17
18
1 2
3 6
4 7
5
8
9
15
10
1116
17 18
12
14
13
[1]
[2]
[1]
[1]
[1]
[2] [5][2]
[3]
[5]
[1]
[3]
[2]
[11]
[5]
[11]
[1]
[1]
[0]
Redes TemporizadasRedes Temporizadascom Transições com Transições TemporizadasTemporizadas
Redes TemporizadasRedes Temporizadascom Transições com Transições TemporizadasTemporizadas
0 0 2 6 7 8 9 10 11 12 13 14 15 17
T-minimum semiflowsT-minimum semiflows
st = {t ,t ,t ,t ,t ,t ,t ,t ,t ,t ,t ,t ,t }
1 0 2 6 7 8 9 10 11 12 13 14 16 18= {t ,t ,t ,t ,t ,t ,t ,t ,t ,t ,t ,t ,t } st
p
pp p
p
p
p
p
p
p p
p p
pp
p
p
t
t
t
t
t t
t t t
t t
t
t
t
t
p
0
1
2 3
0
5
8
16
119
10
13
14
12
19 20
15
17
18
2
6
7
8
9
15
10
1116
17 18
12
14
13
[1]
[2] [5] [2]
[3]
[5]
[1]
[3]
[2]
[11]
[5]
[11]
[1]
[1]
[0]
Redes TemporizadasRedes Temporizadascom Transições com Transições TemporizadasTemporizadas
P-minimum semiflowsP-minimum semiflows sp = {p ,p ,p ,p ,p ,p }sp = {p ,p ,p ,p ,p ,p } sp = {p ,p ,p ,p ,p ,p ,p ,p }sp = {p ,p ,p ,p ,p ,p ,p ,p } sp = {p ,p ,p ,p ,p }sp = {p ,p ,p ,p ,p } sp = {p ,p ,p ,p ,p }sp = {p ,p ,p ,p ,p } sp = {p ,p ,p ,p ,p ,p }sp = {p ,p ,p ,p ,p ,p } sp = {p ,p ,p ,p ,p ,p ,p }sp = {p ,p ,p ,p ,p ,p ,p }
0
0
0
0
0
0
11
1
5
5
5
8 16 18
8 16
18
18
18
18
18
2
2
2
3
3
3
4
12 15 17 19 20
10
109
9
11 13 14 17
Redes TemporizadasRedes Temporizadascom Transições com Transições TemporizadasTemporizadas
Transition paths sn = {t ,t ,t ,t ,t ,t } sn = {t ,t ,t ,t ,t ,t ,t ,t ,t } sn = {t ,t ,t ,t ,t } sn = {t ,t ,t ,t ,t } sn = {t ,t ,t ,t ,t ,t } sn = {t ,t ,t ,t ,t ,t ,t }
1
2
2
23
4
5
6
6
6
6
6
7
7
8
8
9
0
0
0
0
0
0
10
10
11 12
12
13
13
13
13
13
13
14
14
14
14
14
14 15
16 17 18
Redes TemporizadasRedes Temporizadascom Transições com Transições TemporizadasTemporizadas
Redes TemporizadasRedes Temporizadascom Transições com Transições TemporizadasTemporizadas
Decomposição dos Caminhos
sn = {t ,t ,t ,t ,t ,t ,t ,t ,t } sn = {t ,t ,t ,t ,t ,t ,t } sn = {t ,t ,t ,t ,t ,t ,t }
2
21
22
0
0
0
10 11 12 13 14 16 17 18
10
10
11
12
12
13
13 14
14 16
17
18
Redes TemporizadasRedes Temporizadascom Transições com Transições TemporizadasTemporizadas
Tempo do Caminho CríticoTempo do Caminho Crítico CT(N) = max {T(sn ),T(sn ),T(sn ),T(sn ),CT(N) = max {T(sn ),T(sn ),T(sn ),T(sn ),
T(sn ),T(sn ),T(sn )} = 22T(sn ),T(sn ),T(sn )} = 22 Tempo MínimoTempo Mínimo MT(N) = max {T(sn ),min {T(sn ),MT(N) = max {T(sn ),min {T(sn ),
T(sn )},T(sn ),T(sn ),T(sn ),T(sn )},T(sn ),T(sn ),T(sn ),
T(sn )} = 20T(sn )} = 20
1 21 22 3
4 5 6
1 21
22 3 4 5
6
Redes TemporizadasRedes Temporizadascom Transições com Transições TemporizadasTemporizadas
Redução de Transição em SeqüênciaRedução de Transição em Seqüência
Seja uma rede Seja uma rede N=(P,T,I,O,MN=(P,T,I,O,M00,D), p,D), pii P P um um lugar, onde lugar, onde I(pI(pii)=[t)=[tjj] O(p] O(pii)=[t)=[tkk].]. NN pode ser pode ser transformada em transformada em N’=(P’,T’,I’,O’,M’N’=(P’,T’,I’,O’,M’00,D’),D’) pela pela fusão de fusão de ttjj e e ttkk e eliminação dee eliminação de p pii. A . A transição transição ttj/k j/k T’ T’ representa as transições representa as transições fundidas tal que fundidas tal que I(tI(tj/kj/k) = I(t) = I(tjj)) e e O(tO(tj/kj/k) = O(t) = O(tkk)) e e ddj/kj/k= d= djj + ddkk
.
.
.
Redes TemporizadasRedes Temporizadascom Transições com Transições TemporizadasTemporizadas
Redução de Transição em SeqüênciaRedução de Transição em Seqüência
tj pi tk
dj dk
.
.
....
.
.
.
tj/k
dj/k
dj/k= dj + dk
Redes TemporizadasRedes Temporizadascom Transições com Transições TemporizadasTemporizadas
Redução de Transição de um EscolhaRedução de Transição de um Escolha
Seja uma rede Seja uma rede N=(P,T,I,O,MN=(P,T,I,O,M00,D), p,D), pii, p, pll P P lugares, onde lugares, onde O(pO(pii)=[t)=[tjj, t, tkk] e I(p] e I(pll)=[t)=[tjj,t,tkk].]. NN pode pode ser transformada em ser transformada em N’=(P’,T’,I’,O’,M’N’=(P’,T’,I’,O’,M’00,D’),D’) pela pela fusão de fusão de ttjj e e ttkk. A transição . A transição ttj/k j/k T’ T’ representa representa as transições fundidas tal que as transições fundidas tal que I(tI(tj/kj/k) = I(t) = I(tjj)) e e O(tO(tj/kj/k) = O(t) = O(tkk)) e o tempo mínimo é e o tempo mínimo é ddj/kj/k= min{d= min{djj, ddkk} } e o tempo máximo é e o tempo máximo é ddj/kj/k= max{d= max{djj, ddkk} }
Redes TemporizadasRedes Temporizadascom Transições com Transições TemporizadasTemporizadas
Redução de Transição de um EscolhaRedução de Transição de um Escolha
.
.
....
.
.
....
tj
tk
dj
dk
pi pl pi pl
tj/k
dj/k
dj/k= min{dj, dk}dj/k= max{dj, dk}
Redes TemporizadasRedes Temporizadascom Transições com Transições TemporizadasTemporizadas
Redução de LaçoRedução de Laço
Seja uma rede Seja uma rede N=(P,T,I,O,MN=(P,T,I,O,M00,D), p,D), pii, p, phh P P lugares, onde lugares, onde O(pO(pii)=[t)=[tjj, t, tkk] e O(t] e O(tjj)=[p)=[pii], ], I(pI(phh)=[t)=[tkk] .] . NN pode ser transformada em pode ser transformada em N’=(P’,T’,I’,O’,M’N’=(P’,T’,I’,O’,M’00,D’),D’) pela eliminação de pela eliminação de ttjj. . O tempo associado a transição O tempo associado a transição ttk k T’ T’ é é ddkk
N’N’= m = m d dj j + ddkk ..
Redes TemporizadasRedes Temporizadascom Transições com Transições TemporizadasTemporizadas
Redução de LaçoRedução de Laço
.
.
.
.
.
....
.
.
.
pi ph
tk
dk
tk
tj
dk
dj
pi ph
dkN’= m dj + dk
Redes TemporizadasRedes Temporizadascom Transições com Transições TemporizadasTemporizadas
Redução de Transições ParalelasRedução de Transições Paralelas
Seja uma rede Seja uma rede N=(P,T,I,O,MN=(P,T,I,O,M00,D), t,D), tii, t, tjj , t , thh, t, tll T T transições, onde transições, onde I(I(tI(I(tii))=I(I(t))=I(I(tjj)) )) ee O(O(t O(O(tii))=O(O(t))=O(O(thh)) .)) . NN pode ser transformada em pode ser transformada em N’=(P’,T’,I’,O’,M’N’=(P’,T’,I’,O’,M’00,D’),D’) pela eliminação da estrutura pela eliminação da estrutura SN=(PSN=(PSNSN,T,TSNSN,I,ISNSN,O,OSNSN,M,M00
SNSN,D,DSNSN)), onde , onde PPSNSN={I(t={I(tii), I(t), I(tjj)), )), O(tO(tii), O(t), O(tjj)}, T’={t)}, T’={tii, t, tj, j, I(I(tI(I(tii))=t))=thh, O(O(t, O(O(tii))=t))=tll}. t}. th/l h/l T’ T’ representa a estrutura reduzida, tal que representa a estrutura reduzida, tal que I(tI(th/lh/l)= )= I(I(I(tI(I(I(tii)))= I(I(I(t)))= I(I(I(tjj))), O(O(O(t))), O(O(O(tii)))= O(O(O(t)))= O(O(O(tjj)))))) e e ddi/ji/j
N’N’= = ddI(I(ti)) I(I(ti)) + max{ddii, ddjj}+ ddO(O(ti))O(O(ti))..
Redes TemporizadasRedes Temporizadascom Transições com Transições TemporizadasTemporizadas
Redução de Transições ParalelasRedução de Transições Paralelas
pa
th
p2tj
p4
tlpf
p1
ti
p3
...
...
.
.
....
pa pf
th/l
dh/l
di/jN’= dI(I(ti)) + max{di, dj}+ dO(O(ti))
Classificação da Técnicas Classificação da Técnicas de Avaliação de de Avaliação de
DesempenhoDesempenho
Avaliação de DesempenhoAvaliação de Desempenho
Avaliação DeterminísicaAvaliação Determinísica Modelagem EstocásticaModelagem Estocástica
MediçãoMedição PrototipaçãoPrototipação MétodosMétodos Simulação de EventosSimulação de Eventos MétodosMétodos AnalíticosAnalíticos DiscretosDiscretos
AnalíticosAnalíticos
SistemaSistema BenchmarksBenchmarks SimulaçãoSimulação
RealReal Modelagem
Modelagem para Análise Modelagem para Análise de Desemde Desemppenhoenho
Algumas MedidasAlgumas Medidas
– Tempo de ManufaturaTempo de Manufatura– ThroughputThroughput– UtilizaçãoUtilização– CapacidadeCapacidade– ConfiabilidadeConfiabilidade
Redes Temporizadas Redes Temporizadas EstocásticasEstocásticas
Modelagem para Análise de Modelagem para Análise de DesemDesemppenhoenho
– Modelos para SimulaçãoModelos para Simulação
– Modelos AnalíticosModelos Analíticos Cadeias de MarkovCadeias de Markov Teoria das FilasTeoria das Filas Redes de Petri EstocásticasRedes de Petri Estocásticas
Redes Temporizadas Redes Temporizadas EstocásticasEstocásticas
Proriedade MarkovianaProriedade Markoviana– Ausência de MemóriaAusência de Memória
Variáveis Aleatórias com Variáveis Aleatórias com ProPropriedade Markovianapriedade Markoviana
– Variável Aleatória GeométricaVariável Aleatória Geométrica– Variável Aleatória ExponencialVariável Aleatória Exponencial
Probabilidade Condicional Probabilidade Condicional Seja Seja AA um evento um evento
arbitrário em um espaço arbitrário em um espaço amostral amostral SS. A . A probabilidade de que probabilidade de que ocorra um evento ocorra um evento A A uma uma vez que vez que MM tenha tenha ocorrido é denotado por ocorrido é denotado por P(P(A/MA/M)) que é definido que é definido por:por:
P(P(A/MA/M)=)=P(P(A A MM))
P(P(MM))
S
A MA M
Caso Caso M M A A então então P(P(A/MA/M)=1)=1
Caso Caso A A M M então então
P(P(A/MA/M)= )= P(P(AA)) P(P(MM) )
Distribuição ExponencialDistribuição Exponencial
fdp exponencialfdp exponencial
ffXX(t)(t)
tt
FD FD - - Função de Função de DistribuiçãoDistribuição
ffXX(t) = (t) = ee--tt
FD(t) = 1 - eFD(t) = 1 - e--tt
Valor EsperadoValor Esperado
E(X) = 1E(X) = 1
Propriedade:Propriedade:
Não possui memóriaNão possui memória
Variável Aleatória Exponencial
Distribuição ExponencialDistribuição Exponencial
Variável Aleatória ExponencialVariável Aleatória Exponencial
P{X>t}P{X>t} = e = e--tt
P{X>t+u | X > t} = P{X>t+u P{X>t+u | X > t} = P{X>t+u X>t} X>t}
P{X>t}P{X>t} P{X>t+u | X > t} = P{X>t+u}P{X>t+u | X > t} = P{X>t+u}
P{X>t}P{X>t}
P{X>t+u | X > t} = P{X>t+u | X > t} = ee--(t+u) (t+u) = e= e--uu = = P{X>u}P{X>u} ee--tt
ProbabilidadeCondicional
t t+u
t
Processos EstocásticosProcessos Estocásticos Processo EstocásticoProcesso Estocástico é definido por um conjunto de variáveis é definido por um conjunto de variáveis
aleatórias, aleatórias, {{X(t) : t X(t) : t T T}, onde }, onde X(t)X(t) é uma variável aleatória para cada é uma variável aleatória para cada t t T T..t t é denominado parâmetro e cada valor de é denominado parâmetro e cada valor de X(t)X(t) são estados. são estados. Processo Estocástico MarkovianoProcesso Estocástico Markoviano é um processo estocástico onde as é um processo estocástico onde as
variáveis aleatórias não dependem da história passada.variáveis aleatórias não dependem da história passada. Tipos de Processos EstocásticosTipos de Processos Estocásticos
– Processos de espaço de estados e tempo discretos Processos de espaço de estados e tempo discretos ((Discret Time Markov ChainDiscret Time Markov Chain - - DTMCDTMC))– Processos de espaço de estados contínuo e tempo discretoProcessos de espaço de estados contínuo e tempo discreto– Processos de espaço de estados discreto e tempo contínuo Processos de espaço de estados discreto e tempo contínuo
((Continuos Time Markov Chain - Continuos Time Markov Chain - CTMCCTMC))– Processos de espaço de estados e tempo contínuosProcessos de espaço de estados e tempo contínuos
Continuos Time Markov Continuos Time Markov ChainChain
O comportamento de O comportamento de uma rede uma rede estocástica é estocástica é representado por representado por CTMCCTMC
0 1 0 1
0 10 1
-(-(++) ) 0 0
Q = Q =
-(-(++) 1) 1
++ ++ 0 0
P = P =
++ ++ 1 1
Matriz de Taxas
Matriz de Propabilidadesde Próximo Estados
Redes EstocásticasRedes Estocásticas Soluções para Soluções para Steady-StatesSteady-States
aa1111 a a1212 a a13 13 UU11=(a=(a1111 a a1212 a a1313))
P = P = aa2121 a a2222 a a23 23 UU22=(a=(a2121 a a2222 a a2323))
aa3131 a a3232 a a33 33 UU33=(a=(a3131 a a3232 a a3333))
aaijij - probabilidade- probabilidade Mi Mi RSRS a aijij=1=1
Y . P = YY . P = Y , , si si SS y yii=1=1, onde , onde yyii fornece o fornece o
número relativo de visitas ao estado número relativo de visitas ao estado ssii
Redes EstocásticasRedes Estocásticas Soluções para Soluções para Steady-StatesSteady-States
Q = Q = 00
MiMiRS(N)RS(N) [M[Mii]=1]=1
Onde Onde [M] [M] fornece a fornece a steady-state probabilitysteady-state probability de um sistema estar no estado de um sistema estar no estado ssii
Soluções TransientesSoluções Transientes
dd(t)(t) = Q = Q (t) (t)
dtdt
Onde Onde (t) [M(t) [Mii] ] é probabilidade de se estar na é probabilidade de se estar na estado estado ssii no instante no instante tt
Redes EstocásticasRedes Estocásticas Definição:Definição:
SPN=(P,T,I,O,W,MSPN=(P,T,I,O,W,M00))
p1p1
s t1s t1
p2p2
p t2 f t3p t2 f t3
p3 p3
t4 r t4 r
PP é o conjunto de lugares, é o conjunto de lugares,
TT o conjunto de transições, o conjunto de transições,
I: PI: PT T é a função de é a função de mapeamento de que mapeamento de que representam as pré-condições,representam as pré-condições,
OO : P: PT T é a função de é a função de mapeamento de que mapeamento de que representam as pós-condiçõesrepresentam as pós-condições
W : T W : T ( (ou ou W : TW : TM M )) é é uma função que associa taxas uma função que associa taxas de distribuição exponencial às de distribuição exponencial às transiçõestransições
MM00-- Marcação inicial - Marcação inicial - MM00: P : P
Redes EstocásticasRedes Estocásticas
Definição:Definição:
SPN=(P,T,I,O,H,W,MSPN=(P,T,I,O,H,W,M00))
PP é o conjunto de lugares, é o conjunto de lugares,TT o conjunto de transições, o conjunto de transições, I: PI: PT T é a função de é a função de
mapeamento de que mapeamento de que representam as pré-condições,representam as pré-condições,
OO : P: PT T é a função de é a função de mapeamento de que mapeamento de que representam as pós-condições representam as pós-condições
H : PH : PT T é a função de é a função de mapeamento de que mapeamento de que representam os arcos representam os arcos inibidoresinibidores
W : T W : T ((ou ou W : TW : TM M )) é é uma função que associa taxas uma função que associa taxas de distribuição exponencial às de distribuição exponencial às transiçõestransições
MM00-- Marcação inicial - Marcação inicial - MM00: P : P
p1
p2
p3
p4
t1 t2
t3t4
1
2
4 3
Redes EstocásticasRedes EstocásticasSemântica de Disparo de TransiçãoSemântica de Disparo de Transição Uma transição Uma transição ttjj é é disparáveldisparável se estiver habilitadase estiver habilitada
– Regras de habilitaçãoRegras de habilitação M[tM[tjj > , M(pi) > , M(pi) pi, tpi, tjj)) pi pi PP Transições com Transições com delays delays menoresmenores disparam primeiro disparam primeiro
((RaceRace)) Enabling MemoryEnabling Memory Regras de disparoRegras de disparo Se M[tSe M[tjj >M’ >M’ M’(pi)=M0(pi) - I(pi, tM’(pi)=M0(pi) - I(pi, tjj)+O(pi, t)+O(pi, tjj), ), pi pi PP
Redes EstocásticasRedes Estocásticas Definição:Definição:
SPN=(P,T,I,O,W,MSPN=(P,T,I,O,W,M00))
W : T W : T p1p1
s t1s t1
p2p2
p t2 f t3p t2 f t3
p3 p3
t4 r t4 r
Grafo de MarcaçõesGrafo de Marcações
M0M0
t2 t1 t4t2 t1 t4
M1 M1
t3 t3
M2M2
1,0,0
0,1,0
0,0,1
Redes EstocásticasRedes Estocásticas Definição:Definição:
SPN=(P,T,I,O,W,MSPN=(P,T,I,O,W,M00))
W : T W : T p1p1
s t1s t1
p2p2
p t2 f t3p t2 f t3
p3 p3
t4 r t4 r
Grafo de MarcaçõesGrafo de Marcações
M0M0
t2 t1 t4t2 t1 t4
M1 M1
t3 t3
M2M2
1,0,0
0,1,0
0,0,1
Redes EstocásticasRedes Estocásticas Definição:Definição:
SPN=(P,T,I,O,W,MSPN=(P,T,I,O,W,M00))
W : T W : T p1p1
s t1s t1
p2p2
p t2 f t3p t2 f t3
p3 p3
t4 r t4 r
Grafo de MarcaçõesGrafo de Marcações
M0M0
t2 t1 t4t2 t1 t4
M1 M1
t3 t3
M2M2
1,0,0
0,1,0
0,0,1
Redes EstocásticasRedes Estocásticas Definição:Definição:
SPN=(P,T,I,O,W,MSPN=(P,T,I,O,W,M00))
W : T W : T p1p1
s t1s t1
p2p2
p t2 f t3p t2 f t3
p3 p3
t4 r t4 r
Grafo de MarcaçõesGrafo de Marcações
M0M0
t2 t1 t4t2 t1 t4
M1M1
t3 t3
M2M2
1,0,0
0,1,0
0,0,1
Redes EstocásticasRedes Estocásticas Definição:Definição:
SPN=(P,T,I,O,W,MSPN=(P,T,I,O,W,M00))
W : T W : T p1p1
s t1s t1
p2p2
p t2 f t3p t2 f t3
p3 p3
t4 r t4 r
Grafo de MarcaçõesGrafo de Marcações
M0M0
t2 t1 t4t2 t1 t4
M1 M1
t3 t3
M2M2
1,0,0
0,1,0
0,0,1
Redes EstocásticasRedes Estocásticas Definição:Definição:
SPN=(P,T,I,O,W,MSPN=(P,T,I,O,W,M00))
W : T W : T p1p1
s t1s t1
p2p2
p t2 f t3p t2 f t3
p3 p3
t4 r t4 r
Grafo de MarcaçõesGrafo de Marcações
M0M0
t2 t1 t4t2 t1 t4
M1 M1
t3 t3
M2M2
1,0,0
0,1,0
0,0,1
Redes Estocásticas Redes Estocásticas Generalizada (GSPN)Generalizada (GSPN)
Definição:Definição:
GSPN=(P,T,I,O,H,GSPN=(P,T,I,O,H,,W,M,W,M00))
P,T,I,OP,T,I,O definidos como definidos como usualmente.usualmente.
H : PH : PT T é a função de é a função de mapeamento de que mapeamento de que representam os arcos inibidoresrepresentam os arcos inibidores
: T : T 0 0 se se tt for temporizada for temporizada(Prioridade)(Prioridade) ++ se se tt for imediata for imediata
W : T W : T ((ou ou W : TW : TM M )) é é 1.1.uma função que associa uma função que associa taxas taxas de distribuição exponencialde distribuição exponencial às às transições temporizadastransições temporizadas e e
2.2.pesospesos usados na computação usados na computação das probabilidades de disparo das probabilidades de disparo das das transições imediatastransições imediatas
MM00-- Marcação inicial - Marcação inicial - MM00: P : P
p1
p2
p3
p4
t1 t2
t3t4
1
4
Redes Estocásticas Redes Estocásticas Generalizada (GSPN)Generalizada (GSPN)
Semântica de Disparo de TransiçãoSemântica de Disparo de Transição Uma transição Uma transição ttjj é é disparáveldisparável se estiver habilitadase estiver habilitada
– Regras de habilitaçãoRegras de habilitação M[tM[tjj > , M(pi) > , M(pi) pi, tpi, tjj)) pi pi PP Transições com Transições com delays delays menoresmenores disparam primeiro ( disparam primeiro (RaceRace)) Transições Transições imediatasimediatas disparam disparam instantaneamenteinstantaneamente com com
prioridades sobre as temporizadasprioridades sobre as temporizadas Diferentes Diferentes níveis de prioridade níveis de prioridade são associados às são associados às transições transições
imediatas.imediatas. Transições imediatas Transições imediatas comcom mesmo nível de prioridade mesmo nível de prioridade
associadaassociada disparam disparam de acordo com ode acordo com o peso associado peso associado a cada a cada uma.uma.
Enabling MemoryEnabling Memory Regras de disparoRegras de disparo Se M[tSe M[tjj >M’ >M’ M’(pi)=M0(pi) - I(pi, tM’(pi)=M0(pi) - I(pi, tjj)+O(pi, t)+O(pi, tjj), ), pi pi PP
Redes EstocásticasRedes Estocásticas
Lema: seja Lema: seja N=(P,T,I,O,W,MN=(P,T,I,O,W,M00)) uma SPN. Dadas uma SPN. Dadas
MMii,M,Mjj RS(N),RS(N), existe uma probabilidade de existe uma probabilidade de se atingir se atingir MMjj imediatamente de imediatamente de MMi i . .
Probabilidade de se atingir Probabilidade de se atingir MMjj de de MMii
ppijij= = ijij//i,i,, , ijij= = ttijij(t), (t), ii= = ttii (t)(t)
(t)(t) é a taxa associada a transição através da é a taxa associada a transição através da W W
TTijij = {t = {t TT : M: Mii[t > M[t > Mjj}, T}, Tii = {t = {t TT : M: Mii[t >}[t >}
Redes Estocásticas Redes Estocásticas Generalizada (GSPN)Generalizada (GSPN)
Grafo de Grafo de MarcaçõesMarcações
1,0,0,0
0,1,0,00,0,1,0
p1
t1
p2
p3 p4
t2
t3
t41
t52
0,0,0,1
t4 t1 t5
t2 t3
1,0,0,0
0,0,1,0 0,0,0,1
21. +
. +
Tangiblemarking
Vanishingmarking
Redes EstocásticasRedes Estocásticas
Tempo esperado de permanência num Tempo esperado de permanência num sub-conjunto de marcações sub-conjunto de marcações (mean sojourn (mean sojourn
time)time)
tm(tm(MM,t)=1/t ( ,t)=1/t ( MMMM 00tt (z)[M]dz)(z)[M]dz)
M M RS (N) RS (N)
Se Se MM = {M} = {M}, então: , então:
tm(tm(MM,t)=1/t (,t)=1/t (00tt (z)[M]dz)(z)[M]dz)
Redes EstocásticasRedes Estocásticas
Tempo de permanência numa Tempo de permanência numa marcação marcação ((sojourn timesojourn time))
tmtmii = min = min ttjjTTii(1/(1/j j ))
TTii = {t = {tjj TT : M: Mii[t[tjj >} >}
Redes EstocásticasRedes Estocásticas
TT00 = {t = {t11}, T}, T0101 = {t = {t11}}
TT11= {t= {t22,t,t33}, T}, T1010={t={t22}}
TT1212={t={t33}}
TT22={t={t44}, T}, T2020={t={t44}}
M0 M1 M2M0 M1 M2
0 1 0 M00 1 0 M0
P = p 0 f M1P = p 0 f M1
p+f p+fp+f p+f
1 0 0 M21 0 0 M2
1,0,0
0,1,0
0,0,1
M0
M1
M2
t1t2
t3
t4
Redes EstocásticasRedes Estocásticas
Para garantir a existência de uma distribuição Para garantir a existência de uma distribuição de probabilidade estacionária, a rede deve ser:de probabilidade estacionária, a rede deve ser:
limitadalimitada (bounded)(bounded) reversívelreversível e e livre de bloqueiolivre de bloqueio (deadlock-free) (deadlock-free)
Y . P = YY . P = Y |RS||RS|
yyii=1 Y : M=1 Y : Mii ++
i=1 yi=1 yii é o numero relativo de visitas à é o numero relativo de visitas à marcaçãomarcação M Mii
Redes EstocásticasRedes Estocásticas Probabilidade estacionária Probabilidade estacionária
de uma marcação de uma marcação MMii
ss
ppii = = yyii . tm . tmii / / yyj j .tm.tmjj
j=1j=1
Probabilidade que um lugar Probabilidade que um lugar ppjj tenha tenha kk marcas marcas
p(pj,k) = p(pj,k) = iiSS1 1 ppii
SS 1 1 = { i = { i {1,2,..,S} : M{1,2,..,S} : Mii(p(pjj)=k})=k}
Número esperado de Número esperado de marcas no lugar marcas no lugar ppjj
KK
Em(pEm(pjj) = ) = k .p(pj,k) k .p(pj,k)
k=1k=1
K K é o número máximo de é o número máximo de marcas que o lugar marcas que o lugar pj pj pode pode conter conter
Redes EstocásticasRedes Estocásticas Throughput rateThroughput rate de uma transição de uma transição
TR(tTR(tjj) = ) = p pii . . (t(tjj,W) . q,W) . qij ij
iiSS2 2
SS 2 2 = { i = { i {1,2,..,S} : M{1,2,..,S} : Mii[t[tjj>}>}
ppii é a probabilidade estacionária de uma marcaçãoé a probabilidade estacionária de uma marcação Mi Mi que que habilitahabilita t tjj
(t(tjj)) é a taxa associada a transição é a taxa associada a transição
1, se #O(I(t1, se #O(I(tjj))=1 ))=1 (se (se ttjj não é conflitante) não é conflitante)
qij= qij=
x,x, caso contrário ( caso contrário (probabilidade de disparo d probabilidade de disparo d ttj j entre as entre as
transições conflitantes)transições conflitantes)
Redes EstocásticasRedes Estocásticas
ConclusõesConclusões Redes de Petri estocásticas são uma Redes de Petri estocásticas são uma
representação compacta de alto nível das representação compacta de alto nível das CTMCCTMC
Isomorfismo com CTMCIsomorfismo com CTMC Análise quantitativaAnálise quantitativa Análise qualitativaAnálise qualitativa Modelagem de sistemas concorrentes, não-Modelagem de sistemas concorrentes, não-
determinísticos e assíncronos. Modelagem de determinísticos e assíncronos. Modelagem de sincronismo, escolha, mútua exclusão etcsincronismo, escolha, mútua exclusão etc
Redes EstocásticasRedes Estocásticas
Extensões às SPNExtensões às SPN
GSPN (Marsan et al.)GSPN (Marsan et al.)
DSPN (Lindermann, Ciardo)DSPN (Lindermann, Ciardo)
Redes EstocásticasRedes Estocásticas
BibliografiaBibliografia
Modelling with Generalized Stochastic Petri Nets, Modelling with Generalized Stochastic Petri Nets,
A. Marsan et al, John Wiley & Sons, 1995.A. Marsan et al, John Wiley & Sons, 1995.
Performance Modelling with Deterministic and Performance Modelling with Deterministic and Stochastic Petri Nets, C. Lindermann, John Wiley Stochastic Petri Nets, C. Lindermann, John Wiley & Sons, 1998.& Sons, 1998.
http://www.daimi.au.dk/PetriNetshttp://www.daimi.au.dk/PetriNets