Abstract: Motivated by the virtual machine scheduling problem in today's computing systems, we propose a new setting of stochastic bin-packing in service systems that allows the item sizes (job resource requirements) to vary over time.  In this setting, items (jobs) arrive to the system, vary their sizes, and depart from the system following certain Markovian assumptions.  We focus on minimizing the expected number of non-empty bins (active servers) in steady state.  Our main result is a policy that achieves an optimality gap of O(r^0.5) in the objective, where the optimal objective value is Θ(r) and r is a scaling factor such that the item arrival intensity scales linearly with it.  When specialized to the setting where the item sizes do not vary over time, our result improves upon the state-of-the-art o(r) optimality gap.  Our technical approach highlights a novel policy conversion framework that reduces the policy design problem to that in a single-bin (single-server) system.

This is joint work with Yige Hong (CMU) and Qiaomin Xie (UW-Madison).  A preprint of the paper is available at: https://arxiv.org/abs/2209.04123

Bio: Weina Wang is an Assistant Professor in the Computer Science Department at Carnegie Mellon University.  Her research lies in the broad area of applied probability and stochastic systems, with applications in resource orchestration in large computing systems, data centers, and privacy-preserving data analytics.  She was a joint postdoctoral research associate in the Coordinated Science Lab at the University of Illinois at Urbana-Champaign, and in the School of ECEE at Arizona State University, from 2016 to 2018.  She received her Ph.D. degree in Electrical Engineering from Arizona State University in 2016, and her Bachelor's degree from the Department of Electronic Engineering at Tsinghua University in 2009.  Her dissertation received the Dean’s Dissertation Award in the Ira A. Fulton Schools of Engineering at Arizona State University in 2016.  She received the Kenneth C. Sevcik Outstanding Student Paper Award at ACM SIGMETRICS 2016.  She received an NSF CAREER Award in 2022.