WSC 2005 Final Abstracts |
Monday 10:30:00 AM 12:00:00 PM
Estimation in Simulation
Experiments
Chair: Russell Cheng (University of Southampton)
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.
Monday 1:30:00 PM 3:00:00 PM
Rare Events Simulation I
Chair:
Bruno Tuffin (IRISA-INRIA)
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.
Monday 3:30:00 PM 5:00:00 PM
Rare Events Simulation II
Chair:
Bruno Tuffin (IRISA-INRIA)
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.
Tuesday 8:30:00 AM 10:00:00 AM
Plenary: Simulation Problems and
Models
Chair: Helena Szczerbicka (Universität Hannover)
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.
Tuesday 10:30:00 AM 12:00:00 PM
Panel: Is Simulation Model Solving,
Mission Critical?
Chair: Ray Paul (Brunel
University)
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.
Tuesday 1:30:00 PM 3:00:00 PM
Modeling Call Centers
Chair:
Enver Yücesan (INSEAD)
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.
Tuesday 3:30:00 PM 5:00:00 PM
Modeling and Simulation of Computer
Systems
Chair: Dave Nicol (University of
Illinois)
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.
Wednesday 8:30:00 AM 10:00:00 AM
Simulation Languages
Chair:
Sam Steckley (Cornell University)
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.
Wednesday 10:30:00 AM 12:00:00 PM
Language Modeling Improvements
Chair: Sujin Kim (Cornell University)
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.