This work addresses the problem of delay-sensitive job scheduling in cloud computing systems that offer two compute options: (i) low-cost, high-demand spot servers and (ii) high-cost on-demand servers. While prior research has focused on scheduling a single job, we consider a more practical scenario where a continuous stream of jobs, categorized into n different classes, must be managed. Each class i is characterized by an on-demand cost ki, an arrival rate λi, and an average delay constraint δi. With Poisson job arrivals and spot server availability modeled as an exponential service process, we optimize two key aspects: (i) the wait-time distribution for each job class and (ii) the precedence order for processing classes in case of scheduling conflicts. By modeling the system as a Markov chain, we formulate constrained optimization problems for two cases: (i) equal treatment of all job classes and (ii) priority-based scheduling, the latter introducing a combinatorial challenge. We propose algorithms to determine optimal wait-time distributions in both cases and demonstrate through numerical experiments that precedence-order optimization significantly improves performance, especially when delay constraints are not overly strict.

We study the smoothed online quadratic optimization (SOQO) problem where, at each round $t$, a player plays an action $x_t$ in response to a quadratic hitting cost and an additional squared $\ell_2$-norm cost for switching actions. This problem class has strong connections to a wide range of application domains including smart grid management, adaptive control, and data center management, where switching-efficient algorithms are highly sought after. We study the SOQO problem in both adversarial and stochastic settings, and in this process, perform the first stochastic analysis of this class of problems. We provide the online optimal algorithm when the minimizers of the hitting cost function evolve as a general stochastic process, which, for the case of martingale process, takes the form of a distribution-agnostic dynamic interpolation algorithm that we call Lazy Adaptive Interpolation (LAI). Next, we present the stochastic-adversarial trade-off by proving an $\Omega(T)$ expected regret for the adversarial optimal algorithm in the literature (ROBD) with respect to LAI and, a sub-optimal competitive ratio for LAI in the adversarial setting. Finally, we present a best-of-both-worlds algorithm that obtains a robust adversarial performance while simultaneously achieving a near-optimal stochastic performance.