Academic literature on the topic 'Timed Petri Net'

<p>Embedded systems are used in many technical products of today. The tendency also points to the fact that they are in many ways becoming more and more complex as technology advances. Systems like advanced avionics, air bags, ABS brakes or any real-time embedded system requires reliability, correctness and timeliness. This puts hard pressure on designers, analyzers and developers. The need for high performance and non failing systems has therefore led to a growing interest in modeling and verification of component-based embedded systems in order to reduce costs and simplify design and development. The solution proposed by the Embedded Systems Lab at Linköping University is the modeling language PRES+, Petri Net based Representation for Embedded Systems.</p><p>PRES+ models are then translated into timed automata, TA, which is used by the UPPAAL verification tool. To be able to verify timing properties the translated TA model must be instrumented with certain timers, called clocks. These clocks must be reset in a manner reflected by the property to be verified.</p><p>This thesis will provide a solution to the problem and also give the reader necessary information in order to understand the theoretical background needed. The thesis will also show the reader the importance of modeling and time verification in the development of embedded systems. A simple example is used to describe and visualize the benefit regarding real-time embedded systems as well as the importance of the ability to verify these systems.</p><p>The conclusion drawn stresses the fact that high development costs, possible gain of human lives and the problems in developing complex systems only emphasize the need for easy to handle and intuitive verification methods.</p>

Au cours des dernières décennies, la complexité croissante des systèmes de production et de leur commande a rendu crucial le besoin d’utiliser les méthodes formelles pour faire face aux problèmes relatifs au contrôle, à la fiabilité, au diagnostic des fautes et à l’utilisation optimale des ressources dans les installations de production. Cela concerne en particulier les systèmes automatisés de production (SAP), caractérisés par des cycles technologiques complexes qui doivent s’adapter à des conditions changeantes. Les SAP modernes sont des sous-systèmes interconnectés tels que des machines à commande numérique, des stations d'assemblage , des véhicules guidés automatisés (AGV), des cellules robotisées, des convoyeurs et des systèmes de contrôle par ordinateur. Les fabricants utilisent des machines automatisées et des contrôleurs pour assurer des produits de qualité plus rapidement et plus efficacement. Aussi, ces systèmes automatisés peuvent fournir des informations essentielles pour aider les gestionnaires à prendre les bonnes décisions. Cependant, en raison de la grande flexibilité des SAP, des défaillances telles qu’un mauvais assemblage ou le dépôt d’une pièce dans un tampon inapproprié peuvent se produire lors du fonctionnement du système. De tels dysfonctionnements diminuent la productivité du système générant ainsi des pertes économiques et des effets perturbateurs sur le système. En conséquence, le problème de l’optimisation des performances des SAP est impératif.Cette thèse se focalise sur l’évaluation et l’optimisation des performances des systèmes de production automatisés via le modèle des réseaux de Pétri temporisés<br>In the last decades, there has been a constant increase in the awareness of company management about the importance of formal techniques in industrial settings to address problems related to monitoring and reliability, fault diagnosis, and optimal use of resources, during the management of plants. Of particular relevance in this setting are the so-called Automated Manufacturing Systems (AMSs), which are characterized by complex technological cycles that must adapt to changing demands. Modern AMSs are interconnected subsystems such as numerically controlled machines, assembly stations, automated guided vehicles, robots, conveyors and computer control systems. Manufacturers are using automated machines and controls to produce quality products faster and more efficiently. Meanwhile, these automated systems can provide critical information to help managers make good business decisions. However, due to the high flexibility of AMSs, failures such as a wrong assembly or a part put in a wrong buffer may happen during the operation of the system. Such failures may decrease the productivity of the system which has an economical consequence and can cause a series of disturbing issues. As a result, the performance optimization in AMSs are imperative. This thesis focuses on the performance evaluation and performance optimization of automated manufacturing systems using timed Petri nets models

