Petri Nets for Systems Engineering

This book intends to show how Petri nets fill many of the needs of systems modelling, their verification and implementation, as mentioned in the preface. It first introduces Petri nets in such a way that only those features necessary for system engineers are presented and then introduces important fields such as modelling concepts and verification techniques.

In this chapter a basic model is introduced by extracting information from an intuitive example, given in this section. By doing this some essential features of Petri nets will appear, namely the principles of locality, concurrency, graphical and algebraic representation. For illustration we choose an example where several objects are subject to a coordination procedure. Similar examples can be found in various other fields, e.g. from computer integrated manufacturing to office automation. In our example, a race among a number of cars is started. When the starter receives ready signs from all cars, he gives the starting signal and the cars begin the race. For simplicity, we restrict the example to one starter and two racing cars (Figure 2.1) .

This chapter introduces the most frequently used models of Petri nets, namely place/transition nets and coloured Petri nets, in an intuitive manner. While place/transition nets are a slight generalisation of the nets introduced in Chapter 2, coloured Petri nets allow much more compact models of systems. For bibliographic references see Chapter 1.

In this chapter a formal definition of place/transition nets and coloured Petri nets is given. Although the former are special cases of the latter, for didactic reasons we start with place/transition nets.

The construction of Petri net models from informal requirement specifications is not a trivial task, and requires a great deal of modelling experience, as well as knowledge of the techniques aiding in model construction. As a result, a Petri net model may differ considerably from its original specification. This is especially true when large Petri net models of complex systems are involved.

This chapter is intended to give a more detailed overview of the book than the introduction in Chapter 1. Having read Chapters 1 to 5 the reader should have acquired some intuitive understanding of Petri nets as well as some familiarity with basic formal definitions and properties. At this point the reader should be in a position to understand most of the presentations in the remainder of the book. Although, for the novice it may be beneficial to read the book from beginning to end, more experienced readers should have no problem skipping chapters that are not of foremost importance for them.

The systems engineer often uses models to investigate properties of his system. In the context of this book, the models will be Petri nets, and the chapters to come are filled with various interesting properties to investigate (analyse, verify, validate) in this context. However, the models have to be built first, which is the topic of this part. In fact, the construction of formal models (such as Petri nets) is valuable in itself, as it enforces a full understanding of the aspects treated.

In the literature, and even more in unpublished sources such as lecture notes, there is a treasury of fine examples of using Petri nets for system design. Many such examples are given in this book to illustrate particular definitions, re-sults, or methods. However, some very typical and interesting examples are not included, sometimes due to their size. This chapter is meant to partially bridge the gap and to give a deeper insight into the modelling potential of Petri nets. The examples are not chosen randomly but rather to cover differ-ent areas of applications using different Petri net model classes. In particular, nets, refinement, and abstraction of nets will be used for an example on task execution in a system of functional units. A well-known resource allocation problem will be modelled by place/transition nets, and state-space repre-sentation and place-invariants will be used to illustrate the problem. The alternating-bit protocol will be modelled by a coloured net. Different layers will again be connected by the concept of net refinement.

In this chapter we give general principles of modelling with Petri nets. We will concentrate on the aspects that are specific to Petri nets. We shall discuss how the specific building blocks of Petri nets (places, transitions, arcs, and tokens) are used to model components and aspects of the problem.

This chapter is devoted to the use of Petri nets within methods that support structured approaches for modelling systems and for validating and verifying them using the formal foundation provided. The three approaches presented each have their own way of Petri net modelling, aimed at verification and validation.

This chapter presents three case studies on developing a mutual exclusion (ME) algorithm for a ring architecture, one for each method described in the previous chapter. This section gives a brief introduction to the problem and a classification of the solutions within the ME-area.

In the previous chapters, Petri net models have been presented for various systems. In retrospect, these systems (and the models for them) are somewhat similar. This is no coincidence, since Petri nets are well suited for modelling distributed systems, i.e. systems that consist of many largely independent subsystems that work towards a common goal.

The diversity of the verification methods developed for Petri nets and their extensions may be confusing for the engineer trying to choose appropriate techniques to solve his problem. This chapter aims to clarify the basis of such a choice by discussing some general issues involved in the design and application of a verification method:

Previous chapters bring out the need for system designers to profit from automated verification techniques. Effectively, the known problem of statespace explosion makes it difficult to achieve an a priori understanding of the whole behaviour of any reasonable system. Verification techniques must exceed the capabilities of structural approaches which mainly allow us to check that the system is well-structured. One also wants to know the real semantics of the system to be designed.

Five different approaches based on logical reasoning and process algebraic method swill be presented in this chapter. The sections describe different methods that may seem unrelated at first sight but have certain connections that make their presentation worthwhile. Nevertheless the sections of this chapter are self-contained so there is no preferred order of reading.

The diversity of the verification methods developed for Petri nets and their extensions may confuse the engineer trying to choose the best approach for his problem. This part of the book aimed to clarify the basics of such a choice by discussing some general issues involved in the design and application of a verification method:

Validation is one of the central tasks of system development. The modelled system has to match the expectations of the user/client/customer. A variety of possibilities is available. The models can be executed, simulated, animated, inspected, tested, debugged, observed, controlled, etc. This incomplete list can easily be enlarged. However, in this book the emphasis is on the validation of Petri net models for systems engineering applications. This allows us to concentrate on the major areas of Petri net validation, namely prototyping, net execution, and code generation. Petri net concepts can be applied in some of the most important areas of systems engineering: concurrency and distribution.

The objective of this chapter is to describe the importance of validation for systems engineering approaches, to introduce the notion of validation, to explain prototyping, and to sketch the relevant tools in these areas in relation to Petri nets.

For some years, there has been a growing consensus on the distinction between requirement analysis and software design.

Petri nets as an initial specification introduce the possibility of verification of many properties of the system to be built. Petri nets also introduce the possibility of obtaining many interesting properties for the implementation which do not appear in the initial specification. For example, the fact that a net can be partitioned into a set of disjoint state machines can be used to propose a distributed implementation. The advantage of deducing the implementation from its formal specification is that it avoids (or reduces) the inherent errors associated with the coding task.

Validation can be seen as one of the central tasks of systems engineering. It provides the means to check whether the described, planned, or built system fulfils the expectations of the user, customer, or client. These expectations cover all aspects of a system, be it static or dynamic in nature. In this part of the book some critical parts of systems engineering have been described and some major areas of Petri nets have been presented, namely prototyping, net execution, and code generation.

Petri nets have existed for over thirty years. Especially in the last decade, Petri nets have been put into practice extensively. Thanks to several useful extensions and the availability of computer tools, Petri nets have become a mature tool for modelling and analysing industrial systems. This part describes how and when Petri nets can be used to model and analyse a variety of systems in application domains ranging from logistics to office automation.

A manufacturing system involves manufacturing activity which, as defined in [VN92], is “the transformation process by which raw material, labour, energy and equipment are brought together to produce high-quality goods”. A manufacturing system is composed of two main subsystems:

In this chapter an approach is outlined to support the definition of business processes with Petri nets. Today, business processes are defined using specific business applications called Workflow Management Systems (WFMS). They support workflow management which can be broadly defined as office logistics. A definition of WFMSs is given by the Workflow Management Coalition (WFMC) [WMC94]: “A Workflow Management System is the computerised execution of a process definition.”

A telecommunications system enables communication between remote entities in order to exchange information. It is composed of two subsystems, namely the transport network and the processing system. The transport network is the set of communication resources that enable information transfer between the communicating entities. The processing system is the set of computing resources and programs that control and manage the transport network on the one hand, and that implement the communication software on the other hand ([SKL94]). This software is designed according to syntactic and semantic rules called protocols. The development of these protocols constitutes protocol engineering, which can be defined as the specialisation of software engineering for communication software. Protocol engineering encompasses the set of techniques, methods, and tools that enable the production and exploitation of communication software with an industrial control ([Raf95J). This process of production is organised according to the classical stages of the development cycle, namely specification, design, implementation, deployment, and maintenance.

The three application domains have common characteristics with respect to the modelling of their processes. Most of the processes considered in this part are case-based, i.e. every piece of work is executed for a specific case. Examples of cases are a mortgage, a telephone call, a production order, an insurance claim, a tax declaration, an order, or a request for information. Cases are often generated by an external customer. However, it is also possible that a case is generated by another department within the same organisation (internal customer). The goal of the processes in the three application domains is to handle cases as efficiently and effectively as possible.