Extremal Queueing Theory

Queueing theory has often been applied to study communication and service queueing systems such as call centers, hospital emergency departments and ride-sharing platforms. Unfortunately, it is complicated to analyze queueing systems. That is largely because the arrival and service processes that mainly determine a queueing system are uncertain and must be represented as stochastic processes that are difficult to analyze. In response, service providers might be able to partially capture the main characteristics of systems given partial data information and limited domain knowledge. An effective engineering response is to develop tractable approximations to approximate queueing characteristics of interest that depend on critical partial information. In this thesis, we contribute to developing high-quality approximations by studying tight bounds for the transient and the steady-state mean waiting time given partial information. We focus on single-server queues and multi-server queues with the unlimited waiting room, the first-come-first-served service discipline, and independent sequences of independent and identically distributed sequences of interarrival times and service times. We