About | Research | Events | People | Reports | Alumni | Contact | Home
From September 2011, the QPA seminars will
be integrated in the new STO(chastics) Seminar Series.
Please follow the
link for further details.
Queueing and Performance Analysis seminars
Overview talks 2005 2006 2007 2008 2009 2010
Queueing and Performance Analysis problem sessions
Jevgenijs Ivanovs, August 31, 2011
Occupation densities in solving exit problems for one-sided Levy processes
In this talk I will present a new approach to construct a so-called scale function for a Levy process which does not have positive jumps. This function plays a fundamental role in various exit problems. In particular, it can be used to identify first exit time of the process from an interval through its upper boundary. Our construction of the scale function is based on a number of novel observations. It shows intrinsic relation of the scale function and the expected occupation density at 0 computed up to a certain time. Furthermore, this construction can be extended to so called Markov additive processes. This talk relies on very basic concepts such as the strong Markov property of a Levy process and does not require deep knowledge of the theory of Levy processes.
Gideon Weiss, August 24, 2011
Skill-based service systems with FCFS service
I will talk about matching an infinite sequence of multi-type customers with a sequence of multi-type services, subject to a bipartite compatibility graph, on a FCFS (first come first served) basis. Some very simple formulas emerge to describe the stationary behavior of such matchings. I will then explain how we believe this can be used to obtain approximations for the performance of many server skilled based service systems, when they are overloaded and stabilized by abandonments, and service is FCFS. This is joint work with Ivo Adan.
Mariana Olvera, July 13, 2011
Weighted branching processes and applications to information ranking
We present a new theoretical framework to study recursions on weighted branching trees with generally dependent real-valued weights. Our main result is a full extension of the Implicit Renewal Theorem of Goldie (1991), and it can be used to describe the tail behavior of the solutions to a wide range of stochastic recursions on trees. We illustrate its applications with the linear nonhomogeneous fixed point equation R = sum_{i=1}^N C_i R_i + Q, where {R_i} is a sequence of iid random variables having the same distribution as R, independent of the real valued vector (Q,N, C_1,..., C_N), N in {1,2, ...} U {infty}. This linear fixed point equation appears in the analysis of ranking algorithms, for example, Google's PageRank, where R represents the rank of a randomly selected webpage. We discuss how the analysis of the solution R can be used to design new algorithms with a prespecified steady- state behavior.
Guodong Pang, May 31, 2011
Heavy-Traffic Limits for Infinite-Server Queues with Dependent Service Times
In service systems, service times are often correlated, for example, the treatment of patients arriving to an emergency department in groups due to a traffic accident or food poisoning incident. Motivated by such systems, we prove heavy-traffic limits for infinite-server queues with dependent service times and characterize the distribution of the limit queue-length process. We impose general assumptions on the system, where the external arrival process satisfies a FCLT and the service times form a sequence of weakly dependent stationary sequence with a general continuous distribution. This includes the concrete example that customers arrive in batches, service times within each batch are symmetrically correlated while service times across batches are independent. The FCLT limit of the queue-length process is a continuous two-parameter Gaussian process (random field) involving a generalized Kiefer process. We give explicit formulas for the time-dependent mean and variance of the resulting Gaussian approximation when the arrival limit process is a Brownian motion. The dependence among service times does not affect the mean, but can affect the variance significantly. We interpret the variance formula in terms of the means of individual service times, minimum of two independent service times and minimum of two dependent service times, and show how to quantify the impact of dependence.
Antonis Economou, March 31, 2011
The single server queue with synchronized repeated services
(joint work with Stella Kapodistria and Jacques Resing)
We consider a single server queueing system with generally distributed
synchronized services. More specifically, customers arrive according to a
Poisson process and there is a single server that provides service, if there is
at least one customer present in the system. Upon the initialization of a
service, all present customers start to get service simultaneously. We consider
the gated version of the model, that is, customers who arrive during a service
time do not receive service immediately but wait for the beginning of the next
service time. At service completion epochs, all served customers decide
simultaneously and independently whether they will leave the system or stay for
another service. The probability that a served customer gets another service is
the same for all customers. Therefore, the number of customers in the system is
reduced according to a binomial distribution.
We study the model and derive its main performance measures that include the
equilibrium distribution of the number of customers at service completion epochs
and in continuous time, the busy period and the sojourn time distributions.
Moreover, we prove some limiting results regarding the behavior of the system in
the extreme cases of the synchronization level. Several variants and extensions
of the model are also discussed.
The reading seminar is targeted at a wide
audience interested in (applications of) interacting-particle models,
performance models for wireless networks, or simply stochastic networks in
general. In particular, we intend the material to be accessible to anyone with a
graduate-level knowledge of applied probability.
Format:
The format is envisioned to be informal, with plenty of interaction and little
preparation effort. Specifically, one of the participants will be presenting a
paper or set of papers from the literature, i.e., walking the audience through
the material using the blackboard or possibly a few supporting slides when
appropriate. The topic of the paper will typically be closely related to the
research activities of the presenter, and could serve as a jumping board for a
discussion of the specific problem the presenter is working on.
Tentative outline:
1. Basic model, connection with loss networks, interacting-particle systems 2.
Fairness issues, Markov random fields 3. Achievable region, utility
maximization 4. Glauber dynamics, mixing times, starvation effects 5.
Insensitivity properties, stability issues 6. Queue-based random-access
algorithms.
Time:
The plan is to have about 6 sessions, each consisting of 2 45-minute
presentations interspersed by brief break. The intended time period will
strongly overlap with the Stochastic Activity month of EURANDOM in April, with
Tuesday as the candidate day of the week, e.g. starting March 29 and continuing
through May 10.
PAPER 1 PAPER 2 PAPER 3 PAPER 4
Vidyadhar Kulkarni (University of North Carolina at Chapel Hill), March 8, 2011
Optimal deployment and routing of multi-class correlated traffic to multiple servers
Correlated traffic streams belonging to N classes arrive at a system of M servers. We can enable any server to handle any subset of the N classes of traffic. This is called the deployment. The traffic of a given class can be split between any servers that are enabled to handle that class. This is called routing. The aim is to find the optimal deployment and the optimal routing of the traffic to minimize the deployment cost and the congestion cost. We shall formulate the problem as a mixed non-linear integer programming problem and present a heuristic to solve it.
Fabian Wirth (University of Würzburg, Germany), January 11, 2011
Structure preserving model reduction for logistic systems
In modern logistics applications large scale networks are increasingly important, for instance due to the emergence of transnational supply chains. Due to their size analysis or simulation of such networks becomes expensive to such an extent that is is desirable to derive approximate models with lower complexity, that retain important structural properties of the complex network. In this talk we will discuss techniques of model reduction that help in preserving important structural components of a given logistics network while reducing the complexity to arrive at models that are amenable to analysis. The techniques rely on results from queueing theory, which provides the reference framework for the modelling of logistics networks and ideas from graph theory related to ranking schemes.
Josh Reed (New York University), January 6, 2011
Hazard Rate Scaling of the Abandonment Distribution for the GI/M/n + GI Queue in Heavy Traffic
We obtain a heavy traffic limit for the GI/M/n+GI queue which includes the entire patience time distribution. Our main approach is to scale the hazard rate function of the patience time distribution in such a way such that our resulting diffusion approximation contains the entire hazard rate function. We then show through numerical studies that for various key performance measures, our approximations outperform those commonly used in practice.
Last modified:
14-10-11
Maintained by
PK
P.O. Box 513, 5600 MB Eindhoven, The Netherlands
tel. +31 40 2478100 fax +31 40 2478190
e-mail: info@eurandom.tue.nl