The Library
Multi-objective temporal bin packing problem : an application in cloud computing
Tools
Aydin, Nursen, Muter, I. and Birbil, S. I. (2020) Multi-objective temporal bin packing problem : an application in cloud computing. Computers & Operations Research, 121 . 104959. doi:10.1016/j.cor.2020.104959 ISSN 0305-0548.
|
PDF
WRAP-Multi-objective-temporal-bin-problem--cloud-computing.pdf - Accepted Version - Requires a PDF viewer. Available under License Creative Commons Attribution Non-commercial No Derivatives 4.0. Download (731Kb) | Preview |
Official URL: https://doi.org/10.1016/j.cor.2020.104959
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 predefined 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.
Item Type: | Journal Article | ||||||||
---|---|---|---|---|---|---|---|---|---|
Alternative Title: | |||||||||
Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software T Technology > T Technology (General) |
||||||||
Divisions: | Faculty of Social Sciences > Warwick Business School | ||||||||
Library of Congress Subject Headings (LCSH): | Cloud computing, Mechatronics, Heuristic, Heuristics (Computer algorithms), Integer programming, System analysis | ||||||||
Journal or Publication Title: | Computers & Operations Research | ||||||||
Publisher: | Elsevier BV | ||||||||
ISSN: | 0305-0548 | ||||||||
Official Date: | September 2020 | ||||||||
Dates: |
|
||||||||
Volume: | 121 | ||||||||
Article Number: | 104959 | ||||||||
DOI: | 10.1016/j.cor.2020.104959 | ||||||||
Status: | Peer Reviewed | ||||||||
Publication Status: | Published | ||||||||
Access rights to Published version: | Restricted or Subscription Access | ||||||||
Date of first compliant deposit: | 22 April 2020 | ||||||||
Date of first compliant Open Access: | 28 October 2021 | ||||||||
Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year