logo

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

About | Research | Events | People | Reports | Alumni | ContactHome


 

Workshop

Second Israeli-Dutch Workshop on
Queueing Theory

Eindhoven University of Technology
September 29 - October 1, 2010


Programme

Wednesday September 29, 2010

09.30 Opening  
09.45 - 10.45 D. Perry An Organ Transplantation Model and Double Matching Queues: A New Look
  A. Löpker On the stationary excess operator
10.45 - 11.15 Break  
11.15 - 12.15 O. Perry An Overflow System with Many Servers: Approximations and Implications to Call Center Outsourcing
  S. van Wijk Fairness and Efficiency in Waiting Times for Polling Models with the k-Gated service discipline
12.15 - 13.30 Lunch  
13.30 - 14.30 I. Eliazar Universal generation of fractal statistics: data-traffic, queues, and physics
  N. Litvak Characterization of tail dependence for in-degree and PageRank in complex stochastic networks
14.30 - 15.00 Break  
15.00 - 16.00 N. Shimkin Social Optimality and Pricing in Shared Computing Centers
  Y. Kerner Pricing Time-Sensitive Services Based on Realized Performance
16.00 - 16.30 Break  
16.30 - 17.30 Richard Boucherie Energy consumption in coded queues for wireless information exchange
  Wolfgang Stadje Two Queues Driven by a Birth-Death Process and Coupled by Overflow, Jockeying, and Customers Acting as Servers

Thursday September 30, 2010

10.15 - 11.15 I. Vliegen Optimization of stock levels for service tool inventory
  S. Zacks The Damped Geometric Telegrapher Process
11.15 - 11.45 Break  
11.45 - 12.45 G. J. van Houtum When to use decentralized stocks and lateral transshipment in spare parts networks for high-tech equipment
  F. Karsten Analysis of resource pooling games via a new extension of the Erlang loss function
12.45 - 14.00 Lunch  
14.00 - 15.00 O. Kella Growth collapse processes with phase type inter-collapse time or log phase type collapse ratios
  R. Dekker Trucks waiting in and for container terminals
15.00 - 15.30 Break  
15.30 - 17.00 U. Yechiali Two-Queue Systems where Customers are the Servers
  M. Haviv When to arrive to a queue with tardiness costs?
  J. van der Wal Soft loss systems
  WORKSHOP DINNER  

Friday October 1, 2010

10.15 - 11.15 Y. Nazarathy, Scaling limits of cyclically varying birth-death processes and applications
  J. van Leeuwaarden Critical queues and random graphs
11.15 - 11.45 Break  
11.45- 12.45 G. Weiss First come first served infinite matching with applications to queues with multi-type customer and multi-type servers
  R. Núñez Queija Performance analysis of traffic surges in multi-class communication networks
12.45 - 14.00 Lunch  
14.00 - 15.00 T. de Kok Mathematics converts multi-item multi-echelon networks into serial multi-echelon systems
  M. Mandjes Utility-based appointment scheduling
15.00 - 16.00 Break  
16.00 A. Mandelbaum
(within framework of LOIS lecture series)
Service Engineering: Data-Based Science in support of Service Management, or
"Empirical Adventures in Call-Centers and Hospitals"
  Drinks  

Abstracts


R. Boucherie

Energy consumption in coded queues for wireless information exchange

We show the close relation between network coding and queueing networks with negative and positive customers and use this relation to obtain bounds on the energy consumption in a wireless information exchange setting using network coding.

PRESENTATION


R. Dekker

Trucks waiting in and for container terminals

Congestion of trucks in container terminals has received quite some attention recently, because of high societal costs and emissions because of the waiting. In this presentation we will analyse several aspects of the problem. First we present some empirical facts, explaining the process, the measurements and the arrivals which show a clear time and day pattern. The system may be modelled as a queuing network with time-dependent arrival rates and overload. We analysed it in several ways, using both simulation and time-dependent fluid models. We apply both the Pointwise Stationary Fluid Flow Approximation (PSFFA) proposed by Wang et al. (1996) and the Stationary Backlog Carryover model from Colletz (2007) and compare them. Next, we consider two solutions for the queueing problem, being a separate terminal which is replenished during the night and a so-called truck appointment system, in which trucks are stimulated to spread their arrivals over the day.


I. Eliazar
(joint work with Joseph Klafter)

Universal generation of fractal statistics: data-traffic, queues, and physics

“Fractal statistics” of data traffic – burstiness, long-range dependence and self-similarity – are ubiquitous in modern-age communication systems. Various specific models – such as the superposition of on-off sources – have been devised in order to explain these statistical phenomena. In this talk we establish a unified and universal methodology for the generation of “fractal statistics”. We present a stochastic superposition model which is capable of generating – in a universal fashion – various “fractal statistics”: anomalous diffusion, Levy laws, 1/f noises, and self-similarity. The model considers the superposition of independent stochastic processes: all processes sharing a common – yet arbitrary – stochastic process-pattern; each process having its own random parameters – initiation epoch, amplitude, and frequency. The stochastic superposition model is general and robust, and arises naturally in diverse fields of science and engineering: transmission channels and routers, and Internet servers in Communication; background noises in Physics and Electrical Engineering; probe dynamics in “stochastic baths”, and shot noise processes in Physics; river flows in Hydrology; tax revenues of states in Economics. In the context of Queueing Theory, the stochastic superposition model can be regarded as a generalized M/G/∞ model, in which the superimposed processes represent the random workload processes of incoming jobs. Considering a specific process-statistic of the superposition model’s output, we focus on the following universality question: Is there a randomization of processes’ parameters which renders the output’s process-statistic invariant with respect to the processes’ common stochastic pattern? The answer – for various process-statistics – turns out to be affirmative, and yield the aforementioned “fractal statistics”. This research thus establishes a unified framework that:  (i) explains the universal emergence of “fractal statistics” in diverse fields of science and engineering, and (ii) provides an explicit model and randomization-algorithms that universally yield desired “fractal statistics”. Observed from the “M/G/∞ perspective”, this framework serves as natural and robust model for data-traffic processes displaying “fractal statistics” – which are prevalent in contemporary communication systems.

PRESENTATION


M. Haviv

When to arrive to a queue with tardiness costs?

A random number of customers seek service during some time interval which starts at time zero and can be bounded or not. They face the question of when to arrive so as to minimize their waiting and/or tardiness costs. We look for a Nash equilibrium time of arrival strategy as well as for the the social optimal arrival strategy. Non linear differential equations, which call for numerical solutions, are first suggested. Then, exact solutions for the corresponding fluid approximation models are derived.

PRESENTATION


G.J. van Houtum

When to use decentralized stocks and lateral transshipment in spare parts networks for high-tech equipment
(joint work with A. Kranenburg andA. Scheller-Wolf )

We consider a number of local warehouses that observe demand for expensive, slow-moving items, and that have to satisfy constraints with respect to the aggregate mean waiting time to meet a request. Stock in the local warehouses themselves can be replenished from an ample source, with non-zero lead time. It can be expected that in our setting, common in spare-parts networks, some form of pooling between the local warehouses would be beneficial. In this paper, we examine this premise by comparing three situations: (1) The base case of local warehouses that act as separate stock points, without pooling; (2) Pooling inventory by means of a joint warehouse instead of holding stock in the local warehouses; and (3) Local warehouses that carry stock and share their inventory by means of lateral transshipment. We study the performance of these three configurations via the evaluation of closed-queueing network representations. Using these representations, we obtain analytical results indicating when the situation with lateral transshipment outperforms the others. Furthermore, we obtain numerical results from experiments, inspired by an industrial application, that generate managerial insights.

PRESENTATION


F. Karsten

Analysis of resource pooling games via a new extension of the Erlang loss function

We study a situation where several independent service firms, such as call centers, hold a number of servers for their customer populations. Each firm is modeled as an Erlang loss system and faces holding costs for their servers and penalty costs for lost customers. The firms may collaborate by full pooling of their servers and individual customer streams. We examine the allocation of costs of the pooled system amongst the firms by formulating a cooperative cost game in which each coalition optimizes the number of servers. We identify a cost allocation that is in the core of this game, i.e., no subset of firms has an incentive to split off and form a separate pooling group. For our analysis we define a new extension of the Erlang loss function to a non-integral number of servers and establish several of its properties.

PRESENTATION


O. Kella

Growth collapse processes with phase type inter-collapse time or log phase type collapse ratios

We will discuss growth collapse processes, which are processes that in between collapses do no decrease and at collapse epochs are reduced to a random fraction (collapse ratio) or their pre-collapse state. We will discuss two models in which both the increase is linear. In the first model the distribution of the collapse ratio is general and that of the inter-collapse time is phase-type. In the second model the inter-collapse time has a general distribution and the collapse ratio is the exponent of the negative of a phase type distribution.

PRESENTATION


Y. Kerner

Pricing Time-Sensitive Services Based on Realized Performance
(joint work with
Philipp  Afèche and Opher Baron)

We consider a service provider who can charge the customers according to their delay in the queueing system. The provider's goal is to maximize the expected payment rate. We show that in the case of risk neutral customers the provider's optimal revenue can be achieved by setting a fixed price. We also show that in the case of risk averse customers, reducing the customers' risk is optimal for the provider as well.


T. de Kok

Mathematics converts multi-item multi-echelon networks into serial multi-echelon systems

In this presentation we consider multi-item multi-echelon networks as they occur in real-life: Final products are manufactured from multiple raw materials via multiple subassemblies. Scale efficiencies induce batching of customer demand into production orders. We assume lot sizes are created by batching orders over time. Thus we assume that orders for each item in the network are released according to periodic review base stock policies. As orders generated may face lack of upstream materials, we need to incorporate an appropriate allocation mechanism. Assuming constant replenishment lead times, we synchronize orders for different items according to cumulative lead times with respect to end-items using these items. This synchronization mechanism converts the original multi-item multi-echelon network into one or more divergent single-item multi-echelon networks. Herewith the notion of item is replaced with that of stockpoint. Considering single-item multi-echelon divergent networks under periodic review base stock policies, we assume shortages at a stockpoint, if any, are allocated according to fixed ratios to the stockpoint's successor. Under the resulting control policy we derive optimality equations, assuming linear holding cost for all stockpoints and linear penalty costs for end stockpoints. The optimality equations involve complex probabilistic expressions. Defining auxiliary random variables, we are able to transform the optimality equations into a set of recursive equations that are equivalent to the optimality equations derived by Clark and Scarf in their 1960 seminal paper on serial multi-echelon systems. Though in principle we could solve these equations numerically, we propose an approximate solution procedure. We show that this solution procedure is accurate enough for practical purposes, but that its accuracy reduces as the number of echelons increases or the review periods increase . We formulate a problem, which solution would help to develop a more robust optimization procedure.

PRESENTATION


J. van Leeuwaarden

Critical queues and random graphs

We discuss how to derive scaling limits for random graphs. We consider connected components, and show how these can be described using a queueing (or reflected stochastic) process. For generalized Erdős-Rényi random graphs, we derive limiting results for the critical regime when the number of vertices tends to infinity. Joint work with Shankar Bhamidi and Remco van der Hofstad.

PRESENTATION


N. Litvak

Characterization of tail dependence for in-degree and PageRank in complex stochastic networks
(
joint work with Yana Volkovich, Werner Scheinhardt and Bert Zwart)

