Lorentz Center - Stochastic Systems from 16 Mar 2005 through 19 Mar 2005
  Current Workshop  |   Overview   Back  |   Home   |   Search   |     

    Stochastic Systems
    from 16 Mar 2005 through 19 Mar 2005

No TitleMean-Variance Selection Rules

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,



Arie Hordijk

Multi-modularity and Regularity; recent applications

First 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 Polling

The 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 estimation

In 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





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 Processes

The 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 room                                                 

This 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.