Optimization Online


Bin Packing Problem with Time Dimension: An Application in Cloud Computing

Nursen Aydin(nursen.aydin***at***wbs.ac.uk)
Ibrahim Muter(i.muter***at***bath.ac.uk)
S. Ilker Birbil(birbil***at***ese.eur.nl)

Abstract: Improving energy efficiency and lowering operational costs are the main challenges faced in systems with multiple servers. One prevalent objective in such systems is to minimize the number of servers required to process a given set of tasks under server capacity constraints. This objective leads to the well-known bin packing problem. In this study, we consider a generalization of this problem with a time dimension, where the tasks are to be performed with prede fined start and end times. This new dimension brings about new performance considerations, one of which is the uninterrupted utilization of servers. This study is motivated by the problem of energy efficient assignment of virtual machines to physical servers in a cloud computing service. We address the virtual machine placement problem and present a binary integer programming model to develop different assignment policies. By analyzing the structural properties of the problem, we propose an efficient heuristic method based on solving smaller versions of the original problem iteratively. Moreover, we design a column generation algorithm that yields a lower bound on the objective value, which can be utilized to evaluate the performance of the heuristic algorithm. Our numerical study indicates that the proposed heuristic is capable of solving large-scale instances in a short time with small optimality gaps.

Keywords: Bin packing, cloud computing, heuristics, exact methods, column generation

Category 1: Applications -- OR and Management Sciences


Download: [PDF]

Entry Submitted: 01/14/2019
Entry Accepted: 01/14/2019
Entry Last Modified: 01/14/2019

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society