World Wide Web is often represented as a directed graph, where in-degree of a node is known to follow a power law distribution. Furthermore, ranking scores computed by the celebrated Google PageRank algorithm also appear to follow a power law with the same exponent as in-degree. This phenomenon can be explain by an analytical model based on branching processes. In this talk we go one step further by characterizing correlations between an in-degree and a PageRank score of a randomly chosen node. The dependencies between power law parameters can be evaluated using the so-called angular measure, a notion introduced in extreme value theory to describe the dependency between very large values of coordinates of a random vector. We use this theory to measure dependencies in Wikipedia, Web, and artificially constructed preferential attachment graphs. The results are strikingly different for the three samples. Next, for our analytical stochastic model, we prove that the angular measure for in-degree and PageRank is concentrated in two points. This logically corresponds to the two main sources of high ranking: large in-degree and a high rank of one of the ancestors. However, capturing the angular measure observed in experiments remains a challenging open problem.

PRESENTATION


A. Löpker

On the stationary excess operator
Joint work with Yoav Kerner

In a renewal process the remaining lifetime and the age at time t both converge to a common limit distribution, the equilibrium distribution, as t tends to infinity. One can define the stationary excess operator as the operator that maps a distribution function to its equilibrium distribution. Already in the 60ies and 70ies researchers investigated the properties of this operator. In particular one was interested in the iterated application of the operator and the question whether infinite application leads to some interesting limit. It seems however, that so far there are no significant applications of the higher order stationary excess operators. Instead of finding such an application, we define an approximation to the stationary excess operator that has an immediate application: it is the overshoot of a random variable over an exponential random variable. We investigate the higher order powers of this overshoot operator.

PRESENTATION


A. Mandelbaum

Service Engineering: Data-Based Science in support of Service Management, or
"Empirical Adventures in Call-Centers and Hospitals"

I shall describe examples of complex service operations for which data-based simple models have been found useful - I refer to this as "Simple Models at the Service of Complex Realities." The examples cover hospitals, banks, courts and more, but most attention will be given to telephone call centers. I view these service systems through the mathematical lenses of Queueing Science, with a bias towards Statistics.

More specifically, through the examples I review an emerging scientific discipline which is now being referred to as Service Engineering. I focus on empirical findings that motivate or are motivated by (or both) interesting research questions. These findings give rise to model-features that are prerequisite for useful service models, for example customers' (im)patience, time-varying service demand (predictable variability), heterogeneity of customers and servers (skills-based routing), over-dispersion in Poisson arrivals, generally-distributed (as opposed to exponential) service- and patience-durations, and more. Empirical analysis also enables validation of existing models and protocols, either supporting or refuting their relevance and robustness.
The mathematical framework for my models is asymptotic queueing theory, where limits are taken as the number of servers increases indefinitely, in a way that maintains a delicate balance between staffing level and offered-load. Asymptotic analysis reveals an operational regime that achieves, under already moderate scale, remarkably high levels of both service quality and efficiency. This is the QED regime, discovered by Erlang and substantiated mathematically by Halfin & Whitt. (QED = Quality- & Efficiency-Driven).
My main data-source is a unique data repository from call-centers and hospitals. The data is maintained at the Technion's SEE Laboratory (SEE = Service Enterprise Engineering; see http://ie.technion.ac.il/Labs/Serveng/). It is unique in that it is transaction-based: it details the individual operational history of all the service transactions (e.g. calls in a call center or patients in an emergency department). For example, one source of data, publicly available, is a network of 4 call centers of a U.S. bank, spanning 2.5 years and covering about 1000 agents; there are 218,047,488 telephone calls overall, out of which 41,646,142 where served by agents, while the rest were handled by answering machines. The data can be explored via SEEStat, an environment for online data analysis. SEEStat is accessible at http://seeserver.iem.technion.ac.il/see-terminal/, after registration.

PRESENTATION


M. Mandjes

Utility-based appointment scheduling
(joint work with B. Kemper and Ch. Klaassen)

