The Taub Faculty of Computer Science Events and Talks

We present new job scheduling algorithms and pricing schemes for computing systems. The scheduling mechanisms we design provide guaranteed Service Level Agreements (SLAs) to users (e.g., meeting job deadlines), while obtaining desired properties driven by both system-aware goals and economic considerations. In our framework, users submit jobs along with a value function that specifies the user value (i.e., willingness to pay) as a function of the job completion time. In addition, each user submits other properties of their job, such as resource requirements or inner job dependencies. The scheduler, in response, allocates resources to users under capacity limitations to maximize the total value gained by completed jobs. We consider several allocation models, both offline and online, and develop novel scheduling algorithms that provide high guaranteed value, as well as high resource utilization in practice. Based on our scheduling algorithms, we construct truthful allocation and pricing mechanisms for public clouds, in which users are incentivized to report their true job properties. We empirically evaluate the benefits of our approach through simulations on job traces taken from Microsoft clusters, and show that the revenues obtained by our approach are high compared to commonly used fixed-price mechanisms, which charge a fixed price per resource unit.