Optimizing Spot Instance Savings in the Cloud for Heterogeneous Demand through Priority Scheduling
Neelkamal Bhuyan, Randeep Bhatia, Murali S. Kodialam, T. V. Lakshman · 2025
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.