A Multi-Neighborhood Local Search Algorithm For Cloud Computing Resource Scheduling Problem

Given the physical server resources and the list of virtual machines to be allocated,the cloud computing resource scheduling problem consists of assigning a specific host to each virtual machine in order to maximize the number of virtual machines that can be placed in the system.At the same time,it must meet the resource capacity constraints in each dimension and various allocation rules.According to the specific application scenarios of a cloud computing company,how to integrate the first and secondary scheduling processes and design effective and reliable resource scheduling algorithms is of great significance to improve the resource utilization rate and service quality of cloud computing system.An auxiliary objective based multi-neighborhood local search algorithm(AO-MNLS)is proposed to solve the cloud computing resource scheduling problem.The first scheduling scenario corresponds to the initial solution construction process in cloud computing resource scheduling problem.The algorithm constructs a search tree through the remaining amount of host resources.For the virtual machines to be allocated,it quickly locates a group of hosts in the search tree and executes greedy algorithm,which realizes the rapid response to the allocation request of virtual machines.The secondary scheduling scenario corresponds to the local search process in cloud computing resource scheduling problem.Two auxiliary objective functions based on heuristic rules are proposed: the average objective and the fragment objective.By measuring the average virtual machine size and resource fragmentation in the host before and after performing neighborhood actions,it plays a better guiding role in searching neighborhood actions.Aiming at the problem structure,a single virtual machine moving neighborhood and a double virtual machine exchanging neighborhood are designed,and hosts that temporarily violate the resource capacity constraints are allowed and repair actions are performed during the search process,which greatly expands the search space of local search.In addition,the algorithm adopts the neighborhood partition mechanism in neighborhood search,which further improves the efficiency of the algorithm without sacrificing the solution quality.According to the real data provided by a cloud computing company,100 benchmark instances are generated and tested.The AO-MNLS can obtain the theoretical upper bound value in 50 of the 100 instances,while better results than the comparison algorithm are obtained for 31 instances,and slightly worse results are obtained for 4 instances.The AOMNLS can reach equal results with the comparison algorithm on the remaining 65 instances.These experimental results demonstrate the superiority of the AO-MNLS in terms of the search effectiveness and efficiency.In addition,the simplified version of AO-MNLS is constructed and compared,which shows the effectiveness of the search tree,auxiliary objective function and neighborhood structure in the algorithm.