Para obtener una ventaja competitiva en el mercado global, los fabricantes tienen que adaptarse rápidamente sus sistemas para responder a las fluctuantes demandas de los clientes en virtud de factores de servicio de alta calidad. La alta inversión de capital en los sistemas de fabricación flexible (SFFs), junto con los desafíos de las condiciones de mercado que cambian rápidamente se ha convertido en esencial la utilización eficiente de los recursos. Para maximizar los beneficios de un SFF, se necesita una implantación de técnicas de programación e planificación adecuadas para aprovechar plenamente las flexibilidades de fabricación. El objetivo global de esta tesis es establecer un marco de programación basado en el modelado de redes de Petri coloreadas temporales (RdPCT) para optimizar el rendimiento de los SFF mediante el desarrollo de herramientas y métodos de búsqueda eficientes basados en el análisis del espacio de estados (EdE). El análisis del espacio del estado es una herramienta potente que se puede utilizar para automatizar la actividad de toma de decisiones en problemas de programación mediante el seguimiento de todos los posibles comportamientos del sistema modelado. Sin embargo, adolece del problema de explosión de espacio de estado debido a la complejidad computacional de los problemas de programación de la producción en SFFs. Lo que ha limitado su aplicabilidad a problemas de tamaño pequeño. En la metodología de la programación propuesta, la generación de un plan de producción óptimo consiste en la construcción y el recorrido del espacio de estados con un algoritmo de búsqueda. Además, se requiere un simulador para la ejecución del modelo de RdPCT. Es muy natural utilizar el gráfico algoritmos de búsqueda ya que el método de análisis subyacente se basa en el EdE. La estrategia de búsqueda gráfica es una técnica interdisciplinaria que atraviesa los campos de la inteligencia artificial (IA), la investigación operativa (OR), e Informática. Esta tesis se centra en los métodos de búsqueda heurística basados en IA que se utilizan para simular solamente los mejores escenarios (como un problema de búsqueda del camino más corto). En este método, la exploración de los EdE son guiados con funciones heurísticas que se basan en el conocimiento de los planes de producción. La contribución de esta tesis es cuádruple. La primera ofrece la plataforma en que se implementan las otras tres contribuciones: una herramienta para soporte de decisión automatizada y de uso especial llamado TIMed State space Performance Analysis Tool (TIMSPAT). En segundo lugar, se desarrolló un enfoque de memoria eficiente para aliviar el problema de escalabilidad que aparece en la exploración de EdE de problemas de programación FMS. En tercer lugar, se presenta dos algoritmos de búsqueda heurística a cualquier hora, desarrollados para superar las desventajas de los algoritmos de búsqueda heurística convencionales. Finalmente, la última contribución presenta un enfoque basado en RdPCT a la programación simultánea de máquinas y vehículos guiados automáticamente (AGV) con enrutamiento libre de conflictos.<br>To gain competitive advantage in the global market, manufacturers have to quickly adapt their systems to respond to fluctuating customer demands under high-quality service factors. The high capital investment in flexible manufacturing systems (FMSs) together with the challenges of the rapidly changing market conditions has made efficient resource utilization become essential. To maximize the benefits of an FMS, appropriate scheduling techniques must be put in place to fully exploit the manufacturing flexibilities. The overall objective of this thesis is to establish a scheduling framework based on timed colored Petri net (TCPN) modeling for optimizing the performance of FMSs through the development of tools and efficient search methods based on the reachability graph (or state space) analysis. In the proposed TCPN-based scheduling methodology, the generation of an optimal production schedule involves the construction and traversal of the state space with a search algorithm. Also, a simulator is required for executing the TCPN model. It is quite natural to use graph search algorithms since the underlying analysis method relies on the reachability graph. Graph search strategy is an interdisciplinary technique that spans across the fields of Artificial intelligence (AI), Operations research (OR), and Computer science. This thesis focuses on AI-based heuristic search methods used in simulating only the best scenarios (as a shortest-path search problem). In this method, the exploration of reachability graphs are guided with heuristic functions that rely on the knowledge of the production plans. The contribution of this thesis is fourfold. The first provides the platform called TIMSPAT in which the other three contributions are implemented. Because of the complex data structure, TCPN-based scheduling using reachability graph analysis has been merely looked at in the literature. Thanks to the common data structure of the heuristic search methods, TIMSPAT is capable of incorporating different search algorithms in a single executable tool. So far, nine algorithms have been implemented, which includes the search algorithms proposed in this thesis and those by other authors. Second, a memory-efficient approach is developed to alleviate the scalability problem that appears in the state space exploration of FMS scheduling problems. The approach tackles the research questions: Is it necessary to store all the generated states to guarantee an optimal solution without revisiting states? and how can one reduce the number of states to be stored so that larger problems can be solved without forgoing optimality? It assumes that the state space graphs of a system with increasing problem size may contain repetitive patterns while the underlying model structure remains as constant as possible. The proposed solution is based on the notion that the structural behavior captured in the state space of a solvable smaller problem size can be extended to explore a larger size if the two problems share a certain kind of similarity. The third contribution presents two anytime heuristic search algorithms developed to overcome the drawbacks of conventional heuristic search algorithms. The first anytime algorithm adapts and improves an existing anytime algorithm to TCPN-based scheduling, while the second proposes a new algorithm that combines two heuristic search algorithms making them anytime for deadlock-free scheduling. The algorithms are suitable for both off-line and on-line scheduling purposes due to their effectiveness in adapting to different CPU constraints. The last contribution presents a TCPN-based approach to the simultaneous scheduling of machines and automated guided vehicles (AGVs) with conflict-free routing. Unlike the existing approaches that employ a decomposition framework, the entire scheduling problem is described in a single model. Two simultaneous scheduling models are proposed and evaluated using an event-driven vehicle assignment solution as opposed to the traditional dispatching rules.

