LEVANTAMENTO DA APLICAÇÃO DE REDES DE PETRI

October 3, 2017 | Autor: M. Cristina de Aq... | Categoria: Physics
Share Embed


Descrição do Produto

LEVANTAMENTO DA APLICAÇÃO DE REDES DE PETRI

Márcia C. de Aquino Passos1 (UFPE) [email protected]

RESUMO Quando exposta em 1962 por Carl Adam Petri, a Rede de Petri (RdP) tratava-se de um modelo matemático onde as propriedades mais sobressalentes são a capacidade de apresentar sistemas graficamente e a verificação de interações entre as distintas partes que os compõem (MACIEL et al, 1996). Mas será que o autor (então mestrando) imaginaria que ali constituía-se um poderoso e definitivo mecanismo de análise, perfeito para constatação de propriedades e a corretude de sistemas? Este trabalho visa focar um levantamento da aplicabilidade das Redes de Petri, evidenciando que a utilização de formalismos baseados em grafos é até os dias atuais, amplamente aplicada às várias áreas do conhecimento, admitindo, com a reprodução de modelo, que sistemas sejam simulados e os seus procedimentos sejam observados. Desde os seus primórdios as RdP têm se prestado como valoroso método para análise de sistemas de áreas como sistemas discretos, rede de computadores, engenharias, transportes, fluxo de processos de negócio, além de sistemas de hardware/software, protocolos de comunicação e análise de desempenho, dentre outras classes de sistemas. A metodologia utilizada foi ancorada na análise de artigos, estudo e leitura bibliográfica de escritos sobre rede de Petri, como também material disponível a respeito do tema proposto. No que se refere aos objetivos da pesquisa a mesma se constituirá do tipo exploratório tendo por escopo uma análise ao atual Rede de Petri. O método científico consiste num conjunto das atividades sistemáticas e racionais que, com maior segurança e economia, permite alcançar o objetivo da pesquisa, traçando o caminho a ser seguido, detectando erros e auxiliando as decisões do cientista (LAKATOS; MARCONI, 2003). E, por fim, as considerações finais, apontando que a técnica e o uso de redes de Petri é condicionado de ferramentas de software, que são imprescindíveis para auxiliar na modelagem do sistema e que são genuinamente eficazes para a execução das várias análises que podem ser alcançadas sobre o modelo. Palavras-Chave: Rede de Petri, Analise de Desempenho, Sistemas.

1

Aluna da disciplina de Modelos de Sistemas Comunicantes do Curso de Pós-Graduação em Engenharia da

Computação do Centro de Informática da UFPE.

1. INTRODUÇÃO

O modelo sugerido por Petri atrai a atenção de diversos pesquisadores e, ao longo dos anos, foi se revolvendo cada vez mais difundida. Desde então, Diferentes propostas de extensões ao modelo original foram surgindo, determinando o aparecimento de novos tipos de redes de Petri como as redes Temporizadas, Coloridas e Estocásticas. Outra particularidade que chama a atenção na Redes de Petri é a sua facilidade em conceber paralelismo e concorrência, e igualmente as inclusões de causalidade em meio às partes do sistema (PAES, 2005). Isto devido ao caso de ser uma prática capaz de modelar o estado do sistema em graus de granularidades, o que é provido pela teoria convencional de autômatos, ainda segundo o autor. As Redes de Petri levando em consideração o momento de acontecimento dos eventos, foram introduzidas independentemente por Ramchandani (1974) e Merlin (1974). Depois disto, um amplo número de distintas influências para Redes de Petri têm sido recomendado na literatura, e cada uma delas sendo utilizada em uma atenção particular. Então, logo surgiram aquelas chamadas extensões, que na maioria das vezes, se distinguem em, além da configuração de temporização, aspectos como localização da restrição (CERONE; MAGGIOLO-SCHETTINI, 1999), ambientes ou marcas que transportem informações temporais (AURA; LILIUS, 1996), dentre outros. O objetivo do estudo trata-se de mostrar que as redes de Petri têm ampla capacidade de demonstração e podem ser aproveitadas para modelar sistemas as mais variadas gamas.

2. AS REDES DE PETRI Para que este trabalho seja compreendido corretamente, uma introdução conceitual se faz indispensável. Este tópico não traz como desígnio cobrir toda a conjectura que abrange as Redes de Petri, pois esta é vasta e contém grande número de informação que não está no intento deste estudo.

