A Two-Stage Algorithm for the Dynamic Bin Packing Problem with Placement Groups

A Two-Stage Algorithm for the Dynamic Bin Packing Problem with Placement Groups Full article

Journal

Journal of Applied and Industrial Mathematics
ISSN: 1990-4789 , E-ISSN: 1990-4797

Output data

Year: 2025, Volume: 19, Number: 1, Pages: 92–103 Pages count : 12 DOI: 10.1134/S1990478925010090

Funding (1)

Sobolev Institute of Mathematics

FWNF-2022-0019

A new dynamic bin packing problem relevant to cloud computing is considered. The creation time, deletion time, and required resources are known for each item (virtual machine). The containers (servers) have a NUMA architecture and specific rules for placing the machines. The servers are grouped into racks, and some machines form groups. Each group is divided into partitions. Machines from different partitions cannot be placed on the same rack to ensure system fault tolerance. The objective is to pack all the machines into the minimum number of racks over a given planning horizon. A two-stage algorithm is developed to solve the problem: an initial solution is constructed, where some constraints may be violated, followed by iterative improvement using local search aimed at eliminating the violations. Using the proposed approach, an average deviation of 3.8% from the lower bound was achieved on open test cases.

Ratushnyi A.V. , Kochetov Y.A.
A Two-Stage Algorithm for the Dynamic Bin Packing Problem with Placement Groups
Journal of Applied and Industrial Mathematics. 2025. V.19. N1. P.92–103. DOI: 10.1134/S1990478925010090 Scopus РИНЦ OpenAlex

Ратушный А.В. , Кочетов Ю.А.
Двухстадийный алгоритм для динамической задачи упаковки в контейнеры с группами размещения
Дискретный анализ и исследование операций. 2025. Т.32. №1. С.99–118. DOI: 10.33048/daio.2025.32.813 РИНЦ

Submitted:	Sep 11, 2024
Accepted:	Sep 22, 2024
Published print:	Nov 2, 2025
Published online:	Nov 2, 2025

Scopus:	2-s2.0-105020677088
Elibrary:	83155454
OpenAlex:	W4415775054

Пока нет цитирований