Bevistema

Esta seção apresenta os fundamentos teóricos necessários para compreender os métodos formalizados no Capítulo 3. A subseção 2.1.1 apresenta as terminologias e notações básicas relacionadas à teoria da rede de Petri, que são essenciais para o entendimento da WorkFlow net e da WorkFlow net interorganizacional, que são apresentadas nas subseções 2.1.2 e 2.1.3, respectivamente. A subseção 2.1.4 apresenta os conceitos básicos da relação entre a rede de Petri e a Lógica Linear, que são utilizados nos métodos apresentados no Capítulo 3.

2.1.1 Redes de Petri

A teoria inicial da rede de Petri foi proposta por Carl Adam Petri em sua tese de doutorado ((PETRI, 1962)). Desde então, o estudo e uso da rede de Petri tem crescido consideravelmente. Murata (1989) apresenta uma revisão histórica e bibliográĄca extensa da rede de Petri.

De acordo com Murata (1989), a rede de Petri clássica é um grafo bipartido direcionado com dois tipos de nós denominados lugares e transições, conectados via arcos direcionados. As conexões entre dois nós do mesmo tipo não é permitida (MURATA, 1989). Os lugares são representados por círculos e as transições por retângulos ou barras. Murata (1989) apresenta a seguinte deĄnição para uma rede de Petri.

DeĄnição 1. (Rede de Petri)

Uma rede de Petri clássica é uma tripla 𝑃 𝑁 = ¶𝑃, 𝑇, 𝐹 ♢, onde: a) 𝑃 é um conjunto Ąnito de lugares;

b) 𝑇 é um conjunto Ąnito de transições, onde (𝑃 ∩ 𝑇 = ∅);

c) 𝐹 ⊖ (𝑃 × 𝑇 ) ∪ (𝑇 × 𝑃 ) é um conjunto de arcos (relação de Ćuxo).

Um lugar 𝑝 é denominado lugar de entrada de uma transição 𝑡 se, e somente se, existe um arco direcionado de 𝑝 para 𝑡. Por exemplo, considerando a rede de Petri da Figura 1(a), os lugares 𝑃 1 e 𝑃 2 são lugares de entrada da transição 𝑡1.

Um lugar 𝑝 é chamado de lugar de saída de uma transição 𝑡 se, e somente se, existe um arco direcionado de 𝑡 para 𝑝. Por exemplo, considerando a rede de Petri da Figura 1(a), o lugar 𝑃 3 é um lugar de saída da transição 𝑡1.

Um lugar 𝑝 contém em um dado momento zero ou mais Ąchas (tokens), que são repre- sentadas por pontos pretos. Por exemplo, considerando a rede de Petri da Figura 1(a), o lugar 𝑃 1 contém uma Ącha e o lugar 𝑃 2 contém zero Ąchas.

A marcação de uma rede de Petri refere-se à distribuição de Ąchas nos lugares, sendo que o número de Ąchas pode mudar durante a execução da rede. As transições são os componentes ativos em uma rede de Petri: elas mudam a marcação da rede de acordo com as seguintes regras de disparo (MURATA, 1989):

a) uma transição 𝑡 é dita sensibilizada se, e somente se, cada lugar de entrada 𝑝 de

𝑡 contém pelo menos uma Ącha. Por exemplo, a transição 𝑡1 da rede de Petri da

Figura 1(a) não está sensibilizada. Já a transição 𝑡1 da rede de Petri da Figura 1(b) está sensibilizada, pois há uma Ącha em cada lugar de entrada desta transição; b) uma transição sensibilizada pode disparar. Se a transição 𝑡 disparar, então 𝑡 con-

some uma Ącha de cada lugar de entrada 𝑝 de 𝑡 e produz uma Ącha em cada lugar de saída 𝑝 de 𝑡. As Figuras 1(b) e 1(c) mostram um exemplo de disparo de transição. Neste caso, 𝑡1 consome uma Ącha de cada lugar de entrada (𝑃 1 e 𝑃 2) e produz uma Ącha em cada lugar de saída (𝑃 3), como pode-se veriĄcar na Figura 1(c).

(b) P1 P3 t1 P2 (a) P1 P3 t1 P2 (c) P1 P3 t1 P2

Figura 1 Ű Exemplos de sensibilização e disparo de transição em uma rede de Petri. Murata (1989) utiliza ∙𝑡 para denotar o conjunto de lugares de entrada para uma transição 𝑡. As notações 𝑡∙, ∙𝑝 e 𝑝∙ possuem signiĄcados similares. Por exemplo, 𝑝∙ é o conjunto de transições que compartilham 𝑝 como lugar de entrada. Considerando a Figura 1(a), tem-se: ∙𝑃 1 = ∅, 𝑃 1∙ = ¶𝑡1♢, ∙𝑃 2 = ∅, 𝑃 2∙ = ¶𝑡1♢, ∙𝑃 3 = 𝑡1, 𝑃 3∙ = ∅, ∙𝑡1 = ¶𝑃 1, 𝑃 2♢ e 𝑡1∙ = ¶𝑃 3♢.

