一种基于Petri网的网络服务兼容性分析方法

针对目前基于网络服务业务过程执行语言(BPEL)的网络服务合成方法缺乏网络服务的兼容性分析机制,不能保证基于网络服务技术的业务过程正确执行的问题,建立了一种能从形式化的角度描述网络服务的接口交互情况的基于Petri网的多元工作流组合网模型,提出了一种能更快地获得网络服务可用性结果的网络服务兼容性判断算法.最后,提出了基于该算法的原型系统架构.     

Real-time deadlock-free scheduling for semiconductor track systems based on colored timed Petri nets

This paper addresses the problem of real-time deadlock-free scheduling for a semiconductor track system. The system is required to process wafers continuously, cassette by cassette. The process is not necessarily a repeated one. In addition, the system is deadlock-prone and its modules are failure-prone. Thus, real-time scheduling approaches are required to achieve high-performance. The problem can be solved in a hierarchical way. A deadlock avoidance policy is developed for the system as a lower-layer controller. With the support of the deadlock avoidance policy, heuristic rules are proposed to schedule the system in real-time. An effective modeling tool, colored–timed resource-oriented Petri net, is presented. It is shown that with this model we can schedule a system to achieve satisfactory results in real-time. This method is tolerant to module failures.     

Deadlock-free genetic scheduling for flexible manufacturing systems using Petri nets and deadlock controllers

In this paper, a new deadlock-free scheduling method based on genetic algorithm and Petri net models of flexible manufacturing systems is proposed. The optimisation criterion is to minimise the makespan. In the proposed genetic scheduling algorithm, a candidate schedule is represented by a chromosome that consists of two sections: route selection and operation sequence. With the support of a deadlock controller, a repairing algorithm is proposed to check the feasibility of each chromosome and fix infeasible chromosomes to feasible ones. A feasible chromosome can be easily decoded to a deadlock-free schedule, which is a sequence of transitions without deadlocks. Different kinds of crossover and mutation operations are performed on two sections of the chromosome, respectively, to improve the performance of the presented algorithm. Computational results show that the proposed algorithm can get better schedules. Furthermore, the proposed scheduling method provides a new approach to evaluate the performance of different deadlock controllers.     

Modeling of system reliability Petri nets with aging tokens

The paper addresses the dynamic modeling of degrading and repairable complex systems. Emphasis is placed on the convenience of modeling for the end user, with special attention being paid to the modeling part of a problem, which is considered to be decoupled from the choice of solution algorithms. Depending on the nature of the problem, these solution algorithms can include discrete event simulation or numerical solution of the differential equations that govern underlying stochastic processes. Such modularity allows a focus on the needs of system reliability modeling and tailoring of the modeling formalism accordingly. To this end, several salient features are chosen from the multitude of existing extensions of Petri nets, and a new concept of aging tokens (tokens with memory) is introduced. The resulting framework provides for flexible and transparent graphical modeling with excellent representational power that is particularly suited for system reliability modeling with non-exponentially distributed firing times. The new framework is compared with existing Petri-net approaches and other system reliability modeling techniques such as reliability block diagrams and fault trees. The relative differences are emphasized and illustrated with several examples, including modeling of load sharing, imperfect repair of pooled items, multiphase missions, and damage-tolerant maintenance. Finally, a simple implementation of the framework using discrete event simulation is described.     

Optimal Legal Firing Sequence of Petri Nets Using Linear Programming

Petri nets (PNs) are a reliable graphical and mathematical modeling tool for the formal modeling and validation of systems (W. Reisig, A Primer in Petri Net Design, Springer-Verlag: Berlin, Heidelberg, 1992). Applications of PNs include discrete event dynamic systems (DEDS) that are recognized as being concurrent, asynchronous, distributed, parallel, and/or nondeterministic. It is also a powerful formal method for the analysis of concurrent, embedded, and distributed finite state systems (K. Varpaaniemi, Series A: Research Reports, No. 26, Helsinki University of Technology, Digital Systems Laboratory, Oct. 1993). The reachability analysis of PNs is strategically significant as it captures the dynamic behavior of the system as well as providing efficient verification of the correctness of the model. Few linear programming (LP)-based methods can be found that address the reachability problem, and some of these are suitable for optimal control problems. However, due to an inherent state explosion they are difficult to implement; other methods run easily into deadlock as they lack appropriate mechanisms to avoid the firing of critical transitions (T. Matsumoto and A. Tarek, in Proceedings of the 35th IEEE Conference on Decision and Control, Kobe, Japan, 1996-12, pp. 4459–4468). In this paper an improved and easy to implement method is proposed that combines the Optimality Principle and Linear Programming (OP + LP) techniques to find an Optimal Legal Firing Sequence (OLFS) in PNs. This method can be applied to ordinary PNs with self-loops, avoids deadlocks, and can also be used for general PNs having cycles.     