When setting up an appointment schedule, one aims at achieving a proper balance between the interests of the service provider and the customers: if the system is frequently idle, then it is not functioning in a cost-effective manner, whereas if it is virtually always busy, the customers’ waiting time may become substantial. In this paper we first analyze a na¨ıve scheduling scheme, in which the arrival times equal the sum of the expected service times of the previous customers. The shortcomings of this scheme are pointed out by showing that the customers’ expected waiting times in the long run explode (while it has for the service provider the attractive property of hardly ever resulting in an idle system). We therefore investigate schemes that better align the utilities of the service provider and the customers. With Ii the idle time before the i-th customer, and Wi denoting the waiting time of the i-th customer, it is shown how to set up a schedule that sequentially minimizes utility functions (or: risks) of the type Eg(Ii)+Eh(Wi), for all customers i and given nondecreasing functions h(•) and g(•). A next question that we address concerns the ordering of the customers; for the special case of exponentially distributed customers it entails that they should be ordered such that their means (and hence also variances) increase. In steady-state the corresponding appointment time at the optimal interarrival times can be computed explicitly for a variety of functions g(•) and h(•). This is illustrated by a number of numerical examples; these also address how fast the transient schedule converges to the corresponding steady-state schedule.

PRESENTATION


Y. Nazarathy

Scaling limits of cyclically varying birth-death processes and applications
(joint work with Matthieu Jonckheere)

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.
In this talk we present a different application: 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.

PRESENTATION


R. Núñez Queija

Performance analysis of traffic surges in multi-class communication networks
(joint work with Matthieu Jonckheere; Balakrishna Prabhu)

We investigate a communication channel with multiple traffic classes. Temporary traffic surges due to one class of users can signicantly degrade the performance of other classes. In this paper, we examine for a suitably-scaled set of parameters the complex interaction occurring between the several classes of traffic when the unstable class is penalized proportionally to its level of congestion. On a suitable timescale, the trajectory of the temporarily unstable class can be described by a differential equation while that of the stable classes retain their stochastic nature. Although the time-scales decouple, the dynamics of the temporarily unstable and the stable classes continue to influence each other.

PRESENTATION


D. Perry

An Organ Transplantation Model and Double Matching Queues: A New Look
(joint work with Onno Boxma Israel David and Wolfgang Stadje)

The waiting-list management of the organ transplantation problem looks like a typical application of queueing theory. The customers are patients who suffer from, e.g., organ failure (kidney, liver, heart, etc.) and who register on the public waiting list. However, there are several aspects which make it difficult to implement standard queueing models here since the notion of "service" formally does not exist. The servers are organs donated from the dead, and they arrive sequentially and randomly. One thus faces a double-matched queue (DMQ); the line of organs on the shelf and the line of customers waiting for transplantation. The two queues are strongly correlated with each other; they cannot be non-empty simultaneously (but both of them can be empty). Also, the queues posses a non symmetric property. While the customers have random patience (lifetime), the organs have a constant finite shelflife that without loss of generality is equal to 1. Accordingly, in case of double Poisson arrivals, the sample path of the VOP (virtual outdating process) is composed of two regions: below level 1 and above level 1. Below 1 the sample path is stochastically equal to that of the finite dam model and above 1 it is equal to a the work of the M/M/1 + G queue. Some possible extensions to the basic model will be introduced.

PRESENTATION


O. Perry
(joint work with Itay Gurvich)

An Overflow System with Many Servers: Approximations and Implications to Call Center Outsourcing

Motivated by call-center outsourcing problems, we consider a network with multiple call centers overflowing some of their calls to a central call center. Relying on a separation of time scales we establish heavy-traffic approximations and prove an asymptotic independence result which facilitates, in turn, simplified expressions for the customer waiting-time distribution. The asymptotic independence is shown to be useful in solving some call center optimization problems.

 

PRESENTATION

 


