Optimizing Spot Instance Savings in the Cloud for Heterogeneous Demand through Priority Scheduling

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 k<inf xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">i</inf>, an arrival rate λ<inf xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">i</inf>, and an average delay constraint δ<inf xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">i</inf>. 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.