Abstract: We introduce a temporal knapsack problem originated in cloud computing. We have a server and a set of virtual machines (VMs). The server is divided by two identical NUMA nodes with their own CPU cores and RAM. For each VM, we know its CPU and RAM capacity, profit, and time interval when it is active. Some VMs we call small. We can put them in any NUMA node. Other VMs we call large. Such a VM occupies two nodes of the server and requires half of its own CPU and RAM on each node. We need to find a subset of VMs and their location on the server to maximize the total profit under the server’s CPU and RAM capacity constraints during the whole-time interval. To tackle this NP-hard problem, we design an adaptive large neighborhood search method based on the destroy and repair approach. At the destroy stage, some VMs are removed from the current solution. At the repair stage, a new solution is created based on the tabu search meta-heuristic with flip and swap neighborhoods and penalties. To obtain an initial solution, we apply a fast greedy algorithm. Computational experiments are conducted for the semi-synthetic test instances with up to 500 VMs. Computational results are discussed and compared with the near-optimal solutions of commercial software Gurobi.

Cite: Glotova Y. , Kochetov Y.
A Heuristic Algorithm for the Temporal Knapsack Problem
In compilation 2023 19th International Asian School-Seminar on Optimization Problems of Complex Systems (OPCS). – IEEE., 2023. – C.31-35. – ISBN 9798350331134. DOI: 10.1109/opcs59592.2023.10275324 Scopus OpenAlex

Dates:

Published print:	Oct 13, 2023
Published online:	Oct 13, 2023

Identifiers:

Scopus:	2-s2.0-85175419808
OpenAlex:	W4387620826

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

Altmetrics: