This thesis demonstrates online scheduling algorithms to reduce latency and cost in dynamic computing environments, indicating practical solutions for cloud platforms.
Key Points
The aim is to investigate how to effectively manage latency and costs in computing systems, particularly under uncertainties and startup overheads.
Study two online scheduling problems related to dynamic container provisioning and uniprocessor scheduling.
Develop online algorithms characterizing cost vs latency trade-offs and evaluate their performance with synthetic and production-inspired workloads.
Introduce Interval Buffer EDF policy for scheduling jobs with setup times and analyze competitive guarantees.
Algorithms achieve operational cost within (1+ϵ) of the optimal offline solution, with worst-case response times bounded by O(1/ϵ).
Empirical evaluations closely approximate the Pareto frontier between cost and latency while exhibiting favorable average-case behavior.
The new scheduling policy approaches 1-competitiveness as job slack increases, outperforming classical methods.