November 1-2-3, 2012 Young European Queueing Theorists (YEQT-VI) Workshop on "Analytic Methods in Queueing Systems"

Program

Keynote and Tutorial Talk Abstracts

Ivo Adan
Title: Analysis of queueing models with multiple waiting lines: direct methods
Abstract: Queueing models with multiple waiting lines can often be described by multi-dimensional Markov processes, the state space of which is the set of non-negative lattice points. The methods for solving the equilibrium equations of these Markov processes can be divided into two groups: complex-function or ''indirect'' methods, and direct methods that try to solve the equilibrium equations directly, i.e., without resorting to transforms. In this talk we will focus on some direct methods, and by means of some illustrative examples, explain their main ideas, strengths and weaknesses.

PRESENTATION

Onno Boxma
Title: Analysis of queueing models with multiple waiting lines: complex-function methods
Abstract: This talk is to some extent a sequel, or a counterpart, to the talk of Ivo Adan. We focus on some complex-function methods to determine the generating function, or Laplace transform, of a multi-dimensional distribution: the uniformization method and the boundary value method. By means of some illustrative examples, we explain their main ideas, strengths, and limitations.

PRESENTATION

Philippe Nain
Title: Mathematics of file dissemination
Abstract: In this talk, we will present basic mathematical models for studying file dissemination in P2P systems. Performance issues will be addressed as well as issues related to fighting illegal behavior.
Keywords: Markov process, branching process, mean-field theory, phase-transition.

PRESENTATION

Bo Friis Nielsen
Title: Queueing models with matrix-exponential distributions and rational arrival processes.
Abstract: Traditional proofs of the matrix geometric solutions for queues of the GI/M/1 type use probabilistic arguments related to the sample paths of Markov chains. Such an approach is not directly applicable when the components with which we are modelling consist of matrix-exponential distributions and rational arrival processes. Two ways of resolving this problem are presented, the first approach is based on a modification of a last entrance argument introduced by Ramaswami while the second approach is based on results for Markov chains on general state spaces when considering state changes in the embedded Markov chain of the queue. This is joint work with Nigel Bean.

PRESENTATION

Peter Taylor
Title: The Physics of Matrix-Analytic Algorithms
Abstract: Since Marcel Neuts first showed that Markov chains of GI/M/1 type have a matrix-geometric stationary distribution in the 1970s and 1980s, the interplay between analytic properties and physical interpretations has played a major part in the development of matrix-analytic methods for analyzing stochastic models.
Most performance measures of interest in such models can be expressed in terms of the solutions of matrix or vector polynomial equations, which have to be solved numerically. Over the years, various iterative algorithms have been proposed for doing this. In order to establish convergence, and gain information about the speed of convergence, it is often helpful to think about the physical interpretation of the iterates.
In this tutorial, I shall discuss the physical interpretation of matrix-analytic algorithms that have been proposed for analyzing block-structured continuous-time Markov chains, stochastic fluid models and multitype continuous-time branching processes.

PRESENTATION

Benny Van Houdt
Title: Multi-type customers with general customer impatience
Abstract: In this lecture we use matrix-analytic methods and fluid queues to study a very general class of queueing systems. More specifically, we focus on a class of multi-type Markovian queues with phase-type distributed service and general (type-dependent) impatience.
In the first part of the lecture we study the discrete-time MMAP[K]/PK[K]/1 queue and show how its main performance characteristics can be computed using a simple Quasi-Birth-Death Markov chain and discuss some possible generalizations.
In the second part we consider the same queueing system in continuous time. For this purpose we briefly introduce the class of Markov chains with a matrix exponential distribution (introduced by Sengupta). To speed up the computation, we reduce this Markov chain to a Markov-modulated fluid queue (without thresholds).
In the last part of the lecture we introduce general, type-dependent customer impatience and show, using the ideas of the first two parts of the lecture, that it can be reduced to a fluid queue with (many) thresholds, the solution of which corresponds to solving a set of algebraic Riccati equations.

PRESENTATION

