Course AsOR: Asymptotic Methods in Operations Research

Course description

Exact analysis of complex queueing systems is often out of scope. For many queueing systems it is all but impossible to obtain exact expressions for expected values of performance measures such as queue lengths, waiting times and sojourn time. Also, average values may not even be the most informative measures to describe a system's performance, but one may rather be interested in performance quantiles for example. For such cases a wide range of asymptotic techniques are available that may serve to develop suitable approximations and provide valuable insights. In this course we will discuss several such techniques and illustrate them on more advanced queueing models such as GPS queues, DPS queues, and bandwidth-sharing networks. The following techniques and topics will be discussed:

• Large deviations and tail asymptotics: We discuss several techniques to estimate tail probabilities in queueing systems. We distinguish two intrinsically different scenarios: one in which performance characteristics have light tailed distributions and one with heavy tails. We will explain the fundamental differences between these two scenarios ("conspiracy" versus "disaster" scenarios) and illustrate several analysis techniques that one may resort to in obtaining asymptotically accurate estimates, including analytic asymptotics, probabilistic bounds and coupling arguments.
• Fluid and diffusion limits: For optimization of complex stochastic processes, one may search for simpler versions of the processes that are still accurate enough to design meaningful optimizing control strategies. Fluid and diffusion limits are particularly useful in this context. For the fluid limit, one starts off the stochastic process (for example a queue length process) at an exceptional high level x and monitors it over a long period of time (order x). As the scaling parameter x tends to infinity, the stochastic process can often be shown to satisfy a functional strong law of large numbers, which is commonly referred to as the fluid limit. In applications, the fluid limit may not give sufficient information to design optimal control strategies and one will typically be interested in deviations from the fluid limit. The diffusion limit describes these deviations.
• Heavy traffic: For efficiency, in practice service systems are aimed at being deployed at fairly high loads. As the load on a (queueing) system approaches the critical capacity, typical performance characteristics such as queue lengths and sojourn times grow beyond limits. In the 1960s, Kingman showed that for single-server queues, the queue length process can be scaled such that a meaningful limit is obtained as the critical capacity is approached. In the past half a century, this concept has been extended to much more complex systems and successfully applied in practice, particularly in inventory systems, production facilities, call centers and communication networks. In the course we will discuss the founding principles of heavy traffic theory.

Literature

Prerequisites

Examination

Address of the lecturer

Prof. Dr. Bert Zwart
CWI, Science Park 123
1098 XG Amsterdam
Phone: 020-5924018
E-mail: Bert.Zwart@cwi.nl