Reassignment of virtual machines into clusters is an important task for the good management of cloud resources since it decisively affects the performance of the Service Provider platform. Thus, for a successful reassignment, a clear and careful reassignment plan should be constructed in advance. In this paper, we propose a planning approach to the problem of reassigning virtual machines in IaaS Cloud platforms and we prove that this problem is NP-Hard. First, we use the well-known A* algorithm to solve this planning problem. Then, we propose two algorithms, called Direct Move Heuristic (DMH) and Iterative Direct Move Heuristic (IDMH), to bridge the space limitation of the A* algorithm. Also, we suggest two experimental studies that have been conducted on randomly generated problem instances. The first experimental study considers small sized problem instances. It aims to show the applicability of the described modeling and assesses the efficiency of the proposed algorithms. The second experimental study focuses on large sized problem instances. It assesses the scalability performance of the IDMH heuristic. Our obtained results show a good scalability performance on problem instances with up to 800 virtual machines.
This paper presents a new heuristic search $$\hbox {F}_{IR}$$ that determines the feasibility of scheduling a set of jobs on a single machine where each job is characterized by its release date, processing time, and deadline. $$\hbox {F}_{IR}$$ uses incremental search and restart strategies to scale the best-first-search heuristic F (Laalaoui and M’Hallah, in: IEEE symposium on evolutionary scheduling and combinatorial optimisation (SSCI) 2022, IEEE, Singapore, 2022). Experimental results provide computational evidence of the superiority of $$\hbox {F}_{IR}$$ for large-scale instances. In fact, $$\hbox {F}_{IR}$$ outperforms the IBM ILOG CP constraint programming solver, the CPLEX mixed integer programming solver, and existing heuristics. It finds feasible solutions for many instances with 100,000 jobs in less than one minute.
In the last two decades we observed a considerably improvement in algorithms' performances and their ability to solve hard combinatorial optimization problems. One of these problems is the knapsack sharing problem (KSP). The latter problem is a challenging variant of the well-known NP-hard single knapsack problem. In fact, we can find in the literature several exact and heuristic resolution approaches to solve the (KSP). We mainly propose here an improvement and an adaptation to parallel computing of one of the existing and most recent algorithm in the literature. The approach is a constructive tree search that runs in two phases: the initial solution construction phase and the second phase where we build the optimal solution through a customized branch and bound. We applied a parallel computing on this second phase in order to improve the overall computational time. Finally we present a comparative study on instances from literature to show the positive effect of parallel processing on the computing time.