Open access peer-reviewed chapter

Petri Net Models Optimized for Simulation

Written By

Juan-Ignacio Latorre-Biel and Emilio Jiménez-Macías

Submitted: 31 May 2018 Reviewed: 20 July 2018 Published: 05 November 2018

DOI: 10.5772/intechopen.80410

From the Edited Volume

Simulation Modelling Practice and Theory

Edited by Evon Abu-Taieh and Asim Abdel El Sheikh Ahmed

Chapter metrics overview

1,862 Chapter Downloads

View Full Metrics

Abstract

Petri nets and simulation are a modeling paradigm and a tool, respectively, which may be successfully combined for diverse applications, such as performance evaluation, decision support, or training on complex systems. Simulation may require significant computer resources; hence, in this chapter, two Petri net-based formalisms are analyzed for profiting from their respective advantages for modeling, simulation, and decision-making support: a set of alternative Petri nets and a compound Petri net. These formalisms, as well as the transformation algorithms between them, are detailed and an illustrative example is provided. Among the main advantages of these formalisms, their intuitive application for modeling discrete event systems in the process of being designed, as well as the compactness that may present the resulting model, in the case of a compound Petri net, leading to efficient decision making, can be mentioned.

Keywords

  • alternative Petri nets
  • compound Petri nets
  • parametric Petri nets
  • modeling and simulation
  • decision support systems

1. Introduction

Simulation can be considered as a tool able to mimic, in an approximated way, some of the properties and the behavior of a certain system. This system can be real or imaginary; hence, simulation can imply a significant saving of money and time, when applied to large and expensive systems, such as manufacturing facilities or road networks, and when implemented to systems that do not exist, such as in the design of products or the development of computer games. The purposes for the application of simulation can be to improve the knowledge of a certain system, to train and educate, to develop games, or to test certain features of systems, such as safety issues. However, the main application field of simulation is decision making. In this context, simulation allows knowing in advance the effects of making certain decisions on a system of interest. As an outcome of a series of simulations, testing different decisions, it is possible to select the best solution or to provide to a human decision maker some information on the effects of certain decisions and how these effects are compatible with the objectives of the decision process. This chapter will focus mainly on the simulation applied to the broad field of decision-making support.

1.1 Decision support systems

Our present technological civilization offers many opportunities for the application of decision support systems. Decision making is a demanding task in systems that show a complex behavior, such as manufacturing systems, supply chains, hospitals, educative institutions, communication networks, just to give a few examples.

Decisions made by experts, who base their choices on their intuition and experience, present evident limitations, since these professionals are scarce resources and expensive to hire. Additionally, human decision makers may be influenced by personal affinities and prejudices and they might tend to simplify reality, limiting the number of feasible solutions to be considered, as well as to skip information that might be relevant in the decision problem.

One solution to the challenge of decision making in complex systems can be the development of a decision support system and its application to solve a specific problem [1]. Different types of decision support systems can be developed for a variety of complex systems and decision problems. A particular kind of methodology for the construction of such support systems is based on the development of a model of the complex system of interest. This model can be analyzed to deduce some properties that may be useful to understand the system itself, as well as to improve it according to the objectives of the decision makers.

1.2 Petri nets in decision support systems

Many complex systems of technological, financial, and social interest can be considered as discrete event systems [2]. The development of a quantitative model of a discrete event system requires the use of a certain formal language to describe it. Petri nets have proven to be very suitable for modeling complex discrete event systems. A large amount of theoretical results and applications of this formalism are available in the scientific literature [3, 4, 5].

Petri nets, as a formal language, have been used extensively to model successfully complex discrete event systems in a broad range of application areas: industrial manufacturing, food industry, transportation systems, road networks, railway networks, communication networks, ports, airports, etc.

A Petri net model of a discrete event system can be considered as a mathematical description of this system. This description contains numbers that quantify certain features of the original system. Depending on the class of Petri net, considered to represent the model of the system, the roles these numbers may play are more or less diverse. For example, an autonomous generalized Petri net would present numbers that represent the initial marking of the places of the net, as well as the weight of every arc between places and transitions [6]. A timed Petri net would present numbers associated to the delay time of firing certain transitions once they are enabled. A prioritized Petri net may present numbers associated to the priority in firing any transition involved in effective conflicts. These are just some examples of the richness of the feasible meaning that a certain number in a Petri net model can show.

A decision problem, implying a Petri net model of a discrete event system, involves one or several decision variables, which are usually associated to one of the numbers of the mathematical description that constitutes the Petri net [7]. The objective of the decision process is to determine a value for every decision variable that meets the objectives of the decision makers and the additional constraints the problem might present [8]. According to this approach, the decision variables can be called parameters of the Petri net model and they might be the initial marking of certain places, weight of some arcs between nodes of the net, delay times associated to a given set of transitions, etc. [9].

