Submitted by Renata Lopes (renatasil82@gmail.com) on 2017-04-25T11:55:26Z No. of bitstreams: 1 wolmararaujoneto.pdf: 9045744 bytes, checksum: 685167b5aabc68d680681643c44b7a4e (MD5) / Approved for entry into archive by Adriana Oliveira (adriana.oliveira@ufjf.edu.br) on 2017-04-25T12:12:34Z (GMT) No. of bitstreams: 1 wolmararaujoneto.pdf: 9045744 bytes, checksum: 685167b5aabc68d680681643c44b7a4e (MD5) / Made available in DSpace on 2017-04-25T12:12:34Z (GMT). No. of bitstreams: 1 wolmararaujoneto.pdf: 9045744 bytes, checksum: 685167b5aabc68d680681643c44b7a4e (MD5) Previous issue date: 2014-08-25 / CNPq - Conselho Nacional de Desenvolvimento Científico e Tecnológico / A presente dissertação tem como objetivo principal desenvolver uma metodologia capaz de auxiliar no projeto e implementação de controles para sistemas a eventos discretos (SED) de forma a otimizar a modelagem, documentação e implantação da planta estudada. Para tanto a definição tradicional de autômato foi alterado para incluir um novo subconjunto de estados obrigatórios, isto é, estados que o sistema deve passar antes de chegar a um estado marcado. Seguindo a modelagem tradicional, cada subsistema é modelado através desta nova abordagem. Em uma segunda etapa, uma nova iteração de análise de cada subsistema é realizada para restringir situações indesejadas do sistema. Com esta fase finalizada os subsistemas são mesclados através de uma técnica tradicional de autômatos em paralelo. O sistema final resultante é apresentado a um otimizador, baseado em PROLOG, que busca a melhor sequência de eventos obedecendo a todas as restrições modeladas e termine no estado marcado informado pelo projeto. Este resultado fornece a Rede de Petri ideal do sistema e sua programação em GRAFCET. Tais métodos serão testados em componentes de um sistema de manufatura flexível real. / The present master thesis has as its main goal to develop a methodology able to assist in design and implementation of discrete event system (DES) controllers in order to optimize the modeling, documentation and deployment of plant in study. To do so the automaton traditional concept was changed to include a new subset of mandatory states, i.e. states that the system should pass before reach a marked state. Following the traditional modeling, each subsystem is modeled using this new approach. In a second step, a new iteration of analysis of each subsystem is performed to restrain system’s unwanted situations. At the end of this step the subsystems are composed by a traditional parallel automatons technique. The resulting system is presented to an optimizer, based in PROLOG, which searches the best event sequence obeying to all modeled restrictions and ends in the marked state defined in design. This result provides the ideal Petri Net of the system and its GRAFCET programming. Such methods will be tested in a flexible real manufacturing system.

Les travaux présentés dans ce mémoire de thèse représentent une contribution au problème de diagnostic des Systèmes à Evénements Discrets (SEDs). L'objectif de ce travail est dans un premier temps une proposition d'une démarche de diagnostic en exploitant l'aspect temporel caractérisant l'occurrence des événements. Pour cela, le système est modélisé par des graphes temporels appartenant au formalisme des automates temporisés. L'approche est conçue selon une architecture décentralisée afin d'éviter toute explosion combinatoire dans la construction des modèles. Elle a permis la détection et localisation des défauts abruptes survenant sur les équipements notamment en combinant des conditions d'autorisation d'événements et des fonctions de non-occurrence d'événements.Dans un second temps, les défauts graduels issus du process sont considérés. Pour cela, les contraintes temporelles exprimant les dates d'occurrence des événements dans les Templates et les Chroniques sont modélisées par des distributions de probabilités (DPs). Celles-ci sont utilisées afin de caractériser un fonctionnement normal, dégradé ou défaillant de chaque sous-système avec un certain degré de certitude. Cette identification du fonctionnement est représentée par la valeur d'un indicateur de dégradation. / The work presented in this thesis represents a contribution to the problem of diagnosis in discrete event systems (DES). The objective of our work consists in a proposition for a diagnostic approach by exploiting the temporal aspect which characterizing the occurrence of events. For this, the system is modeled by temporal graphs belonging to the timed automata formwork. The approach is designed according to the decentralized architecture to avoid any combinatorial explosion in the construction of the models. It has allowed the detection and isolation of abrupt faults occurring on equipment by combining the enablement conditions of events and the Boolean functions for the non-occurrence of events.Secondly, gradual faults coming from the process its self are considerate. For this, time constraints expressing the dates of occurrence of events in the Templates and Chronicles are modeled by probability distributions (PDs). These are used to characterize normal, degraded or failed functioning of each subsystem with a degree of certainty. Identification of this functioning mode is represented by the value of a degradation indicator.