Dieter Fiems
Title: Queuing systems with branching process dynamics
Abstract: A branching process is a specific type of stochastic process, originally developed to model the extinction of aristocratic surnames in Victorian England. Since then, the use of branching processes as a modeling technique has come natural in many areas of science, including nuclear chain reactions, biology and population dynamics. Branching processes also play a key role in the analysis of various queuing systems. The interconnection between branching process theory and busy period analysis in queuing theory was already explicitly established in Kendall's 1951 paper ''Some problems in the theory of queues''. Apart from busy-period analysis, branching processes have been identified that describe the dynamics of polling systems, of processor sharing queues, of random order of service queues, as well as of infinite server queues. This talk focuses on applications in queuing theory of conventional as well as extensions of branching process theory. In particular, the analysis of branching-type polling systems will be discussed.

PRESENTATION

Invited Talk Abstracts

Serban Badila
Title: Dependencies in risk models and their dual queueing models
Abstract: It is known that problems arising in insurance and risk theory are related to problems in queueing theory and performance analysis. More precise, for a risk reserve process, we can consider a dual queueing process in which the time flow is reversed and the inter-arrival time of customers and their service times are the inter-claim periods and the claim sizes, respectively, in the risk process.
Then quantities of interest, like the probability of ruin or the maximum aggregate loss are related to performance measures of the queue, like the waiting time distribution W. Under stability conditions, when starting the risk process with initial capital u, the infinite horizon ruin probability, ψ(u) is equal to the tail P(W>u) of the steady state workload in the dual queue. It is worth mentioning that this duality is a path-wise identity and no independence assumptions are needed. We are particularly interested in models that exhibit some kind of dependence structure. For example the size of the current claim may depend on its inter-arrival time (or dually, the inter-arrival time may depend on the preceding service time in the queueing setting) in such a way that the above performance measures are tractable.
The dependence structure to be presented is modeled by a class of bivariate matrix-exponential distributions (as in Bladt & Nielsen [1]) in which the joint Laplace-Stieltjes transform of the claim size and the inter-claim time is a rational function. This class generalizes some bivariate Gamma models already considered in the literature. We obtain exact results for the infinite-horizon ruin probabilities and for the waiting time in the dual queueing model, by using Laplace-transform methods and solving a Wiener-Hopf type boundary-value problem.
References
[1] M. Bladt and B.F. Nielsen. Multivariate matrix-exponential distributions. Stochastic Models, 26(1):1-26, 2010.

PRESENTATION

Niek Baer
Title: The PH/PH/1 multi-threshold queue
Abstract: We consider a single server queue with infinite capacity in which service times and interarrival times are controlled by a threshold policy. This threshold policy will change the stage of the system once a particular queue length is reached. For each stage s the interarrival times are PH(Λ_s,λ_s) distributed and the service times are PH(M_s,μ_s) distributed. We model this queue as a Level Dependent Quasi-Birth-and-Death process and introduce a decomposition method to obtain the stationary queue length distribution. We use this PH/PH/1 threshold queue to model highway traffic flows. We show that with this queueing system we can obtain the Fundamental Diagram, one of the key elements in highway traffic analysis, which closely resembles emperical data.

PRESENTATION

Eline De Cuypere
Title: Analysis of coupled queues
Abstract: A coupled queueing system consists of multiple queues, served by a single server such that in every queue a customer leaves upon service completion, and such that service is blocked if any of the queues is empty. While conceptually simple, the analysis and performance of coupled queues is a challenging task, which draws upon different analysis methodology. Indeed, the state space of the associated Markov chains grows very fast in the number of queues involved and lead rapidly to a state space explosion. However, the number of possible state transitions from any specific state is limited. This means that most of the entries in the generator matrix are zero; the matrix is sparse. Either direct or iterative techniques for sparse matrices can be used. More advanced methods like Krylov-subspace methods, e.g. the generalized minimal residual method, are expected to reduce the processing time considerably. Another approach takes advantage of the structure of the state space; in the case of two queues, at least one having finite capacity, the Markov chain is a quasi-birth-death process, the phase being the queue content of the finite capacity queue. Such methods do not easily extend to the multi-queue case. However, in the multi-queue case, a numerical Taylor series expansions approach in the service rate, proves to be both accurate and efficient.
Coupled queueing systems are frequently encountered in various contexts including assembly, production and communication networks. Kitting is the operation of collecting the necessary parts for a given end product into a specific container, called a kit, prior to arriving at an assembly unit. As kits can only be completed if all parts are present, the part buffers and the kitting operation constitutes a coupled queueing system. For the case of two-queue coupled systems, often referred to as paired queueing system, some interesting applications can be identified. Decoupling buffers are used to reduce lead times in production systems by buffering semi-finished products at some point in the production process. Hence, paired queueing applies as the next production stage only starts if there are semi-finished products and demand. Finally, energy harvesting is the process by which ambient energy is converted into electrical energy. Sensor nodes with harvesting capability use this energy to transmit data. As data can only be transmitted if the battery level is not empty, the backlogged data queue and the energy queue are paired.

PRESENTATION

Jan-Pieter Dorsman
Title: Dynamic repairman assignment in a layered queueing network with correlated queues
Abstract: In the classical machine-repair model, a machine subject to breakdowns typically faces competition for repair facilities with other machines. This leads to dependencies in their downtimes. What is oftentimes ignored in the MR-model is that the machines make products themselves. Due to the correlations of the downtimes of the machines, the queue lengths of the products in front of the machines are also correlated. In this talk, we study the question of how the repairman should allocate its repair capacity between two machines dynamically, so as to minimize the expected total number of waiting products. The service policy of the repairman has a significant influence on these queue lengths. We derive several properties pertaining to the repairman's optimal strategy. As it is hard to characterize this strategy completely, we also obtain a near optimal policy for the repairman that performs nearly as well over a wide range of parameter settings.

Masha Frolkova
Title: Random Fluid Limit of a Polling System
Abstract: For many basic queueing systems, fluid limits are deterministic functions. In this work, we study a cyclic polling system under conditions that lead to a random fluid limit. These conditions are zero initial state and overload. We obtain a precise description of the fluid limit. Our main tool is the Kesten-Stigum theorem for supercritical branching processes. This work can also be viewed as a generalization of one of the results of Kovalevski, Topchii, Foss (2005), where the case of two queues with exhaustive service is considered. We allow multiple queues and a wide class of service disciplines that guarantee the connection with branching processes.

PRESENTATION

Sophie Hautphenne
Title: Algorithmic methods for branching processes
Abstract: We consider a particular class of continuous-time multi-type branching processes, named Markovian binary trees (MBTs), in which the individuals' lifetime is controlled by a transient Markovian arrival process. The extinction probability of an MBT is the minimal nonnegative solution of a matrix quadratic equation. We describe some linear and quadratic algorithms to solve this equation, which are inspired from the matrix analytic methods and have a probabilistic interpretation. Finally, we consider MBTs with catastrophes, and we use a G/M/1-type Markov process approach to approximate the extinction probability.

PRESENTATION

Esa Hyytiä
Title: Value Functions for M/G/1 Queues and Task Assignment Problem
Abstract: We first analyze M/G/1 queue with different scheduling disciplines (FCFS, LCFS, SRPT, PS, etc.) and derive the so-called size-aware value functions with respect to arbitrary task-specific holding costs. By size-aware we mean that the service requirements become known upon arrival (cf. SRPT).
Then we shift our focus to the task assignment problems (dispatching problems), which arise in numerous settings (manufacturing sites, street tolls, routing, supercomputing, data centers). The task assignment problem is a dynamic decision making problem where the arriving tasks are assigned (dispatched) immediately upon arrival to one of the available servers. Each server processes tasks according to a local scheduling discipline such as FCFS. Typical objective is to minimize the mean delay or slowdown, where the latter imposes a fairness criterion.
The optimal task assignment is non-trivial and only some optimality results are available. For example, Join-the-Shortest-Queue (JSQ) has been shown to be optimal for identical FCFS servers when the service requirements are exponential and the objective is to minimize the mean delay. We utilize the value functions in the MDP framework to derive efficient task assignment strategies for arbitrary holding costs. Starting from an arbitrary state-independent policy, the value functions enable the policy improvement step yielding a robust state-dependent task assignment policy.

PRESENTATION