The most common parameters of a Petri net, involved in a decision-making process, are associated to the initial marking of the net and to the weight of the arcs. The weight of the arcs of a Petri net is ranked as elements of the so-called incidence matrices. It is known that the structure of the Petri net model, and hence the structure of the original system, is represented by means of the incidence matrices, or the weight of the arcs between nodes of the net. This structure is, somehow, the part of the model that remains unchanged, when the Petri net evolves.

Furthermore, the dynamics of the Petri net is described by the changing marking of the net, as a consequence of firing a sequence of transitions. In fact, it is said that the places, which hold the tokens of the marking, are the state variables of the discrete event system, and their values are the marking at a given frame in the evolution of the net.

As a consequence, a decision problem related to the operation of a system, such as specifying the number of resources a certain production in a manufacturing facility would require, is likely to involve Petri net with parameters in the initial marking of certain places [10]. These parameters can be called marking parameters. Moreover, a decision problem involving the design of a new system or a significant redesign of an existing one is probably related to a Petri net containing parameters in the incidence matrices, which can be called structural parameters [11]. The former is a relatively common problem in the scientific literature, while the latter is a much scarcer case. In fact, the design of a discrete event system is, commonly, a much more difficult problem than its mere operation. Not in vain, the design of a discrete event system can be carried out solving in parallel the problem of operating it, in order to obtain from the designed system its maximal “benefit.”

1.3 Simulation as a tool for decision making

One group of methodologies to solve decision problems associated to Petri net models is based on simulation [12]. This approach has been successfully applied to a diversity of case studies described in the literature. Basically, the use of simulation in conjunction with a Petri net model may imply the following steps:

  1. Select one solution to the decision problem. This step can be carried out by intuition, randomly, using a heuristic or metaheuristic algorithm, etc.

  2. Assign values from the chosen solution to every parameter of the Petri net (decision variables).

  3. Simulate the evolution of the Petri net until a certain stop criterion is met.

  4. Analyze the outcome of the simulation process. This step can be developed by calculating a quality parameter that quantifies the degree of verification of the objectives of the decision maker by the tested solution.

  5. Select and test another solution and compare the outcome of its simulation with the previously tested solutions.

  6. When a certain stop criterion is met, finish the procedure.

Simulation is a very useful methodology for decision making in systems that cannot stop their operation for testing their performance after different decisions or these tests are too expensive or the feasible outcome is too risky to be carried out [13]. For example, this situation arises in the case of a manufacturing facility, where the change of the manufacturing strategy may present important implications for the survival of the company [3, 14]. Furthermore, simulation is even more important in the design of systems, since in the design process it is not always possible to test solutions in a system that does not exist yet.

The feasible solutions of a decision problem can be found in the solution space. This space might be huge, in particular when a combinatorial process can be used to build up solutions for the decision problem. This is the case when the structure of a solution contains the decision variables (parameters) of a Petri net and by combining in different ways the diverse values the decision variables can take; the solution space is constructed.

To be confident in making good decisions, the number of tested solutions should be large, when comparing it to the size of the solution space. However, testing one solution implies to carry out one simulation. However, simulation can consume a large amount of computer resources. Adding this fact to a huge solution space implies that, in general, it is not possible to analyze a significant percentage of the solutions contained in the solution space. As a consequence, it is crucial to use efficient search algorithms to select good solutions to be tested. Furthermore, it is very convenient to use efficient simulation methodologies to reduce the computer resources a simulation process requires [15].

This chapter is devoted to studying different approaches for modeling with Petri nets a system in the process of being designed, whose Petri net model contains at least one structural parameter. This analysis aims at providing modeling tools to improve the simulation of a Petri net, when compared with a classic approach. In particular, some of the advantages for simulation the presented formalisms would provide are:

  1. Removal of redundant information in the model of the system, hence, reducing its size.

  2. Feasibility of automatic solving of the decision problem, hence, testing a large number of solutions.

  3. More efficient exploration of the solution space, hence focusing on the most promising regions to obtain good solutions.

Petri nets and their graphical and matrix-based representations are the topic of the second section of this chapter. This overview of some properties of the Petri nets will be applied in the following section.

In Section 1 of this chapter, it was shown how a decision problem could be stated to solve the design of a discrete event system. This kind of decision problem is usually related to the specification of the structure of the system in the process of being designed. One possibility to represent a model of a Petri net, whose structure is not completely defined, is to consider structural parameters or decision variables in the incidence matrices of the net. However, there are other different feasible representations of a discrete event system with a noncompletely specified structure, such as the set of alternative Petri nets, which is the topic of the third section of the chapter.

