Two Types Of Load Balancing Problems Under A Grade Of Service Provision

The load balancing problem under a grade of service provision is one of the classic problems in the field of combinatorial optimization.It has been widely studied in the past ten years.The problem of load balancing under a grade of service provision is that a number of workpieces with a grade of service provision are assigned to some machines with a grade of service provision,the workpiece can be processed on machine when it's grade level is higher than the machine,and each workpiece can only be processed by one machine without interruption.The goal is to find a allocation scheme that minimizes the maximum machine load,The load here is generally defined as the processing time of the workpiece or the various resources required to process the workpiece.This thesis mainly studies two general types of load balancing problems under a grade of service provision:multiple load balancing problems and multidimensional load balancing.The multiple load balancing problem under a grade of service provision is given to a number of customers,and some machine with a grade level,each customer submits a number of workpieces with a grade level to these machines,the workpiece can be processed on a machine when it's grade level is higher than the machine,and each workpiece can only be processed by one machine without interruption.The goal is to find a allocation scheme that minimizes the maximum machine load.For the multiple load balancing under a grade of service provision,when there are 2 machines,this thesis design a-5/4-approximation algorithm,a 5/3-The optimal online algorithm and a 3/2-optimal semi-online algorithm where half of all the workpieces processing times are known and analyze the approximation ratio;when there are more than 2 machines,this thesis design a 2--1/m-1-approximation algorithm and analyze the approximation ratio.The multi-dimensional load balancing problem under a grade of service provision is to assign a number of workpieces with a grade level to some machine with a grade level,the load of the workpiece in this problem is a vector with the same dimension,and the workpiece can be processed on a machine when it's grade level is higher than the machine.The goal is to find a allocation scheme that minimize the maximum component of the machine load.For multi-dimensional load balancing under a grade of service provision,this thesis designs a 2d-approximation algorithm by adding the components of the vector,while gives the dynamic programming for the problem.When the dimension of the load vector and the number of machines are fixed constants,a full-polynomial time approximation scheme is designed based on the 2d-approximation algorithm and dynamic programming.