| PhD Seminar

Name of the Speaker: Ms. Sushmitha Shree S (EE18D702)
Guide: Dr. Avhishek Chatterjee
Co-Guide: Prof. Krishna Jagannathan
Venue: CSD-308 (Conference Hall)
Date/Time: 17th April 2024 (Wednesday), 3:15 PM
Title: Towards Maximizing Nonlinear Delay-Sensitive Rewards in Queuing Systems

Abstract

Job scheduling in single server queuing systems is one of the most widely researched areas due to its diverse applications. Historically, the design of service disciplines focused on optimizing the average linear functions of sojourn times (rewards). Although the goal of optimizing linear rewards is well investigated, hardly any work considers optimizing nonlinear rewards, which have become crucial in many emerging delay-sensitive applications, including quantum communication, multimedia streaming, and online service platforms.

In our work, we focus primarily on identifying a single service discipline that maximizes the long-term average of nonlinear rewards. In particular, we view this problem for two arrival models - the first is a burst arrival model, wherein all jobs arrive at the server at the same instant. We show that the shortest job first (SJF) discipline maximizes the average reward for any monotonic function of the sojourn times. In the second setting, jobs arrive according to some stochastic process with i.i.d. service requirements. This setting is significantly more challenging to analyze, and identifying an optimal discipline remains elusive. We introduce a new service discipline, shortest predicted sojourn time (SPST), and provide analytical guarantees under specific settings. Numerically, we demonstrate that SPST outperforms well-known disciplines across multiple settings.