Current Workshop | Overview | Back | Home | Search | | ||||||||||
Stochastic Systems |
Onno Boxma The G/M/1 queue
revisited
The G/M/1 queue is one of the classical models of queuing theory. The goal of this talk is two-fold: (i) To introduce new derivations of some well-known results, and (ii) to present some new results for the G/M/1 queue and its variants. In particular, we pay attention to the G/M/1 queue with a set-up time at the start of each busy period, and the G/M/1 queue with exceptional first service. Onno Boxma
EURANDOM
and Department of Mathematics and Computer Science, Eindhoven
University of Technology Hans Daduna On throughput in large queuing
networks
The talk presents joint work with Victor
Pestien and Subrahmanian Ramakrishnan (University of Miami). We consider closed cyclic networks of
exponential single server queues. The service rates at the servers are locally
state dependent and for any node some increasing sequence m = (m(n); n = 1, 2,
…), called the service rate, determines service rates provided by that server
if n customers are present. We let the number of customers and the number of
nodes grows unboundedly such that the ratio of customers to nodes has a well
defined limit (asymptotic customer density). We further require that the
proportion of nodes for each service rates that occur converges in distribution
to a limiting service rate (probability) measure on the closure of all such
m's. We define for each such sequence of networks an asymptotic profile which
consists of the asymptotic customer density, the limiting service rate measure and the set of all
nodes that occur in the network sequence. Our asymptotics does not require
rescaling of time and space, we work completely on a microscopic level of the
system's description. We first investigate the sequence of network throughputs and compute upper and lower bounds for the liminf and limsup of the sequence of throughputs as functions of the limiting customer densities. These are then used to find conditions for the existence of the limiting throughput. We are further able to prove even necessity of these conditions by construction of counterexamples: In all cases of asymptotic profiles which are not covered by the conditions there exists a sequence of networks with this asymptotic profile such that the limiting throughput does not exists. For network sequences where a limiting
throughput exists we obtain the limiting queue length behavior of nodes with
persistent service rates. The results can be extended to general Gordon-Newell
networks. Hans
Daduna
Department of
Mathematics, Hamburg University Center of Mathematical
Statistics and Stochastic Processes Eugene A. Feinberg
Optimality of
Nonrandomized Policies for Certain Constrained MDPs
As it is well known, randomized policies may outperform
nonrandomized policies in Markov Decision Processes (MDPs) with multiple
criteria and constraints. Seminal
papers of Hordijk and Kallenberg studied geometric properties of constrained
MDPs with finite state and action spaces and developed linear programming
algorithms to compute optimal randomized policies. It is also known that, in some cases, nonrandomized policies may
be optimal. For example, time-sharing
policies described by Ross, Altman and Shwartz are optimal for unichain
problems with average rewards per unit time. We discuss two other situations when nonrandomized
policies are optimal for constrained MDPs: continuous time MDPs and
discrete-time nonatomic MDPs. For
continuous-time MDPs, switching policies are at least as good as randomized
policies. For nonatomic MDPs, nonrandomized
policies are as good as randomized policies.
We also discuss the link between nonatomic MDPs and the work of
Dvoretzky, Wald, Wolfowitz, and Blackwell on non-randomized statistical
decisions. Eugene A. Feinberg
Department
of Applied Mathematics & Statistics SUNY at Stony Brook Jerzy Filar Doubly Stochastic Matrices
& The Hamiltonian Cycle Problem We consider the classical
(NP-hard) problem of determining whether a given graph possesses a Hamiltonian
cycle. Exploiting singularly perturbed controlled Markov chains and their
fundamental matrices we reduce the problem to that of minimising the
variability of the ``first return time” to the home node. The latter is a
highly structured, non-convex, optimisation problem whose properties shed light
on both the theoretical complexity of the problem and its algorithmic tractability. A key recent innovation in
this approach is the restriction to those controls that induce doubly
stochastic Markov chains. This domain is convex, rich enough to include
Hamiltonian cycles and structured enough to considerably simplify fundamental
matrices of the relevant Markov chains. Arguably,
the problem of determining whether a given graph possesses a Hamiltonian cycle
contains the essential difficulty of the famous “Travelling Salesman
Problem”. We claim that it is
conceptually insightful, and algorithmically useful, to characterise this
difficulty in terms of quantities such as the variability of returns (to the
initial state) in a
controlled
stochastic process, or gaps between the minimal Vivek Borkar, Vladimir Ejoy and Jerzy Filar
Centre
for Industrial and Applied Mathematics, University of South Australia,
Adelaide, Australia T.P. Hill Algorithms for Constructing
Probability Measures at Random
The solution to many problems in operations research,
applied analysis, and statistics is a probability distribution: e.g., in
queuing, the worst-case arrival, or optimal service distributions. Exact
analytical solutions are often not available, and it is useful to have
computationally feasible methods for generating probability distributions at random
(which can then be used to identify nearly-optimal distributions, or to analyze
average-case performance, etc). This talk will survey some of the classical and
recent algorithms, and open problems, for constructing probability
distributions at random. T.P.
Hill School
of Mathematics, Georgia
Institute of Technology, Atlanta
Arie
Hordijk
Multi-modularity and Regularity; recent applicationsFirst I will give a brief introduction
to Multi-modularity and Regularity. It is based on results obtained in the
monograph: E. Altman, B. Gaujal, A. Hordijk (2003), Discrete-Event Control
of Stochastic Networks: Multi-modularity and Regularity. Also a new lemma
on the convexity of the average cost of the regular policy as function of the
density will be presented. The second part of the talk will be devoted to the
results of two recent papers, in which multi-modularity and regularity are
applied. The first paper is on dropping sequences for the Random Early
Detection Algorithm used in communication networks. By using Multi-modularity
and convex stochastic ordering it follows that uniform dropping yields a better
performance than geometrical dropping. The second paper is on the optimal
policy for deterministic and exponential polling systems. For two deterministic
queues the best polling sequence is computed, it is always periodic and regular inside the stability region.
The fractions of time spent by the server in the queues are highly
discontinuous in the parameters of the system and show a fractal behavior. Arie Hordijk
Joint work with Bruno Gaujal and Dinard van der Laan Ger Koole On the edge of queuing and
decision
making
Queuing and
Markov decision theory have been two constants in the research and teaching of
Arie Hordijk. We discuss both in the context of routing to parallel queues. Ger
Koole
Dinard van der Laan Optimal Open-Loop PollingThe optimal open-loop polling policy for polling systems
with a single server serving two queues is analysed. Considering computational
results the focus is on the similarities and differences in the optimal policy
for deterministic and exponential systems (joint work with Arie Hordijk and
Bruno Gaujal). Dinard
van der Laan
Ulrich
Rieder Optimization with Different
Information Structures
We considersimple models of financial markets with regular
traders, with insiders possessing some extra information hidden in a random
variable from the beginning of the trading interval and with investors having
only partial information about their stock prices. All investors are interested
in maximizing the expected utility from terminal wealth. The optimal values and
portfolio strategies are derived and compared for various models of
differential information. Ulrich
Rieder
University of Ulm
Ad Ridder The minimium cross-entropy method for rare event estimationIn this talk I discuss the minimium cross-entropy (MCE)
method for estimating probabilities of rare events in random walks and in
queueing systems. The MCE method is an infinite-dimensional optimisation
program that minimises an entropy under constraints with respect to the
original density. Its solution is used as the new density for the importance sampling
simulations. Issues: the relationship with the importance sampling
using the large deviations solution, and the prospect of obtaining better
estimation results. Ad
Ridder
Rhonda Righter Staffing
Decisions for Heterogeneous Workers with Turnover We consider a firm that employs heterogeneous workers to
meet demand for its product or service.
Workers differ in their skills, speed, and/or quality, and they randomly
leave, or turn over. Each period the
firm must decide how many workers of each type to hire or fire in order to meet
randomly changing demand forecasts at minimal expense. We explore several different notions of
discrete convexity and their impact on structural results for the optimal
policy. Rhonda
Righter and J. George Shanthikumar
Department of Industrial Engineering
and Operations Research University of California\\ Berkeley,
CA 94720 USA RRighter@IEOR.Berkeley.edu Shanthikumar@IEOR.Berkeley.edu Volker Schmidt Fitting
and Simulation of Models for Telecommunication Access Networks Stochastic
models for telecommunication networks are important tools aiming to allow e.g.
cost analysis and parametric optimization of the network. In a joint project
between France Telecom R&D, Paris and the University of Ulm, the Stochastic
Subscriber Line Model (SSLM) has been developed, which is a ealistic and
versatile model for telecommunication networks. In the
first part of the talk, after an introduction of the SSLM, a model fitting procedure
based on distance measures for global geometric characteristics is presented.
Examples of such characteristics are the mean total length of the edges or the
number of vertices of the induced cells per unit area. The procedure is
validated by using simulated input data and is afterwards applied to real
infrastructure data of Paris. In the
second part, we focus on a particular part of the SSLM by investigating typical
serving zones, described as typical cells of Cox-Voronoi tessellations induced
by Poisson point processes on random lines. Based on Slyvniak's Theorem, a
simulation algorithm for these typical cells is provided. Numerical results
concerning basic characteristics as well as comparisons to characteristics for
typical cells of Poisson-Voronoi tessellations are given. Volker Schmidt (Joint work with Frank Fleischer,
Catherine Gloaguen, and Hendrik Schmidt) Karel Sladký
Variance Selection Rules in Markov Decision ProcessesThe usual optimization criteria for Markov decision
processes can be quite insufficient to fully capture the various aspects for a
decision maker. It may be preferable to select more sophisticated criteria that
also reflect variability-risk features of the problem. Most notably, the
variance of the cumulative rewards can be indicative and seems of interest. To this end formulae for the variance of cumulative reward
earned up to a fixed time point of a Markov reward chain are obtained and their
asymptotical properties are studied. Particularly, the variance growth rate is
shown to be asymptotically linear in time and expressions are provided to
compute this growth rate. By a careful examination of these formulae we can
discover difficulties arising if the mean-variance penalization is considered.
To this end some simplifications in the expression of the growth rate are
considered in the papers on mean-variance penalization. Comparison of the
obtained results with those reported in the literature will be given. Karel
Sladký
Institute
of Information Theory and Automation Academy
of Sciences of the Czech Republic Pod
vodárenskou vezí 4, P. O. Box 18 CZ-182 08 Prague 8, Czech Republic
Adam
Shwartz Large Deviations for Queues: recent
extensions After a short overview of sample-path large deviations for
queuing networks, providing the state of the art of the theory, I will describe
three recent advances I was involved with. The first concerns a class of
systems were service rate is design to meet
demand, or systems that employ soft controls to prevent overflows. The
large deviations principle was recently established for such networks. Then I
will show how LD tools are useful even when LD theory does not apply. Finally I
will describe a new (in the context of LD) class of models for which the LD principle can be established, with non-local
rate functions. The last two issues are illustrated via concrete examples. Adam
Shwartz Joint
work with Maxim Ioresh, Ad Ridder and Alan Weiss. Sandy Stidham On the
Optimality of a Full-Service Policy for a Queuing System with
Discounted Costs We provide weak sufficient conditions for a full-service
policy to be optimal in a queuing control problem in which the service rate is
a dynamic decision variable. In our
model there are service costs and holding costs and the objective is to
minimize the expected total discounted cost over an infinite horizon. We begin with a semi-Markov decision model
for a single-server queue with exponentially distributed inter-arrival and
service times. Then we present a
general model with weak probabilistic assumptions and demonstrate that the full-service
policy minimizes both finite-horizon and infinite-horizon total discounted cost
on each sample path. Sandy Stidham
Henk Tijms Approximations for multi-server queues with finite waiting roomThis talk will report on ongoing research to approximate
the waiting-time percentiles in the multi-server queue with Poisson input,
general service times and finite waiting -room. The practical importance of such approximations is
highlightened by a rule in call-centers
requiring that 80% of the calls should be answered within 20 seconds. The main
idea of the approximation is twofold. First, calculate the state probabilities
for the finite-capacity model through the state probabilities of the
infinite-capacity model. Second, use the solutions for the waiting-time
percentiles for the special cases of deterministic and exponential services as
building blocks for the case of general services. Henk Tijms
Vrije University, Amsterdam
Uri
Yechiali Controllling an oscillating Jackson-type network having state-dependent service rates We consider a Jackson-type network comprised of 2 queues
having state dependent service rates, in which the queue lengths evolve
periodically, exhibiting noisy cycles. To reduce the noise we apply a certain
heuristic and show that in order to decrease the probability of customers
overflow in one of the queues, the server in that same queue - contrary to
intuition - should be shut down for a short period of time. Further noise
reduction is obtained if the server in the second queue is briefly shut down as
well, when certain conditions hold. [Back] |