Réseaux de Petri stochastiques à forme produit
Institution:
Paris 7Disciplines:
Directors:
Abstract EN:
The aim of this thesis is to characterise and to analyse stochastic Pétri nets which have a product-form steady-state distribution. The first contribution is the characterisation of a class of product-form Petri nets. We introduce the class of Π 2-nets for which a product-form steady-state distribution exists for every choice of transition rates. Next, we show that intersecting this class and the class of free-choice nets yields a classical class of product-form queueing networks: the Jackson networks. The second contribution consists of two effective methods to construct arbitrary Π 2-nets. One can either generate a Π 2-net from the empty net using a finite set of synthesising rules, or to directly modify an existing net. The third contribution is a characterisation of the Π 2-nets in term of complexity. We show that the reachability and liveness problems are PS PAC E-complete for 1-bounded Π 2-nets and that the coverability problem is EXPSPACE-complete for general Π 2-nets. Finally, we introduce the subclass of Π3-nets whose normalising constant can be efficiently computed using dynamic programming.
Abstract FR:
L'objectif de cette thèse est de caractériser et d'analyser les réseaux de Pétri stochastiques ayant une distribution stationnaire à forme produit. La première contribution est la caractérisation d'une classe de réseaux de Pétri à forme produit. On introduit la classe des Π2-nets pour lesquels une distribution stationnaire à forme produit existe pour tous les taux de transition, Ensuite, on montre que l'intersection de la classe des Π2-nets et de la classe des réseaux de Pétri à choix libres est une classe classique des réseaux de files d'attente à forme produit : les réseaux de Jackson. La deuxième contribution consiste en deux méthodes effectives pour créer des Π2-nets. La première méthode consiste à générer un Π2-net à partir du réseau vide en utilisant un ensemble de règles de synthèse. La deuxième méthode revient à ajouter des contraintes à un réseau existant afin de le transformer en un Π2-net. La troisième contribution est une caractérisation de la classe des Π2-nets en terme de complexité. On montre que les problèmes d'accessiblité et de vivacité pour les Π2-nets 1-bornés sont PSPACE-complets. Cependant, le problème de couverture pour les Π2-nets généraux est EXPSPACE-complet. La dernière contribution est l'introduction de la sous-classe des Π3-nets, pour lesquels la constante de normalisation peut être calculée efficacement par la programmation dynamique.