A domain-specific modeling language called Healthcare System Specifications (HSS) was proposed for developing clinical pathways. This high-level language was defined as a Unified Modeling Language (UML) profile. It was also proposed a model to model transformation which obtains from pathways HSS specification, a Stochastic Well-formed Net (SWN). The SWN has the capacity to model the complex healthcare system, however, it is hard to perform qualitative and quantitative analysis in this kind of nets. This paper presents a set of relaxations, abstractions and modifications to be applied in the SWNs in order to obtain subclasses of Petri Nets in which formal analysis can be performed. In particular, we obtain the classes of S4PR and DSSP nets. The first one considers the shared resources of the hospital while the second class allows managing the interchange of information between clinical pathways.

In this paper, the scheduling problem of elective patients in the Orthopedic Department of the “Lozano Blesa” Hospital in Zaragoza is considered. This problem takes into account two contradictory objectives: obtain a given occupation rate of the Operation Room (OR) and respect as much as possible the preference order of the patients in the waiting list. Three different mathematical models are discussed: 1) Quadratic Assignment Problem (QAP); 2) a Mixed Integer Linear Programing (MILP) model; and 3) Generalized Assignment Problem (GAP). These models solve combinatorial problems with a high computational cost; for this reason, heuristic methods have been used to solve large instances. In particular, 1) a meta-heuristic Genetic Algorithm (GA) for the QAP; 2) a heuristic Steepest Descent Multiplier Adjustment Method (SDMAM) for the GAP; and 3) a heuristic iterative method for MILP. Finally, the models and the heuristics are compared according to the occupation rate and the preference order criteria.

This paper considers the operation scheduling and planning of elective patients in the Orthopedic Department of the “Lozano Blesa” Hospital in Zaragoza. We assume an ordered list of patients that should be planned for surgery in two available rooms, each room being possible to be used for a specific duration per day. Based on the average durations of surgeries that have been computed by considering historical information, we propose a Mixed Integer Linear Programming (MILP) problem to obtain a specific utilization rate per room. We have developed a Decision Support System (DSS) base on MILP that helps doctors in their daily planning. The results are tested on some real data from the hospital and some simulation results are provided.

A performance measure which is often used when evaluating systems modeled by Petri nets is the throughput of a transition in steady-state, i.e., the number of firings per unit time in permanent regime if it exists. When fluid Petri nets are considered, such measure corresponds to the continuous flow of the transitions. Its value depends on the firing rates associated to transitions and also on the initial marking of the net. In this work two properties of the steady-state throughput, monotonicity and continuity, are studied under firing rate and initial marking variations. It is shown that in certain cases there exists a kind of duality between both type of changes, that is, some property eventually holds no matter if firing rate or initial marking is varied. These results are obtained in a structural framework using the P-flows, T-flows, and configurations of the net model.

A Markovian Petri net (MPN) is a stochastic discrete event system (DES) frequently used for qualitative analysis, performance evaluation, and control purposes. In the past, the fluidization has been proposed in different DES formalisms (Markov chains, queuing networks, stochastic Petri nets (PNs), stochastic process algebra, etc.) as a relaxation technique for avoiding the state-explosion problem. Following that kind of approach, in this paper, a new hybrid PN model is defined as a partial relaxation of an original MPN. Nevertheless, it is shown through a simple example that such a partial relaxation can be worse than a full relaxation (given by a fully continuous PN), if certain conditions are not meet. Therefore, the rest of this paper is devoted to analyze the approximation of MPNs by means of hybrid PNs, where both the discrete and the continuous parts are stochastic. It is demonstrated that under certain conditions, the average and probability distribution function of the marking of a MPN can be approximated by those of the marking of the corresponding hybrid PN. The key point is to recognize the variability in behavior due to the time stochasticity. In some sense, a kind of functional central limit approach is obtained in a hybrid context.

This paper approaches the deadlock prevention problem for the well known class of S3PR used in Resource Allocation Systems. The proposed control policy is based on inhibitor arcs and the new Petri net class will be called S3PR2. The liveness characterization of this new class is given. The main application of the approach is to robot motion for a team of robots evolving in a partitioned environment with some limited capacity regions. In a previous work it is shown that the sets of trajectories for robots can be modeled by a particular S3PR and the deadlock-free execution has been solved using a centralized approach. Based on the results in this paper, we show that a decentralized control law for robots can be implemented.

In this paper, we consider the decentralized fault diagnosis problem of discrete event systems modeled by time Petri nets (TPNs). Our approach is based on the fault diagnosis graph which is obtained from the time reachability graph by removing the irrelevant nodes. A coordinator computes the diagnosis states of the global system using information from subsystems. Local systems send small amounts of information to the coordinator for the computation of diagnosis states of the global system.