考虑资源成本的Petri网在FMS调度中的应用

本文针对目前基于petri网的调度方法中调度目标单一的缺点，通过在petri网的结构中引入资源成本元素的方法，使得在调度计划产生的过程中可以同时考虑时间和资源成本优化，为企业作出更为科学合理的生产决策提供依据．最后通过一个实例来验证了提出的算法。     

Using Extended Timed Petri Nets to evaluate and validate timing performance of hard real‐times software

Abstract

An important issue in real‐time systems development is to check the satisfaction of timing requirements. In this paper, we propose a formal model of the Extended Timed Petri Nets (ETPN) to model real‐time software systems. Some basic types of transitions are used to model the structures among software processes. The general equations for evaluating the performance in firing the basic transitions of ETPN are presented. The timing performances of a modelled software system can be evaluated using the corresponding ETPN. The evaluated results are validated with the corresponding timing constraints for checking the satisfaction of the results. The systematic procedure for evalution and validation are also discussed.     

Supply chain modelling and managing,using timed coloured Petri nets: a case study

This paper aims at developing a new methodology for designing and managing a supply chain (SC) and, at the same time, for evaluating the performance of every stakeholder involved in a production chain. The methodology proposed has been applied to a footwear supply chain and is based on coloured Petri nets (CPNs). The supply chain analysed in this paper is a complex production system consisting of a network of manufacturers and service suppliers related to logistics systems that provide transportation and storage. The model developed uses coloured, timed Petri nets to represent a supply chain and it is such that resources are the Petri Net (PN) places, the tokens are jobs, orders and/or products, while the colours represent job attributes. These colours are used to encode different data types and values that are attached to tokens. A “coloured token” represents a specific production order or a certain amount of a particular material supplied. Thus, it can be processed in different ways and it can be easily localised within the CPN model. The use of coloured Petri nets allows companies to create a compact representation of states, actions and events of the modelled system. The particular structure of this network allows the designers the easy realisation of a simulator using an “object-oriented”, dedicated programming, which is a useful tool for developing what-if analyses.     

基于着色Petri网的钢结构施工过程仿真研究

根据着色Petri网理论,利用着色token代表不同的资源,并通过分级建模的方法,建立钢结构施工过程的仿真模型;以实验数据为依据确定模型中的随机变量,通过仿真运算得到施工工期、设备利用率以及施工中各资源数量对两者的影响程度等数据.利用这些数据,可对工程的施工工序及资源配置等进行优化处理.     

基于Petri网的管理人员素质变化过程定性模拟

将QSIM定性模拟方法与Petri网集成用于描述管理人员素质变化过程,采用概率统计的方法处理模拟结果以提高管理人员任职资格确定的准确程度.将企业管理者的素质划分为成就动机、领导能力、人际关系能力、专业职务能力四类,设计了企业管理人员素质变化过程的PETRI网模型,规定了变量知识的表示方法和网络变迁推理规则;设计了基于素质改变成本的网络知识状态转移过滤规则,以防止定性模拟过程中的组合爆炸;设计了管理人员素质确定的概率统计处理方法,并给出了一个应用示例说明其应用过程.     

Phased mission modelling of systems with maintenance-free operating periods using simulated Petri nets

A common scenario in engineering is that of a system which operates throughout several sequential and distinct periods of time, during which the modes and consequences of failure differ from one another. This type of operation is known as a phased mission, and for the mission to be a success the system must successfully operate throughout all of the phases. Examples include a rocket launch and an aeroplane flight. Component or sub-system failures may occur at any time during the mission, yet not affect the system performance until the phase in which their condition is critical. This may mean that the transition from one phase to the next is a critical event that leads to phase and mission failure, with the root cause being a component failure in a previous phase. A series of phased missions with no maintenance may be considered as a maintenance-free operating period (MFOP). This paper describes the use of a Petri net (PN) to model the reliability of the MFOP and phased missions scenario. The model uses Monte-Carlo simulation to obtain its results, and due to the modelling power of PNs, can consider complexities such as component failure rate interdependencies and mission abandonment. The model operates three different types of PN which interact to provide the overall system reliability modelling. The model is demonstrated and validated by considering two simple examples that can be solved analytically.     

Hierarchical Colored Timed Petri Nets for Maintenance Process Modeling of Civil Aircraft

Civil aircraft maintenance process simulation model is an effective method for analyzing the maintainability of a civil aircraft. First, we present the Hierarchical Colored Timed Petri Nets for maintenance process modeling of civil aircraft. Then, we expound a general method of civil aircraft maintenance activities, determine the maintenance level for decomposition, and propose the methods of describing logic of relations between the maintenance activities based on Petri Net. Finally, a time Colored Petri multi-level network modeling and simulation procedures and steps are given with the maintenance example of the landing gear burst tire of a certain type of aircraft. The feasibility of the method is proved by the example.     

