WSC 2005 Final Abstracts

Controlled Sequential Factorial Design for Simulation Factor Screening
Hua Shen and Hong Wan (Purdue University)

Abstract:
Screening experiments are performed to eliminate unimportant factors so that the remaining important factors can be more thoroughly studied in later experiments. Sequential screening methods are specifically fit for simulation experiments. They are usually more efficient than one-step procedures. The challenge is to prove the "correctness" of the result. This paper proposes Controlled Sequential Factorial Design (CSFD) for discrete-event simulations. It combines sequential hypothesis-testing procedures with the traditional factorial design to control the Type I Error and power for each factor under heterogeneous variances conditions. CSFD requires minimum assumptions and demonstrates robust performance with different system conditions.

Estimation of Percentiles of Cycle Time in Manufacturing Simulation
Feng Yang, Bruce E. Ankenman, and Barry L. Nelson (Northwestern University)

Abstract:
We present a simulation-based method for estimating percentiles of the cycle time distribution of a manufacturing system as a function of the factory throughput and percentile of interest. The method fits metamodels to the first three moments of cycle time as a function of throughput, and then uses a moment-based approximation to obtain the percentiles of interest.

Balancing Bias and Variance in the Optimization of Simulation Models
Christine S.M. Currie (University Southampton) and Russell C.H. Cheng (University of Southampton)

Abstract:
We consider the problem of identifying the optimal point of an objective in simulation experiments where the objective is measured with error. The best stochastic approximation algorithms exhibit a convergence rate of n^-1/6 which is somewhat different from the n^-1/2 rate more usually encountered in statistical estimation. We describe some simple simulation experimental designs that emphasize the statistical aspects of the process. When the objective can be represented by a Taylor series near the optimum, we show that the best rate of convergence of the mean square error is when the variance and bias components balance each other. More specifically, when the objective can be approximated by a quadratic with a cubic bias, then the fastest decline in the mean square error achievable is n^-2/3. Some elmentary theory as well as numerical examples will be presented.

Sensitivity Analysis of Network Reliability Using Monte Carlo
Gerardo Rubino (Campus Universitaire de Beaulieu)

Abstract:
We analyze the computation of sensitivities in network reliability analysis. The associated models are graphs whose components are weighted by probabilities (their reliabilities) and they are widely used, for instance, in the design of communication networks. The paper deals with the sensitivities of usual reliability network metrics, with respect to the reliabilities of the components. The importance of sensitivities in this context is discussed and it is shown how to efficiently estmate the vector of sensitivities using Monte Carlo procedures. A first result allows to evaluate sensitivities using the standard Monte Carlo approach. A second method is then presented to deal efficiently with the rare event case. The ideas presented here can be applied to other classes of reliability problems and/or methods.

Importance Sampling in Markovian Settings
Werner Sandmann (University of Bamberg)

Abstract:
Rare event simulation for stochastic models of complex systems is still a great challenge even for Markovian models. We review results in importance sampling for Markov chains, provide new viewpoints and insights, and we pose some future research directions.

Application of Rare Event Techniques to Trace Driven Simulation
Poul E. Heegaard (Norwegian University of Science and Techonology), Bjarne E. Helvik (orwegian University of Science and Techonology) and Ragnar Ø. Andreassen (Telenor R&D)

Abstract:
This paper describes a trace driven, fast simulation approach applicable to deal with the performance evaluation of a multiplex of heterogeneous traffic streams with variable bit rate and long lived serial correlation offered routers in the Internet. A challenge with simulations of the Internet is the huge number of events that are needed for each event of interest, e.g. the loss or excessive delay of a packet. The simulation efficiency of the trace driven approach in this paper is improved by use of importance sampling to provoke constellation of traces where the loss and long delays are more likely. The approach is successfully applied to speed-up the simulation of multiplexing of heterogeneous MPEG encoded video streams.

New Measures of Robustness in Rare Event Simulation
Hector Cancela (Universidad de la Republica) and Gerardo Rubino and Bruno Tuffin (ampus Universitaire de Beaulieu)