N. Shimkin

Social Optimality and Pricing in Shared Computing Centers
(joint work with Ishai Menache and Asuman Ozdaglar)

Cloud computing centers offer, among other services, on-line access to computing resources of flexible size and capabilities. We consider a computing facility of this type that can offer simultaneous service to multiple heterogeneous users, each associated with a distinct job. The major performance criterion for each job is assumed to be its execution time, which depends on computing resources allocate to it. Our main concern here is in maximizing the steady-state social surplus, which comprises of aggregate value of executed jobs minus a linear delay cost and load-dependent operating expenses. This is to be achieved by regulating the resource allocation to arriving jobs, as well as controlling the arrival rates of each job class. Our formulation relies on basic notions of welfare economics, augmented by queueing aspects that arise due to varying execution times. Under appropriate convexity assumptions on the execution times and operating costs, we establish existence and uniqueness of the social optimum, which is uniquely characterized by first-order conditions. We proceed to show that this social optimum may be achieved by simple per-unit pricing, which charges a fixed amount per unit time and resource from all users. We further consider some additional issues and extensions that include on-line price tuning, the relation between profit-maximizing pricing and the social optimum, the effect of job blocking due to finite resources, and non-linear delay costs.

PRESENTATION


W. Stadje

Two Queues Driven by a Birth-Death Process and Coupled by Overflow,  Jockeying, and Customers Acting as Servers

We consider two interacting queueing systems with overflows, jockeying and customers in the first system acting as servers for the second one. The number of customers in the first queue evolves as a birth and death process on the state space {0,...,N} with state-dependent arrival and service rates and reflecting barriers. A fixed number of slots in the first queue may act as servers for the second queue and the remaining slots may act as waiting positions. The arrival stream of the second queue consists of the overflow from the first queue plus a Poisson arrival stream independent of the first queue. Since the customers in the first queue act as servers for the second queue, the  service rate in the second queue depends on the state of the first one. We give a necessary and sufficient stability condition in terms of the  system parameters and derive the two-dimensional steady-state distribution of the queue lengths. Based on these results, several steady-state quantities of interest can be determined and are explicitly given in some special cases. Our work generalizes a model presented recently by Perel and Yechiali. We further extend the model to include jockeying policies like the following: if at least one customer is present in the second queue and the first one is empty, then a certain number of customers is forced to move from the second queue to the first one and starts serving the second queue. The analysis can be generalized to these jockeying models. This is joint work with Peter Sendfeld.

PRESENTATION


I. Vliegen

Optimization of stock levels for service tool inventory

Many Original Equipment Manufacturers not only sell machines to their customers, but also service contracts in which a certain system availability level is agreed upon. To ensure this availability level is met, a suffciently fast provisioning of spare parts, service engineers, and service tools is required when a machine failure occurs. This presentation focuses on the planning problem for service tools, and is based on an actual service tools planning problem of an OEM in the semiconductor supplier industry. The objective is to minimize the investment in service tools, subject to meeting the service level agreed upon for the aggregate order fill rate, i.e., the percentage of demands for which all requested tools are delivered from stock. The aim of this study is to provide a heuristic to determine near-optimal base stock levels for this optimization problem. We develop four heuristics, and compare the heuristics with each other on the basis of costs, service level and running time of the heuristics, and with a Lagrangian lower bound on the costs. Furthermore, we compare two of the heuristics on a case, based on a real-life data. We conclude that the heuristic that takes into account some of the characteristics of service tools outperforms the heuristic currently used for the stock planning of spare parts. However, including all details leads to slow solutions, which makes it impossible to use in real-life.

PRESENTATION


 J. van der Wal

Soft loss systems

Some systems are loss systems, but not in the hard sense. An example is an IC unit. If all IC beds are occupied and a new patient arrives, something has to be done. In this presentation we will be trying to get a feeling for how to look at the performance of such a system.

PRESENTATION