Performance modelling of a fault-tolerant real-time multiprocessor using stochastic Petri nets

The fault-tolerant multiprocessor (ftmp) is a bus-based multiprocessor architecture with real-time and fault-tolerance features and is used in critical aerospace applications. A preliminary performance evaluation is of crucial importance in the design of such systems. In this paper, we review stochastic Petri nets (spn) and developspn-based performance models forftmp. These performance models enable efficient computation of important performance measures such as processing power, bus contention, bus utilization, and waiting times.     

A Petri net based design engine for manufacturing systems

Support for the efficient design and operation of complex manufacturing systems requires an integrated modelling, analysis, and control methodology as well as its implementation in a software tool. In this paper the Petri net based design engine TimeNET is presented for this task. Petri nets are able to capture the characteristic features of manufacturing systems in a concise form. A subclass of coloured Petri nets is used, which has been developed especially for the application area of manufacturing. Structure and work plans are modelled separately. Stochastic as well as deterministic and more general distributions are adopted for the firing times of transitions. Fundamental questions about system properties can be answered using qualitative analysis. For an efficient performance and dependability prediction, different evaluation techniques are proposed: direct numerical analysis, approximate analysis, and simulation. Finally, the model can be used to evaluate different control strategies and to control the manufacturing system directly. There is no need to change the modelling methodology, thus avoiding additional effort, for example for model conversion. In the paper this necessary steps are described using an application example.     

A model based approach to assess the performance of production systems in degraded mode

Nowadays production systems are asked to perform their activities in a high uncertainty environment and to guarantee their performance in this environment. Therefore, they are asked to master risks that are part of their daily activities, to maintain the performance which is considered as their key success factor. Risks may cause serious effects that threaten the production systems and degrade their performance. Nevertheless, we cannot estimate the degradation that a risk may cause to system performance, since risk analysis methods found in the literature do not allow simulating the behaviour of the system in degraded mode. In order to help production systems to assess their performance in risk situations, we propose in this paper a model-based approach that enables assessing the performance of production systems in degraded mode. Our approach is based on function, interaction, structure (FIS) modelling framework that enables modelling complex system and its failures. The resulting model is converted into an executable simulation model based on a new class of Petri Nets (PNs) called predicate-transition, prioritised, synchronous (PTPS) PN. The obtained simulation model is then executed in order to obtain performance indicators in degraded mode. This tool is used during the system design, in order to study the impact of risks on the designed production system performance. It is also used to study an existing production system in order to analyse and optimise its behaviour in degraded mode. In this article, we present our tool and apply it to a special case of production systems which is a hospital sterilisation system.     

Multilevel intelligent scheduling and control system for an automated flow shop manufacturing environment

Current manufacturing scheduling and control systems are incapable of coping with complex system dynamics inherent in real-world situations and, hence, human intervention is required to maintain real-time adaptation and optimization. A unique feature of biological intelligent systems is that they build and improve over their communication, decision-making and control structures in real time autonomously. A challenge is now emerging in the design of manufacturing systems where on-line adaptation and optimization become increasingly important. This paper reports on the development of a new integrated intelligent scheduling and control system for an automated manufacturing environment using a multilevel approach. At the first level, a conventional scheduling and control system is considered, then at the second level, a new fuzzy logic mechanism is developed to enable the conventional system to improve and perceive the changes of system parameters adaptively. A new perturbation mechanism is embedded in the third level to implement on-line optimization for coping with the more complex structural changes of system dynamics. The final level is composed of artificial neural networks that can learn from experiences provided by the perturbation mechanism. The approach is designed to improve system intelligence gradually to cope with various forms of systems dynamics. A fully automated flow shop manufacturing system is taken to demonstrate this approach.     

On deadlock control for a class of generalised Petri net models of flexible manufacturing systems

This paper develops a deadlock prevention policy for a class of Petri nets that can model flexible manufacturing systems with assembly and disassembly operations. Siphons in a plant Petri net model are divided into elementary and dependent siphons according to the linear dependency of their characteristic T-vectors. The proposed approach is to make every siphon satisfy the controlled-siphon property (the cs-property), i.e., at any reachable marking, any siphon is max-marked, so that no deadlock states can be reached. The satisfiability of the cs-property is achieved by explicitly adding a monitor for each elementary siphon. The max-controllability of a dependent siphon is ensured by properly supervising its elementary siphons. More permissive behaviour of the non-blocking supervisor is obtained through the rearrangement of the output arcs of the monitors. Compared with existing policies reported in the literature, the advantage of the present method is that a small number of monitors are added and the iterative computing process is accordingly avoided. Finally, the application of the proposed method to an FMS example is presented.