An extended event graph-based modelling method for parallel and distributed discrete-event simulation

The developing logical process (LP)-based parallel and distributed discrete-event simulation (PDES) in the existing PDES programming environments is a difficult and time-consuming process. Event graph is a simple and powerful modelling formalism of discrete-event simulation, whereas this formalism does not support PDES. This article proposes an extension of the event graph to consider the communication of LPs via the events sent, which is called ‘extended event graph (EEG)’, and proposes an EEG-based modelling method for PDES. This modelling method shifts the focus of PDES development from writing code to building models, and the system implementation can be automatically and directly generated from EEG model. The experimental results show that EEG models can successfully execute in the parallel simulator, and this framework can effectively improve the PDES modelling activities.     

Decomposing Timed Petri Net Models of Open Queueing Networks

This paper develops a Petri net-based decomposition approach to model and perform steady-state analysis of open queueing networks with multi-class customers. For each customer class we assume deterministic routeing and different service time distribution. The current decomposition may also consider equipment failures, defective units that have to be re-worked and on-line preparations (to switch from one mix of customers to another) as additional customer classes. In contrast to most of the published works on timed Petri nets, their present use is marked by input flows, originating from external sources. A simple method, directly derived from the timed Petri nets theories, is used for calculating the expected utilization of each server and eventually the maximal productivity of the system for the given deterministic routeing. An important application of the model is in validating discrete-event non-terminating simulation models.     

Qualitative fault tolerance analysis for a class of hybrid systems

This paper investigates the fault tolerance problem of hybrid systems with faults that affect the switching sequence. A hierarchical model is developed, which consists of four parts from bottom to top: hybrid automata, qualitative abstraction, discrete abstraction, and supervisor. Under this model, the reachability and fault tolerability properties of hybrid systems can be analyzed in a qualitative manner and from discrete-event system point of view. Sufficient conditions are given to maintain the system’s ideal (or acceptable) performance in spite of faults. Several numerical examples and an application to hose insertion task illustrate the efficiency of the proposed method.     

Pancake网络的t/k-诊断度及其算法

由于大型多处理机系统规模的不断扩大, 其组件脆弱性也随之增加, 因此故障容错性能对于多处理机系统尤为重要. t/k-诊断分析是一种能极大提高多处理机系统自我诊断性能的系统级故障诊断策略,该诊断策略能识别至多t个故障处理机节点, 其中可能包含至多$k$个被误诊的处理机. 首先给出了Pancake网络P_n(n\geq 5) 的容错性分析, 其后证明了P_n在PMC模型下是((k+1)n-3k-1)/k-可诊断的, 其中1\leq k\leq 3, 最后还给出复杂度为O(NlogN)的快速诊断算法来识别所有的故障节点.     

Modeling Discrete Event Systems With Faults Using a Rules-based Modeling Formalism

Obtaining accurate models of systems which are prone to failures and breakdowns is a difficult task. In this paper we present a methodology which makes the task of modeling failure prone discrete event systems (DESs) considerably less cumbersome, less error prone, and more user-friendly. The task of obtaining commonly used automata models for DESs is non-trivial for most practical systems, owing to the fact that the number of states in the commonly used automata models is exponential in the number of signals and faults. In contrast a model of a discrete event system, in the rules based modeling formalism proposed by the co-authors of this paper, is of size polynomial in the number of signals and faults. In order to model failures, we augment the signals set of the rules based formalism to include binary valued fault signals, the values representing either a non-faulty or a faulty state of a certain failure type. Addition of new fault signals requires introduction of new rules for the added fault signal events, and also modification of the existing rules for non-fault events. The rules based modeling formalism is further extended to model real-time systems, and we apply it to model delay-faults of the system as well. The model of a failure prone DES in the rules based can automatically be converted into an equivalent (timed)-automaton model for a failure analysis in the automaton model framework.     

Modeling and solution of COA development based on timed influence net and game theory

The development of a course of action (COA) is one of key steps in operation planning. Considering the conflict game, resource restriction, and the influence of execution time, this paper establishes a COA development model based on the timed influence net and game theory. The given problem is solved by transforming it into a standard matrix game model. An example is provided to illustrate this model and its solution.     

Some contributions with Petri nets for the modelling, analysis and control of HDS

Petri nets (PN) are useful for the modelling, analysis and control of hybrid dynamical systems (HDS) because PN combine in a comprehensive way discrete events and continuous behaviours. On one hand, PN are suitable for modelling the discrete part of HDS and for providing a discrete abstraction of continuous behaviours. On the other hand, continuous PN are suitable for modelling the continuous part of HDS and for working out a continuous approximation of the discrete part in order to avoid the complexity associated with the exponential growth of discrete states. This paper focuses on the advantages of PN as a modelling tool for HDS. Investigations of such models for diagnosis and control issues are detailed.

