# Equivalent and Efficient Optimization Models for an Industrial Discrete Event System with Alternative Structural Configurations

Authors: Juan-Ignacio Latorre-Biel; Emilio Jiménez-Macías; Mercedes Pérez de la Parte
Journal: Complexity
 (2018)

---

## Abstract

Discrete event systems in applications, such as industry and supply chain, may show a very complex behavior. For this reason, their design and operation may be carried out by the application of optimization techniques for decision making in order to obtain their highest performance. In a general approach, it is possible to implement these optimization techniques by means of the simulation of a Petri net model, which may require an intensive use of computational resources. One key factor in the computational cost of simulation-based optimization is the size of the model of the system; hence, it may be useful to apply techniques to reduce it. This paper analyzes the relationship between two Petri net formalisms, currently used in the design of discrete event systems, where it is usual to count on a set of alternative structural configurations. These formalisms are a particular type of parametric Petri nets, called compound Petri nets, and a set of alternative Petri nets. The development of equivalent models under these formalisms and the formal proof of this equivalence are the main topics of the paper. The basis for this formal approach is the graph of reachable markings, a powerful tool able to represent the behavior of a discrete event system and, hence, to show the equivalence between two different Petri net models. One immediate application of this equivalence is the substitution of a large model of a system by a more compact one, whose simulation may be less demanding in the use of computational resources.


---

## Body

## 1. Introduction

A significant number of systems of technological, social, or financial interest may present a high degree of complexity in their composition, in the interrelation among their components, in their behavior, or in all of these features [1, 2]. Many of these systems can be considered as discrete event systems (DES) [3, 4], such as manufacturing facilities, food industry, supply chains, airports, or traffic networks [5–8].The design of such systems can be a challenging task, involving experts from a variety of knowledge fields [9]. In this context, an effective communication of the partial and final results of the design process may be achieved, when using a formal language to represent a model of the system of interest. Additionally, the formal verification of some specifications of the designed system, such as checking the compliance of certain structural properties or assessing the performance of the system, can be carried out before the system itself has been built up [10, 11]. One effective strategy for achieving this purpose with a certain degree of accuracy consists of using a formal model of the system [10, 12].A very popular paradigm to represent the model of a DES is Petri nets [13]. This formalism has been applied to a wide range of different fields [14, 15]. The Petri nets present many favourable features, such as an important body of knowledge referred to as subclasses of formalisms, structural analysis techniques and properties, or methodologies for implementing performance evaluation and simulation [16]. Petri nets are the paradigm chosen in this research to represent models of DES.The research presented in this paper deals with Petri net models applied to the design process of DES. In this design process, the DES modeled by the Petri net has not been completely specified yet; hence, the Petri net should model the lack of concretion in some of the features of the original DES. These nonspecified features of the DES in process of being designed constitute a set of degrees of freedom, which should be solved by decision making as long as the design process is being completed. The mentioned decision-making process can be carried out by means of different strategies, such as “what-if” analysis or the statement of an optimization problem. The formalisms presented in this paper, belonging to the paradigm of the Petri nets, are particularly suited for developing optimization processes. Nevertheless, they are also appropriate for other strategies of decision making [17].Usually, in the design process of a DES, some of the degrees of freedom that should be solved by the designers refer to structural features of the system [18], while some others can be related to the system’s behavior. For example, the layout of the components of the system is a feature related to its structure. On the contrary, the dynamics or evolution of some of these components, such as raw materials supply, human resources, or communication packets, is associated with its behavior [19]. In a Petri net model, the structural features of a DES are explicitly represented in the so-called incidence matrices. These structural features can be clearly distinguished from the behavior of the system, which is described by successive markings of the net. An introduction of Petri nets can be found in [16, 20].A large number of scientific reports on the application of decision-making methodologies for solving certain stages of the design process of a DES can be found in the literature. However, most of them refer to the management or control of the operation of such systems; hence, the methodologies they present are aimed at solving behavioral degrees of freedom of the DES.The references presenting Petri net models of discrete event systems with structural degrees of freedom usually fall under one of the two following approaches:(a)
Each alternative configuration for the structural degrees of freedom, in brief alternative structural configuration, is represented by a different Petri net model [7, 8, 21, 22]. These Petri nets can be called alternative Petri nets.(b)
The incidence matrix representing the structure of the Petri net model contains a number of parameters. Giving diverse feasible values to these parameters, it is possible to specify different alternative structural configurations of the DES. These Petri nets can be called parametric, parameterized, parameterized, or compound Petri nets [6].Many of these works, dealing with structural degrees of freedom, lack formal and systematic approach to the definition and implementation of the structural degrees of freedom. In fact, they mainly focus on the decision-making process to select one alternative structural configuration of the DES [6, 8, 21, 22].Some previous works have advanced an equivalence relation between both formalisms, a set of alternative Petri nets and a compound Petri net, without providing a rigorous proof.The main contribution of this paper consists of formally proving that both formalisms, a set of alternative Petri net and a compound Petri net, can be equivalent and describing the conditions for achieving this equivalence. This result leads to some consequences of interest, since from this result it is possible to do the following:(a)
Apply appropriate algorithms to transform a compound Petri net into a set of alternative Petri nets, detailed in this paper, and vice versa.(b)
Use any of both formalisms for modeling in different stages of the design process of a DES, profiting from the advantages of each one of them. For example, depending on the particular case, the development of the original Petri net model of a discrete event system with structural degrees of freedom may be easier with one of the two formalisms.(c)
Reduce the amount of data required to describe a Petri net model with an associated set of feasible alternative structural configurations by its transformation into a compact compound Petri net. It has to be considered that there are virtually infinite compound Petri nets, of different sizes, that are equivalent to a given set of alternative Petri nets. Moreover, in the design of a discrete event system, the alternative structural configurations may share a large amount of data. If this redundant data is removed, significant reductions in the size of the simulation model of the system might be achieved.(d)
Accelerate the simulation-based optimization of a Petri net model with an associated set of feasible alternative structural configurations by using an appropriate implementation of distributed computing profiting from the advantages of using compact models.The rest of the paper is organized as follows. Section2 is devoted to formally define a set of alternative Petri nets and a compound Petri net. Section 3 focuses on proving that a certain transformation on a compound Petri net, based on the concept of partition of a set, leads to a set of alternative Petri nets. Section 4 presents some definitions related to the graphs of reachability and the marking of a Petri net. Section 5 describes a methodology to construct the reachability graph of a set of alternative Petri nets and of a compound Petri net. Section 6 uses the concept of reachability graph to prove the equivalence between a compound Petri net and the set of alternative Petri nets that results from the application of the transformation algorithm presented in Section 3. Section 7 illustrates the concepts, definitions, proposition, and theorems from previous sections by means of an example of application. Last section details the conclusions and future research lines.


## 2. Alternative Petri Nets and Compound Petri Net

One possible definition of a Petri net system is based on a weighted flow relation through two incidence functions [16, 20]. A Petri net system is also called marked Petri net or just Petri net for simplicity.Definition 1 (Petri net).
A (generalized)Petri net is a five-tuple:(1)N=P,T,pre,post,m0,where P and T are disjoint, finite, nonempty sets of places and transitions, respectively. Pre: P×T→N is the preincidence or input function. Post: T×P→N is the postincidence or output function. m0 is a marking of the set of places P, where m0=m1,m2,…,mnT∈Nn, whose ith component is the marking of place pi∈P.The first four elements of the Petri net define its structure of a Petri net, which is a static feature, while the fifth one, the marking, represents the behavior of the system, that is, the system state and its changes.It is possible to describe the structure of a Petri net by using the incidence matricesW- and W+. These matrices represent the incidence functions given in Definition 1 and can be called pre- and postincidence matrices, respectively.A pair of placep and transition t is called a self-loop if p is both an input and output place of t. A Petri net is said to be pure if it has not any self-loop. Moreover, pure nets are completely characterized by a single incidence matrix W=W+-W-.As it has been stated in the Introduction, a Petri net associated with a set of alternative structural configurations can be presented as a set of alternative Petri nets. Every Petri net of the mentioned set consists of the complete Petri net model of the original DES, particularized with one of the alternative structural configurations.Given a set of alternative Petri nets, any pair of these Petri nets verifies a property called mutually exclusive evolution, meaning that only one of the alternative Petri nets can be active at a given time, since all of them are exclusive models of the same DES. This property allows characterizing a set of alternative Petri nets as shown in the following.Definition 2 (mutually exclusive evolution).
Given two Petri netsR and R′, they are said to have mutually exclusive evolutions if the following is verified:
(i) ifm(R)≠m0(R)⇒mR′=m0(R′),
(ii) ifmR′≠m0(R′)⇒m(R)=m0(R).Once this property has been stated, it is possible to carry out the definition of a couple of Petri nets and a set of alternative Petri nets, as it is stated below.Definition 3 (pair of alternative Petri nets).
Given two Petri netsR and R′, they are said to be alternative Petri nets if it is verified that
(i)R and R′ have mutually exclusive evolution;
(ii)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 netsSR={R1,…,Rn}, SR is said to be a set of alternative Petri nets if it verifies that
(i)n>1;
(ii)∀i,j∈N, such that i≠j and 1≤i, j≤n; then Ri and Rj are a pair of alternative Petri nets.R i is called the ith alternative Petri net of SR.The second formalism, belonging to the paradigm of the Petri nets, which will be considered in this research document, is the compound Petri nets. It is a particular case of parametric Petri net, containing parameters in any of the two incidence matrices. It is associated with a set containing all the feasible combinations of values that can be assigned to these parameters.Definition 5 (parameter of a Petri net).
Any variable in a Petri net model, associated with a set of feasible values, its cardinality is greater than 1. A value can be assigned to this variable as a consequence of a decision. The outcome of this decision is a choice from a set of feasible values. Once a decision has been made, the value assigned to the parameter is unique.Definition 6 (structural parameter of a Petri net).
Any parameter of an incidence matrix of a Petri net.Definition 7 (compound Petri net).
A compound Petri net is a 7-tupleRc=P,T,pre,post,m0,Sα,Svalα, where
(i)Sα is the set of parameters of Rc;
(ii)Svalα is the feasible combination of values for the parameters, meaning that not all the combinations of values for the parameters of the Petri net lead to a valid structural configuration;
(iii) additionally,∃Sstrα⊆Sα, set of structural parameters of Rc, such that Sstrα≠⌀, meaning that a compound Petri net should contain at least one structural parameter among all its parameters.In the previous definitions, two different Petri-net-based formalisms able to represent a discrete event system with alternative structural configurations have been formally presented. Two numerical examples of these two formalisms can be found in Figures1 and 2. In the following section, an algorithm will be developed to transform a compound Petri net into a set of alternative Petri nets.Figure 1
Compound Petri netRc.Figure 2
Petri nets obtained from a compound Petri net.


## 3. Partitions

