Virtual Machine（VM） allocation for multiple tenants is an important and challenging problem to provide efficient infrastructure services in cloud data centers. Tenants run applications on their allocated VMs, and th...Virtual Machine（VM） allocation for multiple tenants is an important and challenging problem to provide efficient infrastructure services in cloud data centers. Tenants run applications on their allocated VMs, and the network distance between a tenant＇s VMs may considerably impact the tenant＇s Quality of Service（Qo S）. In this study, we define and formulate the multi-tenant VM allocation problem in cloud data centers, considering the VM requirements of different tenants, and introducing the allocation goal of minimizing the sum of the VMs＇ network diameters of all tenants. Then, we propose a Layered Progressive resource allocation algorithm for multi-tenant cloud data centers based on the Multiple Knapsack Problem（LP-MKP）. The LP-MKP algorithm uses a multi-stage layered progressive method for multi-tenant VM allocation and efficiently handles unprocessed tenants at each stage. This reduces resource fragmentation in cloud data centers, decreases the differences in the Qo S among tenants, and improves tenants＇ overall Qo S in cloud data centers. We perform experiments to evaluate the LP-MKP algorithm and demonstrate that it can provide significant gains over other allocation algorithms.展开更多
The multiple knapsack problem denoted by MKP (B,S,m,n) can be defined as fol- lows.A set B of n items and a set Sof m knapsacks are given such thateach item j has a profit pjand weightwj,and each knapsack i has a ca...The multiple knapsack problem denoted by MKP (B,S,m,n) can be defined as fol- lows.A set B of n items and a set Sof m knapsacks are given such thateach item j has a profit pjand weightwj,and each knapsack i has a capacity Ci.The goal is to find a subset of items of maximum profit such that they have a feasible packing in the knapsacks.MKP(B,S,m,n) is strongly NP- Complete and no polynomial- time approximation algorithm can have an approxima- tion ratio better than0 .5 .In the last ten years,semi- definite programming has been empolyed to solve some combinatorial problems successfully.This paper firstly presents a semi- definite re- laxation algorithm (MKPS) for MKP (B,S,m,n) .It is proved that MKPS have a approxima- tion ratio better than 0 .5 for a subclass of MKP (B,S,m,n) with n≤ 1 0 0 ,m≤ 5 and maxnj=1{ wj} minmi=1{ Ci} ≤ 2 3 .展开更多
This paper describes methods to merge two cover inequalities and also simultaneously merge multiple cover inequalities in a multiple knapsack instance. Theoretical results provide conditions under which merged cover i...This paper describes methods to merge two cover inequalities and also simultaneously merge multiple cover inequalities in a multiple knapsack instance. Theoretical results provide conditions under which merged cover inequalities are valid. Polynomial time algorithms are created to find merged cover inequalities. A computational study demonstrates that merged inequalities improve the solution times for benchmark multiple knapsack instances by about 9% on average over CPLEX with default settings.展开更多
The multiple knapsack problem （MKP） forms a base for resolving many real-life problems. This has also been considered with multiple objectives in genetic algorithms （GAs） for proving its efficiency. GAs use self- ...The multiple knapsack problem （MKP） forms a base for resolving many real-life problems. This has also been considered with multiple objectives in genetic algorithms （GAs） for proving its efficiency. GAs use self- adaptability to effectively solve complex problems with constraints, but in certain cases, self-adaptability fails by converging toward an infeasible region. This pitfall can be resolved by using different existing repairing techniques; however, this cannot assure convergence toward attaining the optimal solution. To overcome this issue, gene position-based suppression （GPS） has been modeled and embedded as a new phase in a classical GA. This phase works on the genes of a newly generated individual after the recombination phase to retain the solution vector within its feasible region and to im- prove the solution vector to attain the optimal solution. Genes holding the highest expressibility are reserved into a subset, as the best genes identified from the current individuals by re- placing the weaker genes from the subset. This subset is used by the next generated individual to improve the solution vec- tor and to retain the best genes of the individuals. Each gene＇s positional point and its genotype exposure for each region in an environment are used to fit the best unique genes. Further, suppression of expression in conflicting gene＇s relies on the requirement toward the level of exposure in the environment or in eliminating the duplicate genes from the environment.The MKP benchmark instances from the OR-library are taken for the experiment to test the new model. The outcome por- trays that GPS in a classical GA is superior in most of the cases compared to the other existing repairing techniques.展开更多
基金supported in part by the National Key Basic Research and Development (973) Program of China (No. 2011CB302600)the National Natural Science Foundation of China (No. 61222205)+1 种基金the Program for New Century Excellent Talents in Universitythe Fok Ying-Tong Education Foundation (No. 141066)
文摘Virtual Machine（VM） allocation for multiple tenants is an important and challenging problem to provide efficient infrastructure services in cloud data centers. Tenants run applications on their allocated VMs, and the network distance between a tenant＇s VMs may considerably impact the tenant＇s Quality of Service（Qo S）. In this study, we define and formulate the multi-tenant VM allocation problem in cloud data centers, considering the VM requirements of different tenants, and introducing the allocation goal of minimizing the sum of the VMs＇ network diameters of all tenants. Then, we propose a Layered Progressive resource allocation algorithm for multi-tenant cloud data centers based on the Multiple Knapsack Problem（LP-MKP）. The LP-MKP algorithm uses a multi-stage layered progressive method for multi-tenant VM allocation and efficiently handles unprocessed tenants at each stage. This reduces resource fragmentation in cloud data centers, decreases the differences in the Qo S among tenants, and improves tenants＇ overall Qo S in cloud data centers. We perform experiments to evaluate the LP-MKP algorithm and demonstrate that it can provide significant gains over other allocation algorithms.
基金Supported by the National Natural Science Foundation of China(1 9971 0 78)
文摘The multiple knapsack problem denoted by MKP (B,S,m,n) can be defined as fol- lows.A set B of n items and a set Sof m knapsacks are given such thateach item j has a profit pjand weightwj,and each knapsack i has a capacity Ci.The goal is to find a subset of items of maximum profit such that they have a feasible packing in the knapsacks.MKP(B,S,m,n) is strongly NP- Complete and no polynomial- time approximation algorithm can have an approxima- tion ratio better than0 .5 .In the last ten years,semi- definite programming has been empolyed to solve some combinatorial problems successfully.This paper firstly presents a semi- definite re- laxation algorithm (MKPS) for MKP (B,S,m,n) .It is proved that MKPS have a approxima- tion ratio better than 0 .5 for a subclass of MKP (B,S,m,n) with n≤ 1 0 0 ,m≤ 5 and maxnj=1{ wj} minmi=1{ Ci} ≤ 2 3 .
文摘This paper describes methods to merge two cover inequalities and also simultaneously merge multiple cover inequalities in a multiple knapsack instance. Theoretical results provide conditions under which merged cover inequalities are valid. Polynomial time algorithms are created to find merged cover inequalities. A computational study demonstrates that merged inequalities improve the solution times for benchmark multiple knapsack instances by about 9% on average over CPLEX with default settings.
文摘The multiple knapsack problem （MKP） forms a base for resolving many real-life problems. This has also been considered with multiple objectives in genetic algorithms （GAs） for proving its efficiency. GAs use self- adaptability to effectively solve complex problems with constraints, but in certain cases, self-adaptability fails by converging toward an infeasible region. This pitfall can be resolved by using different existing repairing techniques; however, this cannot assure convergence toward attaining the optimal solution. To overcome this issue, gene position-based suppression （GPS） has been modeled and embedded as a new phase in a classical GA. This phase works on the genes of a newly generated individual after the recombination phase to retain the solution vector within its feasible region and to im- prove the solution vector to attain the optimal solution. Genes holding the highest expressibility are reserved into a subset, as the best genes identified from the current individuals by re- placing the weaker genes from the subset. This subset is used by the next generated individual to improve the solution vec- tor and to retain the best genes of the individuals. Each gene＇s positional point and its genotype exposure for each region in an environment are used to fit the best unique genes. Further, suppression of expression in conflicting gene＇s relies on the requirement toward the level of exposure in the environment or in eliminating the duplicate genes from the environment.The MKP benchmark instances from the OR-library are taken for the experiment to test the new model. The outcome por- trays that GPS in a classical GA is superior in most of the cases compared to the other existing repairing techniques.