2.1 Rede de Petri: Visão Geral A Rede de Petri é um padrão matemático capaz de modelar sistemas colaterais, contendores, assíncronos e não-determinísticos. Foram primeiramente deliberadas em 1962 por Carl Adam Petri em sua tese de doutorado Kommunication Mit Automaten na Universidade de Dramsdadt na remota Alemanha Ocidental (MACIEL et al, 1996). As redes

são analisadas em um progresso da teoria dos autômatos finitos (PAES, 2005), uma vez que essas redes, são capazes de modelar o paralelismo dos sistemas. Na sua representação gráfica, a RdP promove a abrangência e explicação do funcionamento de sistemas. Uma rede é composta por elementos fundamentais: Os lugares, os quais concebem os elementos passivos da rede. Os lugares simulam os estados que um sistema pode tomar durante o seu curso de efetivação. Para tal, os lugares exibem certos elementos designados marcas ou tokens, os quais sugerem a presença ou disponibilidade de algum recurso. É à acomodação destas marcas nos lugares que determina os estados da rede. (...) Quando certas précondições são atendidas, uma transição incide do estado de desabilitada para habilitada e pode disparar. O disparo das transições é responsável pela concepção e pelo aniquilamento dos recursos (marcas) da rede (PAES, 2005).

Ver-se através de (PAES, 2005), (MACIEL et al, 1996) e outros, que os elementos concebidos pelo então doutorando Carl Adam Petri, se solidificou em uma forma de representação simples, porém aperfeiçoada abrangência, de considerar condutas de sistemas. Os autores ainda esclarecem que os lugares são representados por círculos ou elipses e as marcas por pontos dentro dos lugares; As transições satisfazem aos elementos ativos da rede, pois são as responsáveis por oferecer a propriedade do dinamismo desta. Para representar graficamente os elementos que compõem qualquer Rede de Petri são titulados de lugares, transições e arcos (MURATA, 1989). A Figura 1 expõe a reprodução gráfica destes elementos. Lugares (Fig 1.a) são representados graficamente por círculos (ou elipses), transições (Fig. 1.b) por retângulos e arcos por setas que unem um lugar a uma transição ou uma transição a um lugar (jamais um lugar a mais um ou uma transição a outra) (Fig. 1.c,d).

(a)

(b)

(c)

(d)

Figura 1 – a) Lugar; b) Transição; c) Arco unindo um lugar e uma transição; d) Arco conectando uma transição a um lugar. Lugares podem ser marcados ou não. Um lugar marcado é concebido por um ou mais pontos delineados dentro do círculo que concebe o lugar (Figura 2). Estes pontos são titulados de tokens (fichas). O número de tokens que um lugar tem é o que determina o seu

estado e é chamado de marcação deste lugar. O contíguo dos lugares da Rede de Petri configura o conjunto das alteráveis de estado que simulam o sistema modelado. Portanto, as marcações de todos os lugares em certo andamento é uma propriedade importante da rede, concebendo o estado do sistema naquele período. Este estado global, combinado pelos estados de cada lugar, é chamado de marcação da rede.

Figura 2. Lugar com um token e lugar com vários tokens Os lugares são elementos indiferentes e determinam o estado do sistema. As mudanças, por outro lado, são elementos funcionais. Elas concebem ações que podem acontecer e que transformam o estado do sistema (marcação da rede). Os lugares que permanecem acoplados a uma transição por meio de arcos são os que determinam quando uma transição pode acontecer e como o estado é transformado posteriormente a sua ocorrência. Um arco conectando um lugar a uma transição (idêntico visto na Fig. 1.c) importa uma qualidade que deve ser apropriada para que aquela transição aconteça (MACIEL et al, 1996). E para todo arco que liga algum lugar a esta transição deve haver pelo menos um token naquele lugar. Todo este procedimento que ocorre quando uma transição acontece é chamado de disparo da transição. Exemplificando um modelo de sistema representado por RdP segue a figura 3, onde pode-se perceber como lugares, transições e tokens se juntam dando forma a sistemas, representando suas propriedades.

