The stochastic generalized bin packing problem

The Generalized Bin Packing Problem (GBPP) is a recently introduced packing problem where, given a set of bins characterized by volume and cost and a set of items characterized by volume and profit (which also depends on bins), we want to select a subset of items to be loaded into a subset of bins which maximizes the total net profit, while satisfying the volume and bin availability constraints. The total net profit is given by the difference between the total profit of the loaded items and the total cost of the used bins. In this paper, we consider the stochastic version of the GBPP (S-GBPP), where the item profits are random variables to take into account the profit oscillations due to the handling operations for bin loading. The probability distribution of these random variables is assumed to be unknown. By using the asymptotic theory of extreme values a deterministic approximation for the S-GBPP is derived. © 2011 Elsevier B.V. All rights reserved.