Modeling, analysis, simulation, scheduling, and control ofsemiconductor manufacturing systems: A Petri net approach

This paper presents a Petri net approach to modeling, analysis, simulation, scheduling, and control of semiconductor manufacturing systems. These systems can be characterized as discrete event systems that exhibit sequential, concurrent, and conflicting relations among the events and operations. Their evolution is dynamic over time. The system complexity is tremendous owing to the complex semiconductor manufacturing processes and test procedures. A formal approach such as Petri nets enables one to describe such complex discrete event systems precisely and thus allows one to perform both qualitative and quantitative analysis, scheduling and discrete-event control of them. This paper also serves as a tutorial paper. It briefly reviews applications of Petri nets in semiconductor manufacturing automation. It then introduces definitions and concepts of Petri nets. It proceeds with a discussion of basic Petri net modules in system modeling, a modeling method and a practical system's modeling example. Next, the paper presents their properties and their implications in manufacturing systems, as well as their analysis methods. Timed Petri nets are introduced for system simulation, performance evaluation, and scheduling purposes. An application-oriented case study is presented. Finally, the paper concludes with the active research areas in applying Petri nets to design of semiconductor manufacturing systems     

Structuring and composability issues in Petri nets modeling

Along Petri nets' history, numerous approaches have been proposed that try to manage model size through the introduction of structuring mechanisms allowing hierarchical representations and model composability. This paper proposes a classification system for Petri nets' structuring mechanisms and discusses each one of them. These include node fusion, node vectors, high-level nets, and object-oriented inspired Petri nets extensions, among others. One running example is used emphasizing the application of the presented mechanisms to specific areas, namely to automation systems modeling, and software engineering, where object-oriented modeling plays a major role.     

Comparing ladder logic diagrams and Petri nets for sequencecontroller design through a discrete manufacturing system

Design methods for sequence controllers play a very important role in advancing industrial automation. The increasing complexity and varying needs of modern discrete manufacturing systems have challenged the traditional design methods such as the use of ladder logic diagrams (LLDs) for programmable logic controllers. The methodologies based on research results in computer science have recently received growing attention by academic researchers and industrial engineers in order to design flexible, reusable, and maintainable control software. Particularly, Petri nets are emerging as a very important tool to provide an integrated solution for modeling, analysis, simulation, and control of industrial automated systems. This paper identifies certain criteria to compare LLDs and Petri nets in designing sequence controllers and responding to the changing control requirements. The comparison is performed through a practical system after introducing “real-time Petri nets” for discrete-event control purposes. The results reported in this paper will help: (a) further establish Petri net based techniques for discrete-event control of industrial automated systems; and (b) effectively convince industrial practitioners and researchers that it is worthy and timely to consider and promote the applications of Petri nets to their particular discrete-event control problems     

Modeling and simulation of an electronic component manufacturingsystem using hybrid Petri nets

Modelling and analysis for the design and operation of manufacturing systems is a vital need. For semiconductor manufacturing systems, which are large scale systems, discrete Petri nets do not constitute an adequate tool for modeling and analysis. In fact, use of discrete Petri nets is confronted with tile state explosion and the high cost of simulation. In this paper, hybrid Petri nets are presented as powerful tools for modeling and simulation of semiconductor manufacturing systems. This model has been used for modeling and simulation of a real life electronic components manufacturing system. It provides an accurate and first simulation of this system     

有界Petri网等价性的判定算法

Petri网语言是系统行为分析的一种重要工具,为了分析有界Petri网的行为等价,借助于有限自动机的等价性问题和算法,研究了有界Petri网的等价性问题和算法.定义了带标注Petri网语言等价性,证明了带标注的有界Petri网到有限自动机的等价转化,给出了判定有界Petri网的等价性算法,为模拟系统的性能比较提供了处理方法.     

基于FPGA的有色Petri网仿真系统设计

为了实现大规模有色Petri网模型的性能测试,设计了基于FPGA的高速仿真系统。该系统实现了库所、变迁模块到硬件结构的映射,采用C语言实现了有色Petri网的硬件自动生成工具。通过分析有色Petri网的特征,该工具生成对应的Verilog代码和基于Quartus的自动脚本。以通信中"包传输"的模型为例,在FPGA中对生成的代码进行测试,验证了设计的正确性。     

一种基于逻辑Petri网的过程挖掘方法

逻辑Petri网是抑制弧Petri网和高级Petri网的抽象和扩展,可在过程挖掘中简洁准确的表示活动之间复杂的业务逻辑关系.本文在传统Petri网挖掘方法的基础上,为了进一步提高复杂系统挖掘模型的简洁度和拟合度,尤其是对并行活动间存在复杂与或关系的系统,提出了一种基于逻辑Petri网的过程挖掘方法,并给出了逻辑Petri网中逻辑变迁的挖掘算法.它可以充分挖掘活动之间的业务逻辑,并且业务逻辑可用逻辑表达式表示.通过与相应Petri网模型的实例比较分析,例证了本文方法的正确性和有效性,且逻辑Petri网模型更加适合日志行为.     

A modeling framework to evaluate performability parameters ingracefully degrading systems

A systematic approach to modeling and assessing gracefully degrading systems, exploiting the formalism offered by Petri nets, is provided. The procedure followed is based on the definition of some fundamental modules, the composition of which allows a complete model of the system to be obtained. The model can then be solved by computer simulation or analytically by means of a class of Petri nets to obtain interesting performability parameters either at steady state or when the system is time-varying. A number of real cases are examined and the results obtained are described     

Algebraic tools for the performance evaluation of discrete eventsystems

It is shown that a certain class of Petri nets called event graphs can be represented as linear time-invariant finite-dimensional systems using some particular algebras. This sets the ground on which a theory of these systems can be developed in a manner which is very analogous to that of conventional linear system theory. Some preliminary basic developments in that direction are shown. Several ways in which one can consider event graphs as linear systems are described. These correspond to approaches in the time domain, in the event domain, and in a two-dimensional domain. In each of these approaches, a different algebra has to be used for models to remain linear, but the common feature of these algebras is that they all fall into the axiomatic definition of `dioids'. A unified presentation of basic algebraic results on dioids is provided     

Analysing Internet Software Retrieval Systems: Modeling and Performance Comparison

Nowadays, there exist web sites that allow users to retrieve and install software in an easy way. The performance of these sites may be poor if they are used in wireless networks; the reason is the inadequate use of the net resources that they need. If these kinds of systems are designed using mobile agent technology the previous problem might be avoided. In this paper, we present a comparison between the performance of a software retrieval system especially designed to be used in a wireless network and the performance of a software retrieval system similar to the well-known Tucows.com web site. In order to compare performance, we make use of a software performance process enriched with formal techniques. The process has as important features that it uses UML as a design notation and it uses stochastic Petri nets as formal model. Petri nets provide a formal semantics for the system and a performance model.     

Differential Petri net models for industrial automation and supervisory control

Supervisory control systems play a central role in modern industrial automation. However, control theory has recently made significant advances in modeling mixed continuous/discrete event systems ("hybrid control systems"), whose typical instantiations include the industrial supervisory controller. This article shows how differential Petri nets, a model for hybrid control systems, can be used to represent industrial supervisory systems in a unified way. Typical industrial automation tests can be modeled, whereas the effect of communication protocols and software can be straightforwardly included using conventional Petri nets. Therefore, a global model for the operation of an industrial control system can be formed and its behavior analyzed.     

Model-driven software synthesis for hard real-time applications with energy constraints

Model-driven methods have been quite effective for reducing the intricacies of embedded software development, since they provide effective means for property verification as well as automatic code generation. Nevertheless, regarding energy-constrained hard real-time systems, few model-driven methods are available and, usually, most methods (model-driven or not) consider simplified system specifications, such as absence of intertask relations. This paper presents a model-driven method for software synthesis of hard real-time embedded applications with energy constraints. A formal model based on time Petri nets is adopted in order to provide a basis for pre-runtime schedule generation and property analysis/verification.     

Petri net as a modeling tool

Over the last decade, Petri nets have emerged as a most suitable, powerful and widely acceptable modeling tool for representing and studying the asynchronous concurrent hardware (or software) systems/processes. Petri nets can be viewed as formal automata or as an automation which can generate the formal languages or a model to analyse and synthesize various kinds of systems. The structure of Petri nets, their markings, extensions and subclasses are briefly discussed. Several examples of Petri net models of computer hardware and software are presented. Various applications of reachability concepts are also given.     

Constructing and Refining Large-Scale Railway Models Represented by Petri Nets

A new method for rapid construction of large-scale executable railway models is presented. Computer systems for railway systems suffer from poor integration and lack of explicit understanding of the large amount of static and dynamic information in the railway. In this paper, we give solutions to both problems. It is shown how a component-oriented approach makes it easy to construct and refine basic railway models by effective methods, such that a variety of models with important properties can be maintained within the same framework. Basic railway nets are refined into several new kinds: nets that are safe, permit collision detection, include time, and are sensitive to its surroundings. Since the underlying implementation language is Petri nets, large expressibility is combined with simplicity, and in addition, the analysis of the behavior of railway models comes gently.     

Petri nets and integrality relaxations: A view of continuous Petri net models

Petri nets are formalisms for the modeling of discrete event dynamic systems (DEDS). The integrality of the marking and of the transitions firing counters is a clear reflection of this. To reduce the computational complexity of the analysis or synthesis of Petri nets, two relaxations have been introduced at two different levels: (1) at net level, leading to continuous net systems; (2) at state equation level, which has allowed to obtain systems of linear inequalities, or linear programming problems. These relaxations are mainly related to the fractional firing of transitions, which implies the existence of non-integer markings. We give an overview of this emerging field. It is focused on the relationship between the properties of (discrete) PNs and the corresponding properties of their continuous approximation. Through the interleaving of qualitative and quantitative techniques, surprising results can be obtained from the analysis of these continuous systems. For these approximations to be "acceptable", it is necessary that large markings (populations) exist. It can also be seen, however, that not every populated net system can be continuized. In fact, there exist systems with "large" populations for which continuation does not make sense. The possibility of expressing nonlinear behaviors may lead to deterministic continuous differential systems with complex behaviors.     

Use of Petri nets for resource allocation in projects

Traditional models for project management have not adequately incorporated a number of factors that are important for resource allocation. This paper describes the use of Petri nets to facilitate resource allocation in projects under some conditions commonly encountered in practice. Petri nets provide a powerful formalism for representing and analyzing concurrent systems. To date, however, very little has been done to integrate this graphical and mathematical tool with the area of project management. Petri net models can be used to analyze interdependencies, criticality, substitution, conflicting resource priorities and variations in the availability of resources. This paper proposes a new model and demonstrates the usefulness of the model for real-time activity scheduling in a resource-constrained project environment. The model has been computerized using the C language, and a simple project is chosen as an example to provide step-by-step explanations of the simulation carried out. This paper also discusses the implications of the model and the analysis it supports     

Microprogramming implementation of timed Petri nets

This paper describes a method to implement restricted timed Petri nets by microprograms. These timed Petri nets are used to represent control parts of VLSI systems to produce sequences of control signals that evoke the operations of a corresponding data part. The proposed method consists of a set of transformation algorithms which have been implemented as parts of CAMAD, an integrated design aid system. We have also studied the problem of microprogram optimization, for example, how to reconstruct the control structure of a VLSI system so as to produce better microprograms.     

Modeling and analysis of message passing in distributedmanufacturing systems

This paper addresses the information flow between devices and programs in computer integrated manufacturing systems. Specifically, it presents modeling techniques and methods for detecting the existence of message paths among hardware and software components and the upper bound on time delays along that message path. The modeling technique can be used to analyze interoperability between hardware and software components in the system in initial design and specification. The modeling technique has three components: an object model to describe the message passing protocols between communicating components; a color timed Petri net to describe the dynamic behavior and state dependency within each individual component; and an object synthesis method that integrates the Petri nets of individual objects and message protocols between objects to describe the dynamics of the entire system. The graphical modeling can enhance communication among different groups involved in system design and the analytical method can provide component specifications. The use of the modeling technique and method in early system design can result in time and cost savings in system integration due to better communication, better component selection and early problem identification