Redes de Petri TemporaisMaterial fruto de uma Monografia submetida Universidade Federal de Santa Catarina como requisito para a aprovao da disciplina: DAS 5511: Projeto de Fim de Curso

Marcelo Henrique Salloum dos Santos

Aracaju, abril de 2012

Constru este material para minha monografia em Engenharia de Controle e Automao. O material foi editado para compor a verso final mas resolvi salvar esta verso como fonte de estudos em Redes de Petri e Redes Temporais. Espero que seja de proveito para outras pessoas.

Captulo 1:

Redes de Petri

Rede de Petri uma tcnica utilizada para modelar sistemas a eventos discretos. Assim denominados aqueles modelados de tal sorte que as variveis de estado variam bruscamente em instantes determinados e que os valores das variveis nos estados seguintes podem ser calculados sabendo apenas seus valores precedentes e sem ter que considerar o tempo entre estes dois instantes. nessa classe de sistemas que o ser modelado a lgica de controle do vagonete [ 1 ]. Esse tipo de modelagem permite a representao de sistemas, utilizando como alicerce uma forte base matemtica. Essa tcnica possui a particularidade de permitir a modelagem sistemas paralelos, concorrentes, assncronos e no determinsticos [ 13 ]. uma ferramenta de modelagem grfica e matemtica aplicvel a muitos sistemas, principalmente na descrio e estudo de sistemas concorrentes, assncronos, distribudos, paralelos, no determinsticos ou

estocsticos. Protocolos de rede, sistemas Fuzzy e aplicaes de RV so exemplos de sistemas que podem ser modelados e simulados utilizando esta ferramenta [ 7 ].

1.1. HistricoRedes de Petri (ou simplesmente RdP) foram criadas a partir tese de doutorado de Carl Adam Petri, intitulada Kommunication mit Automaten

(Comunicao com Autmatos), apresentada Universidade de Bonn em 1962. Desde o princpio, RdP objetivaram a modelagem de sistemas com componentes concorrentes [8].

As primeiras aplicaes de RdP aconteceram em 1968, no projeto norteamericano Information System Theory, da A.D.R. (Applied Data Research, Inc.). Muito da teoria inicial, da notao e da representao de RdP foi desenvolvido neste projeto e foi publicado em seu relatrio final. Este trabalho ressaltou como RdP poderiam ser aplicadas na anlise e na modelagem de sistemas com componentes concorrentes [8]. A dcada de setenta marcou o desenvolvimento da teoria de RdP e a expanso de seu campo de aplicao. Neste perodo aconteceram vrias pesquisas e publicaes sobre o assunto, envolvendo relatrios e teses de doutorado. Essa ferramenta atingiu reas como a modelagem de componentes de hardware, controle de processos, linguagens de programao, sistemas distribudos e protocolos de comunicao [ 8 ]. Nas dcadas de setenta e oitenta, surgiram variaes diferentes de RdP. As RdP temporizadas de Ramchandani, de Merlin e de Sifakis, capazes de modelar caractersticas temporais determinsticas, as de alto nvel, como por exemplo, as numricas, as predicado/transio e as coloridas, seguidas pelas RdP estocsticas [ 8 ]. At os dias de hoje as RdP tm mostrados grandes avanos na representao de sistemas e j muito utilizada em inmeras aplicaes.

1.2. Elementos BsicosA representao grfica de uma rede de Petri bsica formada por dois componentes principais: um ativo chamado de transio (barra) e outro passivo denominado lugar (crculo). Esses dois componentes so ligados entre si atravs de arcos dirigidos (setas) [ 9 ], que alteram as posies e quantidades das fichas.

Figura 1.

Elementos bsicos de uma rede de Petri [ 1 ]

2

