Mathematical Models and Approximate Solution Approaches for the Stochastic Bin Packing Problem

Research output: Contribution to journalResearch articleContributedpeer-review

Abstract

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.

Details

Original languageEnglish
Article number105439
JournalComputers and Operations Research
Volume135
Issue number135
Publication statusPublished - Nov 2021
Peer-reviewedYes

External IDs

Scopus 85108426310

Keywords

Sustainable Development Goals