Abstract:
Rare event simulation requires acceleration techniques in order to i) observe the rare event and ii) obtain a valid and small confidence interval for the expected value. A ``good'' estimator has to be robust when rarity increases. This paper aims at studying robustness measures, the standard ones in the literature being Bounded Relative Error and Bounded Normal Approximation. By considering the problem of estimating the reliability of a static model for which simulation time per run is the critical issue, we show that actually those measures do not validate the satisfying behavior of some techniques. We thus define Bounded Relative Efficiency and generalized bounded normal approximation properties of the two previous measures in order to encompass the simulation time. We also illustrate how a user can have a look at the coverage of the resulting confidence interval by using the so-called coverage function.

Perfect Simulation of Monotone Systems for Rare Event Probability Estimation
Jean-Marc Vincent (Laboratoire ID-Imag)

Abstract:
This paper deals with the estimation of rare event probabilities in finite capacity queueing networks. The traditional product form property of Markovian queueing networks usually vanishes when capacity of queues are finite and clients are blocked or rejected. A new efficient simulation method, derived from Propp-Wilson (1996), perfect simulation, is applied in the finite capacity queue context. An algorithm directly samples states of the network according to the stationary distribution. This method is adapted for simulation of rare events, typically when events are described by an increasing subset of the state space. Provided that events of the network are monotone, monotonicity techniques are used to reduce the sampling time. Moreover, a stopping mechanism has been developed to interrupt the simulation when an increasing set has been reached. Then, for the estimation of a monotonous reward function, the simulation time could be reduced drastically as in Vincent-Marchand(2004).

Efficient Importance Sampling Heuristics for the Simulation of Population Overflow in Jackson Networks
Victor F. Nicola (University of Twente) and Tatiana S. Zaburnenko (Univeristy of Twente)

Abstract:
In this paper we propose state-dependent importance sampling heuristics to estimate the probability of population overflow in Jackson networks with arbitrary routing. These heuristics approximate the ``optimal" state-dependent change of measure without the need for costly optimization involved in other recently proposed adaptive algorithms. Experimental results on tandem, feed-forward and feed-back networks with a moderate number of nodes yield asymptotically efficient estimates (often with bounded relative error) where no other state-independent importance sampling techniques are known to be efficient.

Is Problem Solving, or Simulation Model Solving, Mission Critical?
Ray J. Paul, Tillal Eldabi, Jasna Kuljis, and Simon J. E. Taylor (Brunel University)

Abstract:
How do we consider problems and models in the practice of simulation? It is our possibly contentious observation that simulation model solving seems to be more critical to the mission of simulation modeling than problem solving. Inspired by the theme of this year’s Winter Simulation Conference, we ask the question, “Is problem solving, or simulation model solving, mission critical?” To investi-gate this we look at three perspectives, those of the text-book, the article and the editorial. The textbook perspec-tive is the balance of the “traditional” view of simulation presented by the academic textbook against practical ex-perience. The article perspective is a classification of pa-pers published in four leading simulation journals in the year 2004 (ACM TOMACS, SIMULATION, Simulation Modelling Practice and Theory, and Simulation & Gaming). The editorial perspective is a discussion of editorial policy presented by the same journals. Our findings show that our observation is not contradicted.

Is Problem Solving, or Simulation Model Solving, Mission Critical? The Panel Reloads
Ray J. Paul (Brunel University), Mark Elder (Corporate Headquaters), Richard Nance (Orca Computer, Inc.), Ernest Page (The MITRE Corporation) and Jerzy Rozenblit (The University of Arizona)

Abstract:
Discussion from panellists representing different simulation schools of thought: Software engineering, standardised Simulation methodologies, Simulation software vendors, traditional academic, and a typical Simulation consumer/user.

A Java Library for Simulating Contact Centers
Eric Buist and Pierre L'Ecuyer (Université de Montréal)

Abstract:
ContactCenters is a Java library for writing contact center simulators. It supports multi-skill and blend contact centers with complex and arbitrary routing, dialing policies, and arrival processes. The programmer can alter the simulation logic in many ways, without modifying the source code of the library. A simulator can interoperate with other libraries, e.g., for optimization and statistical analysis. Performance, flexibility, and extensibility are the main goals of its design and implementation. In this paper, we present the general architecture of the library, its main components and their interaction. We give an example of a contact center simulator and provide comparisons with a widely used commercial simulation system also offering facilities for contact center simulation.

Performance Measures for Service Systems with a Random Arrival Rate
Samuel G. Steckley and Shane G. Henderson (Cornell University) and Vijay Mehrotra (San Francisco State University)

Abstract:
It is commonly assumed that the arrival process of customers to a service system is a nonhomogeneous Poisson process. Call center data often refute this assumption, and several authors have postulated a doubly-stochastic Poisson process for arrivals instead. We develop approximations for both the long-run fraction of calls answered quickly, and the distribution of the fraction of calls answered quickly within a short period. We also perform a computational study to evaluate the approximations and improve our understanding of such systems.

Approximate Dynamic Programming in Multi-Skill Call Centers
Ger Koole and Auke Pot (Vrije Universiteit)

Abstract:
We consider a multi-skill call center consisting of specialists and fully cross-trained agents. All traffic is inbound and there is a waiting queue for each skill type. Our objective is to obtain good call routing policies. In this paper we use the so-called policy iteration (PI) method. It is applied in the context of approximate dynamic programming (ADP). The standard PI method requires the exact value function, which is well known from dynamic programming. We remark that standard methods to obtain the value function suffer from the curse of dimensionality, i.e., the number of states grows exponentially with the size of the call center. Therefore, we replace the real value function by an approximation and we use techniques from ADP. The value function is approximated by simulating the system. We apply this method to our call routing problem, yielding very good results.

A Component-level Path-based Simulation Approach for Efficient Analysis of Large Markov Models
Vinh V. Lam and William H. Sanders (University of Illinois) and Peter Buchholz (Universität Dortmund)

Abstract:
Markov models are used in many industrial applications, but, for very large models, simulation is often currently the only viable evaluation technique. However, simulation techniques that are based on evaluating trajectories at level of individual states/transitions can be inefficient because they have to keep track of many details. Moreover, since they use statistical methods, estimating solutions at higher confidence intervals requires evaluation of increasingly large number of trajectories which often leads to poor performance. On other hand, analytical path-based techniques can be used for computing guaranteed bounds on the true solutions, but they have poor performance because they must evaluate many paths to obtain reasonable bounds. In this paper, we present a path-based simulation approach for evaluating models at the component, rather than individual state/transition, level. At this level of abstraction, the approach can compute more accurate solutions than traditional discrete-event simulation techniques can in a given amount of time.

Scaling an Optimistic Parallel Simulation of Large-Scale Interconnection Networks
Nilesh Choudhury, Yogesh Mehta, Terry L. Wilmarth, Eric J. Bohm, and Laxmikant V. Kale (University of Illinois)

Abstract:
Parallel computers today are designed with larger number of processors than ever before, connected by large scale Interconnection Networks. Communication is the key to achieving high performance on such machines, making the study of Interconnection Networks important. Parallel simulations of Interconnection Networks present a unique problem characterized by fine-grained computation and strong dependence among events. The absence of large lookaheads makes it unsuitable to use a conservative simulation. Using an optimistic Parallel Discrete Event Simulation allows us to extract reasonable parallelism from this simulation. In this paper we present BigNetSim, an Interconnection Network simulator. We analyze its performance and present techniques related to enhancing performance and scaling it to a large number of processors on different artificial traffic patterns and real application logs. Inspite of the overheads of a parallel optimistic simulation, we have achieved a breakeven with sequential simulation at four processors and demonstrate perfect scaling to 128 processors.

Performance Analysis of Binary Code Protection
David M. Nicol and Hamed Okhravi (University of Illinois)

