O(n) algorithms for load balancing in distributed computing systems

The problem of optimally balancing a given workload among identical processors with preassigned loads is considered. An improved algorithm which solves the problem in O(n) time under both cases-the case where perfect load balancing is possible and the case where only approximate load balancing is possible-are presented. Properties used to develop the algorithm are also provided. Finally, it is shown how this algorithm can be modified for the case in which the processing rates are not equal.