In this section, it is proven that any partition of the set of feasible combinations of values for the structural parameters of a compound Petri net leads to a set of alternative Petri nets. A numerical example of the definition and results presented in this section can be found in Stage1 of Section 7.Definition 8 (partition of the set of feasible combination of values for the set of structural parameters of a compound Petri net).
Given a compound Petri netRc and a set Svalstrα(Rc), containing the feasible combinations of values for the structural parameters of Rc, a partition of Svalstrα(Rc), denoted by ∏q(Svalstrα(Rc)), can be defined as the collection of subsets ∏q(Svalstrα(Rc))={Svalstrα(R1),Svalstrα(R2),…,Svalstrα(Rmr)} such that
(i)Svalstrα(Rc)=Svalstrα(R1)∪Svalstrα(R2)∪⋯∪Svalstrα(Rmr);
(ii)Svalstrα(Ri)≠⌀, 1≤i≤mr;
(iii)Svalstrα(Ri)∩Svalstrα(Rj)=⌀, ∀i,j∈N, such that 1≤i,j≤mr.The next Algorithm9 describes a procedure to obtain a set of Petri nets from the following elements:(a) a compound Petri net,Rc;(b) a partition of the set of feasible combinations of values for their structural parameters,∏q(Svalstrα(Rc)).Some properties of the resulting set of Petri nets are proven in Proposition10.Algorithm 9 (construction of a set of Petri nets from a pair (Rc, ∏q(Svalstrα(Rc)))).
Inputs:  Rc=P,T,pre,post,m0,Sα,Svalα, ∏q(Svalstrα(Rc)), which are, respectively, a compound Petri net and a partition of the set of feasible values for the structural parameters of the compound Petri net.StartRepeat Steps  1 and 2∀i∈N, such that 1≤i≤mr, where mr=∏qSvalstrαRc.Step  1 (construction of Svalα(Ri))Svalα(Ri) = ⌀.Repeat∀j∈N, such that 1≤j≤qi, where qi=card(SvalstrαRci)
Let us considercvsj=(b1,…,brs)⊆SvalstrαRci, where b1,…,brs are feasible values for the structural parameters α1,…,αrs respectively. Notice that cvs stands for “combination of values for the structural parameters.”Repeat∀k∈N, such that 1≤k≤q, where q=card(Svalα(Rc))
Let us considercvk=(c1,…,crs,crs+1,…,cr)⊆Svalα(Rc), where c1,…,crs,crs+1,…,cr are feasible values for the parameters of Rc:α1,…,αrs,αrs+1,…,αr∈Sα(Rc), respectively, and parameters α1,…,αrs∈Sstrα(Rc) are structural parameters of Rc.If it is verified thatb1=c1, b2=c2,…,brs=crs, then Svalα(Ri)←cvk, that is, assign cvk to Svalα(Ri).Step  2 (construction of Sα(Ri) and update of Svalα(Ri))Sα(Ri)=Sα(Rc).Repeat∀j∈N, such that 1≤j≤r, where r=card(Sα(Rc))
LetSvalα(Ri)=cv1,cv2,…,cvqi, where ∀k∈N, such that 1≤k≤qi; it can be expressed cvk=(c1(k),…,cr(k)).Ifcj(1)=cj(2)=⋯=cj(qi), then Sα(Ri)=Sα(Ri)∖αj and αj=cj(1), which is not a parameter anymore.∀k∈N, such that 1≤k≤qi, remove cj(k) from cvj, and update Svalα(Ri).ri=card(Sα(Ri)).EndOutput: A set of Petri nets SR=R1,…,Rmr, where Ri=P,T,pre,post,m0,Sα(Ri),Svalα(Ri)  ∀i∈N, such that 1≤i≤mr.Proposition 10 (properties of the Petri nets obtained from the application of Algorithm9).
Let us consider a compound Petri netRc=P,T,pre,post,m0,Sα,Svalα,
LetSvalstrα(Rc) be the set of feasible combinations of values for the structural parameters of Rc, Sstrα(Rc)⊆Sα.
Let∏q(Svalstrα(Rc)) be a partition of Svalstrα(Rc), which verifies
(i)∏qSvalstrαRc=SvalstrαR1,SvalstrαR2,…,SvalstrαRmr;
(ii)∏qSvalstrαRc=mr>1.
A set of Petri netsSR=R1,…,Rmr can be constructed by the application ofAlgorithm9 such that the following properties are verified:
(i)∀i∈N, such that 1≤i≤mr; it is possible to build up a Petri net Ri=P,T,pre,post,m0,Sα(Ri),Svalα(Ri), such that ∃Svalstrα(Ri)⊆∏q(Svalstrα(Rc)).
(ii)∃ bijection f:SR→∏q(Svalstrα(Rc)), where f(Ri)=Svalstrα(Ri)∀Ri∈SR.
(iii)Sstrα(Ri)⊆Sα(Ri)⊆Sα(Rc).
(iv)Svalstrα(Ri)⊆Svalα(Ri)⊂Svalα(Rc) (every subset of the partition has been assigned to one of the Petri nets as the set of feasible combinations of values for the parameters in it).Proof.
(i) It is evident by the method of construction, since∏q(Svalstrα(Rc)) is a prerequisite for the application of this proposition and Svalstrα(Ri) is one of the elements of ∏q(Svalstrα(Rc)).
(ii) Due to the fact that|∏q(Svalstrα(Rc))|=|SR|=mr, it is possible to define a bijection between the sets SR and ∏q(Svalstrα(Rc)).
(iii) By definitionSstrα(Ri)⊆Sα(Ri), since the structural parameters are a particular type of parameters. Moreover, Sα(Ri)⊆Sα(Rc) by construction, since the first step in the construction of Sα(Rc) consists of making Sα(Ri)=Sα(Rc) and the subsequent feasible operations for the construction of Sα(Ri) may lead to the removal of elements of Sα(Ri).
(iv) By definitionSvalstrα(Ri)⊆Svalα(Ri), since Sstrα(Ri)⊆Sα(Ri). On the other hand, by construction, Svalα(Ri)⊂Svalα(Rc), since the values of the first set are taken from the second. Finally, Svalα(Ri) ≠ Svalα(Rc), because, according to the statement of Proposition 10, ∏qSvalstrαRc=mr>1 and, according to the definition of partition, ∃Svalstrα(Ri), Svalstrα(Rj)∈∏q(Svalstrα(Rc)), where Svalstrα(Ri)∩Svalstrα(Rj)=⌀ and Svalstrα(Ri)≠⌀, Svalstrα(Rj)≠⌀; hence ∃cvs∈Svalstrα(Rj) and cvs∉Svalstrα(Ri) and, by the construction Algorithm 9, ∃cv∈Svalα(Rj) and cv∉Svalα(Ri).Theorem11 proves that the set of Petri nets built up according to Algorithm 9 is a set of alternative Petri nets. In other words, it is a model suitable for describing a discrete event system with freedom degrees in its structure.Theorem 11.
Let us consider a compound Petri netRc=P,T,pre,post,m0,Sα,Svalα, where Svalstrα(Rc) is the set of feasible combinations of values for the structural parameters of Rc.Given a partition ofSvalstrα(Rc), ∏q(Svalstrα(Rc))=SvalstrαR1,SvalstrαR2,…,SvalstrαRmr, where ∏qSvalstrαRc=mr>1.LetSR=R1,…,Rmr be a set of Petri net, built up according to Algorithm 9; then SR is a set of alternative Petri nets.Proof.
∀ R i , R j ∈ S R, such that i≠j, the following are verified:
(i)SvalstrαRi∩SvalstrαRj=⌀⇒Wi≠Wj; that is to say, they present different incidence matrices.
(ii) The choice ofcvsk∈Svalstrα(Rc) is the result of a decision ⇒ if cvsk=(c1,…,crs), then ∀cvsq∈Svalstrα(Rc) such that cvsq≠cvsk; it is verified that (c1,…,crs)≠cvsq⇒ if cvsk∈Svalstrα(Ri), then cvsk∉Svalstrα(Rj)∧ as m(Ri)≠m0(Ri), m(Rj)=m0(Rj)⇒ the evolutions of Ri,Rj,∀i,j∈{1,…,n}, such that i≠j, are mutually exclusive.
(ii) Let us make a decision to solve the structural degrees of freedom of the original compound Petri net,Rc: let us choose cvsk∈Svalstrα(Rc), such that cvsk∈Svalstrα(Ri). Additionally, Svalstrα(Ri)∈∏q(Svalstrα(Rc)) and Svalstrα(Ri)∩Svalstrα(Rj)=⌀⇒cvsk∉Svalstrα(Rj)⇒m(Rj)=m0(Rj), since the incidence matrices of Rj are not univocally defined and the dynamic of the Petri net is not defined either. On the contrary, cvsk defines univocally the incidence matrices of Ri and the evolution rules of the Petri net; the so-called “token game” can be applied; hence it may be possible for the marking of Ri to verify m(Ri)≠m0(Ri)⇒ the evolutions of Ri, Rj, ∀i,j∈{1,…,n}, such that i≠j, are mutually exclusive.
∀ R i , R j ∈ S R, Ri and Rj are a pair of alternative Petri nets, by Definition 3, and mr>1⇒ by Definition 4, SR={R1,…,Rn} is a set of alternative Petri nets.As it has been seen in Theorem11, every partition of the set of feasible values for the structural parameters of a compound Petri net leads to a set of alternative Petri nets. This set constitutes a collection of models, which are pairwise exclusive. This exclusion is a consequence of the fact that every feasible combination of values for the parameters of the compound Petri net can be chosen as a result of a decision. When one of these combinations of values is chosen, the other ones are rejected; hence, the alternative Petri nets related to them are also rejected.


