Geodesic
Upper and lower bounds for the optimum in a temporal bin packing problem
Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 30 (2024) no. 1, pp. 109-127
Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice du chapitre de livre

A new temporal bin packing problem originating from cloud computing is introduced. There is a finite set of virtual machines. For each machine, the time window for processing, the number of cores, and the RAM size are known. Each machine can be of one of two types: large or small. Each server consists of two identical nodes. Each small machine is placed completely on one of the nodes, and each large machine is divided into two identical parts placed on both nodes of a server. The goal is to pack all the machines into the minimum number of servers. For this problem, we develop a heuristic based on the column generation method. To get lower bounds of the optimum, we choose the times with the greatest total load and solve the static problem for them. To derive upper bounds, we extend the solution of the static problem to all times using the well-known First Fit algorithm. Computational experiments for real test instances indicate a small gap between the bounds, which is at most 0.9% for a week horizon, 50 000 machines, and 26 s average running time on a personal computer. We manage to improve some well-known results for open instances.
Keywords: knapsack problem, column generation method, virtual machine.
Mots-clés : NUMA architecture 
@article{TIMM_2024_30_1_a8,
     author = {Yu. A. Kochetov and A. V. Ratushnyi},
     title = {Upper and lower bounds for the optimum in a temporal bin packing problem},
     journal = {Trudy Instituta matematiki i mehaniki},
     pages = {109--127},
     year = {2024},
     volume = {30},
     number = {1},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/TIMM_2024_30_1_a8/}
}
TY  - JOUR
AU  - Yu. A. Kochetov
AU  - A. V. Ratushnyi
TI  - Upper and lower bounds for the optimum in a temporal bin packing problem
JO  - Trudy Instituta matematiki i mehaniki
PY  - 2024
SP  - 109
EP  - 127
VL  - 30
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/TIMM_2024_30_1_a8/
LA  - ru
ID  - TIMM_2024_30_1_a8
ER  - 
%0 Journal Article
%A Yu. A. Kochetov
%A A. V. Ratushnyi
%T Upper and lower bounds for the optimum in a temporal bin packing problem
%J Trudy Instituta matematiki i mehaniki
%D 2024
%P 109-127
%V 30
%N 1
%U http://geodesic.mathdoc.fr/item/TIMM_2024_30_1_a8/
%G ru
%F TIMM_2024_30_1_a8
Yu. A. Kochetov; A. V. Ratushnyi. Upper and lower bounds for the optimum in a temporal bin packing problem. Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 30 (2024) no. 1, pp. 109-127. http://geodesic.mathdoc.fr/item/TIMM_2024_30_1_a8/

[1] Johnson D.S., Near-optimal bin packing algorithms, Ph.D. dissertation, Department of Mathematics, Massachusetts Institute of Technology, Cambridge: MA, 1973 | MR

[2] Christensen H.I., Khan A., Pokutta S., Tetali P., “Multidimensional bin packing and other related problems: A survey”, Computer Science Review, 24 (2017), 63–79 | DOI | MR | Zbl

[3] Aggoun A., Rhiat A., Fages A., “Panorama of real-life applications in logistics embedding bin packing optimization algorithms, robotics and cloud computing technologies”, Proc. of 3rd Internat. Conf. on Logistics Operations Management (GOL), 2016, 1–4 | DOI

[4] 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 (2018), 389–401 | DOI

[5] Furini F., Shen X., “Matheuristics for the temporal bin packing problem”, Oper. Res., Comput. Sci. Interfaces Series, 62, 2018, 333–345 | DOI

[6] Aydin N., Muter I., Birbil I.S., “Multi-objective temporal bin packing proble: An application in cloud computing”, Comput. Oper. Res., 121 (2021), 104959 | DOI | MR

[7] de Cauwer M., Mehta D., O'Sullivan B., “The temporal bin packing problem: An application to workload management in data centres”, IEEE 28th Internat. Conf. on Tools with Artificial Intelligence (ICTAI 2016), 157–164 | DOI

[8] Bartlett M., Frisch A.M., Hamadi Y., Miguel I., Tarim S.A., Unsworth C., “The Temporal Knapsack Problem and its solution”, Proc. of the Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, Second Internat. Conf. (CPAIOR 2005), Lecture Notes in Comp. Sci., 3524, eds. R. Barták, M. Milano, Springer, Berlin; Heidelberg, 2005, 34–48 | DOI | Zbl

[9] Caprara A., Furini F., Malaguti E., “Uncommon Dantzig–Wolfe reformulation for the Temporal Knapsack Problem”, INFORMS J. Comput., 25 (2013), 560–571 | DOI | MR

[10] Pires F.L., Baran B., “A virtual machine placement taxonomy”, Proc. of the 15th IEEE/ACM Internat. Symposium on Cluster, Cloud, and Grid Computing, 2015, 159–168 | DOI

[11] Wolsey L.A., “Valid inequalities, covering problems and discrete dynamic programs”, Annal. Discrete Math., 1 (1977), 527–538 | DOI | MR | Zbl