When discrete-event systems are used to model systems with a large number of possible (reachable) states, many problems such as simulation, optimization, and control, may become computationally prohibitive because they require some enumeration of such states. A common way to effectively address this issue is fluidization. The goal of this paper is that of studying the effect of fluidization on fault diagnosis. In particular, we focus on the purely logic Petri net (PN) model that results in the untimed continuous PN model after fluidization. In accordance to most of the literature on discrete-event systems, we define three diagnosis states, namelyN,U, andF, corresponding respectively to no fault, uncertain, and fault state. We prove that, given an observation, the resulting diagnosis state can be computed solving linear programming problems rather than integer programming problems as in the discrete case. The main advantage of fluidization is that it enables to deal with much more general PN structures. In particular, the unobservable subnet needs not be acyclic as in the discrete case. Moreover, the compact representation of the set of consistent markings using convex polytopes can be seen in some cases as an improvement in terms of computational complexity.

Fluidization constitutes a relaxation technique to study discrete event systems through a continuous approximated model, thus overcoming the state explosion problem. In this paper, the approximation of the average marking of Markovian Petri nets by the marking of the corresponding timed continuous Petri nets, under infinite-server semantics, is studied. This represents a sort of legitimization for the use of a continuous Petri net as a relaxation of a discrete Petri net. The main contribution is the addition of Gaussian noise in order to improve the approximation when the number of active servers (enabling degree) is large. The improvement is more evident when the system evolves “close” to the boundary of regions. In such a case, not only the expected value but also the probability distribution function of the marking may be approximated.

This paper deals with fault detection of manufacturing systems modeled by Petri nets. We show that the theoretical results obtained for continuous Petri nets allow us to treat with systems that are intractable using the theory developed for discrete Petri nets. In particular systems in which the unobservable part contains cycles can be studied. On the other hand, only three diagnosis states can be defined making impossible the splitting of the uncertain state into two different states, to obtain different degrees alarm for the uncertainty.

In this paper, we develop an automated framework for formal verification of timed continuous Petri nets (ContPNs). Specifically, we consider two problems: (1) given an initial set of markings, construct a set of unreachable markings and (2) given a Linear Temporal Logic (LTL) formula over a set of linear predicates in the marking space, construct a set of initial states such that all trajectories originating there satisfy the LTL specification. The starting point for our approach is the observation that a ContPN system can be expressed as a Piecewise Affine (PWA) system with a polyhedral partition. We propose an iterative method for analysis of PWA systems from specifications given as LTL formulas over linear predicates. The computation mainly consists of polyhedral operations and searches on graphs, and the developed framework was implemented as a freely downloadable software tool. We present several illustrative numerical examples.

This paper is devoted both to the study of observability criteria and the design of observers in the continuous Petri net setting. The concept of structural observability, regarding the possibility of estimating the marking of places, i.e., the system state, for any speed of the transitions is introduced and studied for the subclass of join-free Petri nets (JF). For non-join-free Petri nets, conditions to compute suitable state estimates are established. The proposed observers are piecewise linear systems that assure the continuity of the estimate even when a switch occurs. The system simulation may allow us to estimate even the unobservable space of the net system during a given time period.

This paper addresses several questions related to the control of timed continuous Petri nets under infinite server semantics. First, some results regarding equilibrium states and control actions are given. In particular, it is shown that the considered systems are piecewise linear, and for every linear subsystem the possible steady states are characterized. Second, optimal steady-state control is studied, a problem that surprisingly can be computed in polynomial time, when all transitions are controllable and the objective function is linear. Third, an interpretation of some controllability aspects in the framework of linear dynamic systems is presented. An interesting finding is that noncontrollable poles are zero valued. Note to Practitioners-Petri nets are a well-known formalism for the analysis and design of discrete event systems. Due to the state- explosion problem some kind of relaxation is frequently used. In particular, fluidification is a classical approximation technique that it is usually employed in the analysis of manufacturing or logistic systems, specially when heavily loaded. This work focuses on timed continuous Petri nets which are a fluidified version of discrete Petri nets with timing associated to transitions (representing stations with servers that perform activities). Furthermore, transitions have associated control actions which can slow down the corresponding activities from an initial maximum speed, that depends on the marking, and possibly halt them completely. The steady-state control problem of this kind of system and some invariant-dynamical properties are addressed.

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

Forrester diagrams (FD) and Petri nets (PN) are formalisms introduced in the sixties to model complex systems. This paper explores similarities and differences between FDs and the continuous relaxation of the originally discrete PNs. Historically speaking, the approaches were quite different: the PNs paradigm was introduced at a very abstract level, without timing interpretation, while FDs led to a modelling methodology where the systematic simulation of a set of differential equations was the goal. Strict flow conservation around valves, non explicit fork and join operations, separation of information and material flows, are peculiarities of FDs. In PN models the existence of global conservation laws is a potential for structural analysis.

