Quantitative analysis of continuous weighted marked graphs

This paper deals with the computation of the asymptotic firing rate vector and the stationary marking of continuous weighted marked graphs under infinite servers semantics. The continuous weighted marked graphs are a particular class of continuous Petri net where each place has exactly one input and one output transition. First, we give an explicit formula to compute the asymptotic firing rate vector of transitions using the structure of the given net. Then, under the assumption that there exists only one critical circuit in the strongly connected continuous neutral weighted marked graphs, an original approach to compute the vector of stationary marking is presented. Finally, an application to a flexible manufacturing system is given.     

First-order hybrid Petri nets. An application to distributed manufacturing systems

In this paper we consider Hybrid Petri Nets (HPNs), a particular formalism that combines fluid and discrete event dynamics. We first provide a survey of the main HPN models that have been presented in the literature in the last decades. Then, we focus on a particular HPN model, namely the First-Order Hybrid Petri Net (FOHPN) model, whose continuous dynamics are piece-wise constant. Here the problem of designing an optimal controller simply requires solving on-line an appropriate linear integer programming problem. In this paper we show how FOHPNs can efficiently represent the concurrent activities of Distributed Manufacturing Systems (DMS), and some interesting optimization problems are also solved via numerical simulation.     

Representation and analysis of behavior for multiprocess systems by using stochastic Petri nets

This paper proposes a new approach to visually represent the behavior of multiprocess in a computer network system using stochastic Petri net (SPN) and an aggregate approach of SPN and Markov renewal process (MRP) to conduct behavior analysis and performance evaluation for the system. SPN is employed because of its highly visual nature that can give insight into the nature of the modeled system and because of its expressive power for an exponentially distributed event. In order to increase the analytical power of the SPN model, MRP is introduced and an embedded transference probability matrix is applied to obtain the steady-state solution of the model, from which it is possible to obtain automatically the performance measures of the multiprocess computer network system.     

A new stochastic Petri net model and its applications to logistics systems

This is a summary of the author’s PhD thesis supervised by Lionel Amodeo and Hoaxun Chen and defended on 29 November 2005 at the Université de Technologie de Troyes (France). The thesis is written in French and is available from the author upon request. This work deals with a new stochastic Petri net model and its applications for modeling and studying logistics systems and more generally discrete event dynamic systems.      

Rapid and modular prototyping-based Petri nets and distributed simulation for manufacturing systems

This paper presents an approach to simulate and implement by stepwise refinement the whole manufacturing system (MS) by means of distributed simulation. This approach is based on the use of different classes of Petri nets to model different levels of a manufacturing system. Furthermore these classes may match the abstraction levels of a high-level Petri net used to model the MS. Each level can be simulated on a processor or a cluster of processors which can communicate between themselves using a network. The main contribution is to give the opportunity to combine simulation, performance evaluation and emulation. The emulation means that a part of the system can be run in real time while the other part is simulated. Moreover based on the abstraction levels of high-level Petri nets, subsystems can be integrated step-by-step from the design stage to the implementation one, allowing inter-changeability between simulated components and real-time physical systems. This approach is achieved by defining a simulation engine which involves a local simulator, an emulator and an interface to the physical process. Criteria are defined to use an emulator or a local control software for a physical process as a logical process for the conservative distributed simulation.     

SimHPN: A MATLAB toolbox for simulation, analysis and design with hybrid Petri nets

This paper presents a MATLAB embedded package for hybrid Petri nets called SimHPN. It offers a collection of tools devoted to simulation, analysis and synthesis of dynamical systems modeled by hybrid Petri nets. The package supports several server semantics for the firing of both, discrete and continuous, types of transitions. Besides providing different simulation options, SimHPN offers the possibility of computing steady state throughput bounds for continuous nets. For such a class of nets, optimal control and observability algorithms are also implemented. The package is fully integrated in MATLAB which allows the creation of powerful algebraic, statistical and graphical instruments that exploit the routines available in MATLAB.     

Numerical investigation of finite-source multiserver systems with different vacation policies

Systems with vacations are usually modeled and analyzed by queueing theory, and almost all works assume that the customer source is infinite and the arrival process is Poisson. This paper aims to present an approach for modeling and analyzing finite-source multiserver systems with single and multiple vacations of servers or all stations, using the Generalized Stochastic Petri nets model. We show how this high level formalism, allows a simple construction of detailed and compact models for such systems and to obtain easily the underlying Markov chains. However, for real vacation systems, the models may have a huge state space. To overcome this problem, we give the algorithms for automatically computing the infinitesimal generator, for the different vacation policies. In addition, we develop the formulas of the main exact stationary performance indices. Through numerical examples, we discuss the effect of server number, vacation rate and vacation policy on the system’s performances.     

Production scheduling with alternative process plans