Les travaux effectués durant cette thèse portent sur la spécification, l'analyse et l'application de systèmes a événements discrets pour la modélisation de processus biologiques stochastiques en biologie des systèmes. Le point de départ de cette thèse est le langage de modélisation AltaRica, que nous étendons afin de permettre de décrire des événements temporisés selon des distributions de probabilités quelconques (dégénérées, discrètes et continues). Nous définissons ensuite la sémantique de ce langage en terme d'automates de mode stochastiques et présentons trois opérations de compositions permettant de modéliser des systèmes hiérarchiques avec événements synchronisés et partage de valeurs via un mécanisme de connexion. Nous donnons ensuite au automates de mode stochastiques une sémantique en termes de systèmes de transitions dont les transitions sont étiquetées par des distributions de probabilités et des probabilités de transitions instantanées. Nous caractérisons ensuite 6 sous classes de ces systèmes de transitions et donnons pour chacune de ces classes un algorithme de simulation ainsi qu'une mesure de probabilité sur les chemins finis. Nous montrons que pour certaines de ces classes, notre sémantique est conforme avec les mesures de probabilité de chemin usuellement associées aux chaînes de Markov a temps discret, a temps continu et aux processus semi-Markoviens généralisés. Nous abordons ensuite le problème de la réutilisation de modèles continus existant dans un système discret. Nous donnons une méthode d'abstraction permettant de représenter un ensemble de trajectoires bornées ou non d'un modèle continu sous forme d'un système de transition stochastique fini. A travers des exemples tirés de la littérature, nous montrons que notre abstraction préserve les propriétés "qualitatives" (par exemple oscillations, hystérie) des modèles continus et qu'une comparaison entre trajectoires basée sur leurs représentations en termes de systèmes de transitions permet de regrouper les trajectoires en fonction de comportements qualitatifs plus fins que ceux permis par la théorie des bifurcations. Finalement, nous étudions a l'aide de ces modèles des processus liés a la division cellulaire chez les levures. En particulier, nous définissons un modèle pour le vieillissement cellulaire dans une population de levure où le comportement individuel d'une cellule est régi par une équation différentielle ordinaire et où le processus de division est régi par un système de transition. Nous montrons a l'aide de ce modèle que la survie d'une population de levure de type Schizosaccharomyces Pombe, qui se divisent par une fission médiane, n'est possible que grâce a un mécanisme de distribution non symétrique des dégâts oxydatifs entre la progéniture et la cellule souche. Cette hypothèse fut validée expérimentalement lors d'une collaboration avec le laboratoire de micro-biologie de Göteborg. / A general goal of systems biology is to acquire a detailed understanding of the dynamics of living systems by relating functional properties of whole systems with the interactions of their constituents. Often this goal is tackled through computer simulation. A number of different formalisms are currently used to construct numerical representations of biological systems, and a certain wealth of models is proposed using ad hoc methods. There arises an interesting question of to what extent these models can be reused and composed, together or in a larger framework. In this thesis, we propose BioRica as a means to circumvent the difficulty of incorporating disparate approaches in the same modeling study. BioRica is an extension of the AltaRica specification language to describe hierarchical non-deterministic General Semi-Markov processes. We first extend the syntax and automata semantics of AltaRica in order to account for stochastic labeling. We then provide a semantics to BioRica programs in terms of stochastic transition systems, that are transition systems with stochastic labeling. We then develop numerical methods to symbolically compute the probability of a given finite path in a stochastic transition systems. We then define algorithms and rules to compile a BioRica system into a stand alone C++ simulator that simulates the underlying stochastic process. We also present language extensions that enables the modeler to include into a BioRica hierarchical systems nodes that use numerical libraries (e.g. Mathematica, Matlab, GSL). Such nodes can be used to perform numerical integration or flux balance analysis during discrete event simulation. We then consider the problem of using models with uncertain parameter values. Quantitative models in Systems Biology depend on a large number of free parameters, whose values completely determine behavior of models. Some range of parameter values produce similar system dynamics, making it possible to define general trends for trajectories of the system (e.g. oscillating behavior) for some parameter values. In this work, we defined an automata-based formalism to describe the qualitative behavior of systems’ dynamics. Qualitative behaviors are represented by finite transition systems whose states contain predicate valuation and whose transitions are labeled by probabilistic delays. We provide algorithms to automatically build such automata representation by using random sampling over the parameter space and algorithms to compare and cluster the resulting qualitative transition system. Finally, we validate our approach by studying a rejuvenation effect in yeasts cells population by using a hierarchical population model defined in BioRica. Models of ageing for yeast cells aim to provide insight into the general biological processes of ageing. For this study, we used the BioRica framework to generate a hierarchical simulation tool that allows dynamic creation of entities during simulation. The predictions of our hierarchical mathematical model has been validated experimentally by the micro-biology laboratory of Gothenburg

