A survey of the perturbation analysis of discrete event dynamic systems

This paper introduces an analysis and optimization technique for discrete event dynamic systems, such as flexible manufacturing systems (FMSs), and other discrete part production processes. It can also be used for enhancement of the simulation results of, or the monitoring of the operations of such systems in real time. Extensive references are given where readers may pursue futher details.     

Convergence properties of ordinal comparison in the simulation of discrete event dynamic systems

Recent research has demonstrated that ordinal comparison has fast convergence despite the possible presence of large estimation noise in the design of discrete event dynamic systems. In this paper, we address the fundamental problem of characterizing the convergence of ordinal comparison. To achieve this goal, an indicator process is formulated and its properties are examined. For several performance measures frequently used in simulation, the rate of convergence for the indicator process is proven to be exponential for regenerative simulations. Therefore, the fast convergence of ordinal comparison is supported and explained in a rigorous framework. Many performance measures of averaging type have asymptotic normal distributions. The results of this paper show that ordinal comparison converges monotonically in the case of averaging normal random variables. Such monotonicity is useful in simulation planning.The author would like to thank C. G. Cassandras, X. Chao, S. G. Strickland, X. Xie, and the reviewers for their helpful suggestions.     

A simulation study of despatch bay performance in the steel processing industry

The despatch bay is a critical interface within an organisation, linking the warehousing and transport operations. However, delays here have wider supply chain implications given that the flow of materials through the supply chain is disrupted. Despite this, there has been little research on improvement activities to this process. This paper uses a case study of a steel processor to develop a simulation model to test strategies for increasing despatch bay productivity. From the simulation results, it was found that a combination of improvements were needed, to both reduce process times and ensure the earlier receipt of orders. The research approach presented in this paper can be used in other business environments having similar operating conditions.     

Robust decentralized diagnosability of networked discrete event systems against DoS and deception attacks

Denial-of-Service (DoS) are attacks conducted by malicious agents that consists in disrupting, temporally or indefinitely, the services provided by a communication network. When a malicious agent gets access to some network node, it may also perform deception attacks by inserting valid packets with fake information into vulnerable channels. We address, in this paper, DoS and deception attacks (DoS-D attack) that flood some communication channels with fake packets causing delays, loss of observations and insertion of fake observations, and their implications in decentralized fault diagnosability of networked discrete event systems (NDES). To this end, we propose an automaton model for NDES subject to DoS-D attacks that represents the adverse effects of DoS-D attacks on the observations of local diagnosers. We introduce a new codiagnosability definition called DoS-D-robust codiagnosability, and present a necessary and sufficient condition for a language to be DoS-D-robustly codiagnosable. We also propose a verification algorithm for regular languages to check DoS-D-robust codiagnosability.     

A discrete event simulation of the adult trabecular skeleton

A verified, but unvalidated discrete event computer simulation of the adult bone remodeling system is presented. It implements the unit-based theory of adult skeletal remodeling proposed by Frost. The simulation allows a scientist to design trials involving the adult skeleton by inputting the times of administration, and effects (remodeling cycle initiation, activity, lifespan, proliferation) on bone cells of drugs, according to his current understanding of their mechanisms of action. The simulation constantly tracks the contents and age of all bone structural units, updating each every 2.5 days, to reflect ongoing bone resorption, osteoid formation, osteoid mineralization, and the passage of time. In reality, the simulation tabulates the results of remodeling cycles which take place during the trial. The investigator may receive histomorphometric, densitometric, and biochemical data, as indicators of skeletal status, as often as every 2.5 days during the trial, far more frequently than is usually done in real experiments. At the conclusion of a trial, he may plot/review time-related graphs of the interim data. Validation trials of aging, “activation,” and clodronate administration, are presented. This simulation, when validated, could be a cost-saving device because it can increase the chance for success of any adult skeletal experiment by guiding investigators toward taking fewer, better selected measurements. Furthermore, when refined to include color graphics display of skeletal structure, it could be the basis for an educational device. This could help both the medical community and the public by providing a more ready understanding than can currently be had of adult skeletal remodeling, its relationship to adult metabolic bone disease, and the prevention/treatment of adult metabolic bone disease (e.g. osteoporosis).     

Stochastic quasigradient methods for optimization of discrete event systems

In this paper, stochastic programming techniques are adapted and further developed for applications to discrete event systems. We consider cases where the sample path of the system depends discontinuously on control parameters (e.g. modeling of failures, several competing processes), which could make the computation of estimates of the gradient difficult. Methods which use only samples of the performance criterion are developed, in particular finite differences with reduced variance and concurrent approximation and optimization algorithms. Optimization of the stationary behavior is also considered. Results of numerical experiments and convergence results are reported.     

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.     

A sharp global stability result for a discrete population model

We get a sharp global stability result for a first order difference equation modelling the growth of bobwhite quail populations. The corresponding higher-dimensional model is also discussed, and our stability conditions improve other recent results for the same equation.     

A discrete dynamical system as a model of a neural network with generalized Hebbian synapses

We study the dynamical behavior of a discrete time dynamical system which can serve as a model of a learning process. We determine fixed points of this system and basins of attraction of attracting points. This system was studied by Fernanda Botelho and James J. Jamison in [A learning rule with generalized Hebbian synapses, J. Math. Anal. Appl. 273 (2002) 529-547] but authors used its continuous counterpart to describe basins of attraction.     

A discrete time model for software reliability with application to a flight control software

