An Efficient Genetic Algorithm for Task Scheduling in Heterogeneous Distributed Computing Systems

Task scheduling plays an important role in the operation of distributed computing systems. Because of its importance, several task scheduling algorithms are proposed in the literature, mainly for homogeneous processors. Few scheduling algorithms are proposed for heterogeneous distributed computing systems (HeDCSs). In this paper, we present a new approach which uses a customized genetic algorithm to produce high-quality tasks schedules for HeDCSs. The performance of the new algorithm is compared to that of two leading scheduling algorithms for HeDCSs. The comparison, which is based on both randomly generated task graphs and task graphs of certain real-world numerical applications, exhibits the supremacy of the new algorithm over the older ones, in terms of schedule length, speedup and efficiency.