O presente estudo apresenta a reorganização do projeto de trabalho de uma indústria produtora de equipamentos para compressão de GNV, apoiada pelo uso de sistemas a eventos discretos (SED). A empresa em questão, pioneira neste segmento na América Latina, viveu um súbito aumento na demanda de mercado que expôs fragilidades em seu sistema logístico. Problemas associados ao planejamento e controle de estoque e fluxo de materiais tornaram-se evidentes e deveriam ser resolvidos para que não prejudicassem o fluxo de vendas da empresa. Devido a complexidade existente no projeto produtivo, a simulação foi considerada como a maneira mais segura de planejar alterações nas práticas administrativas e produtivas, sem interferir na rotina da empresa. A modelagem realizada neste trabalho foi feita a partir da construção de uma cadeia de valor para o processo produtivo.Tal abordagem permitiu identificar diversos fatores que contribuíam diretamente à falta de eficiência da empresa tais como a ausência de um sistema logístico estruturado: interligação deficiente entre determinados setores administrativos e a manufatura, formação de estoques paralelos, perda excessiva por manuseio, retrabalho ou uso incorreto de componentes (hidden factory). A modelagem e a análise das propriedades dos modelos foram validadas por meio de um sistema de gestão integralizado (ERP) trabalhando com base em dados reais da empresa estudada. O estudo revelou oportunidades de melhoria baseado na reorganização da seqüência de fabricação e de abastecimento de materiais, aumento de produtividade através de realocação da mão-de-obra, organização do local de trabalho e padronização das atividades. As melhorias identificadas no estudo exploratório e na simulação foram consolidadas formando um sistema de gestão customizado para a empresa objeto do estudo. / This study presents the reorganization of the project work of an industry producing equipment for compressed natural gas (CNG), supported by the use of discrete event systems (DES). The company in question, a pioneer in this segment in Latin America, experienced a surge in market demand that has exposed weaknesses in their logistics system. Problems associated with planning and inventory control and material flow have become evident and should be resolved not to damage the flow of the companys sales. Because of the complexities that exist in productive project, the simulation was considered the safest way to plan changes in administrative and productive practices, without interfering with the routine. The modeling performed in this work was done from the construction of a value chain for the production process. This approach has identified several factors that contributed directly to the inefficiency of the company such as the absence of a structured logistics system: poor interconnection between certain administrative sectors and the manufacture, stockpiling, parallel loss by excessive handling, rework or incorrect use of components ("hidden factory"). The modeling and analysis of the properties of the models were validated by means of a management system (ERP) work based on real data of the studied company. The study revealed opportunities for improvement based on the reorganization of the sequence of manufacturing and supply materials, increased productivity through reallocation of labor, work, workplace organization and standardization activities. The improvements identified in the exploratory study and simulation were consolidated to form a customized management system to the company object of study.

