Upper and lower bounds for the optimum in a temporal bin packing problem

A new temporal bin packing problem originating from cloud computing is introduced. There is a finite set of virtual machines. For each machine, the time window for processing, the number of cores, and the RAM size are known. Each machine can be of one of two types: large or small. Each server consists of two identical nodes. Each small machine is placed completely on one of the nodes, and each large machine is divided into two identical parts placed on both nodes of a server. The goal is to pack all the machines into the minimum number of servers. For this problem, we develop a heuristic based on the column generation method. To get lower bounds of the optimum, we choose the times with the greatest total load and solve the static problem for them. To derive upper bounds, we extend the solution of the static problem to all times using the well-known First Fit algorithm. Computational experiments for real test instances indicate a small gap between the bounds, which is at most 0.9% for a week horizon, 50 000 machines, and 26 s average running time on a personal computer. We manage to improve some well-known results for open instances.