|Current Workshop | Overview||Back | Home | Search ||
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.
EURANDOM and Department of Mathematics and Computer Science,
Eindhoven University of Technology
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.
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
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
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.
School of Mathematics,
Georgia Institute of Technology,
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.
Joint work with Bruno Gaujal and Dinard van der Laan
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.
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
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.
University of Ulm
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.
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
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.
(Joint work with Frank Fleischer, Catherine Gloaguen, and Hendrik Schmidt)
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.
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
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.
Joint work with Maxim Ioresh, Ad Ridder and Alan Weiss.
On the Optimality of a Full-Service Policy for a Queuing System with
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.
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.
Vrije University, Amsterdam
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.