Método de desdobramento temporal para redes de petri temporais

Orientador : Prof. Dr. Marcos CastilhoCo-orientador : Prof. Dr. Luis Allan KünzleTese (doutorado) - Universidade Federal do Paraná, Setor de Ciências Exatas, Programa de Pós-Graduação em Informática. Defesa: Curitiba, 26/02/2016Inclui referências : f. 105-108Área de concentração: Ciência da ComputaçãoResumo: Sistemas reais modeláveis como sistemas dinâmicos a eventos discretos têm, em seu comportamento, fortes restrições temporais. As redes de Petri temporais são uma importante ferramenta de modelagem e análise desses sistemas. Entretanto, os principais métodos de análise existentes na literatura trabalham por enumeração exaustiva do espaço de estados, com alta complexidade computacional, sobretudo em situações de forte concorrência e paralelismo. Estes método também não são adequados para a análise de roteiros de comportamento, aumentando a imprecisão temporal dos resultados de análise, tornando-os inusáveis. O trabalho desenvolvido nesta tese consistiu em aprimorar duas abordagens já existentes, o desdobramento de redes de Petri e a análise por tempo global, de forma a superar estas limitações. O desdobramento, desenvolvido para redes de Petri sem considerações temporais, consiste em gerar uma rede de ocorrência, finita e acíclica, que contém todos os estados acessíveis da rede original, mas com um custo computacional significativamente menor. Entretanto, sua aplicação direta em redes de Petri temporais perde sequências de disparo de transições válidas e gera outras inválidas, considerando as restrições temporais da rede. A parte inicial deste trabalho teve como foco inicial identificar as limitações do uso do algoritmo original de desdobramento em redes de Petri temporais, para em seguida conceber e formalizar um procedimento de desdobramento que seja aplicável a redes temporais. Este procedimento tem como base o algoritmo original, mas já incorpora em sua estrutura elementos de análise temporal. O novo método de desdobramento obtido foi denominado de "desdobramento temporal" e a rede por ele gerada contém todas as classes de estados da rede temporal, assim como todos os caminhos ou roteiros de comportamento resultantes da dinâmica da rede. O resultado será validado mediante provas e também será apresentado um exemplo de aplicação do novo método. A segunda parte deste trabalho de pesquisa foi dedicada a construir uma metodologia de análise temporal, sobre a rede desdobrada, utilizando o método de tempo global. Este método permite a análise de roteiros de comportamento, ou sequências de disparo de transições, sem aumentar a imprecisão dos resultados e é destinado a redes acíclicas. Ou seja, adequado à rede desdobrada. A metodologia de análise proposta permite avaliar temporalmente qualquer roteiro de comportamento entre as diferentes classes de estados temporais. Os resultados obtidos foram comparados com as metodologias já existentes. Palavras-chave: Redes de Petri temporais, desdobramento temporal, análise temporal, tempo global.Abstract: Real systems formable as dynamic discrete event systems have, in their behavior, strong time constraints. The time Petri nets are an important modeling tool and analysis of these systems. However, themainmethods existing of analysis in the literature works by exhaustive enumeration of the state space, with high computational complexity, especially in strong situations of concurrence and parallelism. Also this methods are not suitable for analysis of behavioral scripts, increasing the temporal imprecision of analysis results, making them unusable. The work in this thesis was to improve two existing approaches, the unfolding of Petri nets and the analysis by global time, concerning to overcome these limitations. The unfolding, developed for Petri nets without temporal considerations, consits in generate an occurrence net, finite and acyclic, that contain all accessible states of the original net, but with a significantly lower computational cost. Nonetheless, its direct application in time Petri nets loses the transitions firing sequences valid and generates others invalid considering the temporal net constraint. The initial part of this work had like initial focus an identification of limitations the use original algorithm of unfolding in time Petri nets, and then, develop and formalize an unfolding procedure that applies to time net. This procedure is based on the original algorithm, but it already incorporates in its structure temporal analysis elements. The new obtained unfolding method was called "timing unfolding" and the net generated contains all states class of time net, as well as all paths or behavior scripts resulting from the dynamic of the net. The result will be validated by proofs and it will be presented by an application example of the new method. The second part of this research work was dedicated to build a temporal analysis method on the unfolded net, using tthe global time method. This method allows the scripts analysis behavior, or transitions firing sequences without increasing the inaccuracy of the results and is intended to acyclic nets, that is, suited to unfolded net. The analysis methodology proposed allows to assess, temporally, any behavior script between different time states class. The results were compared with the existing methodologies. Keywords: Time Petri nets, timing unfoldings, timing analysis, global time