Реферат: This report considers a Bin Packing problem, in which the weights of the items are random. It is required to minimize the number of used bins provided the probability of exceeding capacity of some bin is bounded by a given constant. The problem arises in cloud computing, where bins represent servers and items correspond to client virtual machines with uncertain parameters. A proposed solution approach includes Monte-Carlo algorithm for computing the excess probability and an evolutionary optimization heuristic. In order to reduce the computing time, the algorithm is parallelized and implemented with OpenCL framework for running on a graphics processor (GPU). An experimental evaluation on the large-scale instances is provided.

Библиографическая ссылка: Borisovsky P.A. , Gette A.V.
A simulation-optimization approach to solving the chance-constrained bin packing problem
XXIV International conference “Mathematical Optimization Theory and Operations Research” 07-11 Jul 2025