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.     

A Petri Net based algorithm for minimizing total tardiness in flexible manufacturing systems

Petri Nets have been extensively used for modeling and simulating of the dynamics of flexible manufacturing systems. Petri Nets can capture features such as parallel machines, alternative routings, batch sizes, multiplicity of resources, to name but a few. However, Petri Nets have not been very popular for scheduling in manufacturing due to the Petri Net “state explosion” combined with the NP-hard nature of many of such problems. A promising approach for scheduling consists of generating only portions of the Petri Net state space with heuristic search methods. Thus far, most of this scheduling work with Petri Nets has been oriented to minimize makespan. The problem of minimizing total tardiness and other due date-related criteria has received little attention. In this paper, we extend the Beam A^* Search algorithm presented in a previous work with capability to handle the total tardiness criterion. Computational tests were conducted on Petri Net models of both flexible job shop and flexible manufacturing systems. The results suggest that the Petri Net approach is also valid to minimize due date related criteria in flexible systems.     

Petri net modelling of biological regulatory networks

The complexity of biological regulatory networks often defies the intuition of the biologist and calls for the development of proper mathematical methods to model their structures and to delineate their dynamical properties. One qualitative approach consists in modelling regulatory networks in terms of logical equations (using either Boolean or multi-level discretisations). The Petri Net (PN) formalism offers a complementary framework to analyse the dynamical behaviour of large systems, either from a qualitative or from a quantitative point of view.

Our proposal consists in articulating the logical approach with the PN formalism. In a previous work, we have already defined a systematic re-writing of Boolean regulatory models into a standard PN formalism. In this paper, we propose a rigorous and systematic mapping of multi-level logical regulatory models into specific standard Petri nets, called Multi-level Regulatory Petri Nets (MRPNs). We further propose some reduction strategies. Consequently, the resulting models become amenable to the algebraic and computational analyses used by the PN community.

To illustrate our approach, we apply it to a multi-level logical model of the genetic switch controlling the lysis-lysogeny decision in the lambda bacteriophage.     

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.     

A technique for on-line sensitivity analysis of flexible manufacturing systems

The recent perturbation analysis approach to discrete event systems is applied to flexible manufacturing systems (FMS). While analytic (queueing) models are useful in preliminary design of such systems, they are not accurate enough at the detailed design/operation stage. Thus, experimentation on detailed simulations or on the actual system has been the way to optimize system performance. Perturbation analysis allows us to derive the sensitivity of system performance, with respect to several design/operating parameters, by observing a single experiment (and without having to actually alter the parameters — often a costly operation). Thus, observation of one experiment can give accurate directions for the improvement of several parameter values. Here we give a simulation example illustrating how perturbation analysis could be used on-line on an FMS to improve its performance, including reducing its operating cost. Experimental results are also presented validating the estimates obtained from this technique.Work supported by U.S. Office of Naval Research Contracts N00014-75-C-0648 and N00014-79-C-0776, and NSF Grant ENG78-15231, at Harvard University.A preliminary version of this paper appeared in the Proc. 1st ORSA/TIMS Conf. on Flexible Manufacturing Systems, August 1984. This version includes two appendices, which relate to implementation of the technique described in the main body of the paper.     

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.      

Experimental investigation of real-time scheduling in flexible manufacturing systems

This paper presents a new two-phase (TP) approximate method for real-time scheduling in a flexible manufacturing system (FMS). This method combines a reduced enumeration schedule generation algorithm with a 0–1 optimization algorithm. In order to make the combined algorithm practicable, heuristic rules are introduced for the selection of jobs to be scheduled. The relative performance of the TP method vis-a-vis conventional heuristic dispatching rules such as SPT, LPT, FCFS, MWKR, and LWKR is investigated using combined process-interaction/discrete-event simulation models. An efficient experimental procedure is designed and implemented using these models, and the statistical analysis of the results is presented. For the particular case investigated, the conclusions are very encouraging. In terms of mean flow time, the TP method performs significantly better than any other tested heuristic dispatching rules. Also, the experimental results show that using global information significantly improves the FMS performance.     

An optimization-based approach to assess non-interference in labeled and bounded Petri net systems

