Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review
A Column Generation Based Heuristic for a Temporal Bin Packing Problem. / Ratushnyi, Alexey; Kochetov, Yury.
Mathematical Optimization Theory and Operations Research - 20th International Conference, MOTOR 2021, Proceedings. ed. / Panos Pardalos; Michael Khachay; Alexander Kazakov. Springer Science and Business Media Deutschland GmbH, 2021. p. 96-110 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12755 LNCS).Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review
}
TY - GEN
T1 - A Column Generation Based Heuristic for a Temporal Bin Packing Problem
AU - Ratushnyi, Alexey
AU - Kochetov, Yury
N1 - Funding Information: Acknowledgement. The study was carried out within the framework of the state contract of the Sobolev Institute of Mathematics (project no. 0314-2019-0014). Publisher Copyright: © 2021, Springer Nature Switzerland AG.
PY - 2021
Y1 - 2021
N2 - We introduce a new temporal bin packing problem that originated from cloud computing. We have a finite set of items. For each item, we know an arriving time, processing time, and two weights (CPU, RAM). Some items we call large. Each bin (server) has two capacities and is divided into two identical parts (left and right). A regular item can be placed in one of them. A large item is divided into two identical parts and placed in both parts of a bin. Our goal is to pack all items into the minimum number of bins. For this NP-hard problem, we design a heuristic that is based on column generation to get lower and upper bounds. Preliminary computational experiments for real test instances indicate a small gap between the bounds. The average relative error is at most 0.88% for one week planning horizon and about 50000 items. The average running time is 21 s for a personal computer.
AB - We introduce a new temporal bin packing problem that originated from cloud computing. We have a finite set of items. For each item, we know an arriving time, processing time, and two weights (CPU, RAM). Some items we call large. Each bin (server) has two capacities and is divided into two identical parts (left and right). A regular item can be placed in one of them. A large item is divided into two identical parts and placed in both parts of a bin. Our goal is to pack all items into the minimum number of bins. For this NP-hard problem, we design a heuristic that is based on column generation to get lower and upper bounds. Preliminary computational experiments for real test instances indicate a small gap between the bounds. The average relative error is at most 0.88% for one week planning horizon and about 50000 items. The average running time is 21 s for a personal computer.
KW - Bin packing
KW - Column generation
KW - Knapsack problem
KW - Virtual machine
UR - http://www.scopus.com/inward/record.url?scp=85111369793&partnerID=8YFLogxK
UR - https://www.mendeley.com/catalogue/715a1047-2bec-3313-9759-e09631607f56/
U2 - 10.1007/978-3-030-77876-7_7
DO - 10.1007/978-3-030-77876-7_7
M3 - Conference contribution
AN - SCOPUS:85111369793
SN - 9783030778750
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 96
EP - 110
BT - Mathematical Optimization Theory and Operations Research - 20th International Conference, MOTOR 2021, Proceedings
A2 - Pardalos, Panos
A2 - Khachay, Michael
A2 - Kazakov, Alexander
PB - Springer Science and Business Media Deutschland GmbH
T2 - 20th International Conference on Mathematical Optimization Theory and Operations Research, MOTOR 2021
Y2 - 5 July 2021 through 10 July 2021
ER -
ID: 34108868