[12] Clautiaux F., Sadykov R., Vanderbeck F., Viaud Q., “Combining dynamic programming with filtering to solve a four-stage two-dimensional guillotine-cut bounded knapsack problem”, Discr. Optim., 29 (2018), 18–44 | DOI | MR | Zbl

[13] Delorme M., Iori M., Martello S., “Bin packing and cutting stock problems: mathematical models and exact algorithms”, Eur. J. Oper. Res., 255 (2016), 1–20 | DOI | MR | Zbl

[14] Macedo R., Alves C., Valério de Carvalho J.M., “Arc-flow model for the two-dimensional guillotine cutting stock problem”, Comput. Oper. Res., 37 (2010), 991–1001 | DOI | Zbl

[15] Martinovic J., Scheithauer G., “Integer linear programming models for the skiving stock problem”, Eur. J. Oper. Res., 251:2 (2016), 356–368 | DOI | MR | Zbl

[16] Valério de Carvalho J.M., “Exact solution of cutting stock problems using column generation and branch-and-bound”, Int. Trans. Oper. Res., 5 (1998), 35–44 | MR | Zbl

[17] Brandao F., Pedroso J.P., “Bin packing and related problems: general arc-flow formulation with graph compression”, Comput. Oper. Res., 69 (2016), 56–67 | DOI | MR | Zbl

[18] Delorme M., Iori M., “Enhanced pseudo-polynomial formulations for bin packing and cutting stock problems”, INFORMS J. Comput., 32:1 (2020), 101–119 | DOI | MR

[19] Cote J.-F., Iori M., “The meet-in-the-middle principle for cutting and packing problems”, INFORMS J. Comput., 30:4 (2018), 625–786 | DOI | MR

[20] Dell'Amico M., Furini F., Iori M., “A branch-and-price algorithm for the temporal bin packing problem”, Comput. Oper. Res., 112 (2020), 104825 | DOI | MR

[21] Martinovic J., Strasdat N., Selch M., “Compact Integer Linear Programming Formulations for the temporal bin packing problem with fire-ups”, Comput. Oper. Res., 132 (2021), 105288 | DOI | MR | Zbl

[22] Martinovic J., Strasdat N., Valerio de Carvalho J.M., Furini F., “Variable and constraint reduction techniques for the temporal bin packing problem with fire-ups”, Optim. Letters, 16 (2021), 2333–2358 | DOI | MR

[23] Martinovic J., Strasdat N., Theoretical insights and a new class of valid inequalities for the temporal bin packing problem with fire-ups, Preprint MATH-NM-01-2022, Available at:, Technische Universitat Dresden, 2022 URL: http://www.optimization-online.org/DB_HTML/2022/02/8791.html | MR

[24] Valerio de Carvalho J.M., “LP Models for bin packing and cutting stock problems”, Eur. J. Oper. Res., 141:2 (2002), 253–273 | DOI | MR | Zbl

[25] Manchanda N., Anand K., Non-uniform memory access (NUMA), New York University, NY, 2014

[26] Kellerer H., Pferschy U., Pisinger D., Knapsack problems, Springer, Berlin, Heidelberg, 2004, 548 pp. | DOI | MR | Zbl

[27] Kantorovich L.V., Zalgaller V.A., Raschet ratsionalnogo raskroya promyshlennykh materialov, Lenizdat, L., 1951, 198 pp.

[28] Johnson D.S., “Fast algorithms for bin packing”, J. Comp. System Sci., 8:3 (1974), 272–314 | DOI | MR | Zbl

[29] Ratushnyi A., Kochetov Y., “A column generation based heuristic for a temporal bin packing problem”, Mathematical Optimization Theory and Operations Research, Proc. of 20th Internat. Conf. (MOTOR 2021), Lecture Notes Comp. Sci., 12755, eds. P. Pardalos, M. Khachay, A. Kazakov, 2021, 96–110 | DOI | MR

[30] Proc. of 20th Internat. Conf. (MOTOR 2021), eds. P. Pardalos, M. Khachay, A. Kazakov, Springer, Cham, 2021, 493 pp. | DOI | MR

[31] Ratushnyi A., “A pattern-based heuristic for a temporal bin packing problem with conflicts”, Mathematical Optimization Theory and Operations Research: Recent Trends, Proc. of 22nd Internat. Conf. (MOTOR 2023), Communications in Computer and Information Sci., 1881, eds. M. Khachay et al., 2023, 152–166 | DOI | MR

[32] Martello S., Toth P., “Lower bounds and reduction procedures for the bin packing problem”, Discrete Appl. Math., 28 (1990), 59–70 | DOI | MR | Zbl

[33] Kochetov Yu., Kondakov A., “A hybrid VNS matheuristic for a bin packing problem with a color constraint”, Yugoslav J. Oper. Res., 31:3 (2021), 285–298 | DOI | MR

[34] Gurobi optimization, Gurobi optimizer reference manual, Available at:, 2021 URL: http://www.gurobi.com

[35] Scheithauer G., Terno J., “The modified integer round-up property of the one- dimensional cutting stock problem”, Eur. J. Oper. Res., 84 (1995), 562–571 | DOI | MR | Zbl