A Heuristic Algorithm for the Temporal Knapsack Problem
Yana Glotova, Yury Kochetov · 2023
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.