An optimization-based approach to assess both strong non-deterministic non- interference (SNNI) and bisimulation SNNI (BSNNI) in discrete event systems modeled as labeled Petri nets is presented in this paper. The assessment of SNNI requires the solution of feasibility problems with integer variables and linear constraints, which is derived by extending a previous result given in the case of unlabeled net systems. Moreover, the BSNNI case can be addressed in two different ways. First, similarly to the case of SNNI, a condition to assess BSNNI, which is necessary and sufficient, can be derived from the one given in the unlabeled framework, requiring the solution of feasibility problems with integer variables and linear constraints. Then, a novel necessary and sufficient condition to assess BSNNI is given, which requires the solution of integer feasibility problems with nonlinear constraints. Furthermore, we show how to recast these problems into equivalent mixed-integer linear programming (MILP) ones. The effectiveness of the proposed approaches is shown by means of several examples. It turns out that there are relevant cases where the new condition to assess BSNNI that requires the solution of MILP problems is computationally more efficient, when compared to the one that requires the solution of feasibility problems.     

Evaluation of entropy-based dispatching in flexible manufacturing systems

Traditionally, part dispatching has been done using static rules, rules that fail to take advantage of the dynamic nature of today’s manufacturing systems. In modern manufacturing systems, machines carry multiple tools so parts have the option of being machined at more than one machine. This flexibility, termed routing flexibility in the literature, opens up new possibilities for shop floor planners for the scheduling and dispatching of parts.     

From Petri Nets to Automata with Concurrency

Automata with concurrency relations are labelled transition systems with a collection of state-dependent binary independence relations for the actions. We show how to associate with each Petri net (place/transition net) such an automaton having the same dynamic behaviour. We characterize the automata arising in this way, and with suitable notions of morphisms for Petri nets and for automata with concurrency relations we extend this correspondence to a coreflection between the associated categories. As a consequence, we derive that these categories have products and conditional coproducts.     

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.     

Queueing network modelling of flexible manufacturing system using mean value analysis

In the present investigation, we develop queueing model for the performance prediction of flexible manufacturing systems (FMSs) with a multiple discrete material-handling devices (MHD). An iterative method has been suggested using mean value analysis (MVA) for the state-dependent routing. Two queueing network models are considered to determine the material-handling device interference. In the first one, we model the interference from the MHD by inflating the station service times but neglect queueing at the MHD. In another network, the queueing for the MHD is taken into consideration. The performance of FMS configuration is obtained by iterating between two networks. The suggested algorithms demonstrate better results than the algorithm used by earlier workers for single MHD. Some performance indices viz. throughput, mean service time, mean waiting time, etc. are obtained. Numerical results are provided to highlight the effect of the system parameters on performance indices, which are further evaluated by using neuro-fuzzy controller system to validate the tactability of soft computing approach.     

A unified approach to the modelling of holonomic and nonholonomic mechanical systems

An alternative technique, called projection method, for solving constrained system problems is presented. This approach can be used to derive equations of motion of both holonomic and nonholonomic systems, and the dynamic equations can be expressed in generalized velocities and/or quasi-velocities. Compared against the other methods of classical mechanics (Lagrange's, Gibbs-Appell, Kane's,...), the present method turns out to be extraordinarily short, elementary and general. As such, it deserves to be promoted as a generally accepted method in academic and engineering applications. Three examples are reported to illustrate advantages of the technique     

Numerical performance of approximate queuing formulae with application to flexible manufacturing systems

This paper calls attention to two of the more successful queuing approximation formulae — one by Kramer and one by Marchal. The analytic solution of a range of single server Erlang cases is compared to the two approximation formulae. Then a family of H₂/M/1 cases is similarly considered. Maximum errors are seen to be about three percent. The Kramer formula seems to be better when the interarrival coefficient of variation is less than 0.66 and the Marchal formula is better for larger interarrival coefficients of variation. Finally, a multiserver refinement function (the ratio of G/G/1 results to M/M/1 results) is proposed to scale M/M/s as an approximation for G/G/s. In most of these multiple channel cases, the maximum error is less than six percent. The last section of this paper presents a simple, representative FMS. It is modelled as an open queuing network. Then the approximation procedure is applied node by node to illustrate the estimation of system performance measures such as machine utilizations and throughput.     

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.     

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.     

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.     

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.     

The optimality of balancing workloads in certain types of flexible manufacturing systems

Symmetric mathematical programming is used to analyze the optimality of balancing workloads to maximize the expected production in a single-server closed queuing network model of a flexible manufacturing system (FMS). In particular, using generalized concavity we prove that, even though the production function is not concave, balancing workloads maximizes the expected production in certain types of m-machine FMS's with n parts in the system. Our results are compared and contrasted with previous models of production systems.