Stochastic Bin Packing with Time-Varying Item Sizes

          @misc{ scivideos_22739,
            doi = {},
            url = {https://old.simons.berkeley.edu/talks/stochastic-bin-packing-time-varying-item-sizes},
            author = {},
            keywords = {},
            language = {en},
            title = {Stochastic Bin Packing with Time-Varying Item Sizes},
            publisher = {The Simons Institute for the Theory of Computing},
            year = {2022},
            month = {oct},
            note = {22739 see, \url{https://scivideos.org/simons-institute/22739}}
          }
          

Abstract

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.