Martin Lopez Garcia
Title: Extreme values in terms of a matrix exponential: splitting methods in the M/M/c retrial queue
Abstract: In this talk, we aim to study the maximum queue length during a fixed time interval [0, t$$₀ ] in the M/M/c retrial queue [1]. We present a solution in matrix exponential form, and we obtain a simple condition on the service and retrial rates for the matrix exponential solution to be explicit or algorithmically tractable. Our methodology, which has been previously applied under modifications in host-parasitoid models [2], is based on splitting methods and the use of eigenvalues and eigenvectors. A particularly appealing feature of our solution is that it allows us to obtain global error control by using the matrix norm induced by the $\ell_\infty$ vector norm.
References
[1] A. Gomez-Corral, M. Lopez Garcia (2012) Maximum queue lengths during a fixed time interval in the M/M/c retrial queue. In preparation.
[2] A. Gomez-Corral, M. Lopez Garcia (2012) Maximum population sizes in host-parasitoid models. Under review.

PRESENTATION

Athanasia Manou
Title: Strategic customers in a transportation station: When is it optimal to wait?
Abstract: We consider a transportation station, where customers arrive according to a Poisson process. A transportation facility visits the station according to a renewal process and serves at each visit a random number of customers according to its capacity. We assume that the arriving customers decide whether to join the station or balk, based on a natural reward-cost structure. Specifically, we assume that a customer receives a reward of R units for completing service and accumulates costs at a rate of K units per time unit that he remains in the system. This situation leads to a symmetric game among customers. We study the balking behavior of the customers and derive the corresponding Nash equilibrium strategies under two levels of information. In the unobservable case, where an arriving customer does not observe the number of present customers, we prove the existence of a unique Nash equilibrium strategy. In the observable case, where an arriving customer observes the number of present customers, we prove some recursive formulas for the LST's of the conditional sojourn time of a customer, given that he finds n present customers at his arrival instant and then we give a recursive scheme for the computation of the Nash equilibrium strategies.

PRESENTATION

David Meisch
Title: Uncertainty calculations for estimates of project durations
Abstract: The "Successive Principle" is an analysis tool for project management. It is a group analysis method, originally developed by Steen Lichtenberg. The basic idea is to model subtasks of a project using independent gamma distributions, more specifically Erlang distributions. This modeling process uses triple group estimates, which are obtained from groups of various sizes.
Erlang distributions belong to the broader class of phase-type (PH) distributions and can be analyzed using matrix algebra. There are also closed form solutions for the expectation and all other moments. In project management, the main focus of the analysis is often only on the cost benefit ratio. Nevertheless, the duration of a project can be of major concern. In some cases, e.g. stadiums for the Olympic Games, a delay would be disastrous. In other cases, e.g. toll roads, a delay postpones the revenues and therefore directly affects the cost -benefit analysis.
We will reuse the basic idea of the "Successive Principle", but will extend it by calculating the distribution of the duration time directly, in addition to using general phase-type distributions. This makes, it possible to handle projects with very few subtasks as well as to account for overlapping processes and concurrent subtasks. This is a very common occurrence in construction projects, where the overall project is completed once the last subtask has been executed. Having modeled the entire project as an absorbing Markov jump process, the natural step is to use multivariate PH (MPH*) distributions as introduced by Kulkarni in order to analyze the correlation between the total cost and the duration of a project.

PRESENTATION

Wouter Minnebo
Title: Pull versus Push Mechanism in Large Distributed Networks: Closed Form Results
Abstract: We compare the performance of the pull and push strategy in a large homogeneous distributed system. When a pull strategy is in use, lightly loaded nodes attempt to steal jobs from more highly loaded nodes, while under the push strategy more highly loaded nodes look for lightly loaded nodes to process some of their jobs.
Given the maximum allowed overall probe rate R and arrival rate λ, we provide closed form solutions for the mean response time of a job for the push and pull strategy under the infinite system model. More specifically, we show that the push strategy outperforms the pull strategy for any probe rate R > 0 when λ < φ− 1, where φ = (1 + √5)/2 ≈ 1.6180 is the golden ratio. More generally, we show that the push strategy prevails if and only if 2 λ < ((R + 1)^2 + 4(R + 1))^(1/2) − (R + 1). We also show that under the infinite system model, a hybrid pull and push strategy is always inferior to the pure pull or push strategy. The relation between the finite and infinite system model is discussed and simulation results that validate the infinite system model are provided.