Um estado de uma rede de Petri, denominado marcação, é uma distribuição de Ąchas sobre os lugares. Uma marcação é denotada por 𝑀, um vetor de tamanho 𝑚, onde 𝑚 é o número total de lugares. O 𝑝-ésimo componente de 𝑀, denotado por 𝑀(𝑝) é o número de Ąchas no lugar 𝑝 (MURATA, 1989). Aalst (1998a) representa uma marcação da seguinte maneira: 1𝑝1 + 2𝑝2 + 1𝑝3 + 0𝑝4 é o estado com uma Ącha em 𝑝1, duas Ąchas em 𝑝2, uma Ącha em 𝑝3 e nenhuma Ącha em 𝑝4. Esta mesma marcação pode ser equivalentemente representada por 𝑝1 + 2𝑝2 + 𝑝3.

Assim, dada uma rede de Petri 𝑃 𝑁 e uma marcação 𝑀1, Murata (1989) apresenta as seguintes notações:

a) 𝑀1

𝑡

⊗

⊃ 𝑀2: a transição 𝑡 é sensibilizada na marcação 𝑀1 e o disparo de 𝑡 resulta na marcação 𝑀2;

b) 𝑀1 ⊗⊃ 𝑀2: há uma transição 𝑡 tal que 𝑀1

𝑡 ⊗ ⊃ 𝑀2; c) 𝑀1 à ⊗

⊃ 𝑀𝑛: a sequência de disparo à = 𝑡1𝑡2𝑡3...𝑡𝑛⊗1 leva da marcação 𝑀1 para a marcação 𝑀𝑛, isto é, 𝑀1 𝑡1 ⊗⊃ 𝑀2 𝑡2 ⊗⊃ ... 𝑡n⊗1 ⊗⊗⊃ 𝑀𝑛.

Uma marcação 𝑀𝑛 é alcançável a partir de 𝑀1 (notação 𝑀1 ⊗⊃ 𝑀* 𝑛) se, e somente, se

existe uma sequência de disparo à = 𝑡1𝑡2𝑡3...𝑡𝑛⊗1 tal que 𝑀1

à

⊗

⊃ 𝑀𝑛 (MURATA, 1989).

Além disso, a notação (𝑃 𝑁, 𝑀) é utilizada para denotar uma rede de Petri 𝑃 𝑁 com uma marcação inicial M. Uma marcação 𝑀′ _{é alcançável a partir de (𝑃 𝑁, 𝑀) se, e somente} se, 𝑀 *

⊗

⊃ 𝑀′ _{(MURATA, 1989).}

De acordo com Aalst e Hee (2004), é importante considerar no contexto do gerencia- mento de workĆow redes de Petri de alto nível, que são extensões da rede de Petri clássica. Os autores destacam que as extensões mais importantes são as extensões de cor, tempo e de hierarquia. Na presente pesquisa são utilizadas somente as extensões de cor e tempo. Assim, na sequência são apresentadas noções básicas sobre a rede de Petri colorida e a rede de Petri t-temporal.

A rede de Petri colorida foi deĄnida por Jensen (1981). Uma rede de Petri colorida, de acordo com Aalst e Stahl (2011), é uma rede de Petri onde cada lugar possui um tipo, e cada Ącha possui um valor (isto é, uma cor) em conformidade com o tipo do lugar. De acordo com Valette e Cardoso (1997), as cores são adicionadas às Ąchas com o objetivo de diferenciá-las. Um arco em uma rede de Petri colorida pode possuir uma inscrição de arco, que é uma expressão com algumas variáveis que avaliam a um multiset Ű um multiset se assemelha a um conjunto comum, mas o mesmo elemento pode aparecer múltiplas vezes (AALST; STAHL, 2011). A cada lugar se associa o conjunto de cores das Ąchas que podem pertencer a este lugar e a cada transição se associa um conjunto de cores que corresponde às diferentes maneiras de disparar uma transição (VALETTE; CARDOSO, 1997). Além disso, uma transição pode possuir uma guarda, isto é, uma expressão booleana que condiciona o disparo da mesma (AALST; STAHL, 2011).

A deĄnição formal de rede de Petri Colorida, de acordo com Valette e Cardoso (1997), é apresentada na sequência.