Stability for Two-class Multiserver-job Systems
October 7, 2020 (Zoom - See email or contact organizers for link)

Abstract: Multiserver-job systems, where jobs require concurrent service at many servers, occur widely in practice. In stochastic multiserver-job systems, much is known in the dropping setting, where jobs are immediately discarded if they require more servers than are currently available. However, very little is known in the more practical setting where jobs queue instead.

One of the most fundamental properties of a stochastic queueing system is its stability region. The stability region describes the set of arrival rates that the system can handle without piling up jobs and becoming hopelessly overloaded.

In this talk, we derive a closed-form analytical expression for the stability region of a two-class (non-dropping) multiserver-job system where each class of jobs requires a distinct number of servers and requires a distinct exponential distribution of service time, and jobs are served in first-come-first-served (FCFS) order. This is the first result of any kind for an FCFS multiserver-job system where the number of servers required and the job duration may be correlated.

Our work is based on a technique that leverages the idea of a "saturated" system, in which an unlimited number of jobs are always available. Our analytical formula provides insight into the behavior of FCFS multiserver-job systems, highlighting the huge wastage (idle servers while jobs are in the queue) that can occur, as well as the nonmonotonic effects of the service rates on wastage.

This talk is based on joint work with Mor Harchol-Balter and Alan Scheller-Wolf.

Presented in partial fulfilment of the CSD Speaking Skills Requirement.