Rami Atar (Keynote)

Moderate deviation approach to heavy traffic

There is a vast literature on heavy traffic analysis of controlled queueing models at the diffusion scale. In this talk I will describe recent developments on the alternative approach that considers these models at the moderate deviation scale.

Ioannis Dimitriou

Multiclass retrial queues with preemptive priorities

Retrial queueing systems are characterized by the feature that an arriving customer who finds all the servers busy leaves the system and repeats his demand after a random amount of time. In such a case we assume that the blocked customer joins a virtual queue, called the orbit queue. In this work we study a single server retrial queueing system accepting n types of customers. We assume that customers of type i have preemptive priority over customers of type j, i < j. Customers of type 1 are queued in an infinite capacity ordinary queue and served in a FIFO discipline. An arriving type 1 customer who finds the server busy with a customer of type i (i = 2, ..., n) pushes him in his own orbit and occupy the server. The behavior of customers of type i, i = 2, ..., n is described as follows. If a newly arriving customer of type i, i = 2, ..., n finds the server busy with a customer of type j, where i < j, pushes the customer in service in his own orbit and occupy the server. Otherwise the newly arriving customer of type i, is blocked and routed to a seperate type i orbit queue. Both blocked and interrupted customers of type i, i = 2, ..., n, leave the system and repeat their demand individually after an exponentially distributed amount of time. Such a queueing system serves as a model for competing job streams in a carrier sensing multiple access system. We study the queueing system using multi-dimensional probability generating functions. For such a model we obtain the mean number of type i (i = 1, 2, ..., n) customers in steady state and use them to draw conclusions from numerical calculations.

Martin Erausquin

Job scheduling in a single-server in a random environment

We discuss the problem of scheduling stochastic jobs in a single-server system, where the capacity of the system varies over time. The Gittins' index policy, which is known to be optimal in systems with constant capacity, turns out to be suboptimal in the general case. However, Glazebrook 87 showed the optimality of Gittins' index in ON-OFF systems with geometric ON periods. We give an alternative proof for this result, provide a new expression for the index, and use it to characterize the optimal policy when the service time distributions have some specific properties.

Ragavendran Gopalakrishnan

Staffing and Routing to Incentivize Servers in Many-Server Systems

Traditionally, research focusing on the design of scheduling and staffing policies for service systems has modeled servers as having fixed (possibly heterogeneous) service rates. However, service systems are often staffed by people. Then, the rate a server chooses to work may be impacted by the scheduling and staffing policies used by the system. We present a model for such "strategic servers'' that choose their service rate in order to maximize a trade-off between an "effort cost'', which captures the idea that servers exert more effort when working at a faster rate, and a "value of idleness'', which assumes that servers prefer to be idle as much as possible. We re-visit routing and staffing questions for an M/M/N system in this strategic server framework. First, we establish the conditions for the existence of a symmetric equilibrium service rate under any idle-time-order-based routing policy. Then, we find the staffing level that asymptotically minimizes linear staffing and waiting costs as the arrival rate grows large. An important interesting insight is that that asymptotically optimal staffing level staffs many more servers (of the order of the arrival rate more) than the common square-root staffing policy that has been shown to be asymptotically optimal in the conventional M/M/N setting, when servers are not strategic.

Anindya Goswami

Risk-sensitive cost for a Markovian multiclass queue with priority

A multi-class M/M/1 system, with service rate $\mu_in$ for class-$i$ customers, is considered with the risk-sensitive cost criterion $n^{-1}\log E\exp\sum_ic_iX^n_i(T)$, where $c_i>0$, $T>0$ are constants, and $X^n_i(t)$ denotes the class-$i$ queue-length at time $t$, assuming the system starts empty. An asymptotic upper bound (as $n->\infinity$) on the performance under a fixed priority policy is attained, implying that the policy is asymptotically optimal when $c_i$ are sufficiently large. The analysis is based on the study of an underlying differential game.
(joint work with Rami Atar and Adam Shwartz)

Michael Harrison (Tutorial)

Dynamic Scheduling in Heavy Traffic

This tutorial will focus on single-hop stochastic processing networks. That is, in the network models to be considered, arriving jobs of various types each require a single service before departing, but that service may be obtainable from several different servers, or may require capacity allocations from several servers simultaneously. In the heavy traffic parameter regime, the dynamic scheduling problem for the processing network is formally approximated by a corresponding Brownian control problem (BCP). In all cases the approximating BCP is more tractable than the conventional scheduling problem that it replaces. In particular, the approximating BCP may have a smaller effective dimension than the original problem, and if its effective dimension is one, then the approximating BCP can be solved explicitly. Many open problems remain, especially concerning the translation of Brownian solutions back into the conventional model context.