Taking inspiration from the discrete event approach, sensor selection for diagnosis is discussed according to the structural analysis of the PN models. Faults are represented with fault transitions and a faulty behaviour occurs when a sequence of transitions is fired that contains at least one fault transition. Minimal sets of observable places are defined for detecting and isolating faulty behaviours.

Taking inspiration from the continuous time approach, flow control of HDS modelled with continuous PN is also investigated. Gradient-based controllers are introduced in order to adapt the firing speeds of some controllable transitions according to a desired trajectory of the marking. The equilibria and stability of the controlled system are studied with Lyapunov functions.     

Towards an auction-driven gas supply: a simulation-based optimization framework for utilities

A platform for the study of the whole transmission problem (arrival of ships, regasification, transportation and distribution) faced by gas utilities companies is proposed. The main objective of this research is to develop a platform that includes the analysis of the new capacity auctions (and not the traditional commodity auctions) that will govern the supply chain in the near future. A simulation-optimization approach has been used to favour the more realistic abstraction of the system. The discrete-event model includes a genetic algorithm to reach the solution in a satisfactory short time, a requisite in auction markets. Design and optimization studies for the utilities are addressed using the platform, which has been validated with real data for one of the main zones in the Spanish market.     

An example of simulation optimisation using a neural network metamodel: finding the optimum number of kanbans in a manufacturing system

A method of finding the optimum solution for a stochastic discrete-event system is described. A simulation model of the system is first built and then used to train a neural network metamodel. The optimisation process consists of using the metamodel to find an approximate optimum solution. This solution is then used by the simulation as the starting point in a more precise search for an optimum. The approach is demonstrated with an example that finds the optimum number of kanbans needed to control a manufacturing system.     

Modeling uncertain activity duration by fuzzy number and discrete-event simulation

This paper introduces how to incorporate fuzzy set theory and a fuzzy ranking measure with discrete-event simulation in order to model uncertain activity duration in simulating a real-world system, especially when insufficient or no sample data are available. Fuzzy numbers are used to describe uncertain activity durations, reflecting vagueness, imprecision and subjectivity in the estimation of them. A fuzzy ranking measure is merged with an activity scanning simulation algorithm for performing fuzzy simulation time advancement and event selection for simulation experimentation. The uses of the fuzzy activity duration and the probability distribution-modeled duration are compared through a series of simulation experiments. It is observed that the fuzzy simulation outputs are arrived at through only one cycle of fuzzy discrete-event simulation, still they contain all the statistical information that are produced through multiple cycles of simulation experiments when the probability distribution approach is adopted.     

Facilitated modelling with discrete-event simulation: Reality or myth?

Is it possible for discrete-event simulation to be used in a facilitated workshop environment? Over the last decade there have been various attempts to use simulation in this way, but we argue here that none have been successful in achieving a fully facilitated mode where the model is both developed and used in the workshop. We attempt to use a discrete-event simulation in a facilitated mode as part of a lean improvement workshop in a hospital setting. The model was successfully developed and used within the 3 day period of the workshop. Although the intervention was successful, we still had to build the model in the ‘back-office’, meaning that a fully facilitated mode was not achieved. The paper concludes by discussing how fully facilitated modelling with discrete-event simulation might be made possible; the answer is more about changing mind-sets than about technological challenge.     

Hybrid modeling based double-granularity fault detection and diagnosis for quadrotor helicopter

Fault detection and diagnosis (FDD) is an effective technology to assure the safety and reliability of quadrotor helicopters. However, there are still some unsolved problems in the existing FDD methods, such as the trade-offs between the accuracy and complexity of system models used for FDD, and the rarely explored structure faults in quadrotor helicopters. In this paper, a double-granularity FDD method is proposed based on the hybrid modeling of a quadrotor helicopter which has been developed in authors’ previous work. The hybrid model consists of a prior model and a set of non-parametric models. The coarse-granularity-level FDD is built on the prior model which can isolate the faulty channel(s); while the fine-granularity-level FDD is built on the nonparametric models which can isolate the faulty components in the faulty channel. In both coarse and fine granularity FDD procedures, principal component analysis (PCA) is adopted for online fault detection. Using such a double-granularity scheme, the proposed FDD method has inherent ability in detecting and diagnosing structure faults or failures in quadrotor helicopters. Experimental results conducted on a 3-DOF hover platform can demonstrate the feasibility and effectiveness of the proposed hybrid modeling technique and the hybrid model based FDD method.     

Combining discrete-event simulation and system dynamics in a healthcare setting: A composite model for Chlamydia infection