PRESENTATION

Giang Nguyen
Title: The morphing of fluid queues into Markov-modulated Brownian motion
Abstract: Ramaswami (2012) shows that standard Brownian motion arises as the limit of a family of Markov-modulated linear fluid processes. We pursue this analysis and show the fluid approximation for Markov-modulated Brownian motion. Furthermore, we prove that the stationary distribution of a Markov-modulated Brownian motion reflected at zero can be obtained from the well-analyzed stationary distribution of linear fluid processes. Key matrices in the limiting stationary distribution are shown to be solutions of a new quadratic equation, and we describe how this equation may be efficiently solved.

Tuan Phung-Duc
Title: Perturbation analysis for multiserver retrial queues
Abstract: We consider multiserver retrial queues where a blocked customer has two opportunities for abandonment: at the moment of blocking or at the departure epoch from the orbit. In this queueing system, the number of customers in the queue (servers and buffer) and that in the orbit form a level-dependent quasi-birth-and-death (QBD) process whose stationary distribution is expressed in terms of a sequence of sparse rate matrices. Using a perturbation technique and a matrix continued fraction approach, we derive a Taylor type expansion for non-zero elements of the rate matrices with respect to the number of customers in the orbit. We also obtain explicit expressions for all the coefficients of the expansion. Furthermore, we derive tail asymptotic formulae for the joint stationary distribution of the number of customers in the queue and that in the orbit.

PRESENTATION

Shlomi Reuveni
Title: Occupation Probabilities in the Asymmetric Inclusion Process
Abstract: The Asymmetric Inclusion Process (ASIP) is a system of n Markovian queues in tandem, each with unbounded capacity and batch service [1]. That is, when service is completed at queue k, all particles present at that queue move simultaneously to queue k+1 or out of the system when k=n. Numerical simulations demonstrated that the probability that site k is occupied (by one or more particles) is inversely proportional to the square root of k [2]. We show that occupation probabilities in the ASIP obey a discrete two-dimensional boundary value problem. Solving this problem we analytically validate the numerically observed "square root law" and find explicit expressions for the probability that site k is occupied by l particles (l=0,1,2,…). The numbers of Catalan's triangle are shown to naturally arise in the context of these occupation probabilities.
References
[1] S. Reuveni, I. Eliazar and U. Yechiali, Asymmetric Inclusion Process. Phys. Rev. E. 84, 041101, (2011).
[2] S. Reuveni, I. Eliazar and U. Yechiali, The Asymmetric Inclusion Process: A Showcase of Complexity. Phys. Rev. Lett. 109, 020603, (2012).

PRESENTATION

Eleni Vatamidou
Title: Approximation errors for the MAP/G/1 queue
Abstract: Numerical evaluation of the ruin probability when the claims arrive according to a Markovian Arrival Process (MAP) is an important problem, since MAPs are dense in the class of arrival processes. Motivated by the connection between ruin probabilities and the waiting time distribution of a queue, we study the numerical evaluation of the MAP/G/1 queue. However, if the service times are generally distributed and especially heavy-tailed, such evaluations are challenging. To overcome this problem, an attractive way is to approximate the bulk service time distribution with a phase-type one, where closed form expressions exist for the waiting time distribution of a MAP/PH/1 queue, and accept a small error on the tail. Using this approximation for the service times, we derive a closed-form expression for the waiting time distribution and we give a first order approximation of the resulting error. For special cases, we additionally propose two different ways to approximate the waiting time distribution, and provide a probabilistic interpretation of the approximation errors and error bounds.

PRESENTATION

Contact
For more information please contact Patty Koorn, workshop officer of Eurandom.

With special thanks and acknowledgement for the contributions of the following sponsors:

P.O. Box 513, 5600 Eindhoven, The Netherlands
tel. +31 40 2478100
e-mail: info@eurandom.tue.nl