The description of a Petri net, whose structure is not known, because its design has not been completed or it is being modified, can also be done by means of parameters in its incidence matrices. This type of Petri net can be called parametric Petri net. Section 4 of this chapter devotes to the compound Petri nets, a particular type of parametric Petri net, which contains at least one structural parameter.

The following section describes and illustrates the transformation of a set of alternative Petri nets into a compound Petri net and vice versa. These transformation algorithms allow profiting from the advantages of the different formal languages at the diverse stages of the decision-making process.

The chapter ends with the conclusions and bibliographical references.

The main objective of this chapter is to show the application of Petri net models optimized for simulation in a decision support system. The adaptation of the Petri net models to these systems is based on the development of formal languages that profit from the characteristics of the discrete event systems and the decision support methodology to reduce the computational resources applied to decision support.

Advertisement

2. Petri nets

2.1 Graphical representation of a Petri net

Among the more outstanding characteristics of a Petri net model, it is possible to mention a double graphical and matrix-based representation. The former may show, in a very intuitive way, the components or subsystems of the discrete event system and how they relate. Additionally, the tokens, representing the marking of the Petri net, configure a distributed state of the system, which informs about the dynamics of the system.

On the contrary, the matrix-based representation is an appropriate description of the discrete event system to process the model in a computer, in order to develop a structural analysis or a performance evaluation [5]. Among the tools that can be used to study the structure and behavior of the system, simulation can be mentioned. Moreover, the structure of the Petri net model is also shown in this matrix-based representation, by means of the incidence matrices. Subsystems appear as boxes in the matrices, while their interrelations, in the form of transitions, are shown as columns of the incidence matrices.

These ideas are very useful for the development and application of Petri nets–based formalisms to represent appropriate models in the frame of decision-making processes.

In this section, some ideas on the graphical representation of a Petri net are stated [3].

Definition 1. Marked generalized Petri net

A marked generalized Petri net is a 5-tuple:

N=PTprepostm0.E1

where

P and T are disjoint, nonempty, finite sets of places and transitions, respectively.

Pre: P × T → N is called the input or preincidence function.

Post: T × P → N is called the output or postincidence function.

m0 is the initial marking of P and m0 = (m1, m2, …, mn)TNn. The ith component of m0 is the marking of place piP.

The sets of places and transitions in addition to the input and output functions determine the structure of a Petri net, while the marking characterizes its dynamics.

A Petri net can be seen as a bipartite graph with oriented arcs, where the nodes can belong to a set of places or a set of transitions and the arcs relate to couples of nodes of different types. In other words, an arc cannot relate a place with another (or the same) place or a transition with another (or the same) transition. Additionally, an arc can be represented from a place to a transition or from a transition to a place. In both cases, there is a clear and different implication of the arc in the behavior of the Petri net model. In certain classes of Petri nets, generalized Petri nets, natural numbers are represented in conjunction with the arcs. These weights represent different things depending on the type of arc:

  1. If the arc starts in a place and finishes in a transition, the weight of the arc presents two meanings. The first one is the number of tokens in the place that constitutes a necessary condition to enable the transition, previous step to firing it. The sufficient condition to enable the transition is that the number of tokens in all the input places of the transition is equal or greater to the weight of the arcs from the input places to the mentioned transition. The second meaning of one of these input arcs is the number of tokens that are removed from the place, when the transition fires.

  2. If the arc starts in a transition and finishes in a place, the weight of the arc corresponds to the number of tokens added to the output place, once the transition is fired.

Tokens may flow from one or several places to other ones through fired transitions. This flow represents the evolution of the Petri net model by means of the variation of the state of the model (represented by means of the Petri net marking).

The input and output functions can be represented in a matrix-based way by means of the so-called input and output incidence matrices W− and W+. These matrices contain the weight of the arcs from places to transitions and from transitions to places, respectively. Each row is associated to a given place of the Petri net and each column to a certain transition.

2.2 Matrix-based representation of a Petri net

The input incidence matrix, W+, ranks the weight of the arcs from places to transitions. The element of the matrix placed in the ith row and jth transition, wij+, corresponds to the weight of the arc that starts in the jth place and finishes in the ith transition. It is a natural deduction that interchanging the name (number) between two places or two transitions has two implications:

  1. The structure and behavior of the Petri net do not change, since the graphical representation of the Petri net remains the same, as well as the initial marking and other features of the net.

  2. The two rows (columns) associated to the places (transitions) that have interchanged the names are swapped, thus leading to a different incidence matrix.

  3. Swapping rows or columns of the incidence matrices does not modify the structure or the behavior of the Petri net.

