Genetic algorithm based on-arrival task scheduling on distributed computing platform

Abstract

This paper models a dynamic task scheduling problem on a distributed computing platform and proposes a strategy for mapping tasks to resources. It presents an adaptive scheduling approach, ‘Dynamic Genetic Algorithm for Earliest Completion Time (^dGA-ECT)’, with the objective of reducing schedule length by efficient utilization of distributed resources. The algorithm improves the throughput of a multi-workflow distributed computing platform. A central scheduler calls ^dGA-ECT when the number of waiting tasks is more than that of idle processing units, otherwise, it simply maps as per FIFO (First In First Out), maintaining precedence relationships among tasks. The proposed algorithm can schedule dependent tasks having different arrival times on a real-time system and maintain schedule cycles without delay. Simulations on MATLAB consider standard task graphs of three benchmark programs for performance evaluation, based on fixed population size with different generations and variable population size with different generations. To exhibit the applicability of our approach, we have carried out an extensive simulation to compare performance with a similar algorithm. The comparative study of results with existing policy shows that our approach is more efficient in generating feasible solutions in the case of different arrival time of tasks.

KEYWORDS:

• Distributed computing
• scheduling
• genetic algorithm
• central scheduler
• on-arrival task scheduling

Disclosure statement

No potential conflict of interest was reported by the author(s).

Additional information

Notes on contributors

Rintu Nath

Rintu Nath is a senior scientist working with Vigyan Prasar, an organisation of the Department of Science and Technology, Government of India.

A. Nagaraju

A. Nagaraju is an Assistant Professor of Department of Computer Science, Central University of Rajasthan.