This work is motivated by a particular software reliability problem in a unit of flight control software developed by the Indian Space Research Organization (ISRO), in which the testing of the software is carried out in multiple batches, each consisting of several runs. As the errors are found during the runs within a batch, they are noted, but not debugged immediately; they are debugged only at the end of that particular batch of runs. In this work, we introduce a discrete time model suitable for this type of periodic debugging schedule and describe maximum likelihood estimation for the model parameters. This model is used to estimate the reliability of the software. We also develop a method to determine the additional number of error‐free test runs required for the estimated reliability to achieve a specific target with some high probability. We analyze the test data on the flight control software of ISRO. Copyright © 2011 John Wiley & Sons, Ltd.     

Massively time-parallel,approximate simulation of loss queueing systems

A time-parallel simulation obtains parallelism by partitioning the time domain of the simulation. An approximate time-parallel simulation algorithm named GG1K is developed for acyclic networks of loss FCFSG/G/1/K queues. The GG1K algorithm requires two phases. In the first phase, a similar system (i.e. aG/G/1/ queue) is simulated using the GLM algorithm. Then the resultant trajectory is transformed into an approximateG/G/1/K trajectory in the second phase. The closeness of the approximation is investigated theoretically and experimentally. Our results show that the approximation is highly accurate except whenK is very small (e.g. 5) in certain models. The algorithm exploits unbounded parallelism and can achieve near-linear speedup when the number of arrivals simulated is sufficiently large.     

A discrete hierarchical model of intra-specific competition

A discrete hierarchical model with either age, size, or stage structure is derived. The resulting scalar equation for total population level is then used to study contest and scramble intra-specific competition. It is shown how equilibrium levels and resilience are related for the two different competition situations. In particular, scramble competition yields a higher population level while contest competition is more resilient if the uptake rate as a function of resource density is concave down. The conclusions are reversed if the uptake rate is concave up.     

A modified Markov model for the estimation of computer software performance

The model proposed by Trivedo and Shooman [8] is extended and modified by assuming that (1) the error occurrence rate when the machine is running is proportional to the number of errors in the system; (2) the error correction rate has two components, either an error is corrected with correction rate μ₀ or an error is corrected but a new error is created with ineffective correction rate μ₁. The solution of the differential equations corresponding to the model is obtained in closed form.     

A critical review of discrete filled function methods in solving nonlinear discrete optimization problems

Many real life problems can be modeled as nonlinear discrete optimization problems. Such problems often have multiple local minima and thus require global optimization methods. Due to high complexity of these problems, heuristic based global optimization techniques are usually required when solving large scale discrete optimization or mixed discrete optimization problems. One of the more recent global optimization tools is known as the discrete filled function method. Nine variations of the discrete filled function method in literature are identified and a review on theoretical properties of each method is given. Some of the most promising filled functions are tested on various benchmark problems. Numerical results are given for comparison.     

A note on adapting methods for continuous global optimization to the discrete case

In this note we show that various branch and bound methods for solving continuous global optimization problems can be readily adapted to the discrete case. As an illustration, we present an algorithm for minimizing a concave function over the integers contained in a compact polyhedron. Computational experience with this algorithm is reported.     

A discrete time optimal control model with uncertainty for dynamic machine allocation problem and its application to manufacturing and construction industries

This paper proposed a discrete time optimal control model in which machine failure time is modeled assuming a Weibull distribution and machine productivity is regarded as a fuzzy variable for dealing with a dynamic machine allocation problem (DMAP) in manufacturing and construction industries. The aim is to maximize total production or construction throughput when uncertainties such as machine breakdowns are taken into account. A failure probability-work time equation is presented to describe the relationship between machine failure probability and mean time to work. To transform the uncertain optimal control model into a deterministic one, the expected value model (EVM) was introduced for forming an equivalent crisp model. The fuzzy variables in the model are also defuzzified by using an expected value operator with an optimistic–pessimistic index. Then a number of lemmas and theorems are presented and proved to formulate the theoretical algorithm so that the crisp model of the DMAP can be solved. Three actual construction and production projects are used as practical application examples. The theoretical algorithm results for the three project examples are compared with a particle swarm optimization approach and a genetic algorithm method, which demonstrates the practicality and efficiency of our optimization method.     

On the definition of a computational fluid dynamic solver using cellular discrete-event simulation

The Discrete Event System Specification (DEVS) has rarely been applied to the physics of motion. To explore the formalism's potential contribution to these applications, we need to investigate the definition of moving gases, liquids, rigid bodies, and deformable solids. Here, we show how to use Cell-DEVS to analyze the movement and interactions of fluids using computational fluid dynamics (CFD). We describe a set of rules that produce the same patterns as traditional CFD implementations. We present the inner workings of the CFD algorithm, the incorporation of solid barriers, and the adoption of variable time steps within the context of biomechanical simulations.     

Permanence of a delayed discrete mutualism model with feedback controls

This paper discusses a two species discrete model of mutualism with delays and feedback controls. Sufficient conditions are obtained for the permanence of the system. The results show that feedback control variables have no influence on the persistence property of the system.     

Asymptotic stability of traveling waves in a discrete convolution model for phase transitions

In a recent paper [P. Bates, A. Chmaj, A discrete convolution model for phase transition, Arch. Rational Mech. Anal. 150 (1999) 281-305], a discrete convolution model for Ising-like phase transition has been derived, and the existence, uniqueness of traveling waves and stability of stationary solution have been studied. This nonlocal model describes l₂-gradient flow for a Helmholts free energy functional with general range interaction. In this paper, by using the comparison principle and the squeezing technique, we prove that the traveling wavefronts with nonzero speed is globally asymptotic stable with phase shift.