Les systèmes d'alarmes jouent un rôle critique dans la bonne exploitation des installations industrielles modernes. Cependant, dans la plupart de ces systèmes, les alarmes ne sont pas toujours traitées correctement par les opérateurs car il y a régulièrement beaucoup trop d’alarmes à gérer, notamment lors des avalanches d’alarmes. Pour réduire le flux d'alarmes, notre approche consiste à détecter des redondances entre alarmes qui pourraient être supprimées. Pour atteindre cet objectif, nous recherchons dans un premier temps les adjacences fréquentes entre les alarmes contenues dans un historique. Ceci est réalisé en adaptant l’algorithme de recherche de motifs fréquents AprioriAll. Nous explorons également une seconde méthode consistant à trouver des précédences systématiques. Pour les découvrir, nous identifions les relations de domination et de mutuelle dépendance contenues dans l’historique des alarmes. Pour faciliter l’analyse experte, les relations découvertes sont traduites sous la forme d’un réseau de Pétri.Ces deux méthodes sont ensuite confrontées à un historique d’alarmes industriel fourni par General Electric. Les résultats obtenus montrent que nos deux méthodes permettent une réduction globale du flux d'alarmes qui est plus importante durant les avalanches. / Alarm systems play an important role for the safe and efficient operation of modern industrial plants. However, in most of industrial alarm systems, alarm flows cannot always be correctly managed by the operators as they often turn into alarm floods, sequences of numerous alarms occurring in a short period of time. To reduce the alarm flows, this report focuses on detection of redundant alarms that could be removed. This objective is met by, first, looking for frequent adjacency in the alarm log. To identify them, the frequent pattern mining algorithm AprioriAll is adapted. Another way to find potentially redundant alarms is to look for systematic predecessors. To discover them, dominations and mutual dependencies contained in the alarm log are identified. To ease this analysis, the discovered relations are depicted in the form of Petri nets.Both those methods are then tested against an industrial alarm log made available by General Electric. The results show that both methods allow a reduction of the alarm flow, with the biggest reduction being during alarm floods.

<p>A decentralized discrete-event system (DES) consists of supervisors that are physically distributed. Co-observability is one of the necessary and sufficient conditions for the existence of a decentralized supervisors that correctly solve the control problem. In this thesis we present a state-based definition of co-observability and introduce algorithms for its verification. Existing algorithms for the verification of co-observability do not scale well, especially when the system is composed of many components. We show that the implementation of our state-based definition leads to more efficient algorithms.</p> <p>We present a set of algorithms that use an existing structure for the verification of state-based co-observability (SB Co-observability). A computational complexity analysis of the algorithms show that the state-based implementation of algorithms result in quadratic complexity. Further improvements come from using a more compact way of representing finite-state machines namely Binary Decision Diagrams (BDD).</p> / Master of Science (MSc)

Le travail présenté s'inscrit dans le contexte de la théorie des systèmes linéaires dans les dioïdes. La motivation initiale de cette étude a été de contribuer à l'analyse et la commande de systèmes linéaires dans max-plus en utilisant spécifiquement une approche géométrique. La contribution de cette thèse est centrée sur deux problèmes. La première partie est dédiée à l'étude de la relation entre les notions d'invariance contrôlée et d'invariance contrôlée par retour d'état dynamique dans un semi-anneau. Cette relation permet de montrer l'équivalence de ces deux notions. La deuxième partie concerne un problème original dans la théorie des systèmes linéaires dans max-plus, il s'agit de la synthèse d'une loi de commande par retour d'état, qui permette de satisfaire un ensemble de spécifications exprimées sous la forme de restrictions sur l'état du système, avec une approche géométrique. Il s'agit plus précisément de commander des systèmes à événements discrets décrits par un modèle linéaire dans max-plus. Nous définissons et caractérisons l'ensemble des conditions initiales admissibles, lesquelles sont à l'origine de solutions non décroissantes. Les restrictions temporelles imposées à l'espace d'état du système sont décrites par le semi-module défini par l'image de l'étoile de Kleene de la matrice associée aux restrictions temporelles. Les propriétés géométriques de ce semi-module permettant de garantir que l'évolution du système en boucle fermée satisfasse les restrictions sont étudiées. Des conditions suffisantes concernant l'existence d'une loi de commande causale par retour d'état statique sont présentées. Le calcul des lois de commande causales est également présenté. Pour illustrer l'application de cette approche, deux problèmes de commande sont présentés. / This work is in the context of the theory of linear Systems in the dioids. The initial motivation of this study was to contribute to the analysis and control of max-plus linear systems, specifically using a geometric approach. The contribution of this thesis focuses on two issues. The first part is dedicated to study of the relationship between the concepts of controlled invariance and dynamic state feedback controlled invariance in a semi-ring. This relationship allows us to show the equivalence of these two concepts. The second part relates to a new problem in the theory of max-plus linear systems, it is the synthesis, with a geometric approach, of a static state feedback control law, in order to satisfy a set of specifications that apply to the state space of the system. This is specifically to control of discrete event systems described by a linear model in max-plus. We define and characterize the set of admissible initial conditions, which are the cause of non-decreasing solutions. Temporal restrictions on the system state space are described by the semi-module defined by the image of the Kleene star of the matrix associated with time restrictions. The geometric properties of this semi-module are studied. Sufficient conditions for the existence of a causal control law by static feedback are presented. Calculating causal control laws is also presented. To illustrate the application of this approach, two control problems are presented.