As it has been seen, the input incidence matrix represents the number of tokens that the firing of a transition removes from each input place.

The output incidence matrix is composed of the weight of the arcs from transitions to places. The element of the matrix that is located in the ith row and jth column, wij, consists of the weight of the arc beginning in the jth transition and finishing in the ith place. This output incidence matrix represents the number of tokens that the firing of each transition adds to each output place.

From the point of view of the ith place, pi, the number of tokens that remain after the firing of the jth transition, tj, is the balance between the following:

  1. The weight of the arc that starts in the jth transition and ends in the ith place, wij+. This number adds wij+ tokens to the place pi.

  2. The weight of the arc that starts in the ith place and ends in the jth transition, wij. This number subtracts wij tokens to the place pi.

This balance can be represented as wij+ − wij. As a consequence, a single incidence matrix can be built up from the input and output incidence matrices:

W=W+W.E2

From the graphical representation of the Petri net or from the input and output incidence matrix, it is possible to obtain this single incidence matrix W. However, the reconstruction of the original Petri net (described by its graphical representation or by the input and output incidence matrices) is not possible in the case when at least one of the element of the incidence matrix wij = wij+ − wij is obtained by the subtraction of two elements of the input and output incidence matrices different to zero: wij+0 and wij0. This situation corresponds to a Petri net, where at least one transition is, both, input and output transition of a given place.

A Petri net not presenting any transition that is simultaneously input and output transition of the same place is called pure Petri net. The simulation of a Petri net requires the calculation of a sequence of markings (states) that are allowed by the Petri net structure, the initial marking, and other additional restrictions that might arise (such as delay times, priorities, etc.).

Advertisement

3. Set of alternative Petri nets

3.1 Definition and properties

One classic and usually intuitive way to represent a system with a noncompletely specified structure is a set of alternative Petri nets [16]. This approach arises naturally, when considering a discrete event system in the process of being designed as a Petri net with alternative structural configurations [17].

The classic approach, when a discrete event system is to be designed, or, more generally, its structure is to be specified, consists of selecting (manually) a small set of alternative structures to be tested as final solutions for the decision problem.

This modeling strategy may lead to a lack of generality by focusing on a reduced set of alternative structural configurations. However, it is intuitive, simple to apply, and, in general, its analysis requires a reduced amount of computer resources.

Basically, a set of alternative Petri nets contains exclusive models for a certain discrete event system presenting different static structures. Any pair of nets belonging to such a set verifies the following property, which guarantees the exclusiveness between the feasible models for the original discrete event system.

Definition 2. Mutually exclusive evolution

Given two Petri nets R and R’, they are said to have mutually exclusive evolutions if they verify:

  1. If m(R) ≠ m0(R) ⇒ m(R’) = m0(R’).

  2. If m(R’) ≠ m0(R’) ⇒ m(R) = m0(R).

In addition to the previous property, any couple of Petri nets should meet an additional constraint to be considered as alternative Petri nets.

Definition 3. Pair of alternative Petri nets

Given two Petri nets R and R’, they are said to be alternative Petri nets if they verify:

  1. R and R’ have mutually exclusive evolutions.

  2. W(R) ≠ W(R’), where W(R) ≠ W(R’) are the incidence matrices of R and R’, respectively.

Definition 4. Set of alternative Petri nets

Given a set of Petri nets SR = {R1, …, Rn}, SR is said to be a set of alternative Petri nets if it verifies:

  1. n > 1.

  2. i, jN, such that i ≠ j and 1 ≤ i, j ≤ n, then Ri and Rj are a pair of alternative Petri nets.

3.2 Examples

In order to illustrate the concept of set of alternative Petri nets, an example from [18] is shown. In this example, different manufacturing strategies are shown for their application to a manufacturing line composed of two manufacturing stages followed by an assembly stage. Figure 1 represents a basic pull control strategy, named base sock control system (BSCS). Figure 2 shows a simultaneous Kanban control system (SKCS) and Figure 3 depicts an independent Kanban control system (IKCS). All these figures contain a graphical and a matrix-based representation of the Petri net models. More examples of sets of alternative Petri nets can be found in [19, 20].

Figure 1.

Manufacturing line under a push strategy.

Figure 2.

Manufacturing line under an SKCS strategy.

Figure 3.

Manufacturing line under an IKCS strategy.

Advertisement

4. Compound Petri net/parametric Petri net

4.1 Definition and features

In this section, a compound Petri net is defined as a parametric Petri net that presents structural parameters [20]. Additionally, the equivalence between alternative Petri nets and a compound Petri net is analyzed. Furthermore, transformation algorithms are provided and an illustrative example of application is detailed.