## 4. Markings and Graphs of Reachable Markings

In the previous sections, both formalisms, the set of alternative Petri nets and the compound Petri net, have been defined. It has also been proven that it is possible to obtain a set of alternative Petri nets from a compound Petri net. In this section some definitions and results on the reachability graph of both formalisms are discussed for preparing the equivalence proof between compound Petri nets and a set of alternative Petri nets obtained from the application of Algorithm9.The first definition is devoted to characterize an isomorphous graph of reachable markings, which will be used to prove the equivalence between Petri net models. The following definition, in fact, could be stated and applied for generic graphs.Definition 12 (isomorphous graph of reachable markings).
Let us consider two graphs of reachable markings rg1 and rg2.
Let us callV1 and V2 the set of vertices in rg1 and rg2, respectively.
Let us callE1 and E2 the set of directed edges in rg1 and rg2, respectively.
E 1 is a set of ordered pairs (vi,vj) such that vi,vj∈V1 and there exists a directed arc which starts in vi and ends in vj.
E 2 is a set of ordered pairs (vp,vq) such that vp,vq∈V2 and there exists a directed arc which starts in vp and ends in vq.
rg1 and rg2 are said to be isomorphous or isomorphic graphs, denoted by rg1≅rg2, if it is possible to define the following bijection:(2)f:V1⟶V2such that ∀vi,vj∈V1, it is verified that (vi,vj)∈E1⇔(f(vi),f(vj))∈E2.This bijectionf is called labeled directed graph isomorphism. Two graphs of reachable markings are isomorphous if they have the same structure of nodes and directed arcs. This property plays a vital role in the proof of equivalence between a compound Petri net and a set of alternative Petri nets obtained from the application of Algorithm 9 to the former. It is considered in this paper that the equivalence between Petri nets do not imply the same marking in all the states, because it is not taken into account the marking that remains constant along all the feasible evolutions of the Petri net.Definition 13 (significant marking [20]).
The significant marking is the marking restricted to the places which do not have the same marking in all the stable states.More information on this previous definition can be found in [20].Definition 14 (graph of reachable markings of a set of alternative Petri nets).
LetSR={R1,…,Rmr} be a set of alternative Petri nets, where(3)Ri=Pi,Ti,prei,posti,m0Ri,SαRi,SvalαRi.The graph of reachable markings of SR, called rg(SR), verifies the following three properties:
(i)rg(SR) is made up of vertices which correspond to reachable markings and arcs corresponding to firing of transitions resulting in passing from one marking to another one.
(ii) Considering the set of alternative Petri nets as a single model of a DES, a marking of this set contains the tokens of every alternative Petri net. Moreover, the set of places of the set of alternative Petri nets is(4)PSR=⋃i=1mrPi.(iii) The construction of this graph of reachable markings is performed by the exploration of the subgraphs corresponding to the different alternative Petri nets. This choice means that the places of the rest of alternative Petri nets will remain in their initial marking. In other words, the places of the nonchosen Petri nets will not contribute to the significant marking of SR.A numerical example of Definition14 is given in Stage 2 of Section 7, while in Stage 3 of the same section a numerical application of Definition 15 is provided.Definition 15 (choice subgraph of the reachability graph of a set of alternative Petri nets).
LetSR be a set of alternative Petri nets, where |SR|=mr.
LetC={1,…,mr} be a set of natural numbers. Due to the fact that |C|=|SR| it is possible to create a bijection f:SR↔C.
Letc∈C be the result of a choice of one of the alternative Petri nets in the solution process of a decision problem.
Thecth choice subgraph of the reachability graph of SR is the reachability graph obtained for SR when thecth alternative Petri net is chosen as solution of a decision problem.
It is calledrg(SR,c).In fact, a choice subgraph is the subset of a reachability graph composed by all the nodes corresponding to all the feasible evolutions of a single alternative Petri net.Remark 16.
It can be easily deduced that the choice subgraph of an alternative Petri netRi belonging to a certain set SR can be transformed into the reachability graph of Ri by the removal of the marking of the places that do not belong to Ri but to another alternative Petri net. This removed marking does not vary in the evolution of Ri and, hence, does not contribute to the significant marking and does not modify the structure of the graph of reachable markings.
On the other hand, the transformation of the reachability graph of a certain alternative Petri netRi into a choice subgraph associated with a certain set SR, where Ri∈SR, can be done by the addition of a constant marking to every state. The marking to be added is the initial marking of the places that do not belong to this alternative Petri net but to the rest of the Petri nets of SR.


## 5. Construction of the Reachability Graph of a Set of Alternative Petri Nets and a Compound Petri Net

In the previous paragraphs the concept of choice subgraph has been introduced. It can be seen as the reachability graph of a set of alternative Petri nets when one of them is chosen as solution of a decision problem. Once this choice is made, the rest of the alternative Petri nets remain in their initial markings by definition.However, in some situations the comparison of the reachability graphs of the different alternative Petri nets may be of interest. This comparison may lead to interesting conclusions on the behavior of the different alternative Petri nets and, hence, it can be a valuable tool to make the appropriate choice of a certain structural configuration for the modeled DES.Definition17 describes the process of assembling the choice subgraphs of the different components of a set of alternative Petri nets. The reachability graph of the set of alternative Petri nets is generated from this assembling process, which eases the comparison mentioned in the previous paragraph.Definition 17 (union of choice subgraphs).
Given a set of alternative Petri netsSR={R1,R2,…,Rmr}, let us consider a subset SR′={R1,R2,…,Ri}⊆SR.
LetC={1,…,mr} be a set of natural numbers. Due to the fact that |C|=|SR|, it is possible to create a bijection f:SR↔C. Let c∈C be the result of a choice of one of the alternative Petri nets in the solution process of a decision problem.
The union of the choice subgraphs of the set{rg(SR,1),rg(SR,2),…,rg(SR,i)}, represented by ⋃j=1j=irg(SR,i)=rg(SR′⊆SR), is defined as a graph rg(SR′⊆SR) where
(i) the initial marking inrg(SR′⊆SR) is m0(SR);
(ii)∀k∈{1,2,…,i}, rg(SR,k) is added to rg(SR′⊆SR) by means of the following modifications of rg(SR,k):(ii.a)
the arcs starting from the initial marking ofrg(SR,k) are labeled “choice of Ri,”(ii.b)
the initial marking ofrg(SR,k) is substituted by the initial marking of rg(SR′⊆SR).The next proposition provides a methodology to build up the reachability graph of a set of alternative Petri nets by the assembly of all the choice subgraphs associated with the different alternative Petri nets of the set.In Stage5 of Section 7, a numerical example illustrates both Definition 17 and Proposition 18.Proposition 18.
LetSR={R1,R2,…,Rmr} be a set of alternative Petri nets:(5)⋃i=1mrrgSR,i=rgSR,where rg(SR,i) is the graph of reachable markings of the ith alternative Petri net and rg(SR) is the graph of reachable markings of a set of alternative Petri nets.Proof.
The graph of reachable markings of the set of alternative Petri nets, according to Definition14, complies with three properties, numbered (i), (ii), and (iii). Let us prove that ⋃i=1mrrg(SR,i), the union of the choice subgraphs of every alternative Petri net, complies with the same statements; hence, both constructions are the same.
(i) By Definition17 the initial marking of both constructions is m0(SR). From this initial marking in both cases, there are a set of arcs that represent the possible evolutions of the set of Petri nets by taking a certain decision that chooses an alternative Petri net and keeps the others in their initial marking. From now on, the different nodes of both graphs represent the reachable markings of certain alternative Petri nets in addition to the constant marking of the places that do not belong to this alternative Petri net but to the others in the set SR.
(ii) This condition is complied, since every node of⋃i=1mrrg(SR,i) includes the marking of every place of all the alternative Petri nets in SR.
(iii) This last condition is verified by⋃i=1mrrg(SR,i), since its construction is based on linking the independent evolution of every alternative Petri net to the initial marking. This resulting graph includes the constant marking of other places not belonging to the chosen alternative Petri net but taking part in the other Petri nets of SR. Moreover, the choice subgraphs of all the alternative Petri nets of SR are present in the ⋃i=1mrrg(SR,i); hence all the feasible evolutions of the alternative Petri nets can be found in the union of subgraphs, the same as in rg(SR).
The conclusion of the verification of all the statements of Definition14 in the union of choice subgraphs is that Proposition 18 is true.
The union of choice subgraphs verifies all the statements of Definition14. As a consequence, Proposition 18 is true.The following definition will describe how to construct the reachability graph of a compound Petri net. The aim of this definition is to state Theorem20, which will relate the graph of a compound Petri net with the reachability graph of an equivalent set of alternative Petri nets. Definition 19 is applied to a numerical example presented in Stage 6 of Section 7.Definition 19 (reachability graph of a compound Petri net).
Let us consider a compound Petri netRc and a set Svalstrα(Rc)={cvs1,cvs2,…,cvsmr} composed of the feasible combinations of values for the structural parameters of Rc.
Let us define a partitionSvalstrα(Rc) with the maximal cardinality |Svalstrα(Rc)|=mr, denoted by ∏q(Svalstrα(Rc)), as the collection of subsets ∏q(Svalstrα(Rc))={Svalstrα(R1),Svalstrα(R2),…,Svalstrα(Rmr)} such that ∀i∈{1,2,…,mr} it is verified that Svalstrα(Ri)={cvsi}.
The reachability graph ofRc will be constructed according to the following algorithm.
Step  1. The first node is m0(Rc).
Step  2. From the first node, an arc starts for every feasible evolution of Rc, labeled with the subset Svalstrα(Ri), chosen as a result of a decision. Every arc reaches a node displaying the new marking.
Step  3. From any node, other than the initial one, the reachability graph may continue. This continuation corresponds to the Petri net that results from the application of the choice of Svalstrα(Ri) to the compound Petri net Rc.


## 6. Equivalence of a Compound Petri Net and a Set of Alternative Petri Nets

The next theorem leads to a significant result. Given a compound Petri net, it is possible to obtain a set of alternative Petri nets by means of a partition of the set of feasible combinations of values for its structural parameters. This process is explained in Algorithm9, Proposition 10, and Theorem 11. Additionally, Theorem 20 proves that the graphs of reachable markings of both the compound Petri net and the associated set of alternative Petri nets are isomorphous. Moreover, they are the same for the significant marking. As a consequence, the compound Petri net and the set of alternative Petri nets are said to be equivalent. Theorem 20 is illustrated in a numerical example described in Stage 6 of Section 7.Theorem 20.
Let us consider a compound Petri netRc=P,T,pre,post,m0,Sα,Svalα, where Svalstrα(Rc) is the set of feasible combinations of values for the structural parameters of Rc.
Given a partition ofSvalstrα(Rc), ∏q(Svalstrα(Rc))={Svalstrα(R1),Svalstrα(R2),…,Svalstrα(Rmr)}, such that ∏qSvalstrαRc=mr>1
ByAlgorithm9 andProposition10, it is possible to obtain a set of Petri nets SR={R1,…,Rmr}, which according toTheorem11 is a set of alternative Petri nets.
In addition, it is possible to state that(i)
rg(Rc) is isomorphous to rg(SR);(ii)
rg(Rc)=rg(SR) for the significant marking.Proof.
This proof will be carried out by the principle of induction.
(a) The first step, also called beginning step, consists of describing the relation between the first node and the first set of arcs of the reachability graphs for bothRc and SR.
The initial marking ofRc is m0p1,m0p2,…,m0pnT.
In a general case, the marking of every place ofRc might be a (marking) parameter; hence it is possible to write [m0(p1),m0(p2),…,m0(pn)]T=[αk+1,αk+2,…,αk+n].
Moreover,|SR|=mr. For this reason, every place of Rc is replicated mr times, one for every alternative Petri net. Furthermore, the initial marking of SR is(6)m0p1,R1,m0p1,R2,…,m0p1,Rmrm0p2,R1,m0p2,R2,…,m0p2,Rmr⋯m0pn,R1,m0pn,R2,…,m0pn,Rmr.Given a place pi∈P(Rc), the different values for m0(pi,Rj), ∀j∈N, such that 1≤j≤mr, can be obtained from Svalαk+i={v1(αk+i),v2(αk+i),…,vuk+i(αk+i)} by the application of ∏qSvalstrαRc to Svalα(Rc). In other words, the initial markings of the places of every alternative Petri net derived from Rc are obtained by the assignment of the values of the marking parameters that correspond to the feasible combination of values associated with the alternative Petri nets by the partition of Svalstrα(Rc).
As a consequence, two possibilities may arise form0(pi,Rj):
(i)m0(pi,Rj)=vq(αk+i); hence, this marking presents a unique value; then it is not a parameter of Rj.
(ii)m0(pi,Rj)=αk+ij, where Sαk+ij={v1(αk+ij),v2(αk+ij),…,vuk+ij(αk+1j)}; hence, this marking is a parameter of Rj.
It is clear that any information present inm0(SR) is also present in m0(Rc) and vice versa. This information is classified by means of choices of a subset in ∏q(Svalstrα(Rc)) for Rc or choices of an alternative Petri net in SR. For this reason, both initial markings are equivalent.
From these initial markings, depart a series of arcs, representing the evolution conditions ofRc and SR, respectively.
( 1 ) The arcs starting in m0(Rc) are as follows:
(i) one arc for each choice of a subset in∏q(Svalstrα(Rc)), in case that by means of this choice the initial marking does not contain any parameter;
(ii) one arc for each choice of a subset in∏q(Svalstrα(Rc)) and for feasible value for the remaining marking parameters in m0(Rc), called αk+ij, in case that by means of this choice the initial marking contains at least one parameter.
( 2 ) On the other hand, the arcs starting in m0(SR) will be as follows:
(i) one arc for each choice of an alternative Petri net inSR, in case that by means of this choice the initial marking does not contain any parameter;
(ii) one arc for each choice of an alternative Petri net inSR and for feasible value for the remaining marking parameters in m0(SR), called αk+ij, in case that by means of this choice the initial marking contains at least one parameter.
The choice made in∏q(Svalstrα(Rc)) leads to the same Petri net as the choice made in SR; for this reason the arcs starting in m0 of both cases (Rc and SR) are the same and are labeled with the same information: choice, fired transition, and value selected for the remaining marking parameters.
As a consequence, the markings reached, whileSR evolves, are the same as the markings corresponding to equivalent evolutions of the alternative Petri net Rj. As it has already been mentioned, Rj corresponds to a certain choice made in ∏q(Svalstrα(Rc)). It is clear then that the structure of both reachability graphs will be the same so far (they are isomorphous) and that the markings of Rc will be included in the markings of SR (because the former are the same as the markings of the chosen alternative Petri net). Nevertheless, the markings of SR are not included in the markings of Rc since the markings of SR contain the initial marking of every nonchosen alternative Petri net. However, this difference in the marking of the states of SR and Rc is based on values that remain constant for any evolution of the resulting Petri net after the choice made on ∏q(Svalstrα(Rc)) or SR. This fact means that the markings are the same for the significant marking in every subgraph of the reachability tree that starts in the initial marking.
(b) Assumption step: let us consider that, given two equivalent paths inrg(Rc) and rg(SR), these paths are described by means of the following information:
i t h choice, assignment of values for the remaining marking parameters, sequence of transition firings.
Being equivalent paths, the information that describes them should be the same.
The paths lead to the following nodesmk, which are assumed to be equivalent:
(i) ForRc it is obtained that, in mk(Rc,choicei), the values selected for the remaining marking parameters must be added:(7)mkRc,choicei=mkp1,Rc,mkp2,Rc,…,mkpn,RcT.
(ii) ForSR the following marking is reached:(8)mkSR,choicei=mkp1,R1,mkp2,R1,…,mkpn,R1⋯mkp1,Ri-1,mkp2,Ri-1,…,mkpn,Ri-1mkp1,Ri,mkp2,Ri,…,mkpn,Rimkp1,Ri+1,mkp2,Ri+1,…,mkpn,Ri+1⋯mkp1,Rmr,mkp2,Rmr,…,mkpn,RmrT,where every row corresponds to a certain choice; hence, it is possible to relate the marking of the chosen alternative Petri net to the marking of the compound Petri net and the marking of the nonchosen alternative Petri nets with their initial marking:(9)mkSR,choicei=m0p1,R1,m0p2,R1,…,m0pn,R1…m0p1,Ri-1,m0p2,Ri-1,…,m0pn,Ri-1mkp1,Rc,mkp2,Rc,…,mkpn,Rcm0p1,Ri+1,m0p2,Ri+1,…,m0pn,Ri+1…m0p1,Rmr,m0p2,Rmr,…,m0pn,RmrT.Hence, because the paths are the same for both rg(Rc) and rg(SR), the reachability graphs are isomorphous, and because the significant markings are the same, both nodes are equivalent.
(c) Induction step: let us now analyze a descendant node to the previous one.
First of all, it has to be considered that the set of enabled transitions inRc and SR are the same (the transitions in SR derive from the transitions in Rc and they might even have the same name), since, by the assumption step, the marking of Rc is the same as the marking of the alternative Petri net and the incidence matrices of Rc and Ri are the same after an equivalent choice made from the initial marking.
After the previous considerations, it can be written that(10)mk+1Rc,choicei=mk+1p1,Rc,mk+1p2,Rc,…,mk+1pn,RcT.On the other hand, the marking of the ith alternative Petri net is the ith row of the marking of the set of alternative Petri nets SR, where the other rows have constant values that correspond to the initial markings of the rest of the alternative Petri nets:(11)mk+1Ri=mk+1p1,Ri,mk+1p2,Ri,…,mk+1pn,RiT.It is clear that mk+1(Rc,choicei)=mk+1(Ri); hence it is possible to state that(12)mk+1SR,choicei=mk+1R1⋯mk+1Ri-1mk+1Rimk+1Ri+1⋯mk+1Rmr=m0R1⋯m0Ri-1mk+1Rc,choiceim0Ri+1⋯m0Rmr.
Hence, it is possible to conclude that
(i)rg(Rc) is isomorphous to rg(SR);
(ii)rg(Rc)=rg(SR) for the significant marking.


## 7. Example of Application

