NEW MODEL AND GENETIC ALGORITHM FOR DIVISIBLE LOAD SCHEDULING IN HETEROGENEOUS DISTRIBUTED SYSTEMS
Mingzhao Wang, Xiaoli Wang, Kun Meng, Yuping Wang · International Journal of Pattern Recognition and Artificial Intelligence · 2013
The problem of divisible load scheduling in network based heterogeneous distributed systems is addressed in this paper, where a general platform is considered, and the communication is in non-blocking message receiving mode, moreover, the communication speeds, computation speeds, start-up overheads and workload size are arbitrary. To solve the problem efficiently, we set up an optimization model which can effectively tackle the following three issues: (1) how many and which processors are required in computation; (2) in which order the load fractions are distributed to processors; (3) how much the load fraction should be distributed to each processor. For this model, a novel genetic algorithm is proposed, and the convergence of the proposed algorithm to a globally optimal solution with probability one is proved. Finally, the experiments on several examples indicate the efficiency and effectiveness of the proposed algorithm.