As it has already been mentioned, a compound Petri net can be seen as a parametric Petri net with structural parameters. These are parameters in the incidence matrices or, what is the same, in the weight of some of the arcs of the net.

Definition 5. Compound Petri net

A compound Petri net is a 7-tuple Rc = ⟨P, T, pre, post, m0, Sα, Svalα⟩, where

  1. Sα is the set of parameters of Rc.

  2. Svalα is the feasible combination of values for the parameters.

  3. Sstrα ⊆ Sα, a set of structural parameters of Rc, such that Sstrα ≠ ∅, that is, a compound Petri net should contain at least one structural parameter.

An example of a compound Petri net can be seen in Figures 6 and 7. In the first of these figures, the incidence matrix is shown. The structural parameters have been represented by means of the symbol α and an ordinal subindex. In this example, the set of structural parameters Sstrα coincides with the set of parameters Sα. These sets have been detailed in Figure 6.

Additionally, the set of feasible combinations of values for the parameters of the Petri net, Svalα, can be found in this same figure. This important set should be given as a part of the Petri net model, in addition to the incidence matrices or the graphical representation of the net, since it provides the constraints that the values of the parameters should meet.

From this set, it is possible to determine the sets of feasible values for each one of the parameters of the Petri net. It is important to notice that the opposite statement is not true. In effect, given the set of feasible values for the different parameters of the Petri net:

Svalα1=011;Svalα2=100;Svalα3=010
Svalα4=100;Svalα5=001;Svalα6=110
Svalα7=001;Svalα8=110;Svalα9=001
Svalα10=011;Svalα11=011;Svalα12=001
Svalα13=001;Svalα14=001;Svalα15=001
Svalα16=001;Svalα17=001

It is not possible to obtain from them the set of feasible combinations of values for the parameters of the Petri net, Svalα, since not all the combinations of values for each parameter is allowed. For example, even though α1 and α2 can take both 0 and 1 as feasible values, only the combinations α1α20110 are allowed but the combinations α1α20011 are forbidden, since they do not take part in the Petri net intended as model of the original discrete event system.

4.2 Advantages and drawbacks

A compound Petri net presents a series of advantages, when compared to a set of alternative Petri nets, as model for a discrete event system with a structure that has not been completely designed yet:

  1. (a.1) Compact model: if some alternative structural configurations present strong similarities, a compound Petri net as a metamodel representing all these configurations might imply a reduced set of structural parameters and the removal of a large amount of shared data. As a consequence, the resulting compound Petri net might present a size, which has been considerably reduced, when compared to an equivalent set of alternative Petri nets. In certain cases and applications, a more compact model may lead to faster computer processing of the model and, hence, faster decision-making support.

  2. (a.2) Unified solution space: all the parameters of the Petri net are variable decisions, that is, components of a solution of a decision problem. The feasible combination of values for these parameters configures the solution space. There is no particular difference between structural parameters and other type of parameters of the Petri net, regarding the composition of a solution of the decision problem. As a consequence, a search for promising solutions is simplified and the search process itself can be performed more efficiently, since it can focus in the most promising regions of the solution space.

  3. (a.3) Better understanding of the original discrete event system: a compound Petri net might point out the common structure in all the different feasible structures for the discrete event system, as well as constrain the differences in the structural parameters of the Petri net. This fact might enhance the knowledge of the system.

  4. (a.4) Intuitive modeling: in case of a discrete event system in the process of being designed, the alternative structures that can be considered for the final model can be very similar. It is possible to think of a range of machines provided by the same supplier, which are essentially the same but presenting specific differences. It might be possible to develop a single model for all the machines, describing the common features of all of them. Then, this single model can be particularized for every different machine by representing with parameters their specific characteristics.

Despite these advantages, a compound Petri net may present certain drawbacks, when compared to a set of alternative Petri nets for describing a model of a discrete event system. In fact, depending on the real discrete event system to be modeled by Petri nets, some of the mentioned advantages can be considered as drawbacks of the compound Petri nets if a set of alternative Petri nets is more suitable to fulfill the needs of the decision makers.

  1. (b.1) Novel approach: it is not difficult to find, in the scientific literature, sets of alternative Petri nets as feasible models for discrete event systems, even though they might not be referred by this name. Analyzing a small set of alternative Petri nets might be easier than analyzing a compound Petri net due to the larger availability of theoretical results that can be applied to the former, as well as due to the existence of efficient tools for simulation and performance evaluation, which are much more scarce for parametric Petri nets than for a set of alternative Petri nets.

  2. (b.2) Nonintuitive modeling: this feature can be an advantage or a disadvantage of a set of alternative Petri nets, depending on the particular case study. In the case where the alternative structural configurations for the Petri net lead to very different incidence matrices, developing the model of the discrete event system may be much more difficult if the formalism of the compound Petri nets is used in the case where each structural configuration is modeled separately. This last approach produces a set of alternative Petri nets.