In this section, an example is presented with the purpose of illustrating the concepts and processes described in this research paper. It is divided into a sequence of stages labeled with descriptive titles for better understanding.Stage 1 (transformation of a compound Petri net in a set of alternative Petri nets).
Let us consider the compound Petri net represented in Figure1, Rc, which verifies Definition 7. As it can be seen in Figure 1, Rc presents five parameters, Sα=α1,α2,α3,α4,α5}, and the first four of them are structural parameters, Sstrα=α1,α2,α3,α4, which belong to the incidence matrix. In Figure 1, the set of feasible values for the parameters, Svalα, has also been represented, as well as the set of feasible values for each structural parameter, Svalαi, where i∈{1,2,3,4}.
According to Algorithm9, it is possible to obtain a set of Petri nets from this compound Petri net.
The first step in the transformation of the compound Petri net is the choice of a partition of the set of feasible combination of values for the structural parameters of the compound Petri netSvalstrα={(2,2,0,0),(1,1,1,1)}.
As it can be seenSvalstrα=2; hence, only two possibilities arise to decompose this set.
The first option consists of making a single set from the partition. As a result, the same compound Petri net, rather than the original one, will be obtained. However, this solution is discarded because it does not meet the prerequisite of Proposition10, mr>1.
The case to be analyzed is the decomposition ofSvalstrα into two subsets:
∏ q ( S valstr α ( R c ) ) = S v a l s t r α R 1 , S v a l s t r α R 2, where SvalstrαR1=2,2,0,0 and Svalstrα(R2)={(1,1,1,1)}.
This partition verifies Definition8, since
(i)Svalstrα(R1)∪Svalstrα(R2)={(2,2,0,0)}∪{(1,1,1,1)}={(2,2,0,0),(1,1,1,1)}=Svalstrα(Rc);
(ii)Svalstrα(Ri) ≠ ⌀, 1≤i≤2;
(iii)Svalstrα(R1)∩Svalstrα(R2)=⌀={(2,2,0,0)}∩{(1,1,1,1)}.
On the other hand, every resulting Petri net can be obtained, according to Algorithm9 and Proposition 10, by means of Ri=P,T,pre,post,m0,Sα(Ri),Svalα(Ri), where Svalstrα(Ri)⊆∏q(Svalstrα(Rc)).
In other words,R1 will be obtained by (α1,α2,α3,α4)=(2,2,0,0), which once substituted in the incidence matrix of Rc will lead to the Petri net, whose incidence matrix is shown as follows:(13)WR1=t1t2-11α1=2-α2=-2α3=0-α4=0p1p2p3=t1t2-112-200p1p2p3.As it can be seen, R1 contains a row of zeros, which corresponds to an isolated place. That is to say, there is a place in R1 whose input and output arcs have weight zero. The marking of place p3 can neither change nor modify the marking of other places after firing of any of the transitions of the Petri net. As a consequence, it is possible to remove this isolated place obtaining a Petri net R1′ with a graph of reachable markings which is the same as the graph of R1, when only the marking of the connected places is considered (significant marking of R1).
Furthermore,m0[p1]=1 and Sα(R1)=⌀. In other words, in the compound Petri net the initial marking of p1 is a parameter, α5, since it can take two different values: Svalα5={1,2}. Nevertheless, when place p1 of R1 is considered, its initial marking can take a single value and, hence, it is not a parameter anymore.
Additionally,R2 is obtained by the assignment (α1,α2,α3,α4)=(1,1,1,1). These values can be substituted in the incidence matrix of Rc, hence, leading to the Petri net, whose incidence matrix is given as follows:(14)WR2=t1t2-11α1=1-α2=-1α3=1-α4=-1p1p2p3=t1t2-111-11-1p1p2p3.As it can be seen, R2 does not contain any isolated node. Moreover, m0[p1]=2 and Sα(R2)=⌀.
Figure2 shows R1 and R2, which, according to Theorem 11, constitute a set of alternative Petri nets, SR={R1,R2}.Stage 2 (graph of reachable markings of a set of alternative Petri nets).
The graph of reachable markings ofSR, as presented in Definition 14, is given by the application of every feasible sequence of transition firing to the initial marking of SR for every feasible choice of the alternative Petri nets.
Figure3 depicts the reachability graph of the set of alternative Petri nets SR={R1,R2}, also called graph of reachable markings. Every reachable marking is represented by a box containing the marking of the places of SR, which are the places of P=P1∪P2. Notice that P1 is the set of places of the alternative Petri net R1, while P2 is the set of places of R2.
The arrangement of the markings in any of the boxes (vertices) of the reachability graph ofSR, depicted in Figure 3, corresponds to (15)mp1R1,mp2R1,mp3R1,mp1R2,mp2R2,mp3R2.The different markings or states are linked by means of arrows (directed arcs), which represent the evolution of the Petri net system from one state to another one after the firing of the transitions written next to the arrow. These transitions that label the arrows are associated with the alternative Petri net to which they belong.
The initial marking can lead to different subgraphs according to the choice of one or another alternative Petri net as solution of a decision problem. For this reason, every arc starting in the initial marking is also labeled with the corresponding decision.
Once a decision to choose an alternative Petri net is made, the marking that does not vary in any state of the reachability graph is written between round brackets in the boxes (vertices) of the graph. This absence of variation in the marking of certain places can be due to the fact that a set of places belong to nonchosen alternative Petri nets in a subgraph or because it corresponds to an isolated place. Both situations appear inm1(R1) and, therefore, they have been represented in different brackets.Figure 3
Graph of reachable markings of a set of alternative Petri nets.Stage 3 (choice subgraphs of the set of alternative Petri nets).
The different choice subgraphs of the reachability graph of a set of alternative Petri nets,SR={R1,R2}, are shown in this Stage 3.
LetC={1,2} be a set of natural numbers, such that |C|=|SR|. It is possible to create a bijection f: SR↔C, where f(R1)=1 and f(R2)=2.
Following Definition15, two choice subgraphs can be considered, as it can be seen in Figure 4.
The 1st choice subgraph is obtained from the selection ofR1 as solution of a decision problem associated with SR, while the 2nd choice subgraph is related to R2.Figure 4
Choice subgraphs of the alternative Petri netR1 and R2.Stage 4 (reachability graph of the Petri nets belonging to a set of alternative Petri nets).
Once the choice subgraphs of all the Petri nets belonging toSR, set of alternative Petri nets, have been represented, this stage deals with the graphs of reachable markings of these same alternative Petri nets. This last representation is independent of the fact that they belong to a set of alternative Petri nets. The only difference between both representations (Figures 4 and 5) is the removal, in the latter, of the marking of the places that do not belong to the Petri net but belong to the other Petri net (Petri nets in a more general case) of SR.Figure 5
Reachability graphs of the Petri netsR1 and R2.Figure5 shows the reachability graphs of R1 and R2. It is interesting to compare them with the choice subgraphs presented in Figure 4.Stage 5 (union of choice subgraphs of a set of alternative Petri nets).
In this stage, the union of the choice subgraphs of the alternative Petri nets ofSR={R1,R2}, developed in Stage 3, is performed. Definition 17 describes formally this union.
The first step consists of labeling the arcs that start in the initial marking of the subgraphs with “choice ofRi.” In the labels, i is the ordinal associated with the alternative Petri net whose subgraph is being developed. The result of this step can be seen in Figure 6.
The second step is to define the initial marking ofSR, which is m0(SR)=[100200]T, and to substitute the first marking of every choice subgraph by m0(SR). The result of this process is shown in Figure 7.
As a result of this union, it is possible to verifyrg(SR)=⋃i=12rg(SR,i) as stated in Proposition 18. Notice that the left side of the previous equation refers to the graph of reachable markings of a set of alternative Petri net, SR (Figure 3), while the right side refers to the union of choice subgraphs of reachable markings of the individual alternative Petri nets belonging to SR; that is, ⋃i=12rg(SR,i)=rg(SR,1)∪rg(SR,1) (Figure 7). Comparing Figure 3 with Figure 7, it is possible to see that both reachability graphs are the same. This result is proven in Proposition 18.Figure 6
First step in the union of the choice subgraphs ofR1 and R2, alternative Petri nets.Figure 7
Union of the choice subgraphs ofR1 and R2.Stage 6 (construction of the reachability graph of a compound Petri net).
LetRc be the compound Petri net described in Stage 1 of this section and depicted in Figure 1.
In order to build up the graph of reachable markings of this compound Petri net, calledrg(Rc), the three steps described in Definition 19 are developed.
Step  1. The first node of the reachability graph is m0(Rc)=100T.
Step  2. From this initial marking, there are two possible choices to be made, regarding the set of feasible combination of values for the structural parameters.
Step  2.1 (choice 1: (α1,α2,α3,α4,α5)=(2,2,0,0,1)). With this choice α5=1; hence, only t1 is enabled to fire, allowing the Petri net to evolve to a new state. As a consequence, there will be an arc starting in m0(Rc) with the labels “choice 1,” “α5=1,” and “t1.”
Step  2.2 (choice 2: (α1,α2,α3,α4,α5)=(1,1,1,1,2)). With this choice α5=2; hence, only t1 is enabled to fire, allowing the Petri net to evolve to a new state. As a consequence there will be an arc starting in m0(Rc) with the labels “choice 2,” “α5=2,” and “t1.”
The new states reached from the initial one are named asmi(choice,α5), where i is an ordinal number corresponding to the sequence of different markings reached under a particular combination of values for the parameters of Rc. On the other hand,choice is a natural number associated with the choice performed for the combination of values for the structural parameters. Finally, α5 is the specific value of the marking parameter α5 associated with this evolution of the Petri net.
The result of Step  2 can be seen in Figure8.
Step  3. From the markings labeled “m1(1,1)” and “m1(2,2)” it is possible to explore the feasible evolutions of the Petri net Rc, where every node inherits the choice and value of α5 of the first arc from which it has evolved.
In Figure9 it is possible to find the result of Step  3 in the construction of the reachability graph of the compound Petri net Rc.
At this point of the example, it is possible to compare the reachability graph of the compound Petri net,Rc(Figure 9), and the reachability graph of the set of alternative Petri nets, SR(Figure 3), obtained from Rc in Stage 1.
It can be seen that both graphs are isomorphous, according to Definition12. On the other hand, the marking of every pair of nodes in both graphs, located in the same position, bears the same information concerning the significant marking. The conclusions of this comparison verify Theorem 20.Figure 8
Steps  1 and 2 in the construction of the reachability graph ofRc.Figure 9
Reachability graph of the compound Petri netRc.


## 8. Conclusions

The present paper has focused on two formalisms, based on the Petri net paradigm, commonly used for describing discrete event systems with alternative structural configurations. This is an issue which has an immediate application in the design of discrete event systems. The mentioned formalisms are the parametric Petri nets and a set of alternative Petri nets. In order to specify the particular case of parametric Petri nets that contain parameters in their structure, that is, incidence matrices, this formalism has been defined as compound Petri nets. Formal definitions and analysis of the transformation of a compound Petri net into an equivalent set of alternative Petri nets are provided, with the purpose of profiting from the advantages of both formalisms at different stages of their application to the design of a discrete event system: modeling, structural analysis, performance evaluation, simulation, optimization, or decision making. This analysis has been based on the study of the graph or reachable markings. For example, the analysis of the graph of reachable markings is the methodology used to prove the equivalence between a compound Petri net and a set of alternative Petri nets obtained from the former by the application of an algorithm, also described in the paper.An interesting advantage of the proposed methodology consists in the possibility of automating some stages of the design process of a discrete event system, for example,(a)
the modeling of alternative structural configurations with common features, which might be carried out easily with one of both formalisms;(b)
the selection of one of the alternative structural configurations by means of a decision-making methodology, such as a metaheuristic-guided search in the pool of alternative configurations; this operation can be applied to optimize an objective function that quantifies the objectives of the design process.The main drawbacks or challenges of the proposed methodology are as follows:(a)
knowing in advance which one of the formalisms is best fitted for every stage of the decision process;(b)
knowing in advance which decisions to make in the transformation process, such as which partition of the set of feasible combination of values for the structural parameters of the original compound Petri net is the best to obtain an efficient set of alternative Petri nets for a certain stage of the design process.Two of the main future research lines are the application of the results presented in this paper to a wide range of application cases, as well as mitigating the effects of the mentioned drawbacks of this approach.Additionally, the authors of the present work expect that this research will help in consolidating the feasibility and applicability of model transformation for representing DES with alternative structural configurations. As mentioned before, these transformations may allow profiting from the advantages of different formalisms to be applied in optimization processes based on simulation. In particular, the equivalence between compound Petri nets and a set of alternative Petri nets might contribute to the applicability of the search of efficient and compact models for reducing the computational requirements of simulation of DES. Fast simulation is a key factor in the development of efficient decision support systems for industrial and logistic systems.



---

*Source: 5341346-2018-03-04.xml*