Abstract:
Software protection technology seeks to prevent unauthorized observation or use of applications. Cryptography can be used to provide such protection, but imposes a potentially significant additional computation load. This paper examines the performance impact of two software protection techniques. We develop an analytic model and validate it using a detailed discrete-event simulator applied to memory reference traces of well-known benchmark programs. We find that even though the added workload may be large, that impact is often dominated by inherent costs of disk activity.

Simulation in Java with SSJ
Pierre L'Ecuyer and Eric Buist (Université de Montréal)

Abstract:
We describe SSJ, an organized set of software tools offering general-purpose facilities for stochastic simulation programming in Java. It supports the event view, process view, continuous simulation, and arbitrary mixtures of these. Random number generators with multiple streams and substreams, quasi-Monte Carlo methods and their randomizations, and random variate generation for a rich selection of distributions, are all supported in an integrated framework. Performance, flexibility, and extensibility were key criteria in the design and implementation of SSJ. We illustrate its use by simple examples.

The SIMSCRIPT III Programming Language for Modular Object-Oriented Simulation
Stephen V. Rice (The University of Mississippi), Ana Marjanski and Stephen M. Bailey (CACI Products Company) and Harry M. Markowitz (none)

Abstract:
SIMSCRIPT III is a programming language for discrete-event simulation. It is a major extension of its predecessor, SIMSCRIPT II.5, providing full support for object-oriented programming and modular software development.

Simsolution - An Open Simulation Environment Founded on Extreme Multitasking
Thomas Wiedemann (University of Applied Science Dresden)

Abstract:
There is no universal standard for discrete simulation. Models, created with leading simulation tools can not be exchanged between the systems. In result, there are very high investments and maintenance costs for simulation studies and some additional problems with portability and performance in large simulation studies. This paper discusses in detail, a special approach by using an assembler based, very fast multitasking routine combined with efficient discrete event scheduling algorithms. The basic system approach is realized with Standard C/C++ and Delphi-compilers and offers an unlimited flexibility and very good runtime performance. Language independent, XML-based code generators convert simulation models between different run-time platforms without manual changes.

Channel Based Sequential Simulation
Cameron Kiddle, Rob Simmonds, and Brian Unger (University of Calgary)

Abstract:
Sequential discrete event simulation is widely employed to study the behavior of many systems. Events are typically managed in a central event list which is implemented as a priority queue ordered by event timestamps. Most research to improve sequential simulation performance has focused on improving the priority queue implementations. Recent work has demonstrated that asynchronous conservative parallel discrete event simulation systems can achieve better sequential performance under some conditions, but worse performance under other conditions. This paper introduces a new sequential discrete event simulation algorithm that can exhibit some of the same performance advantages of asynchronous conservative parallel discrete event simulation algorithms and has complexity no more than that of central event list algorithms in the worst case.

Qualitative Discrete Event Simulation
Yen-Ping Leow-Sehwail and Ricki G. Ingalls (Oklahoma State University)

Abstract:
A real world system is full of uncertainties and more than often the parameters, processes or events under study are poorly understood. In order to study a real world system, we often have to make a set of assumptions about how it works using statistical, mathematical or logical relationships. Qualitative discrete event simulation involves the development of simulation models which require less assumptions, less data requirements and yet more robust. This paper presents the concepts involved in the development and implementation of qualitative discrete event simulation models and algorithms.

Requirements for Domain Specific Discrete Event Simulation Environments
Edwin C. Valentin (Systems Navigator) and Alexander Verbraeck (Delft University of Technology)

Abstract:
Domain specific discrete event simulation environments are supposed to enable faster and easier model development and experimentation. Unfortunately, perceived disadvantages from simulation experts hinder the wide application of this technology. We have performed laboratory experiments and simulation studies in two different domains to learn what the difficulty of domain specific simulation environments is. The lessons that we learned from these experiments and simulation studies enabled us to formulate requirements for domain specific simulation environments, for the model constructs in these environments, for the design of these environments and for guidelines for the use of these environments in simulation studies.