European Institute for Statistics, Probability, Stochastic Operations Research and its Applications

About | Research | Events | People | Reports | Alumni | Contact | Home

Overview talks 2005 2006 2007 2008 2009

Queueing and Performance Analysis problem sessions

Queueing and Performance Analysis seminars - 2010

2010

Brian Fralix, (Clemson University, USA), July 20, 2010
(Joint work with Colin Gallagher, Clemson University)

We present a simple proof of the Wiener-Hopf factorization, for a specific subclass of Piecewise-Deterministic Markov Processes (PDMPs). The classical Wiener-Hopf factorizations for both a random walk and a Levy process follow as consequences of our main result. Moreover, we also illustrate how another aspect of Wiener's work is connected to the factorization.

Marvin Steyaert, (Fac. Biomedische Technologie, TU/e Eindhoven), June 23, 2010

Stochastic modeling of intracellular signaling and regulation

Biochemical reaction networks are often described using deterministic models based on macroscopic rate equations. However, for small numbers of molecules, intrinsic noise can play a significant role and stochastic methods may thus be required. This may for instance be the case for some reaction networks involved in intracellular signaling and regulation.
In this presentation we discuss how the behavior of a spatially homogeneous deterministic model can be compared to that of a corresponding mesoscopic stochastic model. To this end, we have developed a framework based on the use of a potential function. Various aspects about the behavior of both the deterministic and stochastic model can be expressed in terms of this potential. This yields a straightforward and intuitive insight into the relations between both models. In addition, it allows expressions for the dependence of various properties of the stochastic model on the number of molecules. This approach can be applied to both elementary reaction systems and to systems with more complex kinetics.

Yoni Nazarathy (EURANDOM, Eindhoven, The Netherlands), June 22, 2010
(Joint work with Matthieu Jonckheere)

Using Scaling Limits to approximate the stationary distributions of cyclically varying birth-death processes

Fluid limits of stochastic queuing systems have received considerable attention in recent years. The general idea is to scale space, time and/or system parameters as to obtain a simpler, yet accurate description of the system. A basic example is the single server queue with time speeded up and space scaled down at the same rate. A second well known example is the Markovian infinite server queue with the arrival rate speeded up and space scaled down at the same rate. Such scalings and their network generalizations are often useful for obtaining stability conditions and approximating optimal control policies.
We consider birth-death processes with general transition rates. We obtain an asymptotic scaling result, generalizing the Markovian single server and infinite server cases. We apply our results to the steady-state analysis of queuing systems with cyclic or time varying behavior. Examples are systems governed by deterministic cycles, queues with hysteresis control and queues with Markov-modulated arrival or service rates. The unifying property of such systems,  is that if they are properly scaled, the resulting trajectories follow a cyclic or piece-wise deterministic behavior which is determined by the asymptotic scaling. This scaling allows for asymptotically exact approximations of stationary distributions.
(Joint work with Matthieu Jonckheere)

Yoshitaka Takahashi (Waseda University, Tokyo, Japan), May 28, 2010

A single-server queueing system with modified service mechanism

We consider a single-server GI/G/1 queueing system with modified service mechanism.  By modified service mechanism, we mean that the service time distribution (H_0) for the customers arriving to find the system idle may be different from the service time distribution (H_1) for the customers arriving to find the system busy.  We present qualitative relationships among the performance measures in the system.  Approximating the virtual waiting time process via the diffusion process and combining the qualitative relationships, we propose a new approximate formula for the mean performance measures.  For special cases, our approximation is seen to be consistent with the previously-obtained exact results for the M/G/1 queueing system with modified service mechanism, and it is further seen to be consistent with the previously-proposed approximate results  for the GI/GI/1 queueing system with standard ( H_0 = H_1 ) service mechanism.

Ananth Krishnamurthy (University of Wisconsin-Madison), May 21, 2010
(joint work with Deng Ge and Oguzhan Alagoz)

Integrating Advanced Demand Information in Kanban Controlled Systems

