Abstract
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.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Aydin, N., Muter, I., Birbil, I.S.: Multi-objective temporal bin packing problem: an application in cloud computing. Comput. Oper. Res. 121 (2020). https://doi.org/10.1016/j.cor.2020.104959
de Cauwer, M., Mehta, D., O’Sullivan, B.: The temporal bin packing problem: an application to workload management in data centres. In: 2016 IEEE 28th International Conference on Tools with Artificial Intelligence (ICTAI), pp. 157–164, November 2016. https://doi.org/10.1109/ICTAI.2016.0033
Furini, F., Shen, X.: Matheuristics for the temporal bin packing problem. In: Amodeo, L., Talbi, E.-G., Yalaoui, F. (eds.) Recent Developments in Metaheuristics. ORSIS, vol. 62, pp. 333–345. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-58253-5_19
Gilmore, R., Gomory, R.: A linear programming approach to the cutting stock problem I. Oper. Res. 9 (1961). https://doi.org/10.1287/opre.9.6.849
Gurobi Optimization: Gurobi optimizer reference manual (2021). http://www.gurobi.com
Johnson, D.S.: Fast algorithms for bin packing. J. Comput. Syst. Sci. 8(3), 272–314 (1974). https://doi.org/10.1016/S0022-0000(74)80026-7
Manchanda, N., Anand, K.: Non-uniform memory access (NUMA) (2010)
Martello, S., Toth, P.: Knapsack Problems: Algorithms and Computer Implementations. Wiley, Hoboken (1990)
Pires, F.L., Báran, B.: A virtual machine placement taxonomy. In: Proceedings of the 15th IEEE/ACM International Symposium on Cluster, Cloud, and Grid Computing, CCGRID 2015, pp. 159–168. IEEE Press (2015). https://doi.org/10.1109/CCGrid.2015.15
Shi, J., Luo, J., Dong, F., Jin, J., Shen, J.: Fast multi-resource allocation with patterns in large scale cloud data center. J. Comput. Sci. 26, 389–401 (2018). https://doi.org/10.1016/j.jocs.2017.05.005
Acknowledgement
The study was carried out within the framework of the state contract of the Sobolev Institute of Mathematics (project no. 0314-2019-0014).
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2021 Springer Nature Switzerland AG
About this paper
Cite this paper
Ratushnyi, A., Kochetov, Y. (2021). A Column Generation Based Heuristic for a Temporal Bin Packing Problem. In: Pardalos, P., Khachay, M., Kazakov, A. (eds) Mathematical Optimization Theory and Operations Research. MOTOR 2021. Lecture Notes in Computer Science(), vol 12755. Springer, Cham. https://doi.org/10.1007/978-3-030-77876-7_7
Download citation
DOI: https://doi.org/10.1007/978-3-030-77876-7_7
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-77875-0
Online ISBN: 978-3-030-77876-7
eBook Packages: Computer ScienceComputer Science (R0)