A Research On Algorithms For Bin Packing And Knapsack Problems In Cloud Computing

In the 21st century,cloud computing technology emerged with the development of computer software and hardware technology.It provides large-scale computing,net-work storage,and other basic services,which solve problems of insufficient computing power,inconvenient access,and electricity wastage.There is a class of important re-source scheduling problems in cloud computing,which is closely related to the classic bin packing problem and knapsack problem.Due to the practical requirements of cloud computing,these combinatorial optimization problems often have a large scale,ele-ments of finite types,constraints from the practical scene,and a short solving time.Those characteristics raise new research problems.The bin packing problem and knapsack problem are two classic combinatorial op-timization problems.Now algorithms for the two problems have been applied in many areas,e.g.,the memory allocation problem,the cutting stock problem,and the adver-tisement arranging problem.This paper mainly researches approximation and heuristic algorithms for bin packing and knapsack problems in cloud computing considering the preceding features.Chapter 2 introduces two linear time bin packing algorithms on uniformly dis-tributed items.They are developed for a file transmission problem in cloud computing.There are millions of items to be packed in a short time.A linear time equidistant group-ing heuristic contributes greatly to the algorithms.Two parameters balance the solving time and the packing result.The two algorithms accomplish in O（n）time and waste O（_Kⁿ）bin space,where K is a constant.In addition,experiments show that,compared to classical bin packing algorithms,the solving speed of the two algorithms is at least6.5 times faster and the solution gap is no more than 1.3%.Chapter 3 presents two fast two dimensional bin packing algorithms on finite types of items.It aims to tackle a virtual machine allocation problem involving the computer core and memory resources in cloud computing.In this problem,types of virtual ma-chines are finite,the configurations of virtual machines are mostly powers of 2,and the solving time is short.Based on those characteristics and inspirations from bin packing algorithmic researches on divisible items,we find a virtual machine combination rule and a physical machine capacity pre-allocation heuristic.The resultant₉¹⁰-asymptotic approximation algorithm outperforms the current best（1.405+?）-asymptotic approx-imation algorithm for two dimensional bin packing problem.Chapter 4 shows a fast two dimensional knapsack algorithm with many practical constraints.This research is to optimize a resource allocation problem in data communi-cation of cloud computing.This problem has many physical constraints,several kinds of resources,and a extremely short solving time.We formulate it as a mixed integer programming problem and find the key constraints.Our heuristic algorithm selects a tool for resource users and designs user evaluation metrics by the contribution of users and the volume of resources.The sorted users occupy resources greedily.Compared to a basic greedy algorithm,our algorithm reduces the running time by 19.23%and improves the allocation result by 25.66%.