This research investigates the benefits of integration of advance demand information (ADI) with the kanban control system (KCS). ADI shared by customers is integrated into production release policies thereby enabling simultaneous improvements in service levels and reductions in inventory and costs. Under Markovian assumptions, an exact analysis of the production system is carried out. Through numerical studies, the system performance is compared to those obtained from classical kanban control system and base stock system with ADI. Subsequently, optimal release control policies are determined by analyzing the underlying Markov Decision Process. The optimal release policies are shown to have a simple threshold structure and numerical studies illustrate that these policies could result in considerable cost savings.

In this talk, we will discuss two different simulation-based algorithms. In the first, our goal is to estimate a function, which is assumed to be convex, from simulations conducted at various points in a d-dimensional convex domain. The estimator is formed by searching for the convex function which minimizes a sum of squares, and involves solving a (finite-dimensional) quadratic program. Our main result is a proof that this estimator is consistent, in the sense that it converges uniformly a.s. on compact subsets of the domain, thereby generalizing known results establishing consistency in the one-dimensional case. This type of estimator also arises naturally in the estimation of consumer preference functions. Our second simulation-based algorithm is concerned with optimization of a function that is assumed convex, in which both the function values and gradients can be estimated by simulation. In this second setting, we are able to identify the rate of convergence and the limit distribution that arises when the evaluation points are generated non-adaptively. This talk is based on joint work with Yen Lin Chia, Eunji Lim and Wei Wu.

Kilian Raschel (Paris VI), April 21, 2010

Counting walks in a quadrant: a unified approach via boundary value problems

It is a matter of counting the number of paths of the plane, moving according to a given jumps set, starting at the origin and ending at some point in a certain time, while remaining in a quadrant.

In this talk I will explain how to make explicit an integral representation of this number of walks, by showing that the associated generating function verifies some boundary value problem.

Alaa Elwany (TU/e - IE&IS). April 13, 2010

Structured Maintenance Policies for Systems with Complex Degradation Processes and Dedicated Sensors

We consider a system that degrades during operation, and whose degradation can be monitored in real-time using sensor technology. The presentation is divided into two main parts:

(1) Sensor-based Degradation Modeling: We present a random coefficients degradation model that utilizes real-time sensory information to compute and periodically update the remaining life distribution (RLD) of partially degraded components. We start by discussing the degradation model assumptions, then present a Bayesian updating framework used to revise the RLD.

(2) Structured Replacement Policies: We present a single-unit replacement problem for a degrading system subject to condition monitoring using dedicated sensors. First, we present a Markov decision process formulation for the replacement problem, and then we show that the structure of the optimal replacement policy is a monotonically non-decreasing control limit policy.

We focus on presenting interesting research challenges and future extensions for the above two models. These challenges are primarily within the scope of Brwonian motion with positive drift, Markov decision processes, and Bayesian statistics.

Ken Duffy (Hamilton Institute, National University of Ireland), February 18, 2010

How hard is it to estimate a large deviations rate function or Loynes' exponent?

The Large Deviations Principle (LDP) has long since been known to hold for the partial-sums processes for a large class of sequences of real-valued random variables. There are numerous applications of this result in everything from statistical physics to information theory. In queueing systems, for example, this LDP has been used to deduce that the stationary waiting-time distribution of a FIFO possess logarithmic asymptotics, with an exponent that we dub Loynes' exponent, in broad generality.

To convert the qualitative observation of exponential decay of probabilities into a quantitative predictions that are practically useful, it is necessary to know the rate function related to the the LDP. If one does not have a priori knowledge regarding the stochastic process in question, given observations of the process what are the statistical limits of a non-parametric estimator of the rate function and, consequently, Loynes' exponent?

Under restrictive assumptions, we present results that prove that one can construct sequences of non-parametric estimators of the rate function and Loynes' exponent that themselves satisfy the LDP. That is the probability the estimate differes from the real quantity, decays exponentially with the number of observations.

We conjecture that this holds in significantly greater generality than we have thus far been able to prove. We provide some evidence for this suspicion and aim to indicate the technical challenges that would have to be overcome to establish.

This talk is based on work two sets of work, one with A. P. Metcalfe (Paris 6) and one with S. P. Meyn (Illinois).

Gideon Weiss (University of Haifa), February 18, 2010

Queuing systems with multi-type jobs and multi-type servers under FCFS discipline

We consider a system where jobs of several types are served by servers of several types, and a bipartite graph between server types and job types describes feasible assignments. This is a common situation in manufacturing, call centers with skill based routing, matching of parent-child in adoption or matching in kidney transplants etc.

We consider the case of first come first served policy:  jobs are assigned to the first available feasible server in order of their arrivals.  We will survey some results for four different situations:

For a loss system, we discover a reversible process.
For stable system, in which there is enough capacity to serve all jobs with no congestion, we discuss a product form solution.
For an overloaded system with reneging, we emphasize a global first come first served property under fluid scaling.
For a balanced model we consider the matching of an infinite sequence of jobs and an infinite sequence of servers, and discuss its modeling by  a Markov chain.

This talk surveys work with Rene Caldentey and Ed Kaplan, as well as work by Jeremy Visschers, Ivo Adan and Cor Hurkens, and by Rishy Talreja and Ward Whitt.

David Perry (University of Haifa, Israel), Feburary 2, 2010

A New Look at Organ Transplantation Models and Double Matching Queues

Abstract: We propose a prototype model for the problem of managing waiting lists for organ transplantations. The model captures the double-queue nature of the problem: there is a queue of patients, but also a queue of organs. Both may suffer from "impatience": the health of a patient may deteriorate, and organs cannot be preserved longer than a certain amount of time. Using tools from queueing theory, we derive explicit results for key performance criteria: the rate of unsatisfied demands and of organ outdatings, the steady-state distribution of the number of organs on the shelf, the waiting time of a patient, and the long-run fraction of time during which the shelf is empty of organs. As will seen the dynamics of the virtual outdating process is closely related to workload of the M/G/1+G queue. This is a joint work with Onno J. Boxma , Israel David and Wolfgang Stadje

Mahmut Parlar, McMaster University, January 22, 2010

Operations Research with Maple: Methods and Models

Maple is a sophisticated symbolic computer algebra system with a mathematical knowledge base that includes calculus, linear algebra, optimization, ordinary and partial differential equations, number theory, logic, graph theory, combinatorics, probability and statistics, transform methods, and more. Although Maple's main strength is in its ability to perform symbolic manipulations, it also has a substantial knowledge of a large number of numerical methods and it can plot attractive-looking and publication-quality 2D and 3D graphs. After almost three decades of continuous improvement of its mathematical capabilities, Maple can now boast a user base of more than 300,000 academics, researchers and students in different areas of mathematics, science and engineering.
Can Maple be useful in the type of modelling work that we do in operations research (OR), management science (and in related disciplines of statistics, operations management, industrial engineering, systems engineering and economics)? In my presentation I hope to provide an affirmative answer to this question.
To that end, I will first give a brief tour of Maple and its treatment of some of the mathematical techniques useful in OR modelling, e.g., algebra, calculus, probability and statistics, differential equations, linear algebra and transform methods. Next, I will discuss some examples of OR techniques such as linear, nonlinear and dynamic programming and stochastic processes where Maple can find solutions in symbolic form. I will then describe the use of Maple in the analysis of OR systems including inventory theory and queueing theory. This will be followed by a description of Maple's random variate generators and some examples of static and dynamic simulation.
I will conclude my workshop by swatting a few Maple bugs to show that even Maple can make mistakes and it is the user's responsibility to follow the age-old maxim of "caveat emptor" and to check the accuracy of output produced by Maple. The workshop will be based on my book "Interactive Operations Research with Maple: Methods and Models" that was published by Birkhauser, Boston.

Last modified: 14-07-10
Maintained by P.Koorn