This paper presents a composite model in which two simulation approaches, discrete-event simulation (DES) and system dynamics (SD), are used together to address a major healthcare problem, the sexually transmitted infection Chlamydia. The paper continues an on-going discussion in the literature about the potential benefits of linking DES and SD. Previous researchers have argued that DES and SD are complementary approaches and many real-world problems would benefit from combining both methods. In this paper, a DES model of the hospital outpatient clinic which treats Chlamydia patients is combined with an SD model of the infection process in the community. These two models were developed in commercial software and linked in an automated fashion via an Excel interface. To our knowledge this is the first time such a composite model has been used in a healthcare setting. The model shows how the prevalence of Chlamydia at a community level affects (and is affected by) operational level decisions made in the hospital outpatient department. We discuss the additional benefits provided by the composite model over and above the benefits gained from the two individual models.     

Implementing a discrete-event simulation software selection methodology for supporting decision making at Accenture

For large international companies with their own simulation team, it is often hard to make a decision related to selection of new discrete-event simulation software. This paper presents a comprehensive discrete-event simulation software selection methodology that has been successfully used for decision making at Accenture consulting company. Accenture already used a simulation tool at the start of the project, but wanted to find out whether the current tool used still was the most appropriate one for its needs, and to evaluate the latest discrete-event simulation tools. The developed methodology consists of two phases: phase 1 quickly reduces the long list to a short list of packages, and phase 2 matches the requirements of the company with the features of the simulation package in detail. Successful application of the proposed methodology indicates its possible application for decision making in other large organisations, provided that the study is performed by a third party to avoid risks of influencing the outcome of the selection process.     

A linear characterization of the switching dynamic behavior of timed continuous Petri nets with structural conflicts

The behavior of timed continuous Petri nets (TCPN) can be ruled by linear equations during certain time elapses (IB-states), but changes in the marking and conflict solving policies make nonlinear the complete computation of the behavior. In this paper a global characterization of the switching behavior of TCPN through Mixed Linear Integer Programming (MLIP) is presented. The contribution is an analytical technique to compute the evolution graph of a TCPN, which allows deriving MLIP problems from TCPN models including cycles and structural conflicts; conflict resolution policies by priorities and sharing are considered.     

An application of discrete-event theory to truck dispatching

This article focuses on the dispatching problem of an oilsand excavation process subject to production objectives and specifications. Herein, we cast the truck dispatching task in a decision-making framework for determining solutions and helping a dispatcher to make decisions. In this paper, we apply the discrete-event formalism to investigate the dispatching of a large truck fleet. For this purpose, we examine the capabilities and limitations of two distinct theories: discrete-event system (DES) and vector discrete-event system (VDES). Despite their differences, both theories can be used to model the logical structure of the dispatching process. These theories also provide techniques for implementing specifications and representing solutions in a compact manner. The results of this paper demonstrate that current procedures and tools available for DES allow a broader range of techniques to be applied, thus increasing the likelihood of finding a suitable solution. This work was supported, in part, by the Natural Sciences and Engineering Research Council of Canada (NSERC), the Canadian Foundation for Innovation and PRECARN and associates. In addition, the first author was supported by NSERC, Fonds pour la formation de Chercheurs et l’Aide a la Recherche (FCAR), and Ontario Graduate Scholarships (OGS).     

Fixed poles in the model matching problem for systems over semirings

In this paper, solution existence conditions for the model matching problem are studied for systems over semirings, which are used in many applications, such as queueing systems, communication networks, and manufacturing systems. The main contribution is the discovery of fixed pole structure in solutions to the model matching problem. This fixed pole structure provides essential information contained in all the solutions to the model matching problem. For a discrete-event dynamic system example, a common Petri net component in the solutions of the model matching problem can be discovered from the fixed pole structure.     

How to optimize discrete-event systems from a single sample path by the score function method

We present a method for deriving theoptimal solution of a class of mathematical programming problems, associated with discrete-event systems and in particular with queueing models, while using asingle sample path (single simulation experiment) from the underlying process. Our method, called thescore function method, is based on probability measure transformation derived from the efficient score process and generating statistical counterparts to the conventional deterministic optimization procedures (e.g. Lagrange multipliers, penalty functions, etc.). Applications of our method to optimization of various discrete-event systems are presented, and numerical results are given.Research supported by the L. Edelstein Research Fund at the Technion-Israel Institute of Technology.     

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 generalized eigenmode algorithm for reducible regular matrices over the max-plus algebra with applications to the Metro-bus public transport system in Mexico city

In this paper, an algorithm for computing a generalized eigenmode of reducible regular matrices over the max-plus algebra is applied to the Metro-bus public transport system in Mexico city. A timed event Petri net model is constructed from the data table that characterizes the transport system. A max-plus recurrence equation, with a reducible and regular matrix, is associated with the transport system timed event Petri net. Next, given the reducible and regular matrix, the problem consists of giving an algorithm which will tell us how to compute its generalized eigenmode over the max plus algebra. The solution to the problem is achieved by studying some type of recurrence equations. In fact, by transforming the reducible regular matrix into its normal form, and considering a very specific recurrence equation, an explicit mathematical characterization is obtained, upon which the algorithm is constructed. The generalized eigenmode obtained sets a timetable for the transport system.