Application of heuristic and metaheuristics to the bi-objective task scheduling problem on heterogeneous distributed computing systems

Abstract

Heterogeneous distributed systems are widely deployed for executing computationally intensive parallel applications with diverse computing needs. The efficient execution of applications in such environments requires effective scheduling strategies that take into account both algorithmic and architectural characteristics to achieve a good mapping of tasks to processors, i.e., to minimize the schedule length (Makespan). An application can be modeled as a Directed Acyclic Graph (DAG). A heterogeneous distributed computing system can be modeled as a resource graph. The most studied heuristic methods are so called list scheduling algorithms. They were primarily developed for generating schedules of good quality considering the single objective of minimal schedule length. The traditional list scheduling heuristics are good in generating schedules due to their greedy nature. This was the motivation factor for this research to use them for handling the two objectives of makespan and reliability. Genetic Algorithm is one of the widely used metaheuristics for solving the task scheduling problem. The efficiency of using GA for solving the task scheduling problem has been proved in a various studies. Hence, the multiobjective genetic algorithms are used in this research to solve the problem under study. Various performance metrics are available in the literature to measure the convergence and diversity of the obtained nondominated solutions of the multiobjective evolutionary algorithms. The spacing and spread metric are used for measuring the performance in this research. The two Pareto based multiobjective genetic algorithms: NSGA-II and SPEA2 are implemented in the pure and hybrid version and compared. The convergence and diversity of the obtained non-dominated solutions are evaluated. The performance is evaluated for the random and real application task graphs. The suitability of using hybrid NSGA-II for solving the task scheduling problem is confirmed by the simulations.