Dans cette thèse, nous nous intéressons à l’optimisation des ressources consommées par un circuit implémentant une loi de commande pour la charge de véhicules électriques sur FPGA. Tout d’abord, nous proposons une nouvelle solution au problème de la synthèse de pipeline minimisant les bascules et garantissant une fréquence minimale de fonctionnement. En se basant sur cette même approche, nous sommes capable de construire un pipeline permettant le pliage (ou multiplexage temporel) du circuit, c’est-à-dire qui permet la fusion de portions du circuit identiques en séquençant leur accès. Ainsi, les ressources consommées sont réduites à la fois en nombre de bascule et en nombre d’unités logiques. Notre approche est basée sur un modèle de Réseau de Petri Temporisé avec des transitions retardables, pouvant rater leur date de tir, et une action spécifique appelée reset qui réinitialise les horloges de toutes les transitions. Ce modèle s’avère équivalent à un automate à une horloge. Une surclasse de ce modèle, les Réseaux de Petri Temporisés avec transitions retardables (sans reset), s’avère être incomparable, en terme d’expressivité en sémantique faible, avec les classes de Réseaux de Petri Temporels ou Temporisés en temps dense ou discret. Enfin, une exploration symbolique de ce modèle ainsi que des résultats de complexité théorique et pratique sont étudiés<br>In this thesis, we are interested in the optimization of the resources consumed by a circuit implementing a control law for the charging of electric vehicles on FPGA. First, we propose a new solution to the pipeline synthesis problem that minimizes the number of flip-flops and guarantees a minimum operating frequency. Based on this same approach, we are able to build a pipeline that allows the folding (or time multiplexing) of the circuit, i.e., that allows the merging of identical circuit portions by sequencing their access. Thus, the consumed resources are reduced both in number of flip-flops and in number of logical units. Our approach is based on a Timed Petri Net model with delayable transitions that can miss their firing date, and a specific action called reset that resets the clocks of all transitions. This model is shown to be equivalent to a one-clock automaton. An overclass of this model, the Timed Petri Nets with delayable transitions (without reset), turns out tobe incomparable, in terms of expressivity in weak semantics, with the classes of Temporal or Timed Petri nets in dense or discrete time. Finally, a symbolic exploration of this model and results on theoretical and practical complexity are studied