The next section will focus on the transformation algorithms between a set of alternative Petri nets and a compound Petri net. These algorithms allow transforming the formal language that describes the model of a system. However, the structure and dynamics of the model itself remain unchanged. These transformation algorithms allow profiting from the advantages of both, compound Petri nets and a set of alternative Petri nets, since certain stages of problem solving can be developed using one of the formalisms, while the other stages may be carried out describing the system with another formalism.

4.3 Transformation algorithms

4.3.1 Transformation of a set of alternative Petri nets into a compound Petri net

This section provides a sequence of steps to transform the formalism in which a model is represented, from a compound Petri net to a set of alternative Petri nets [21]. The application of this algorithm may allow the modeler to profit from the advantages of both formalisms in different stages of the process in which he or she is involved (e.g., a decision-making problem).

4.3.1.1 Step 1: development of a set of alternative Petri nets

This first step consists of building up a set of alternative Petri nets as feasible models of a discrete event system. As it has been explained in the previous section, in some cases, modeling a discrete event system by a set of alternative Petri nets can be a very intuitive process.

In Figures 13, three alternative Petri nets for a manufacturing line can be found. In each one of the mentioned figures, both the graphical representation and the incidence matrix of one of the alternative Petri nets are given. This set of alternative Petri nets is transformed in this section into a single compound Petri net.

4.3.1.2 Step 2: equaling the dimensions of the incidence matrices

In order to merge the three alternative Petri nets into one single compound Petri net requires having the same number of places and transitions in each case.

The first alternative Petri net presents 7 places and 6 transitions, the second, 8 places and 6 transitions, while the last one contains 11 places and 8 transitions. The variation of size of the alternative Petri nets should be made without changing the structure or the behavior of the nets. It is not always possible to reduce the size of a Petri net without modifying the structure or behavior. However, it is always possible to increase the size of a Petri net meeting these conditions by adding isolated places and/or transitions. An isolated place or transition does not present any input or output arc and, hence, it cannot participate in the dynamics of the Petri net and, of course, it cannot modify the behavior of the net.

The minimal size of the Petri nets, modified by adding places and/or transitions, is the size of the large alternative Petri net: 11 places and 8 transitions. As a consequence, four isolated places and two isolated transitions are added to the first alternative Petri net. Moreover, three places and two transitions are added to the second alternative Petri net. The third alternative Petri net remains unchanged. The incidence of the incorporation of isolated places and transitions to a Petri net in the incidence matrix is the addition of rows (one for each new place) and columns (one per new transition) of zeros. Figure 4 shows partially the modified incidence matrices.

Figure 4.

Overlapping the incidence matrices of the alternative Petri nets.

4.3.1.3 Step 3: comparing the elements of the incidence matrices

Before merging the alternative Petri nets into a single compound Petri net, the elements of their incidence matrices at the same position should be compared. As an outcome of this comparison, it is possible to identify which elements of the resulting compound Petri net present a specific value or its value should be chosen from a set of feasible values, leading to a structural parameter.

In general, all the numbers defining the different features of the Petri net should be compared to identify the parameters of the resulting compound Petri net.

This comparison has been depicted in Figure 4, where the incidence matrices of all the alternative Petri nets have been depicted. These incidence matrices are overlapped in order to ease the comparison of each element in the three matrices. Additionally, the comparison of the element was placed in the first row and fourth column. Due to the fact that the elements at this position do not present the same value in all the incidence matrices, the resulting compound Petri net would have a structural parameter in this position.

A result of the comparison of the elements of the incidence matrices can be seen in Figure 5. At the positions where all the values of the incidence matrices are the same, these values have been represented in the matrix of Figure 5. Additionally, where the values are not the same, the complete range of feasible values, depending on the incidence matrix, has been represented.

Figure 5.

Analysis of differences in the elements of the three incidence matrices.

4.3.1.4 Step 4: defining the parameters of the compound Petri net

Once the comparison of the different numbers defining the Petri net has been performed, it is possible to define a parameter for each set of noncoinciding numbers. As it can be seen in Figure 5, there are 17 positions, where the elements of the depicted matrix do not present a single value, but a set of 3 different possibilities. As a consequence, the resulting compound Petri net would include 17 structural parameters.

As it has been mentioned in Section 2.2, rows and columns of an incidence matrix can be swapped without modifying the structure or the behavior of the net. It is possible to profit from this property trying to rearrange the elements of the incidence matrices of the alternative Petri nets in order to minimize the number of structural parameters in the resulting compound Petri net.