Lugar (representado por um crculo): elemento passivo da rede. Representam os estados que um sistema pode assumir durante o seu fluxo de execuo. Para isso, os lugares apresentam certos elementos denominados marcas ou tokens, os quais indicam a presena ou disponibilidade de algum recurso [ 10 ]. Pode ser interpretado como uma condio, um estado parcial, uma espera, um procedimento, um conjunto de recursos, um estoque, uma posio geogrfica num sistema de transporte, etc. Em geral, todo lugar tem um predicado associado, por exemplo, mquina livre, pea em espera (Fig. 6) [ 1 ]; Transio (representada por barra ou retngulo): associada a um evento que ocorre no sistema, como o evento iniciar a operao (transio t na Fig. 6) [ 1 ]. considerado o ativo da rede, pois responsvel por lhe trazer dinamismo. Quando certas pr-condies so satisfeitas, uma transio passa do estado de desabilitada para habilitada e pode disparar. O disparo das transies responsvel pela criao e pela destruio dos recursos (marcas) da rede [10]; Arco (representado por uma seta): responsvel por estabelecer as conexes entre lugares e transies ou vice-versa, mas nunca de lugar para lugar ou de transio para transio [10]; Ficha (representado por um ponto num lugar): um indicador significando que a condio associada ao lugar verificada. Pode representar um objeto (recurso ou pea) numa certa posio geogrfica (num determinado estado), ou ainda uma estrutura de dados que se manipula. Por exemplo, uma ficha no lugar mquina livre indica que a mquina est livre (predicado verdadeiro). Se no tem fichas neste lugar, o predicado falso, por conseguinte a mquina no est livre. Se no lugar peas em espera houvesse trs fichas, indicaria que existem trs peas em espera [ 1 ].

A primeira observao a fazer que estas diversas interpretaes dos lugares e fichas so bastante variadas. Podem ser utilizadas para descrever entidades abstratas como condies ou estados, mas tambm entidades fsicas como peas ou depsitos. Pode-se tambm chegar a uma banalizao completa, no 3

nvel descritivo, entre as peas, ferramentas e, de modo geral, entre todos os recursos utilizados na fbrica. esta grande banalizao que permite uma viso sinttica do sistema a ser modelado e que autoriza certos procedimentos de anlise [ 1 ].

Definio 1 (Rede de Petri). Uma Rede de Petri uma tripla,

onde P um conjunto finito no vazio de lugares, T um conjunto finito no vazio de transies e F uma dupla que representa a relao de fluxo dos arcos, e Ps uma funo

onde Pr uma funo de entrada tal que de sada tal que .

Na rede, os lugares (P) so representados por crculos, que denotam algo passivo tal como uma condio ou um estado local de um componente, enquanto as transies (T) so representadas por retngulos, que denotam algo ativo tal como uma ao, um evento ou a execuo de uma instruo. J os arcos (F) so representados por setas denotando causas ou efeitos. Alm disso, existem arcos que podem ligar um lugar pi a uma transio tj se, e somente se, ,

caracterizando uma pr-condio, e/ou ligar uma transio tj a um lugar pi se, e somente se, , caracterizando uma ps-condio. Os arcos tambm e , tal

podem conter um peso w associado, ou seja, que [ 15 ].

1.3. Marcao de redes de PetriA transio em um grafo de uma rede de Petri representa eventos de um sistema a eventos discretos e os lugares descrevem as condies sobre as quais esse evento pode ocorrer [ 8 ]. Nessa configurao necessrio um mecanismo indicando quando essas condies so verdadeiras ou no. Esse mecanismo definido pela adio de marcas ou fichas aos lugares [15]. Uma Rede de Petri marcada quando os lugares contm um nmero inteiro, no negativo, de fichas. O nmero de fichas contidas em um lugar pi denominado m(pi) ou mi . A marcao de uma rede de Petri definida pelo vetor 4

e determina o estado do sistema descrito em um dado momento. Neste trabalho, redes de Petri marcadas sero denominadas apenas como redes de Petri.

Figura 2.

Marcao inicial M0 de um grafo de rede de Petri.

O grafo da figura acima serve para exemplificar o conceito de marcao de rede de Petri. Caso seja definido o estado atual como sendo o estado inicial (M 0) da rede, ento , , e .

Definio 2 (Rede de Petri Marcada): uma rede de Petri marcada a qudrupla

, em que RP um grafo de rede de Petri, e M0 a marcao inicial do conjunto de lugares,

5

1.4. Comportamento de uma RdPEm um modelo de RdP, os estados esto associados aos lugares e suas marcaes, e os eventos s transies. O comportamento de um sistema modelado por RdP descrito em termos de seus estados e suas mudanas [7]. A dinmica de uma rede de Petri se d atravs da movimentao das marcas pelos lugares da rede, gerando um novo estado da rede. Toda e qualquer movimentao das marcas apenas pode ocorrer se uma transio estiver habilitada, ou seja, se, e somente se, o nmero de marcas contidas em cada lugar pertencente ao conjunto de entrada da transio for maior ou igual ao peso dos arcos respectivos [15]. Definio 3 (Transio Habilitada). Uma transio marcao M, denotado por , de uma rede de Petri est habilitada para a . Isto ,

ela est pronta para disparar se, e somente se,

onde, M(p) o nmero de marcas do lugar peso do arco de lugar-transio.

em uma marcao M e Pr(p, t) o

O disparo de uma transio habilitada far com que n marcas sejam retiradas de um lugar, tal que n o peso do arco que incide sobre a transio. Este procedimento ocorre para todas os lugares que so pr-condio da transio. Contudo, a transio gera marcas nos lugares que so sua ps-condio, onde a quantidade de marcas de cada lugar tambm especificada pelo peso de cada arco. Definio 4 (Disparo de uma Transio). Se uma transio habilitada por e adiciona

uma marcao M, ento o disparo de t retira Pr(p, t) marcas de Ps(p, t) marcas em

, levando a rede a uma nova marcao M0, denotada por

M[t > M0. A evoluo da rede descrita pela equao:

Na figura 8.a, tem-se um exemplo de rede de Petri, com quatro transies, seis lugares e marcao inicial M0 = [100000]. A transio t1 est habilitada, j que M0 Pr(t1).

6

Figura 3.

Estado atual da rede: (a) antes do disparo de t1; (b) aps o disparo de t1

Aps o disparo de t1, a rede atinge a marcao M1 = [011000], que torna as transies t2 e t3 recm habilitadas t2 e t3 esto em paralelo. H um indeterminismo com relao aos disparos das transies t2 e t3, j que ambas esto habilitadas para disparar mas no se sabe qual ir disparar primeiro at que ocorra efetivamente o disparo. Supondo arbitrariamente o disparo de t2, a rede atinge a marcao M2 = [001100], que mantm habilitada a transio t3, agora classificada como transio persistente. Como p5 Pr(t4) e p5 no est marcado, t4 no est habilitada.

Figura 4.

Estado atual da rede: (a) aps o disparo da sequncia t1t2; (b) aps o disparo da sequncia t1t2t3

Ao disparar t3, pode-se disparar t4 e ento no h mais disparos possveis, com a marcao M4 = [000001]. As sequncias t1 t2 t3 t4 e t1 t3 t2 t4 so sequncias disparveis para a rede da figura 8.a, enquanto t1 t2 t4 t3 no uma sequncia disparveis.

Figura 5.

Estado atual da rede aps o disparo da sequncia t1t2t3t4

Nas redes de Petri com extenses temporais, o interesse pode estar em no s verificar se uma determinada sequncia de disparos vlida, mas tambm em 7

calcular qual o tempo necessrio para executar toda a sequncia, ou seja, assim como em diversos problemas reais, o tempo de execuo da tarefa um elemento importante na anlise do problema. Neste tipo de anlise, os casos de paralelismo efetivo como ocorre entre t2 e t3 na rede da figura 8.b podem provocar aumento da impreciso nas informaes temporais, dependendo da metodologia de clculo utilizada [ 17 ].

1.5. PropriedadesPor ser uma forma de representao baseada em conceitos matemticos, as RdP possuem algumas propriedades que podem ser verificas em suas redes. As propriedades das RdP podem ser divididas em dois grupos: propriedades estruturais (ou estticas) e propriedades comportamentais (ou dinmicas) [ 7 ].

1.5.1. Propriedades estruturais As propriedades estruturais no dependem da marcao atual do sistema, referindo-se exclusivamente estrutura da rede. Com as anlises estruturais, possvel obter informaes adicionais sobre a dinmica da rede.

1.5.1.1.

Componentes conservativos Invariantes de lugar:

Procurar por um invariante de lugar verificar se h uma restrio que se refere marcao de alguns (ou de todos os) lugares da rede em todos os estados alcanveis, como por exemplo, a conservao do nmero total de marcaes para um determinado conjunto de lugares. Na rede da figura 11, cuja marcao inicial M0 = [1031], o resultado da soma M(p1) + M(p2) sempre 1, independente do estado atual do sistema note que os disparos de t1 ou de t2 no alteram o resultado desta soma, apesar de modificarem as marcaes. Do mesmo modo, o disparo das transies t3 e t4 tambm no modificam o resultado da soma, uma vez que no alteram as marcaes de p1 e p2. Quando esta propriedade satisfeita, a rede dita Conservativa.

8

Figura 6.

Invariantes

1.5.1.2.

Componentes repetitivos Invariantes de transio:

A anlise de invariantes de transio procura sobre a matriz incidncia da rede, um conjunto de transies cuja sequncia de disparos resulte em um ciclo. Na rede da figura 11, ainda com a marcao inicial M0 = [1031], o disparo da sequncia t3 t4 faz com que a rede retorne para a marcao inicial. Sendo assim, a sequncia t3 t4 um invariante de transio, pois aps o disparo desta sequncia a rede volta ao estado em que se encontrava anteriormente. Note que a sequncia t1 t2 tambm um invariante de transio da rede, gerando o mesmo comportamento cclico das marcaes. Quando uma rede atende a esta propriedade ela dita Repetitiva. Diferentemente do que ocorre com os invariantes de lugar, os invariantes de transio dependem da marcao atual da rede, j que os disparos dependem diretamente das pr condies das transies.

1.5.2. Propriedades Comportamentais As propriedades dinmicas das RdP so aquelas que tm a ver com o seu comportamento e que se modificam durante o funcionamento. Elas so essencialmente dependentes do estgio de execuo em que a rede se encontra e so, por conseguinte, dependentes da marcao da rede [ 1 ].

9

1.5.2.1.

Alcanabilidade

Definio 5 Sejam M0 e Mk respectivamente a marcao inicial e uma outra marcao qualquer de uma RdP. Uma marcao alcanvel se, e somente se, existe ao menos uma sequncia s de disparos tal que da rede o conjunto de todas as marcaes alcanveis da rede. Alcanabilidade uma propriedade fundamental para o estudo de propriedades dinmicas de qualquer sistema, uma vez que checar a alcanabilidade de uma marcao verificar se determinada marcao Mk alcanvel a partir da marcao inicial M0, ou seja, mostrar se (ou no) possvel atingir um determinado estado do sistema representado pela RdP. Em caso afirmativo, outras anlises podem ser feitas, de acordo com as caractersticas do problema que se pretende resolver. . A alcanabilidade

1.5.2.2.

Rede de Petri K-Limitada e rede de Petri Binria

Definio 6 (Lugar k-limitado e lugar binrio): Um lugar p de uma rede marcada N k-limitado (bounded) se e somente se:

Se k = 1 diz-se que o lugar binrio (safe em ingls). Na rede de Petri da Figura 12.a, cujo grafo de marcaes representado na Figura 12.b, para a marcao inicial M = p23 (ou M = [0 3 0]T), o lugar p3 binrio, enquanto os lugares p1 e p2 so 3-limitados.

10

Figura 7.

(a) Rede de Petri; (b) seu respectivo grafo de marcaes acessveis [ 1 ].

Definio 7 (Rede Marcada K-limitada): Uma rede marcada N k-limitada (bounded) se e somente se todos os seus lugares so k-limitados. Definio 8 (Rede Marcada Binria) Uma rede marcada N binria se e somente se todos os seus lugares so binrios. Diz-se tambm salva ou segura. A rede de Petri da Figura 12.a, para a marcao M = p23, 3-limitada, ou, limitada com k = 3. Se sua marcao inicial fosse M = p2 a rede seria binria (entretanto as transies c e d nunca seriam disparadas) [ 1 ].

1.5.2.3.

Rede Reinicivel reinicivel (ou prpria) se e somente se:

Uma rede marcada

possvel, portanto, a partir de qualquer marcao acessvel M, encontrar uma sequncia de disparo s que leve a rede de volta marcao inicial M0. A maioria dos sistemas possuem funcionamentos repetitivos e, portanto, as redes de Petri utilizadas para represent-los so reiniciveis. [ 1 ].

11

Figura 8. Rede Reinicivel

1.5.2.4.

Rede Viva

Definio 9 (Transio quase viva): Uma transio t de uma rede marcada quase viva se e somente se existe uma sequncia de disparo s tal que

Ou seja, a transio t quase viva se possvel sensibiliz-la por uma marcao M do grafo de marcaes acessveis, obtida, a partir da marcao inicial M, atravs do tiro de uma sequncia de transies s, eventualmente vazia (s = ). Diz-se que t pode ser sensibilizada a partir de M atravs do disparo da sequncia s. A equao acima pode ser reescrita sob a forma .

Definio 10(Transio viva) Uma transio t de uma rede marcada viva se e somente se:

Para ser viva, a transio t deve poder ser sensibilizada a partir de qualquer marcao M0 do grafo de marcaes acessveis, atravs de uma sequncia s de disparo. 12

Definio 11(Rede marcada viva) Uma rede de Petri marcada e somente se todas as suas transies so vivas:

viva se

importante observar que: Somente considerada aqui a rede de Petri marcada; Uma rede de Petri viva garante que nenhum bloqueio pode ser provocado pela estrutura da rede. No entanto, ela no prova a ausncia de eventuais bloqueios provocados por uma m interao entre a rede de Petri e seu ambiente externo; Uma rede de Petri viva garante tambm a ausncia de partes mortas (nunca atingidas).

1.6. Redes de Petri e a Representao do TempoInformaes temporais so teis para sequenciar eventos, comparar suas duraes, assim como determinar o intervalo existente entre eles. Desta forma, possvel representar e analisar problemas ligados a diversas atividades onde a avaliao do tempo um critrio de fundamental importncia. Como a noo de tempo no explicitamente dada na definio original de redes de Petri, ento, este conceito foi incorporado posteriormente. Com a adio de tempo, o indeterminismo com relao ao disparo de uma transio , de certa forma, reduzido j que a informao temporal acrescenta uma nova relao de ordem entre os disparos das transies [ 18 ]. As redes de Petri com tempo podem ser divididas em duas classes [ 17 ]: estocsticas e determinsticas. Na primeira, o tempo modelado com variveis aleatrias com distribuio exponencial, permitindo executar as transies atravs de uma funo probabilstica 46 onde possvel considerar incertezas nos tempos. Nas determinsticas, existem quatro abordagens para associar tempo aos elementos constituintes das redes de Petri: 1. Tempo associado s transies; 2. Tempo associado aos lugares; 13

3. Tempo associado s marcas; 4. Tempo associado aos arcos. Cada elemento da rede, dependendo da abordagem escolhida, consome Z unidades de tempo. Por exemplo, se for usada a abordagem 1, ento o tempo associado s transies. Definio 12De forma genrica, uma rede de Petri com tempo pode ser definida como uma dupla:

, onde RPM uma Rede de Petri Marcada e Z a informao temporal aplicada a cada elemento x da rede, onde x uma transio, um lugar, uma marca ou um arco [ 16 ]. Atualmente h trs modelos de RdP que mais se destacam. O primeiro modelo, conhecido como RdP Temporizadas (TdPNs, do ingls Timed Petri Nets), foi introduzido por Ramchandani [ 19 ] onde o tempo descrito atravs da durao do disparo, expresso por um nmero racional positivo. Os disparos das transies neste tipo de rede so executados em trs passos: 1. Uma transio t disparada no momento em que ela habilitada (figura 14.a), consumindo as marcas do seu pr-conjunto; 2. A marcao fica retida por Z(t) unidades de tempo pela transio (figura 14.b); 3. Depois de decorridas Z(t) unidades de tempo, as marcas so depositadas no ps-conjunto de t (figura 14.c).

Figura 9.

Exemplo de disparo de uma rede de Petri temporizada [ 16 ]

14

No segundo modelo de RdP o tempo associado aos lugares. Este modelo foi introduzido por Sifakis [ 21 ], e conhecido como RdP P-temporizadas. Neste caso, Z(p) associa um atraso a cada lugar p P fazendo com que as marcas

permaneam Z(p) unidades de tempo no lugar antes de serem utilizadas para habilitar as transies do seu ps-conjunto. Desta forma possvel definir dois tipos de marcas: disponveis e indisponveis. Quando uma marca chega a um determinado lugar p est no estado indisponvel. Ela se tornar disponvel aps decorrido o tempo associado ao lugar em questo. O estado atual da rede dado pela soma das marcas disponveis e indisponveis de cada lugar. J o disparo de uma transio ocorre de forma semelhante s TdPNs. As redes de Petri P-temporizadas e as TdPNs podem representar um mesmo sistema, pois elas so expressivamente equivalentes [ 22 ]. Sendo assim, existe uma forma de transformar um modelo em outro. As figuras 15 e 16 mostram como so feitas estas transformaes. Por fim, o terceiro modelo: as RdP Temporais. Este modelo de RdP mais abrangente, pois as TdPNs e as P-temporizadas esto contidas neste modelo. Uma vez que este modelo o que possui melhores ferramentais de anlise, ele ser o modelo adotado neste trabalho. P, ela sempre

1.6.1. Redes de Petri temporais O modelo das Redes de Petri Temporais (TPNs, do ingls Time Petri Nets) foi proposto por Merlin [47]. O tempo descrito atravs de um intervalo de disparo, onde, aps

15

Figura 10. Transformao de uma rede de Petri temporizada (a) em uma rede de Petri temporizada de lugar (b).

Figura 11. Transformao de uma rede de Petri temporizada de lugar(a) em uma rede de Petri temporizada (b).

a habilitao de uma transio, tem-se um tempo mnimo durante o qual a transio deve esperar at que possa disparar e um tempo mximo admissvel de espera para o disparo [ 20 ].

16

Definio 13(Rede de Petri Temporal). Uma rede de Petri com tempo dita uma Rede de Petri Temporal se, e somente se,

,onde Z(t) o intervalo de sensibilizao de cada transio os limites inferiores e superiores, respectivamente, de t .

, tal que

e

so

Nas TPNs cada transio deve possuir um relgio independente para o controle de seu tempo. Quando uma transio habilitada o relgio da transio comea a decrementar o tempo a ela atribudo, tanto para o valor de o de . Sendo assim, haver um ponto que o valor de quanto para

chegar ao valor 0 (zero), o pode ainda no

que significa que a transio j pode disparar. Porm, o valor de

ter zerado, o que significa que este o tempo mximo possvel para retardar o disparo. O disparo de uma transio ocorre de forma semelhante s redes de Petri convencionais [ 20 ]: ele instantneo e ocorre em um instante aps decorridos unidades de tempo e antes de unidades de tempo aps a sua habilitao.

importante salientar que para ocorrer o disparo de uma transio necessrio que ela permanea continuamente habilitada, caso contrrio, ela desabilitada e seu relgio removido. Este tipo de disparo chamado de disparo atmico. Em outras palavras, se uma transio for habilitada no tempo , ento t deve permanecer

continuamente habilitada at o seu disparo. Entretanto, t no pode disparar antes de , mas obrigatoriamente deve disparar at o tempo , a no ser que t seja

desabilitada pelo disparo de outra transio atravs do consumo de marcas de suas pr-condies. Definio 14(Condio de Disparo). Se momento ento t pode disparar se, e somente se, uma transio habilitada no

Alm disso, durante o intervalo de tempo continuamente habilitada e tambm deve disparar at desabilitado por outra transio.

a transio deve estar caso t no seja

17

Um exemplo da semntica das transies temporais apresentado pela Figura 17. O quadro (a) representa o estado inicial da rede que possui a transio t1 habilitada para o instante 0 (zero). Porm esta transio ainda no pode disparar, pois ela precisa esperar exatamente duas unidades de tempo pois igual a .

Aps decorrido este tempo, a transio t1 dispara no instante 2 do relgio da rede, como observado no quadro (b) e (c), onde a transio pronta para disparar est na cor cinza. Avanando mais uma unidade de tempo, ento t3 j pode disparar (quadro (d)), mas ela ainda pode retardar este disparo em at 4 unidades de tempo, como acontece neste exemplo. No instante 4, representado pelo quadro (e), passa-se a ter duas transies prontas para disparar e se as duas transies retardam seus disparos por mais uma unidade de tempo (quadro (f) e (g)), ento t2 obrigado a disparar no instante 5, porque o valor de j est zerado. Por fim, a transio t3, a partir deste momento, ainda pode ser disparada em qualquer um dos instantes 5, 6 ou 7.

Figura 12. Exemplo de uma sequncia de disparos de uma rede de Petri temporal com disparo atmico.

Quando uma rede tem transies em conflito, h casos que necessrio escolher uma transio para o disparo. Se considerarmos o tempo = 2, ento t1 e t2

podem disparar (figura 18). Se escolhido t1, ento desabilitar t2. Mas o que fazer com o tempo restante da transio que foi desabilitada e com o tempo do restante das transies da rede? H trs abordagens que podem ser adotadas [ 20 ]: 1. Resampling: Aps cada disparo todos os tempos, de todas as transies da rede, so reiniciadas. Neste caso no h memria, e depois de 18

descartados todos os tempos, novos valores de tempo somente sero aplicados ao novo conjunto de transies que so habilitadas a partir da nova marcao da rede. 2. Enabling memory: Aps cada disparo, os tempos das transies que oram desabilitadas so reiniciados. As demais transies mantm seus valores. esta a abordagem que ser adotada por este trabalho. 3. Age memory: Aps cada disparo, todos os tempos de todas as transies mantm seus valores.

Figura 13. Conflito em uma transio temporal.

A diferena entre TdPN e TPN, quando h conflito, que na primeira, por ter seu disparo em trs fases, se faz a escolha de uma transio para disparar dentre um conjunto de transies habilitadas, obrigando esta transio a disparar e no dando mais chance s demais. J na TPN o disparo atmico faz com que as marcas no sejam removidas na habilitao da transio. Qualquer transio pode ser disparada, desde que obedea a definio 7. Como uma TdPN est contida em uma TPN temporal, ento existe um mapeamento que traduz a primeira para ltima, assim como apresentado pela figura 19.

19

Figura 14. RdP temporizada (a) traduzida para RdP temporal (b).

1.7. Consideraes sobre RdPO presente captulo teve como objetivo apresentar as Redes de Petri, suas propriedades e sua representao temporal, que sero utilizadas posteriormente neste trabalho. Com os parmetros temporais, as RdP expandiram sua capacidade de representao, assim como aconteceu na rea de planejamento. Os modelos temporais propostos por Ramchandani [ 19 ], Merlin [ 22 ] e Sifakis [ 21 ] so os mais comumente utilizados, porm, segundo Balbo [ 20 ], uma rede de Petri temporal com disparo atmico pode preservar o comportamento bsico do modelo das redes de Petri sem tempo. Apesar de ser uma incrvel ferramenta para modelagem e anlise de sistemas, o maior problema que as RdP apresentam o fato de que quando requerido uma modelagem mais detalhada, o modelo tende a ser muito grande (exploso combinatria de estados) portanto, a sua anlise torna-se mais complicada [ 12 ]..

20

Bibliografia

[ 1 ] CARDOSO, J.; VALETTE, R. Redes de Petri, Florianpolis, Editora UFSC, 1997. 212p. [ 2 ] WIKIPEDIA, Petri Net. Disponvel em . Acessado em 01/04/2012. [ 3 ] SMART RADIO, Quick Start Guide: Flexis PIC CLP. 5p [ 4 ] TINA, Time Petri Net Analyzer. Disponvel em . Acessado em 05/04/2012. [ 5 ] DOS SANTOS, R. S. B. Modelagem e Anlise de Performance de Sistemas Flexveis de Manufatura Baseado em Redes de Petri Temporizadas: Estudo de Caso na Indstria Automobilstica. 2008. 115p. Dissertao de Mestrado. PUC-SP, So Paulo, 2008 [ 6 ] SCOLARI, A. P. S., Utilizao de Diagramas de Deciso Multivalorada para representao do espao de estados atingvel em Redes de Autmatos Estocsticos, Dissertao de mestrado, Pontifcia Universidade Catlica do Rio Grande do Sul, 2008. [ 7 ] RIEDER, R., Uma Metodologia para especificar Interao 3D utilizando Redes de Petri, Dissertao de mestrado, Pontifcia Universidade Catlica do Rio Grande do Sul, 2007. [ 8 ] MARRANGHELLO, N., Redes de Petri: Conceitos e Aplicaes, Apostila de Redes de Petri, DCCE/IBILCE/UNESP, 2005. [ 9 ] SOUSA, N. G., Propagao de Comportamento Anormal em Sistemas Hbridos Dinmicos, Dissertao de mestrado, Universidade Federal de Uberlndia, 2010. [ 10 ] RODRIGUES, C. M. de O., Mapeando Estruturas LSC em Redes de Petri Coloridas, Trabalho de Concluso de Curso, Escola Politcnica de Pernambuco, 2006. [ 11 ] BICHO, A. de L., Controle de Animaes por Computador utilizando Redes de Petri, Dissertao de Mestrado, Universidade Estadual de Campinas, 2001.

21

[ 12 ] PALOMINO, R. C., Uma Abordagem para a Modelagem, Anlise e Controle de Sistemas de Produo Utilizando Redes de Petri, Dissertao de Mestrado, Universidade Federal de Santa Catarina, 1995. [ 13 ] FRANCES, C. R. L., Introduo s Redes de Petri, Apostila do Laboratrio de Computao Aplicada, Universidade Federal Do Par, 2003. [ 14 ] SILVEIRA, L. C., Ferramenta de Gerao de Rotinas de Teste a partir de Autmatos, Projeto de Fim de Curso, Universidade Federal de Santa Catarina, 2011. [ 15 ] MONTEZANO, A. F. M. Modelo em Rede de Petri de um Sistema de Automao de Elevador de Passageiros, Trabalho de Concluso de Curso, Universidade Federal do Rio de Janeiro, 2009. [ 16 ] SALVI, J. L. Relacionamentos Temporais entre Redes de Petri e Planejamento Automtico, Dissertao de Mestrado, Universidade Federal do Paran, Curitiba, 2009. [ 17 ] MURATA, T. Petri nets: Properties, analysis and applications. In: Proceedings of the IEEE. Los Alamitos, CA, USA: IEEE, 1989. v. 7, n. 4, p. 541580. [ 18 ] JNIOR, N. M. Redes de Petri Temporais: Mtodo de Anlise Baseado em Tempo Global. Dissertao (Mestrado) Universidade Federal do Paran UFPR, Curitiba, PR, Brasil, fev. 2008. [ 19 ] RAMCHANDANI, C. Analysis of Asynchronous Concurrent Systems by Timed Petri Nets. Tese (Doutorado) Cambridge, Mass.: MIT, Dept. Electrical Engineering, fev. 1974. Project MAC TR-120. [ 20 ] BALBO, G. et al. Petri nets 2000: Introductory tutorial. In: NIELSEN, M.; SIMPSON, D. (Ed.). 21st International Conference on Application and Theory of Petri Nets (ICATPN). Aarhus, Denmark: Springer, 2000. [ 21 ] SIFAKIS, J. Use of Petri nets for performance evaluation. In: BEILNER, H.; GELENBE, E. (Ed.). Performance. Bad Godesberg, Bonn, Germany: NorthHolland, 1977. p. 7593. [ 22 ] MERLIN, P. M. A Study of Recoverability of Computer Systems. Tese (Doutorado). University of California, Dep. Comput. Sci, Irvine, CA, USA, 1974. [ 23 ] WIKIPEDIA, Petrleo. Disponvel em

. Acessado em 17/04/2012. 22