Truthful Online Scheduling of Cloud Workloads under Uncertainty
Moshe Babaioff, Ronny Lempel, Brendan Lucier, Ishai Menache, Aleksandrs Slivkins, Sam Chiu-wai Wong · Proceedings of the ACM Web Conference 2022 · 2022
Cloud computing customers often submit repeating jobs and computation pipelines on approximately regular schedules, with arrival and running times that exhibit variance. This pattern, typical of training tasks in machine learning, allows customers to partially predict future job requirements. We develop a model of cloud computing platforms that receive statements of work (SoWs) in an online fashion. The SoWs describe future jobs whose arrival times and durations are probabilistic, and whose utility to the submitting agents declines with completion time. The arrival and duration distributions, as well as the utility functions, are considered private customer information and are reported by strategic agents to a scheduler that is optimizing for social welfare.