Asynchronously communicating stochastic modules (SAM) are Petri nets that can be seen as a set of modules that communicate through buffers, so they are not (yet another) Petri net subclass, but they complement a net with a structured view. This paper considers the problem of exploiting the compositionality of the view to generate the state space and to find the steady-state probabilities of a stochastic extension of SAM in a net-driven, efficient way. Essentially we give an expression of an auxiliary matrix, G, which is a supermatrix of the infinitesimal generator of a SAM. G is a tensor algebra expression of matrices of the size of the components for which it is possible to numerically solve the characteristic steady-state solution equation /spl pi//spl middot/G=0, without the need to explicitly compute G. Therefore, we obtain a method that computes the steady-state solution of a SAM without ever explicitly computing and storing its infinitesimal generator, and therefore without computing and storing the reachability graph of the system. Some examples of application of the technique are presented and compared to previous approaches.

Scheduling problems are very important in order to optimise the behaviour of discrete events dynamic systems. Nevertheless, the computation of scheduling policies turns out to be NP-hard in most interesting cases in practice. The purpose of the paper is to apply transformation/reduction rules to the solution of the scheduling problem. These kind of rules have already been applied to the analysis of autonomous Petri nets or to program coding optimisation by means of time Petri nets. Here, reduction is intended to preserve the existence of at least one optimal solution for the scheduling problem. In many practical cases, transformation/reduction allows us to alleviate the computational problem of synthesising an optimal schedule. We show its usefulness by means of an illustrative example.

Deterministically synchronized sequential processes (DSSP) are a subclass of Petri nets, well suited for the methodical construction of models of concurrent systems where several agents cooperate through asynchronous message passing, In this paper, DSSP are presented, illustrating their usability in manufacturing systems. They are compared to other more restrictive subclasses of Petri nets used for similar purposes. In spite of being more expressive, DSSP still enjoy many strong analytical results, some of which are derived and illustrated in the paper.

Among discrete event systems, those exhibiting concurrency are especially challenging, requiring the use of formal methods to deal with them. Petri nets are a well-established such formalism. The structure theory aims at overcoming the state space explosion problem, inherent to the analysis of concurrent systems, by bridging structural and behavioral properties. To date, this has been successfully achieved mainly for some subclasses of ordinary nets. However weights are a modeling convenience in many situations. In this paper we study a formal model for a subclass of concurrent systems with bulk services and arrivals which structurally avoids conflicts. Structural results and techniques for dealing with them are introduced. These include structural conditions on properties of correct behavior and a unified framework for checking general behavioral properties by reasoning solely on the structure.

A general iterative technique for approximate throughput computation of stochastic strongly connected marked graphs is presented. It generalizes a previous technique based on net decomposition through a single input-single output cut, allowing the split of the model through any cut. The approach has two basic foundations. First, a deep understanding of the qualitative behavior of marked graphs leads to a general decomposition technique. Second, after the decomposition phase, an iterative response time approximation method is applied for the computation of the throughput. Experimental results on several examples generally have an error of less than 3%. The state space is usually reduced by more than one order of magnitude; therefore, the analysis of otherwise intractable systems is possible.>

Embedded in the divide-and-conquer paradigm, the authors introduce a technique for iterative analysis of stochastic marked graphs. The basic idea is to split the original net system into two parts. It is demonstrated on a model which represents the implementation of a Kanban manufacturing system. From the stochastic perspective, the throughput computation on partial subnets uses a response time approximation. Experimental results on several examples were usually pessimistic with respect to the throughput with an error of less than 3-5%. The computational effort was usually reduced by more than one or two orders of magnitude.>

Ergodicity and throughput bound characterization are addressed for a subclass of timed and stochastic Petri nets, interleaving qualitative and quantitative theories. The nets considered represent an extension of the well-known subclass of marked graphs, defined as having a unique consistent firing count vector, independently of the stochastic interpretation of the net model. In particular, persistent and mono-T-semiflow net subclasses are considered. Upper and lower throughput bounds are computed using linear programming problems defined on the incidence matrix of the underlying net. The bounds proposed depend on the initial marking and the mean values of the delays but not on the probability distributions (thus including both the deterministic and the stochastic cases). From a different perspective, the considered subclasses of synchronized queuing networks; thus, the proposed bounds can be applied to these networks.>

This paper discusses the design of the coordination subsystem of a Flexible Manufacturing System (FMS) and its integration into the integrated control system of the FMS. The approach adopted is based on the use of high level Petri nets (colored Petri nets) for the subsystem modeling, its qualitative and quantitative analysis and its software implementation. The design of the real time scheduling subsystem as an expert system is proposed. The interaction between the coordination subsystem and the local controllers and the scheduling subsystem is done by using a terminology based on the colors of the coordination model.