Talks
Fall 2022

Stochastic Bin Packing with Time-Varying Item Sizes

Monday, October 10th, 2022, 11:00 am12:00 pm

Add to Calendar

Speaker: 

Weina Wang (Carnegie Mellon University)

Location: 

Calvin Lab Auditorium

In today's computing systems, there is a strong contention between achieving high server utilization and accommodating the time-varying resource requirements of jobs. Motivated by this problem, we study a stochastic bin packing formulation with time-varying item sizes, where bins and items correspond to servers and jobs, respectively. Our goal is to answer the following fundamental question: How can we minimize the number of active servers (servers running at least one job) given a budget for the cost associated with resource overcommitment on servers? We propose a novel framework for designing job dispatching policies, which reduces the problem to a policy design problem in a single-server system through policy conversions. Through this framework, we develop a policy that is asymptotically optimal as the job arrival rate increases. This is a joint work with Yige Hong at Carnegie Mellon University and Qiaomin Xie at University of Wisconsin–Madison.

AttachmentSize
PDF icon Slides2.1 MB