Maialen Larranaga

Dynamic fluid-based scheduling in a multi-class abandonment queue

We investigate how to share a common resource among multiple classes of customers in the presence of abandonments. We consider two different models: (1) customers can abandon both while waiting in the queue and while being served, (2) only customers that are in the queue can abandon. Given the complexity of the stochastic optimization problem we propose a fluid model as a deterministic approximation. For the overload case we directly obtain that the $\tilde c \mu$-rule is optimal. For the underload case we use Pontryagin's Maximum Principle to obtain the optimal solution for two classes of customers; there exists a switching curve that splits the two-dimensional state-space into two regions such that when the number of customers in both classes is sufficiently small the optimal policy follows the $\tilde c \mu$-rule and when the number of customers is sufficiently large the optimal policy follows the $\tilde c μ-rule. The same structure is observed numerically in the optimal policy of the stochastic model for an arbitrary number of classes. Based on this we develop a heuristic and by numerical experiments we evaluate its performance and compare it to several index policies. We observe that the suboptimality gap of our solution is small.
 

Mihalis Markakis

Delay Analysis of the Max-Weight Policy under Heavy-Tailed Traffic via Fluid Approximations

We consider a single-hop switched queueing network with a mix of heavy-tailed (i.e., arrival processes with infinite variance) and light-tailed traffic, and study the delay performance of the Max-Weight policy, known for its throughput optimality and asymptotic delay optimality properties.
Classical results in queueing theory imply that heavy-tailed queues are delay unstable, i.e., they experience infinite expected delays in steady state. Thus, we focus on the impact of heavy-tailed traffic on the light-tailed queues, using delay stability as performance metric. Recent work has shown that this impact may come in the form of subtle rate-dependent phenomena, the
stochastic analysis of which is quite cumbersome. Our goal is to show how fluid approximations can facilitate the delay analysis of the Max-Weight policy under heavy-tailed traffic. More specifically, we show how fluid approximations can be combined with renewal theory in order to prove delay instability results. Furthermore, we show how fluid approximations can be combined with stochastic Lyapunov theory in order to prove delay stability results. We illustrate the benefits
of the proposed approach in two ways: (i) analytically, by providing a sharp characterization of the delay stability regions of networks with disjoint schedules, significantly generalizing previous results; (ii) computationally, through a Bottleneck Identification algorithm, which identifies (some) delay unstable queues by solving the fluid model of the network from certain initial conditions.

Prajwal Osti

Optimal dynamic TDD intercell coordination for elastic traffic

We consider the intercell coordination problem between two interfering cells combined with dynamic TDD. In dynamic TDD, each station selects whether it is serving uplink (u) or downlink (d) traffic. Thus, the system has four possible operation modes (uu, du, ud, dd). The amount of intercell interference between the stations clearly depends on the operation mode. Traffic in our model consists of elastic data flows in both cells (cells 1 and 2) and in both directions (uplink and downlink), i.e., there are four traffic classes. Flows in each class are served according to the processor sharing (PS) queueing discipline. We first characterize the maximal stability region, and then determine the optimal static (i.e., state-independent) policy to choose the operation mode for various scenarios. We also consider further optimizing the performance by dynamic policies, where the chosen operation mode depends on the instantaneous state of the system. We define several dynamic priority policies and also consider the policy resulting from applying the first policy iteration algorithm to the optimal static policy. In addition, as a reference policy, we have the well-known max-weight policy. We show that certain simple priority policies are, in fact, stochastically optimal in some special cases, but which policy is optimal depends on the setting. In the general case, we simulate the performance of the dynamic policies and give insight into how the policies perform relative to each other and what is the ultimate gain achieved by the dynamic policies.

Georgios Paschos

Stability via Evacuation Times and Applications

A first order performance characterization of queueing systems is the stability region. We study the relation of system stability to minimal evacuation times, i.e. the necessary time to clear specific snapshots of packets. It is shown that under certain conditions the stability region is completely characterized by the asymptotic growth of the evacuation function. This in turn can be determined in closed form for specific systems, which makes the proposed tool very useful.
We focus on the example of input queued switches to illustrate the interplay between the original system with arrivals and the model with snapshot evacuation. Although optimal evacuation policies are always throughput optimal (even the asymptotically optimal ones), well known throughput optimal policies such as maxweight scheduling are shown to be asymptotically suboptimal with respect to evacuation times. Furthermore, we show that given any throughput optimal policy, a randomized version of it that is asymptotically optimal can be designed.
Then we examine applications of the proposed tool. In particular we consider wireless network coding, index coding, broadcast erasure channel and opportunistic routing and showcase how this tool can be used.

Liron Ravner