Figura 3. Rede de Petri modelando um sistema qualquer Assim, o nível de detalhamento de uma rede de Petri é capaz de propagar várias condições que fiquem acontecendo respectivamente em diferentes partes do sistema e o seu formalismo admite expor como condições comprometem a passagem entre estados.

2.2 EXTENSÕES DAS REDES DE PETRI Permanecem hoje em dia, diferentes tipos, ou extensões, das redes de Petri. Estes tipos foram designados devido a obrigações nascidas pelo uso das redes mais simples. Essas precisões constituíam, dentre outras, a procura de uma rede com uma capacidade computacional maior, por meio das quais, sistemas difíceis que abrangem grande quantidade e manipulação dos dados pudessem ser simplesmente representados numa particularização de alto nível.

3. REDES DE PETRI NO CONTEXTO DE WORKFLOW Na modelagem de workflow empregando redes de Petri, cada trabalho é concebido por uma transição apropriada. Lugares concebem as pré e pós-condições ou ainda, os recursos solicitados para o cumprimento de uma definida tarefa. Os arcos simulam as relações coerentes entre as tarefas e o próprio fluxo de trabalho. A reprodução gráfica das RdP tem se manifestando muito útil neste tipo modelo de sistema, pois admite a visualização dos processos e a comunicação entre eles. As marcas dos lugares podem ser prescindidas, representando um estado de algum evento, por exemplo, documento disponível (lugar com marca) ou documento indisponível (lugar sem marca). Em concordância com Holt (2000), as redes de Petri admitem delinear planos de sistemas gerais diferenciados por um alto nível de concorrência. Na composição de workflow, tais planos são delineamentos globais ou parciais da forma particular de conseguir alguns tipos de atividades difíceis e especialmente disseminadas. Essas atividades serão focalizadas como exclusivas (idealização de recursos de vários tipos) ou, como controladoras de falhas, gastos ou carga de trabalho. Desde que todo o negócio possa ser analisado como um sistema que abrange operações complexas e concorrentes (produção, marketing, contabilidade, processos financeiros, negociações, etc), o uso das redes de Petri em seu programa ou análise parece uma ideia natural.

4. REDE DE PETRI E TRANSPORTE LOGÍSTICO Em (Machado, 2006) utilizou a RdP na sua extensão temporal com intuito de promover avaliação operacional do transporte de madeira, vislumbrando a melhoria de recursos como fluxo, abastecimento, volume de entrada, centrando logicamente, nos tempos que envolve todo este ciclo. Com os elementos foi possível simular cenários para avaliar o