Cette thèse s'inscrit dans le cadre de la théorie des systèmes linéaires dans les dioïdes. Cette théorie concerne la sous-classe des systèmes à événements discrets modélisables par les Graphes d'Événements Temporisés (GET). La dynamique de ces graphes peut être représentée par des équations récurrentes linéaires sur des structures algébriques particulières telles que l'algèbre (max,+) ou l'algèbre (min,+).Ce mémoire est consacré à l'analyse de performances des systèmes dynamiques qui peuvent être modélisés graphiquement par des Graphes d'Événements Temporisés Généralisés (GETG). Ces derniers, contrairement au GET, n'admettent pas une représentation linéaire dans l'algèbre (min,+). Pour pallier à ce problème de non linéarité, nous avons utilisé une approche de modélisation définie sur un dioïde d'opérateurs muni de deux lois internes : loi additive correspondant à l'opération (min), et loi multiplicative équivalente à la loi de composition usuelle. Le modèle d'état obtenu, est utilisé pour évaluer les performances des GETG. Pour cela, nous avons proposé une nouvelle méthode qui a pour but de linéariser le modèle mathématique régissant l'évolution dynamique du modèle graphique, dans le but d'obtenir un modèle (min,+) linéaire. La deuxième partie de cette thèse est consacrée au problème qui consiste à déterminer les ressources à utiliser dans une ligne de production, en vue d'atteindre des performances souhaitée. Ceci est équivalent à déterminer le marquage initial de la partie commande du GETG.

Cette thèse concerne les problèmes d'ordonnancement pour une classe de systèmes manufacturiers flexibles (FMS) en environnement incertain. Les systèmes considérés répondent aux exigences de l’industrie 4.0 qui requièrent des organisations plus agiles permettant de proposer des produits personnalisés. Plus précisément, les systèmes proposés dans ce travail sont appelés FMS hybrides et traitent les opérations avec des contraintes de précédence partielles entre les opérations. La première contribution est une approche systématique de modélisation des FMS hybrides avec les réseaux de Petri temporisés sur les transitions (T-TPN) et un formalisme multi-niveaux basé sur la structuration hiérarchique des opérations. La deuxième contribution concerne la recherche d’ordonnancements pour les FMS hybrides. Nous utilisons la recherche en faisceau et proposons une fonction coût basée sur la modélisation multiniveaux. Nous proposons également une nouvelle variante de la recherche en faisceau, appelée Generation Filtered Beam Search (GFBS). Cette nouvelle variante améliore la qualité des candidats sélectionnés par rapport à d’autres variantes par un meilleur équilibre entre la largeur et la profondeur de la recherche. La troisième contribution concerne l’étude des aléas pouvant affecter le système. Un risque d’interruption, dû à l’occurrence d'événements incontrôlables, est intégré, et une nouvelle fonction coût qui intègre ce risque est définie. Enfin, un algorithme de recherche en faisceau modifié, appelé Generation Double Filtered Beam Search (GDFBS), qui accélère la convergence de la méthode, est proposé. Ce nouvel algorithme est basé sur un mécanisme de filtrage qui utilise la fonction coût pour explorer de manière sélective l'espace d'état du T-TPN afin de trouver une séquence de contrôle qui réalise un compromis entre performance et risque<br>This thesis concerns the scheduling problems for a class of flexible manufacturing systems (FMS) in uncertain environment. The considered systems meet the requirements of Industry 4.0, which require more flexibility and modularity to offer personalized products. More precisely, the proposed systems in this work are called hybrid FMS and deal with operations with partial precedence constraints. The first contribution is a systematic approach used for the modeling of hybrid FMS with timed Petri nets (T-TPN) and a multi-level formalism based on the hierarchical organization of operations. The second contribution concerns the scheduling of hybrid FMS. We use the beam search and propose a cost function based on the multi-level modeling. We also offer a new variant of beam search called Generation Filtered Beam Search (GFBS). This new variant improves the quality of the selected candidates compared to other variants of beam search by a better balance between the width and the depth of the search. The third contribution concerns the study of interruptions that can affect the system. A risk of interruption, due to the occurrence of uncontrollable events, is integrated, and a new cost function that incorporates this risk is defined. Finally, a modified beam search algorithm, called Generation Double Filtered Beam Search (GDFBS), which accelerates the convergence of the method, is proposed. The new algorithm is based on a filtering mechanism that uses the cost function to selectively explore the state space of the TPN in order to find a control sequence that achieves a tradeoff between performance and risk

Operational support as an area of process mining aims to predict the temporal performance of individual cases and the overall business process. Although seasonal effects, delays and performance trends are well-known to exist for business processes, there is up until now no prediction model available that explicitly captures this. In this paper, we introduce time series Petri net models. These models integrate the control flow perspective of Petri nets with time series prediction. Our evaluation on the basis of our prototypical implementation demonstrates the merits of this model in terms of better accuracy in the presence of time series effects.