Equilibrium Arrival Times to Congested Queues

Customers are often faced with a choice of when to arrive to a congested queue with some desired service at the end. Suppose the server operates for a certain time interval, and customers are served according to their arrival order. Typically, customers wish to avoid waiting in the queue for a long time, but arriving too late or too early may also incur high costs. We model the interaction between the customers arriving to the queue as a strategic game. Examples of such scenarios are arriving at a concert with unmarked seats, driving to work in the morning or going to lunch in the cafeteria. We will examine an example in which customers incur costs according to their order of arrival. Specifically, an arrival process that constitutes a Nash Equilibrium will be presented.

Rhonda Righter (Keynote)

Using Priorities and Selfish Scheduling to Obtain Global Optima

Determining the structure, properties, and particular values of optimal policies for minimizing a global (social) objective function for scheduling and routing problems is often extremely difficult using standard approaches such as dynamic programming. On the other hand, given a priority order, individually optimal (selfish) scheduling policies are often structurally obvious and easily computed.  We show how to make the social and selfish solutions coincide by assigning appropriate priorities to individuals, and apply the approach to optimal "green" scheduling (with both holding costs and energy usage costs) and to marginal analysis of flexibility in service systems such as call centers.
(joint work with Osman Akgun (Bailard), Doug Down (McMasterUniversity) and Ron Wolff (UC Berkeley)

Jaron Sanders

Scaled Control in the QED Regime

We develop many-server asymptotics in the Quality-and-Efficiency-Driven (QED) regime for models with admission control. The admission control, designed to reduce the incoming traffic in periods of congestion, scales with the size of the system. For a class of Markovian models with this scaled control, we identify the QED limits for two stationary performance measures. We also derive corrected QED approximations, generalizing earlier results for the Erlang B, C and A models. These results are useful for the dimensioning of large systems equipped with an active control policy. In particular, the corrected approximations can be leveraged to establish the optimality gaps related to square-root staffing and asymptotic dimensioning with admission control.

Halldora Thorsdottir

A functional central limit theorem for a Markov-modulated infinite-server queue

We model the production of new molecules in a chemical reaction network as a Poisson process with a varying arrival rate, depending on an external Markov process. It is assumed that the molecules decay after an exponential time, independently of other molecules present. The goal is to analyze the distributional properties of the number of molecules in the system, under a specific time-scaling. In this scaling, the background process is sped up by a factor N^\alpha, for some \alpha>0, whereas the arrival rates are scaled by N, for N large.
By applying the martingale central limit theorem, we show that the number of molecules, after centering and scaling, converges weakly to an Ornstein-Uhlenbeck process, thus obtaining a functional central limit theorem (F-CLT). An interesting dichotomy is observed, namely, if \alpha>1 the background process jumps faster than the arrival process, and consequently the arrival process behaves essentially as a (homogeneous) Poisson process, so that the scaling in the F-CLT is the usual \sqrt{N}, whereas for \alpha <= 1 the background process is relatively slow, and the scaling in the F-CLT is N^{1-\alpha/2}. In the latter regime, the parameters of the limiting Ornstein-Uhlenbeck process contain the deviation matrix associated with the background process.

Kurt Van Hautegem

OPS/OBS Scheduling Algorithms: Incorporating a Wavelength Conversion Cost in the Performance Analysis

With ever-increasing demands for bandwidth optical packet/burst switching is used to utilise more of the available capacity of optical networks. In current prototypes of optical switches time and wavelength multiplexing are combined to resolve packet contentions, by means of Fiber Delay Lines and wavelength converters in the switching elements. Although optical switches have lower energy consumption than their electronic counterparts, it remains substantial. Since wavelength converters contribute significantly to the switches overall energy consumption, they should be used sparingly, rather than continuously. Current scheduling algorithms however do not take the usage of wavelength converters (and the related effectiveness) into account. To this end, we developed and evaluated new cost-based scheduling algorithms, which take both gap and delay into account to schedule an incoming packet. The performance improvement of these algorithms over existing algorithms can be traded off for a significant reduction in up-time of the wavelength converters by introducing a conversion cost in the involved cost function. This is backed by Monte Carlo simulation results, in which the algorithms are applied both in a void-filling and non-void-filling setting. The algorithms are of the same implementation complexity as current algorithms, and thus of immediate value to switch designers.
(joint work with Wouter Rogiest, Herwig Bruneel)

Joris Walraevens

Tail Probabilities in Priority Queues

Tail probabilities of the number of customers and the customer delay of the low-priority class in a two-class infinite priority queue are investigated. The tool used is singularity analysis of probability generating functions, by which it is shown that different (types of) singularities of the respective probability generating function might play a role, leading to distinct asymptotics. We categorize the possible asymptotics either as (i) exponential, (ii) power law or (iii) power law with exponential cut-off. The analytic work is complemented by stochastic intuition, in that the different types of asymptotics are the result of the dominance of different effects in the queue, namely, resp. a queueing effect, a single-event effect and a priority effect. We also look at what happens when the queue is near the instability bound, and at the influence of finite high-priority buffer capacity.
(joint work with T. Demoor, T. Maertens, D. Fiems and H. Bruneel)

Richard Weber (Tutorial)

Bandit processes and index policies

We consider the problem of optimal control for a number of alternative Markov decision processes, where at each moment in time exactly one process must be "continued" while all other processes are "frozen". Only the process that is continued produces any reward and changes its state. The aim is to maximize expected total discounted reward. A familiar example would be the problem of optimally scheduling the processing of jobs that reside in a single-server queue. A each moment one of the jobs is processed by the server, while all the other jobs are made to wait. Our aim is to minimize the expected total holding cost incurred until all jobs are complete. Another example is that of hunting for an apartment; we must choose the order in which to view apartments and decide when to stop viewing and rent the best apartment of those that have been viewed. This type of problem has a beautiful and surprising solution in terms of Gittins indices. In this tutorial I will review the theory of bandit processes and Gittins indices, describe some applications in scheduling and queueing, and tell you about some frontiers of research in the field.

Part 1 :

Index policies. Interchange arguments. Stopping problems. Bandit processes. Gittins index theorem. Calibration. Target processes. Playing golf with more than one ball. Pandora's problem. Branching bandits. Optimal scheduling in the M/G/1 queue.

Part 2 :

Restless bandits. Whittle indexability. Fluid models and asymptotic optimality. Large deviations and risk-sensitive optimal control.

Bo Zhang

Distributed Data Backup Scheduling: Modeling and Optimization

In this talk I will first discuss some general ideas on modeling and optimization of data backup scheduling, an increasingly important problem domain in which no formal mathematical model has been proposed before. Then I will present some queueing-type results on distributed data backup scheduling that we obtained motivated by a real-world project at IBM. Specifically, we developed a novel Markov chain model to describe the distributed data backup process and analyzed its stability conditions and stationary behavior. In the context of our proposed model, we also formulated an optimization problem for choosing a scheduling policy that strikes the right balance between performing frequent backups to improve data safety and reducing backup costs.
 

PRACTICAL INFORMATION

●      Venue

Eurandom, Mathematics and Computer Science Dpt, TU Eindhoven,

Den Dolech 2, 5612 AZ  EINDHOVEN,  The Netherlands

Eurandom is located on the campus of Eindhoven University of Technology, in the brand new TU/e Metaforum building (4th floor) (about the building). The university is located at 10 minutes walking distance from Eindhoven main railway station (take the exit north side and walk towards the tall building on the right with the sign TU/e).
Accessibility TU/e campus and map.

●      Registration

To register for the workshop, please fill out the registration form. There is no fee for participation.

●      Accommodation / Funding

Hotel will be booked for all invited speakers. Please give your arrival and departure date on the registration form.

Other participants have to make their own arrangements.

For hotels around the university, please see: Hotels (please note: prices listed are "best available"). 

More hotel options can be found on the webpages of the Tourist Information Eindhoven, Postbus 7, 5600 AA Eindhoven.

●      Travel

For those arriving by plane, there is a convenient direct train connection between Amsterdam Schiphol airport and Eindhoven. This trip will take about one and a half hour. For more detailed information, please consult the NS travel information pages or see Eurandom web page location.

Many low cost carriers also fly to Eindhoven Airport. There is a bus connection to the Eindhoven central railway station from the airport. (Bus route number 401) For details on departure times consult http://www.9292ov.nl

The University  can be reached easily by car from the highways leading to Eindhoven (for details, see our route descriptions or consult our map with highway connections.

●      Conference facilities : Conference room, Metaforum Building  MF11&12

The meeting-room is equipped with a data projector, an overhead projector, a projection screen and a blackboard. Please note that speakers and participants making an oral presentation are kindly requested to bring their own laptop or their presentation on a memory stick.

●      Conference Secretariat

Upon arrival, participants should register with the workshop officer, and collect their name badges. The workshop officer will be present for the duration of the conference, taking care of the administrative aspects and the day-to-day running of the conference: registration, issuing certificates and receipts, etc.

●      Cancellation

Should you need to cancel your participation, please contact Patty Koorn, the Workshop Officer.

●      Contact

Mrs. Patty Koorn, Workshop Officer, Eurandom/TU Eindhoven, koorn@eurandom.tue.nl

SPONSORS

The organisers acknowledge the financial support/sponsorship of: