Comparison of Heuristics for Scheduling Independent Tasks on Heterogeneous Distributed Environments

Scheduling is one of the core steps to efficiently exploit the capabilities of heterogeneous distributed computing systems and is an NP-complete problem. Therefore using meta-heuristic algorithms is a suitable approach in order to cope with its difficulty. In meta-heuristic algorithms, generating individuals in the initial step has an important effect on the convergence behavior of the algorithm and final solutions. Using some heuristics for generating one or more near-optimal individuals in the initial step can improve the final solutions obtained by meta-heuristic algorithms. Different criteria can be used for evaluating the efficiency of scheduling algorithms, the most important of which are makespan and flowtime. In this paper we propose an efficient heuristic method and then we will compare with five popular heuristics for minimizing makespan and flowtime in heterogeneous distributed computing systems. 1