Optimisation et analyse probabiliste de systèmes à évènements discrets
Institution:
École normale supérieure (Lyon ; 1987-2009)Disciplines:
Directors:
Abstract EN:
This thesis deals with the study of discrete event systems. Three different models are considered. In the first part, we are interested in the trace groups. After giving a simple Möbius-like formula for the generating series of the trace groups, we show the existence and the algebraicity of the asymptotic growth rate of the height of the traces. The second part is devoted to timed free-choice nets, an important sub-class of Petri nets. We define the notion of throughput in those nets and study the variation of the throughput in function of the conflict resolution policies. First, we show how to compute the throughput, then we are interested in the policy that maximizes or minimizes the throughput. Finally, we give an efficient method to generate a marking according to its exact distribution in order to numerically evaluate the throughput. In the last part, we study the computation of performance guarantees in networks thanks to Network Calculus techniques. We show the stability of the ultimately pseudo-periodic functions with the operations of the Network Calculus and give algorithms to compute these functions. These techniques are then applied to the study of performance guarantees in graphs with turn prohibition.
Abstract FR:
L'objet de cette thèse est l'étude des performances dans les systèmes à évènements discrets. Trois modèles différents de ces systèmes sont étudiés. Dans une première partie, nous nous intéressons aux groupes de traces. Après avoir donné une formule simple, semblable à la formule de Möbius pour les monoïdes de traces, de la série génératrice des groupes de traces, nous montrons l'existence et l'algébricité du taux de croissance asymptotique de la hauteur des traces. Une deuxième partie de cette thèse est consacrée aux réseaux à choix libres temporisés, une sous-classe importante de réseaux de Petri. Nous définissons une notion de débit dans ces réseaux et étudions la variation du débit en fonction de la politique de résolution de conflits choisie. Tout d'abord, nous montrons comment calculer ce débit. Ensuite, nous nous intéressons aux politiques qui le maximisent ou le minimisent. Enfin, nous donnons une méthode efficace de simulation exacte du processus des marquages pour l'évaluation numérique du débit. Enfin, nous étudions le calcul des garanties de performances dans les réseaux à l'aide des techniques du Network Calculus. Nous montrons la stabilité des fonctions ultimement pseudo-périodiques par les opérations du network calculus et donnons des algorithmes pour le calcul de ces fonctions. Ces techniques sont ensuite appliquées à l'étude des garanties de performances dans les graphes avec angles interdits.