G. Weiss

First come first served infinite matching with applications to queues with multi-type customer and multi-type servers
(joint work with Ivo Adan, Rene Caldentey, Cor Hurkens and Ed Kaplan, as well as work by Jeremy Visschers, Rishy Talreja and Ward Whitt)

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 survey some results for four different situations
- For a loss system we find conditions for reversibility and insensitivity.
- For a manufacturing type system, in which there is enough capacity to serve all jobs, we discuss a product form solution.
- For an overloaded system with reneging, we emphasize a global first come first served property under fluid scaling.
These queueing models are intimately connected to the following discrete time Markovian model, which is both simpler and more general:
- There is a infinite sequence of customers with i.i.d. types, and infinite sequence of servers of i.i.d. types and the two are matched according to the bipartite customer server graph, using first come first matched.
We obtain a product form stationary distribution for this system, which we use to calculate matching rates.

PRESENTATION


S. van Wijk

Fairness and Efficiency in Waiting Times for Polling Models with the k-Gated service discipline
(joint work with Ivo Adan, Onno Boxma and Adam Wierman)

We consider a polling system, where a single server cyclically serves the queues, with positive switch-over times. Our goal is to minimize the differences in the mean waiting times at each of the queues, i.e. to achieve maximal fairness, without giving up too much on the efficiency of the system. For this, we introduce the k-Gated service discipline, which can be seen as a hybrid version of the well known exhaustive discipline (very efficient, less fair) and gated discipline (less efficient, usually more fair). Upon arrival of the server at queue i, it services the queue consecutively an integer number of times, ki, according to the gated discipline. That is, a first gate closes and only the customers before this gate are served, then a second gate closes, and again only the customers before this gate are served, etcetera, until this is done ki times, or until the queue becomes empty. We derive the distribution of the waiting times, a pseudo conservation law for the weighted sum of the mean waiting times, and the fluid limits of the waiting times. The latter we use for optimization of the ki's, and we provide heuristics for well working settings.

PRESENTATION


U. Yechiali
(joint work with Efrat Perel)

Two-Queue Systems where Customers are the Servers

We consider systems comprised of two interlacing queues where customers of each queue are the servers of the other queue. Denoting by Li the number of customers in queue i = 1, 2, we study four models: (i)Queue 1 (Q1) operates as a multi-server limited-buffer M(λ1)/M(μ1)/L2/max{0,N-L2} system, while queue 2 (Q2) operates as a single-server M(λ2)/M(μ2L1)/1 queue. That is, at any moment, the L2 customers present in Q2 act as the servers of the limited-buffer Q_1 , where service time of each individual customer is exponentially distributed with parameter μ1. The customers of Q_2 are served by the L1 customers in Q1, who join hands together to form a single server with exponentially distributed service time of rate μ2L1. Arrivals to Qi follow a Poisson process with rate λi.  (ii)  Q1 operates as in model (i), but Q2 operates as a multi-server M(λ2)/M(μ2)/L1 system. (iii) Q1 is a limited-buffer single-server M(λ1)/M(μ1L2)/1/N-1 queue, while Q2 is an M(λ2)/M(μ2L1)/1 queue.  (iv) Q1 is as in model (iii), but Q2 is an M(λ2)/M(μ2)/L1 system. For each model we derive the (conditional) probability generating function of L1 (given L2) and determine the condition for stability, where in models (i) and (ii) we apply Matrix Geometric analysis. We further calculate the means of Li, along with their correlation coefficient, and compare between the models.  

PRESENTATION


S. Zacks

The Damped Geometric Telegrapher Process

The geometric telegrapher process has been proposed as a model for the dynamics of price risky assets. We consider a damped telegrapher process where the random times between consecutive slopes is exponential with linearly increasing parameter. The main characteristics of this process and its stationary limit will be discussed.

PRESENTATION


Last updated 22-okt-2010,
By
PK

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