Temporal Bin Packing Problems with Placement Constraints: MIP-Models and Complexity

In this paper, we investigate new problem statements, generalizing the Temporal Bin Packing Problem (TBPP) with possible applications in cloud computing. We suppose that items are organized into batches. All items in the same batch are placed simultaneously. In cloud computing, items correspond to virtual machines (VMs) and batches correspond to user requests for VM placement. In addition, cloud users can create placement groups consisting of VMs united by a single placement constraint named cluster: at any moment in time, VMs from the same placement group must be hosted on the same rack of servers. In this paper, we consider servers as one-dimensional bins. We investigate the computational complexity and inapproximability of different formulations of the TBPP with cluster placement constraint and suggest mixed integer programming models for them.