desempenho tanto operacional como econômico, para isso foram utilizados os softwares JARP e ARP . A figura a seguir (figura 4) demonstrada pela autora a fim de exibir como o ciclo da cadeia logística de transporte de madeira nas regiões analisadas (Cocai das Estadas – CE e Rio Doce – (RD) foi mapeada. Viagem vazia

Colheita Floresta

Garagem

Carregamento

Transporte Viagem

Viagem

Carregada

Carregada

Descarregamento nos

Viagem vazia

tambores rotativos

Pesagem e medição

Viagem Carregada

Viagem vazia

Descarregamento no Pátio

Figura 4. Descrição da cadeia logística do transporte de madeira rodoviário

O modelo é caracterizado pela quantidade de carregadores florestais no campo, pelo número de veículos de transporte rodoviário, pelas condições das estradas e pela distância, dentre outros. E ainda quantifica a autora, dois carregadores frontais, dois picadores e três gruas para movimentação da madeira no pátio.

Na representação com RdPt resultou na seguinte estrutura conforme figura 5 abaixo:

Figura 5. Representação do transporte rodoviário de madeira na estrutura da Rede de Petri Temporal No resultado da pesquisa foram constadas, que através da aplicação da RdP, é possível reduções não apenas nos tempos dos ciclos de transporte de madeira, como nos custos operacionais. E ainda, mais uma vez, o potencial da RdP como via de modelagem, analise e avaliação de sistemas como o da cadeia de transporte rodoviário geral.

5. REDE DE PETRI E TRAFEGO AÉREO A importância da utilização da Rede de Petri para controle do funcionamento de trafego aéreo é demonstrada pelos professores Leonardo Guedes e Eugênio Carvalho, ambos do departamento de computação da Universidade Católica de Goiás em artigo publicado na Associação Brasileira de Engenharia de Produção – 2008.

No referido artigo, os autores descrevem como as companhias, em busca de atender as exigências da ANAC – Companhia Nacional de Aviação, no que diz respeito a logística de controle de movimento dos aviões pela malha aérea, como também seu tempo de voo. O relato mostra que as companhias aéreas nem sempre conseguem administrar com eficiência seus horários rotineiros de voos por vários motivos, dentre eles atrasos e

cancelamento, acarretando uma redefinição de planos e procedimentos, que são resolvidos por profissionais da área, exigindo amplo conhecimentos do HOTRAM2 e das referidas rotas previstas pela companhia. Mesmo diante das novas tecnologias de controles aéreos, existe uma preocupação em resolver o problema de forma a otimizar tempo e procedimentos, assim, propõe-se na publicação a utilização e representação com Rede de Petri para tais fins. Com a modelagem em RdP se permite o controle do funcionamento dos voos da companhia, pois se consegue controlar o deslocamento das aeronaves pela rede, bem como o tempo do voo. Neste sentido é compreendido que a HOTRAM de qualquer companhia aérea ao descrever suas rotas e horários, terão obrigatoriedade no cumprimento das normas sendo avaliadas periodicamente quanto a sua atuação no que diz respeito a atrasos e regularidade de voos. Em busca de exemplificar descrição acima tomou-se como base a figura 6 abaixo onde são demonstrados os elementos envolvidos na problemática.

Figura 6. Representação de Rotas – Cenário para Aplicação.

2

Horário de Transporte - documento que formaliza o direito de uma empresa aérea de realizar uma ou mais rotas

Na representação percebe-se a representação de aeroportos, voos com tempo e rotas entre eles e as aeronaves de uma determinada companhia. Através da figura 7 uma Redes de Petri é concebida para a resolução do problema, dada pela técnica de algoritmo genético onde foi possível mapear os lugares representando aeroportos, transições representando rotas e tempos entre os aeroportos.

Figura 7. Rede de Petri das rotas aéreas

Os autores explicam que na estrutura de Rede de Petri (Figura 7) representa a equação RP(P,T,Pré,Pos), onde: 

P={A(p0),B(p1), C(p2), D(p3), E(p4)} representa os aeroportos atendidos;

 T={TAB(t0),TBA(t1),TAC(t2),TCA(t3),TAD(t4),TDA(t5),TAE(t6),TEA(t7),TBC(t8) ,TCB(t9),TBD(t10),TDB(t11),TCE(t12),TEC(t13),TDE(t14),TED(t15)} representa os voos entre os aeroportos;

Os autores concluem nos lembrando de técnicas e recursos inerentes a RdP como matriz de rastreabilidade e árvore de cobertura ou alcançabilidade da rede, além do próprio algoritmo genético. E que mesmo sem considerar o custo com passagens, foi apresentado resultados satisfatórios.

6. REDE DE PETRI NA BIOINFORMÁTICA

Chegando-se até (Medrado, 2009) observa-se a descreção sobre a importância das vias biológicas que representam interações entre entidades químicas complexas, sejam estas proteínas, substratos, metabólicos dentre outros, que fazem parte do nível molecular das células em sua ocorrência, considerada pelo autor como o principal objeto de estudos da biologia sistêmica. Neste sentido buscou-se uma representação gráfica capaz de demonstrar estes processos biológicos com eficiência. Inicialmente foi definido um grafo chamado de BioProc3 considerados como diagramas de processos modeladores das vias biológicas utilizando como sugestão para descrever em sua tradução algébrica a Rede de Petri em sua extensão “Estocástica” Generalized Stochastic Petri Nets ( GSPN). Neste contexto é colocado como exemplo (figura 8) o uso da linguagem visual com evolução da GSPN gerada também altera o estado do diagrama BioProc; onde a reação exemplificada é uma interação proteína- proteína e ao mesmo tempo sendo demostrada representação em RdP.

Figura 8. Exemplo de interação proteína-proteína.

Na demonstração lado a lado dos grafos é facilmente vista a tradução de BioProc e GPN. E mais clarificado quando o autor indica que foram feitos disparos do lado da RdP para checar propriedades como atingibilidade e reversibilidade, análise invariante e minimal traps e siphons. Em outras palavras foi verificado as propriedades disponíveis na estrutura da RdP fazendo a interação no contexto biológicos. Tais como a própria lógica estocástica.

3

Instâncias são utilizadas no trabalho como diagramas de processos modelando vias biológicas.

7. CONSIDERAÇÕES FINAIS

Os subsídios deste trabalho foi ampliar o mapeamento dos modelos formais, de modo que o arquivo resultante possa ser passado como abertura para um instrumento, onde características dos sistemas possam ser analisadas. Pode-se concluir aqui que as áreas onde a modelagem de Rede de Petri pode ser aplicada são de infinitas possibilidades, assim como HOLT (2000) avalia que um padrão de Rede de Petri de estrutura causal da operação do workflow pode prover firme fundamentação coerente e argumento realístico para aproveitamento de expressões de matemática aplicada, teoria da decisão, teoria de jogos, análise de operação, estatística, etc., toda essa base pode ser aplicada na análise de sistemas e através da evolução das RdP de áreas como biologia, engenharias, computação e informática, economia, dentre outras. Assim, por permitir que aconteça rastreamento meticuloso e sem confusão a cada passo de operações e, por admitir uma representação matemática formal atrelada a mecanismos de análise para constatar propriedades de sistemas e se este está válido, a Rede de Petri comprova benefícios no seu uso em negócios, medicina, transportes de cargas, valores e pessoas, tecnologia da informação e comunicação, computação móvel, engenharia de requisitos, só pra citar alguns exemplos de uma vasta gama. Mas, uma carência do uso de técnicas para a apresentação mais descritiva, ao longo deste trabalho ainda deixa de aclarar múltiplos assuntos que muitas vezes foram apresentados de forma hermética. Isto porque, para uma correta prática, muitos conceitos aqui apresentados precisam ser analisados em detalhes. 8. REFERÊNCIAS AURA, T. ; LILIUS, J. Time processes for time Petri nets, Lecture Notes in Computer Science, Vol. 1248, Springer Verlag, Berlin, Germany, pp. 136–155. 1996. CERONE, A; MAGGIOLO-SCHETTINI, A. Time-base expressivity of time Petri nets, Vol. 216, Theorical Computer Science, pp. 1–53. 1999. GUEDES, L. G. R; CARVALHO E. J. M. C. – Artigo, Um Método Para o Planejamento do Roteamento Contingencial de Tráfego Aéreo - Contingencial air traffic routing, Revista Eletrônica de Engenharia de Produção e Correlatas - ISSN 1676-1901, 2008 disponível em < http://www.producaoonline.org.br/rpo/article/view/133> . Acessado em 12/07/2014. HOLT, A., COMMONER, F. Events and conditions. Massachussets: Record of the Project MAC Conference on Concurrent Systems and Parallel Computation (MIT), June 2000.

MACHADO, R. R. Avaliação do Desempenho Logístico do Transporte Rodoviário de Madeira Utilizando Rede de Petri, Dissertação de mestrado – Universidade Federal de Viçosa, 2006. MACIEL, P. R.; LINS, R. D.; CUNHA, P. Introdução às Redes de Petri e Aplicações, Campinas: X Escola de Computação, 1996. MEDRADO, R. G. Formalização de uma Linguagem Visual para Descrição de Sistemas Biológicos. Dissertação (Mestrado) - Porto Alegre: PGC da UFRGS, 2009. MERLIN, P. A Study of Recoverability of Computer Systems, PhD thesis, University of California IRVINE. available from Ann Arbor: Univ Microfilms, No. 75– 11026. 1974. MURATA, T. Petri Nets: Properties, Analysis and Applications. In: Proceedings of the IEEE, v. 77, n. 4, 1989. PAES, Rodrigo B. Regulando a Interação de Agentes em Sistemas Abertos – uma abordagem de Leis. Dissertação (Mestrado) – Departamento de Informática, Pontifica Universidade Católica do Rio de Janeiro, Rio de Janeiro, 2005. RAMCHANDANI, R. Analysis of Asyncronous Concurent Systems by Time Petri Nets, PhD thesis, Cambridge, Mass.: MIT, Dept. Electrical Engineering. Project MAC TR-120. 1974.

Lihat lebih banyak...

Comentários

Copyright © 2017 DADOSPDF Inc.