European Institute for


November 123, 2012


SUMMARY  SPEAKERS & PARTICIPANTS  PROGRAM & ABSTRACTS  REGISTRATION  CONFERENCE VENUE 
Thursday 
Friday 
Saturday 

09:1509:45 
Registration 
10:0010:45 
Keynote 
Philippe Nain  10:1511:00 
Tutorial 
Onno Boxma  
09:4510:00 
Opening 
10:4511:15 
Invited 
Wouter Minnebo  break 

10:0010:45 
Tutorial 
Peter Taylor  break 
11:1511:45 
Invited 
Shlomi Reuveni  
break 
11:3012:00 
Invited 
Esa Hyytiä  11:4512:15 
Invited 
Eleni Vatamidou  
11:0011:45 
Tutorial 
Peter Taylor  12:0012:30 
Invited 
Athanasia Manou  12:1513:30 
Lunch 

12:0012:30 
Invited 
JanPieter Dorsman  12:3014:00 
Lunch 
13:3014:00 
Invited 
Niek Baer  
12:3014:00 
Lunch 
14:0014:45 
Tutorial 
Ivo Adan  14:0014:30 
Invited 
David Meisch  
14:0014:30 
Invited 
Tuan PhungDuc  14:4515:15 
Invited 
Eline De Cuypere  break 

14:3015:00 
Invited 
Martin Lopez Garcia  break 
14:4515:30 
Keynote 
Benny Van Houdt  
break 
15:3016:15 
Keynote 
Bo Friis Nielsen  
15:3016:15 
Keynote 
Dieter Fiems  break 

break 
16:3017:00 
Invited 
Serban Badila  
16:3017:00 
Invited 
Masha Frolkova  17:0017:30 
Invited 
Giang Nguyen  
17:0017:30 
Invited 
Sophie Hautphenne  
18:3021:00 
Conference Dinner 
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 multidimensional Markov processes, the state space of which is
the set of nonnegative lattice points. The methods for solving the
equilibrium equations of these Markov processes can be divided into
two groups: complexfunction 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.
Onno Boxma
Title: Analysis of queueing models with multiple waiting lines: complexfunction methods
Abstract: This talk is to some extent a sequel, or a counterpart, to the talk of Ivo Adan.
We focus on some complexfunction methods to determine
the generating function, or Laplace transform, of a multidimensional
distribution: the uniformization method
and the boundary value method.
By means of some illustrative examples, we explain their main ideas,
strengths, and limitations.
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, meanfield theory, phasetransition.
Bo Friis Nielsen
Title: Queueing models with matrixexponential 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 matrixexponential 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.
Peter
Taylor
Title: The Physics of MatrixAnalytic Algorithms
Abstract: Since Marcel Neuts first showed that Markov chains of GI/M/1 type have a matrixgeometric stationary distribution in the 1970s and 1980s, the interplay between analytic properties and physical interpretations has played a major part in the development of matrixanalytic 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 matrixanalytic algorithms that have been proposed for analyzing blockstructured continuoustime Markov chains, stochastic fluid models and multitype continuoustime branching processes.
Benny
Van Houdt
Title: Multitype customers with general customer impatience
Abstract: In this lecture we use matrixanalytic methods and fluid queues to study a very general class of queueing systems. More specifically, we focus on a class of multitype Markovian queues with phasetype distributed service and general (typedependent) impatience.
In the first part of the lecture we study the discretetime MMAP[K]/PK[K]/1 queue and show how its main performance characteristics can be computed using a simple QuasiBirthDeath 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 Markovmodulated fluid queue (without thresholds).
In the last part of the lecture we introduce general, typedependent 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.
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 busyperiod 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 branchingtype polling systems will be discussed.
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 interarrival time of customers and their service times are the interclaim 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 pathwise 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 interarrival time (or dually, the interarrival 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 matrixexponential distributions (as in Bladt & Nielsen [1]) in which the joint LaplaceStieltjes transform of the claim size and the interclaim time is a rational function. This class generalizes some bivariate Gamma models already considered in the literature. We obtain exact results for the infinitehorizon ruin probabilities and for the waiting time in the dual queueing model, by using Laplacetransform methods and solving a WienerHopf type boundaryvalue problem.
References
[1] M. Bladt and B.F. Nielsen. Multivariate matrixexponential distributions. Stochastic Models, 26(1):126, 2010.
Niek
Baer
Title: The PH/PH/1 multithreshold 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 QuasiBirthandDeath 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.
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 Krylovsubspace 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 quasibirthdeath process, the phase being the queue content of the finite capacity queue. Such methods do not easily extend to the multiqueue case. However, in the multiqueue 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 twoqueue 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 semifinished products at some point in the production process. Hence, paired queueing applies as the next production stage only starts if there are semifinished 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.
JanPieter
Dorsman
Title: Dynamic repairman assignment in a layered queueing network with correlated queues
Abstract: In the classical machinerepair 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 MRmodel 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 KestenStigum 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.
Sophie
Hautphenne
Title: Algorithmic methods for branching processes
Abstract: We consider a particular class of continuoustime multitype 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/1type Markov process approach to approximate the extinction probability.
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 socalled sizeaware value functions with respect to arbitrary taskspecific holding costs. By sizeaware 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 nontrivial and only some optimality results are available. For example, JointheShortestQueue (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 stateindependent policy, the value functions enable the policy improvement step yielding a robust statedependent task assignment policy.
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$$_{0}
] 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 hostparasitoid 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. GomezCorral, M. Lopez Garcia (2012) Maximum queue lengths during a fixed time interval in the M/M/c retrial queue. In preparation.
[2] A. GomezCorral, M. Lopez Garcia (2012) Maximum population sizes in hostparasitoid models. Under review.
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 rewardcost 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.
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 phasetype (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 phasetype 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.
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.
Giang Nguyen
Title: The morphing of fluid queues into Markovmodulated Brownian motion
Abstract: Ramaswami (2012) shows that standard Brownian motion arises as the limit of a family of Markovmodulated linear fluid processes. We pursue this analysis and show the fluid approximation for Markovmodulated Brownian motion. Furthermore, we prove that the stationary distribution of a Markovmodulated Brownian motion reflected at zero can be obtained from the wellanalyzed 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
PhungDuc
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 leveldependent quasibirthanddeath (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 nonzero 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.
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 twodimensional 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).
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 heavytailed, such evaluations are challenging. To overcome this problem, an attractive way is to approximate the bulk service time distribution with a phasetype 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 closedform 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.
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
email: info@eurandom.tue.nl