Les systèmes de contrôle-commande industriels (Industrial Control System, ICS) sont des infrastructures constituées par un ensemble de calculateurs industriels reliés en réseau et permettant de contrôler un système physique. Ils assurent le pilotage de réseaux électriques (Smart Grid), de systèmes de production, de transports, de santé ou encore de systèmes d’armes. Pensés avant tout pour assurer productivité et respect de la mission dans un environnement non malveillant, les ICS sont, depuis le 21ème siècle, de plus en plus vulnérables aux attaques (Stuxnet, Industroyer, Triton, …) notamment avec l’arrivée de l’industrie 4.0. De nombreuses études ont contribué à sécuriser les ICS avec des approches issues du domaine de la sécurité (cryptographie, IDS, etc…) mais qui ne tiennent pas compte du comportement du système physique et donc des conséquences de l’acte de malveillance en lui-même. Ainsi, une sécurisation se limitant exclusivement à l’analyse des informations qui transitent sur un réseau industriel n’est pas suffisante. Notre approche amène un changement de paradigme dans les mécanismes de détection en y intégrant la modélisation du comportement du système cyber-physique.Cette thèse propose des mécanismes de détection d’attaques en se positionnant au plus proche de la physique. Ils analysent les données échangées entre le système de contrôle-commande et le système physique, et filtrent les échanges au travers de modèles déterministes qui représentent le comportement du système physique soumis à des lois de commande. A cet effet, une méthodologie de conception a été proposée dans laquelle l’ensemble des ordres est identifié afin de détecter les attaques brutales. Pour faire face aux autres attaques, en particulier celles plus sournoises, comme les attaques par séquences, nous proposons une stratégie de détection complémentaire permettant d’estimer l’occurrence d’une attaque avant que ses conséquences ne soient destructives. A cet effet, nous avons développé des concepts de distance d’un état caractérisé comme critique auquel nous avons adjoint un second mécanisme dit de trajectoire dans le temps permettant de caractériser une intention de nuire.L’approche proposée hybride ainsi deux techniques orientées sécurité (sonde IDS) et sûreté (approche filtre) pour proposer une stratégie de détection basée sur quatre mécanismes lié :• A la détection de contexte : basé sur l’état courant de l’ICS, un ordre émis par l’API peut être bloqué s’il conduit vers un état critique (attaque brutale).• Aux contraintes combinatoires (attaque par séquences) : vérifiées par les concepts de distance et de trajectoire (évolution de la distance).• Aux contraintes temporelles (attaque temporelle) : vérifiées par des fenêtres temporelles sur l’apparition d’évènements et d’indicateurs surveillant la durée moyenne d’exécution.• Aux sur-sollicitations basées sur un indicateur surveillant les commandes envoyées afin de prévenir un vieillissement prématuré (attaque sur les équipements).L’approche proposée a été appliquée sur différents exemples de simulation et sur une plateforme industrielle réelle où la stratégie de détection a montré son efficacité face à différents profils d’attaquant. / Industrial Control Systems (ICSs) are infrastructures composed by several industrial devices connected to a network and used to control a physical system. They control electrical power grid (Smart Grid), production systems (e.g. chemical and manufacturing industries), transport (e.g. trains, aircrafts and autonomous vehicles), health and weapon systems. Designed to ensure productivity and respect safety in a non-malicious environment, the ICSs are, since the 21st century, increasingly vulnerable to attacks (e.g. Stuxnet, Industroyer, Triton) especially with the emergence of the industry 4.0. Several studies contributed to secure the ICS with approaches from the security field (e.g. cryptography, IDS) which do not take into account the behavior of the physical system and therefore the consequences of the malicious act. Thus, a security approach limited exclusively to the analysis of information exchanged by industrial network is not sufficient. Our approach creates a paradigm shift in detection mechanisms by integrating the behavioral modeling of the cyber-physical system.This thesis proposes detection mechanisms of attacks by locating detection closer to physical system. They analyze the data exchanged between the control system and the physical system, and filter the exchanges through deterministic models that represent the behavior of the physical system controlled by control laws. For this purpose, a design methodology has been proposed in which all actions are identified in order to instantly detect brutal attacks. To deal with other attacks, especially the more sneaky, such as sequential attacks, we propose a complementary detection strategy to estimate the occurrence of an attack before its consequences are destructive. To this end, we have developed the concepts of distance of a state identified as critical to which we have added a second mechanism called trajectory which leads to a temporal notion that characterize an intention to harm.As part of this thesis, the proposed approach combines two techniques oriented security (IDS probe) and safety (filter approach) to propose a detection strategy based on four mechanisms related to:• Context detection: based on the current state of the system, an order sent by the PLC can be blocked by the control filter if it leads to a critical state (brutal attack).• Combinatorial constraints (sequential attack): verified by the concepts of distance (risk indicator for the current state) and trajectory (indicator of the intention to harm by studying the evolution of the distance on a sequence).• Temporal constraints (temporal attack): verified by time windows on the appearance of events and an indicator monitoring the average duration of execution.• Over-solicitation monitoring mechanism: based on an indicator monitoring orders sent to the actuators to prevent premature ageing of the production equipment (attack on the equipment).The proposed approach has been applied to various simulation examples and an industrial platform where the detection strategy has shown its effectiveness against different scenarios corresponding to attacker profiles.

