A New Nature-inspired Algorithm for Load Balancing
The classical Load Balancing Problem (LBP) is to map tasks to processors so as to minimize the maximum load. Solving the LBP successfully would lead to better utilization of resources and better performance. The LBP has been proven to be NP-hard, thus generating the exact solutions in a tractable amount of time becomes infeasible when the problems become large.We present a new nature-inspired approximation algorithm based on the Particle Mechanics (PM) model to compute in parallel approximate ef.cient solutions for LBPs. Just like other Nature-inspired Algorithms (NAs) drawing from observations of physical processes that occur in nature, the PM algorithm is inspired by physical models of particle kinematics and dynamics. The PM algorithm maps the classical LBP to the movement of particles in a force.eld by a corresponding mathematical model in which all particles move according to certain de.ned rules until reaching a stable state. By anti-mapping the stable state, the solution to LBP can be obtained.
Load balancing approximation algorithm nature-inspired algorithm particle mechanics model distributed and parallel algorithm.
Xiang Feng Francis C.M.Lau Dianxun Shuai
Department of Computer Science East China University of Science and Technology Shanghai,China 200237 Department of Computer Science The University of Hong Kong, Hong Kong Department of Computer Science East China University of Science and Technology Shanghai, China 20023
国际会议
广州
英文
2008-11-19（万方平台首次上网日期，不代表论文的发表时间）