The incidence matrix of the resulting compound Petri net has been detailed in Figure 6. This incidence matrix presents the 17 structural parameters in the positions deduced in the previous step. Additionally, two sets that complete the description given by the incidence matrix are presented:

Figure 6.

Incidence matrix of the compound Petri net, set of parameters, and set of feasible combination of values for these parameters.

The set with the 17 parameters (all of them are structural parameters) is given under the name Sα.

The set with the feasible combinations of values for the parameters has also been presented, named Svalα. In this example, it is verified that Svalstrα. = Svalα. In other words, all the parameters are structural ones; hence, the set of feasible combinations of values for the structural parameters is the same as the set of feasible combinations of values for the parameters of the Petri net.

4.3.1.5 Step 5: building up the resulting compound Petri net

With the previous information, it is possible to detail all the remaining features of the resulting compound Petri net.

In Figure 7, the graphical representation of the compound Petri net is provided. This description should be complemented with the set of feasible combinations of values for the parameters of the Petri net, which detail the constraints applied to the parameters of the Petri nets.

Figure 7.

Compound Petri net.

4.3.2 Transformation of a compound Petri net into a set of alternative Petri nets

This transformation is quite straightforward.

Given a set Svalstrα of feasible combination of values for the structural parameters of the Petri net, let us call q = card(Svalstrα), number of these combinations of values. This set can be represented as Svalstr = {cv1, cv2, …, cvq}.

4.3.2.1 Step 1: obtaining the first alternative Petri net

Let us consider cv1Svalstr. Let us substitute the k components of cv1 in the k structural parameters of the compound Petri net Sstrα = {α1, α2, …, αk}.

The resulting Petri net from this substitution might contain nonstructural parameters but not structural ones. As a consequence, it is a component of a set of alternative Petri nets.

4.3.2.2 Step 2: obtaining the rest alternative Petri nets

Let us choose sequentially the elements of Svalstr and, for each one of them, repeat Step 1.

Advertisement

5. Conclusions

Simulation is a very useful tool for analyzing the structure and, specially, the behavior of the model of a discrete event system. It is a particularly interesting tool, when applied to the development of decision support systems.

However, simulation is a demanding task for a computer, requiring a certain amount of resources, such as memory and processing time.

A Petri net is a modeling formalism that has been broadly and successfully used in a large range of applications. A Petri net model of a discrete event system in a decision process may present degrees of freedom in the initial marking, the incidence matrices, or other components of the model, such as delay times or priorities.

In order to alleviate the modeling process by Petri nets of discrete event systems with degrees of freedom, as well as with the purpose of increasing the efficiency of simulation-based decision making, an analysis of two Petri net–based formalisms has been studied.

In particular, a set of alternative Petri nets and a compound Petri nets has been defined, compared, transformed one into the other, and applied to an illustrative example.

As a conclusion, both formalisms allow modeling a Petri net with alternative structural configurations and provide different characteristics that can be useful in different stages of the application of the model, for example, in the development of a decision support system.

Furthermore, the transformation of one model described using the formalism of the set of alternative Petri nets into an equivalent model represented as a compound Petri net is feasible and may be automated easily. Additionally, the inverse transformation can also be developed and it is even more straightforward than the previous one. These algorithms allow disconnecting the different stages of decision-making support, since the modeling process might be developed using a set of alternative Petri nets, if it is more intuitive, and an equivalent compound Petri net can be developed to be applied for simulation.

Compound Petri nets may produce a significant reduction in the size of the model of a discrete event system, which might alleviate significantly the computer resources required by a decision support system. This statement is based on the fact that when the different alternative structural configurations are similar, which is very common in the design of products, the size of the incidence matrix of the compound Petri net is very similar to the largest incidence matrix of the alternative Petri nets, and the amount of structural parameters may not be large.

References

  1. 1. Bruzzone AG, Longo F. An advanced system for supporting the decision process within large-scale retail stores. Simulation. 2010;86(12):742-762
  2. 2. Cassandras CG, Lafortune S. Introduction to Discrete Event Systems. 2nd ed. Springer; 2008
  3. 3. Silva M. Introducing Petri nets. In: Di Cesare F, editor. Practice of Petri Nets in Manufacturing. Chapman Hall; 1993. pp. 1-62
  4. 4. David R, Alla H. Discrete, Continuous, and Hybrid Petri Nets. 2nd ed2010. pp. 1-550
  5. 5. Giua A, Silva M. Petri nets and Automatic Control: A historical perspective. Annual Reviews in Control. 2018;45:223-239
  6. 6. Latorre-Biel JI, Jiménez-Macías E, Blanco-Fernández J, Martínez-Cámara E, Sáenz-Díez JC, Pérez-Parte M. Decision support system, based on the paradigm of the Petri nets, for the design and operation of a dairy plant. International Journal of Food Engineering. 2015;11(6):767-776
  7. 7. Piera MA, Music G. Coloured Petri net scheduling models: timed state space exploration shortages. Mathematics and Computers in Simulation. 2011;82(3):428-441
  8. 8. Latorre JI, Jiménez E, Pérez M. The optimization problem based on alternatives aggregation Petri nets as models for industrial discrete event systems. Simulation. 2013;89(3):346-361
  9. 9. Zaitsev DA, Shmeleva TR. A parametric colored Petri net model of a switched network. International Journal of Communications, Network and System Sciences. 2011;04(01):65-76
  10. 10. Baruwa OT, Piera MA. A coloured Petri net-based hybrid heuristic search approach to simultaneous scheduling of machines and automated guided vehicles. International Journal of Production Research. 2016;54(16):4773-4792
  11. 11. Latorre-Biel J-I, Jiménez-Macías E, Pérez-Parte M. Sequence of decisions on discrete event systems modeled by Petri nets with structural alternative configurations. Journal of Computational Science. 2014;5(3):387-394
  12. 12. Bruzzone AG, Massei M. Simulation-based military training. In: Mittal S, Durak U, Ören T, editors. Guide to Simulation-Based Disciplines. Simulation Foundations, Methods and Applications. Cham: Springer; 2017
  13. 13. Longo F, Nicoletti L, Chiurco A, Solis A, Massei M, Diaz R. Investigating the behavior of a shop order manufacturing system by using simulation. In: Proceedings of the Emerging M and S Applications in Industry and Academia Symposium, EAIA 2013 and the Modeling and Humanities Symposium 2013, MatH 2013, Part of the 2013 Spring Simulation Multiconference, SpringSim 2013, USA. April 2013. pp. 47-54
  14. 14. Mota MM, Piera MA. A compact timed state space approach for the analysis of manufacturing systems: Key algorithmic improvements. International Journal of Computer Integrated Manufacturing. 2011;24(2):135-153
  15. 15. Latorre-Biel JI, Jiménez E, Pérez M, Leiva F, Martínez E, Blanco J. Simulation model of a production facility of Agaricus bisporus mycelium for decision-making support. International Journal of Food Engineering. 2017;14(2):1-16. Article ID 20170159. DOI: 10.1515/ijfe-2017-0159
  16. 16. Latorre-Biel JI, Jimenez-Macias E, Perez-Parte M, Blanco-Fernandez J, Martinez-Camara E. Control of discrete event systems by means of discrete optimization and disjunctive colored PNs: Application to manufacturing facilities. Abstract and Applied Analysis. 2014:1-16. Article ID 821707. DOI: 10.1155/2014/821707
  17. 17. Latorre-Biel J-I, Jiménez-Macías E, Blanco-Fernández J, Sáenz-Díez JC. Optimal design of an olive oil mill by means of the simulation of a Petri net model. International Journal of Food Engineering. 2014;10(4):573-582
  18. 18. Recalde L, Silva M, Ezpeleta J, Teruel E. Petri Nets and Manufacturing Systems: An Examples-Driven Tour. In: Lectures on Concurrency and Petri Nets, vol. 3098 of Lecture Notes in Computer Science. Berlin, Heidelberg: Springer; 2004. pp. 742-788
  19. 19. Tsinarakis GJ, Tsourveloudis NC, Valavanis KP. Petri net modeling of routing and operation flexibility in production systems. In: Proceedings of the 20th IEEE International Symposium on Intelligent Control, ISIC’05 and the 13th Mediterranean Conference on Control and Automation, MED’05. Cyprus; June 2005. pp. 352-357
  20. 20. Latorre-Biel J-I, Jiménez-Macías E, Pérez-De-La-Parte M, Sáenz-Díez JC, Martínez-Cámara E, Blanco-Fernández J. Compound Petri nets and alternatives aggregation Petri nets: Two formalisms for decision-making support. Advances in Mechanical Engineering. 2016;8(11):1-12
  21. 21. Latorre-Biel JI, Jiménez-Macías E, Pérez De La Parte M. Equivalent and efficient optimization models for an industrial discrete event system with alternative structural configurations. Complexity. 2018:14. Article ID 5341346. DOI: 10.1155/2018/5341346

Written By

Juan-Ignacio Latorre-Biel and Emilio Jiménez-Macías

Submitted: 31 May 2018 Reviewed: 20 July 2018 Published: 05 November 2018