Le travail présenté dans cette thèse constitue une contribution originale à lamodélisation et à l'analyse de performances des systèmes de vélos en libre-service. De nombreuses villes en Europe ont suscité un intérêt considérable et un engouement à l'égard de ce nouveau mode de transport écologique (Vélib' à Paris, Vélov'v à Lyon, Bicing à Barcelone, ...) et dont les progrès technologiques ne cessent de les faire émerger dans les quatre coins dumonde. Contrairement aux systèmes de transport traditionnels, très peu d'étudesfondamentales ont été menées et pourtant, de nombreuses questions émergent, la principale étant celle d'un rééquilibrage (régulation) de la distribution de vélos dans les différentes stations afin de satisfaire au mieux les demandes des usagers. C'est dans ce cadre que s'inscrit cette thèse de doctorat portant sur la modélisation, l'analyse et l'évaluation de performances de ce mode de transport en libre service. Ce travail, basé sur les réseaux de Petri, est d'une aide précieuse pour la mise en oeuvre, l'exploitation et la régulation de ce type de systèmes.La complexité dynamique de tels systèmes, perçus comme des systèmes à événements discrets, nous a conduit au développement d'une approche à base d'une classe particulière de réseaux de Petri stochastiques ayant des arcs à poids variables pertinents aussi bien pour l'analyse que pour la simulation. Un ensemble de modèles et de méthodes d'analyse associées sont développés en vue de leur régulation, en prenant en compte différents paramètres de décision qui les caractérisent notamment le nombre de stations, la capacité de chaque station, les seuils de régulation, la capacité des véhicules de régulation, le type et/ou la fréquence de régulation choisi (périodique ou continue), …. En plus d'être paramétrables, les modèles proposés permettent d'étudier plusieurs configurations en fonction de différents modes de fonctionnement possibles (mode sans régulation, mode avec régulation, mode dynamique, mode statique, etc). La présentation de cette thèse comporte plusieurs illustrations et applicationspermettant d'aider le lecteur à la compréhension du travail développé.A notre connaissance, il s'agit d'un premier travail du genre dans la littérature sur les réseaux de Petri et plus généralement, l'un des premiers sur les systèmes de vélos en libre-service. / Public Bicycle-Sharing Systems (PBSS) have been appearing in more and more cities around the world in the last few years. Although their apparent success as an alternative form of public transportation mode, there are major challenges confronting the operators while few scientific works are available to support such complex dynamical systems to influence their economic viability and operational efficiency. One of the most crucial factors for the success of a PBS system is its ability to ensure that bicycles are available for pick up and vacant berths available for bicycle drop off at every station. In this thesis, we develop an original discrete event approach for modelling and performance evaluation of public bicycle-sharing systems by using Petri nets with time, inhibitor arcs and variable arc weights.

