We consider the (single-stage) stochastic bin packing problem (SBPP) which is based on a given list of items the sizes of which are represented by stochastically independent random variables. The SBPP requires to determine the minimum number of unit capacity bins needed to pack all the items, such that for each bin the probability of exceeding the capacity is bounded by a given constant. Such calculations are particularly relevant in the field of server consolidation, where (not precisely known) jobs have to be assigned to as few processing units as possible to keep the energy consumption and operational costs low. Although not being limited to this assumption, our theoretical investigations are only exemplified for normally distributed item sizes, especially since real-world characteristics can often be reasonably approximated by that type of distribution. From a mathematical point of view, such item characteristics are particularly challenging as the corresponding SBPP turns out to be a nonlinear integer program. For this scenario, we first derive several (improved) lower and upper bounds and study their worst-case performance metrics. Moreover, we describe various linearization techniques to overcome the drawback of nonlinearity. Finally, all approaches are tested based on extensive computational experiments, involving both randomly generated and real-world instances.
Citation
Preprint MATH-NM-02-2020, Technische Universität Dresden, September 2020