This paper deals with a scheduling problem with alternative process plans that was motivated by a production of wire harnesses where certain parts can be processed manually or automatically by different types of machines. Only a subset of all the given activities will form the solution, so the decision whether the activity will appear in the final schedule has to be made during the scheduling process. The problem considered is an extension of the resource constrained project scheduling problem (RCPSP) with unary resources, positive and negative time-lags and sequence dependent setup times. We extend classic RCPSP problem by a definition of alternative branchings, represented by the Petri nets formalism allowing one to define alternatives and parallelism within one data structure. For this representation of the problem, an integer linear programming model is formulated and the reduction of the problem, using time symmetry mapping, is shown. Finally, a heuristic algorithm based on priority schedule construction with an unscheduling step is proposed for the nested version of the problem and it is used to solve the case study of the wire harnesses production.     

Some open problems in the design and use of modern production systems

During the past two decades, manufacturing systems have moved towards automation, integration and modularity. These trends will certainly continue in the future due to the constraints of the market and to evolution of resources and worker requirements. As a consequence, the design and use of manufacturing systems are increasingly expensive. Numerous methods and tools have been developed to face up to this situation, but some complementary aids could be provided for designers and manufacturing engineers. The goal of this paper is to present important open problems whose solutions could certainly significantly improve the design and use of modern production systems.     

Cyclic scheduling for F.M.S.: Modelling and evolutionary solving approach

This paper concerns the domain of flexible manufacturing systems (FMS) and focuses on the scheduling problems encountered in these systems. We have chosen the cyclic behaviour to study this problem, to reduce its complexity. This cyclic scheduling problem, whose complexity is NP-hard in the general case, aims to minimise the work in process (WIP) to satisfy economic constraints. We first recall and discuss the best known cyclic scheduling heuristics. Then, we present a two-step resolution approach. In the first step, a performance analysis is carried out; it is based on the Petri net modelling of the production process. This analysis resolves some indeterminism due to the system’s flexibility and allows a lower bound of the WIP to be obtained. In the second step, after a formal model of the scheduling problem has been given, we describe a genetic algorithm approach to find a schedule which can reach the optimal production speed while minimizing the WIP. Finally, our genetic approach is validated and compared with known heuristics on a set of test problems.     

Stochastic petri net analysis of finite-population vacation queueing systems

We consider queueing systems in which the server occasionally takes a vacation of random duration. The vacation can be used to do additional work; it can also be a rest period. Several models of this problem have been analyzed in the past assuming that the population of the system is infinite. Similarly, it is generally assumed that the capacity of the system is infinite. In this paper we show how the finite-population system can be modeled by the stochastic Petri net. We also extend the model to the finite-capacity system. This research was sponsored by the SDIO Innovative Science and Technology Office and was managed by the Office of Naval Research under grant N3014-88-K-0623.     

A Petri net approach to the modelling and analysis of flexible manufacturing systems

In this paper we present an approach for modelling and analyzing flexible manufacturing systems (FMSs) using Petri nets. In this approach, we first build a Petri net model (PNM) of the given FMS in a bottom-up fashion and then analyze important qualitative aspects of FMS behaviour such as existence/absence of deadlocks and buffer overflows. The basis for our approach is a theorem we state and prove for computing the invariants of the union of a finite number of Petri nets when the invariants of the individual nets are known. We illustrate our approach using two typical manufacturing systems: an automated transfer line and a simple FMS.A shorter version of this paper was presented at the 1st ORSA/TIMS Special Interest Conference on FMSs, University of Michigan, Ann Arbor, August 1984.     

Estimation of the production frequencies for manufacturing systems

Email: dimitri.lefebvre{at}utbm.fr This work deals with the production frequencies estimation formanufacturing systems by measurement of the buffers content.The considered systems are modelled by continuous Petri nets.The estimation problem has exact and approximated solutionsthat are described. In the case of approximated solutions, theestimation error is also valued. At last, when the set of solutionscontains several elements, the Petri net evolution equationis completed to give one unique solution.     

Sequence of decisions on discrete event systems modeled by Petri nets with structural alternative configurations

The management of certain systems, such as manufacturing facilities, supply chains, or communication networks implies assessing the consequences of decisions, aimed for the most efficient operation. This kind of systems usually shows complex behaviors where subsystems present parallel evolutions and synchronizations. Furthermore, the existence of global objectives for the operation of the systems and the changes that experience the systems or their environment during their evolution imply a more or less strong dependence between decisions made at different time points of the life cycle. This paper addresses a complex problem that is scarcely present in the scientific literature: the sequences of decisions aimed for achieving several objectives simultaneously and with strong influence from one decision to the rest of them. In this case, the formal statement of the decision problem should take into account the whole decision sequence, making impractical the solving paradigm of “divide and conquer”. Only an integrated methodology may afford a realistic solution of such a type of decision problem. In this paper, an approach based on the formalism of the Petri nets is described, several considerations related to this problem are presented, a solving methodology based on the previous work of the authors, as well as a case-study to illustrate the main concepts.