Cette thèse porte sur le diagnostic des systèmes à événements discrets modélisés par des Réseaux de Petri labellisés (RdP-L). Les problèmes de diagnostic monolithique et de diagnostic modulaire sont abordés. Des contributions sont proposées pour résoudre les problèmes d'explosion combinatoire et de complexité de calcul. Dans le cadre de l'analyse de la diagnosticabilité monolithique, certaines règles de réduction sont proposées comme un complément pour la plupart des techniques existantes de l'analyse de la diagnosticabilité, qui simplifient le modèle RdP-L tout en préservant sa propriété de diagnosticabilité. Pour un RdP-L sauf et vivant, une nouvelle condition suffisante pour la diagnosticabilité est proposée. Pour un RdR-L borné et non bloquant après l'occurrence d'une faute, l'analyse à-la-volée est améliorée en utilisant la notion d'explications minimales qui permettent de compacter l'espace d'état ; et en utilisant des T-semiflots pour trouver rapidement un cycle indéterminé. Une analyse à-la-volée utilisant Verifier Nets (VN) est proposée pour analyser à la fois les RdP-L bornés et non-bornés, ce qui permet d'obtenir un compromis entre efficacité du calcul et limitation des explosions combinatoires. Dans le cadre de l'analyse de la diagnosticabilité modulaire, une nouvelle approche est proposée pour les RdP-Ls décomposés. Les règles de réduction, qui préservent la propriété de la diagnosticabilité modulaire, sont appliquées pour simplifier le modèle initial. La diagnosticabilité locale est analysée en construisant le VN et le Graphe d'Accessibilité Modifié (MAG) du modèle local. La diagnosticabilité modulaire est vérifiée en construisant la composition parallèle du MAG et des graphes d'accessibilités d'autres modules du système. La complexité de calcul est inférieure à celles des autre approches dans la littérature. D'autre part, l'explosion combinatoire est également réduite en utilisant la technique de ε-réduction / This thesis deals with fault diagnosis of discrete event systems modeled by labeled Petri nets (LPN). The monolithic diagnosability and modular diagnosability issues are addressed. The contributions are proposed to reduce the combinatorial explosion and the computational complexity problems. Regarding monolithic diagnosability analysis, some reduction rules are proposed as a complement for most diagnosability techniques, which simplify the LPN model and preserve the diagnosability property. For a safe and live LPN, a new sufficient condition for diagnosability is proposed. For a bounded LPN that does not deadlock after a fault, the on-the-fly diagnosability analysis is improved by using minimal explanations to compact the state space; and by using T-invariants, to find quickly an indeterminate cycle. An on-the-fly diagnosability analysis using Verifier Nets (VN) is proposed to analyze both bounded and unbounded LPN, which achieves a compromise between computation efficiency and combinatorial explosion limitation. Regarding modular diagnosability analysis, a new approach is proposed for decomposed LPNs model. Reduction rules, that preserve the modular diagnosability property, are applied to simplify the model. The local diagnosability is analyzed by building the VN and the Modified Reachability Graph (MRG) of the local model. The modular diagnosability is verified by building the parallel composition of the MRG and the reachability graphs of other modules of the system. We prove in this study that the computational complexity of our approach is lower than existing approaches of literature. The combinatorial explosion is also reduced by using the ε -reduction technique.