Open AccessAN EFFICIENT TASK SCHEDULING IN DISTRIBUTED COMPUTING SYSTEMS BY IMPROVED GENETIC ALGORITHM
Author(s) -
K. V. N. Sunitha,
P. V. Sudha
Publication year - 2013
Publication title -
international journal of communication networks and security
Language(s) - English
Resource type - Journals
ISSN - 2231-1882
DOI - 10.47893/ijcns.2013.1086
Subject(s) - computer science , directed acyclic graph , parallel computing , scheduling (production processes) , multiprocessor scheduling , multiprocessing , fair share scheduling , schedule , distributed computing , dynamic priority scheduling , fixed priority pre emptive scheduling , two level scheduling , rate monotonic scheduling , algorithm , mathematical optimization , mathematics , operating system
Task Scheduling problem for heterogeneous systems is concerned with arranging the various tasks to be executed on various processors of a system so that computing resources are utilized most effectively. Parallel processing refers to the concept of speeding-up the execution of a task by dividing the task into multiple fragments that can execute simultaneously, each on its own processor i.e. it is the simultaneous processing of the task on two or more processors in order to obtain faster results. It can be effectively used for tasks that involve a large number of calculations, have time constraints and can be divided into a number of smaller tasks. The scheduling problem deals with the optimal assignment of a set of tasks onto parallel multiprocessor system and orders their execution so that the total completion time is minimized. An Optimal scheduling of parallel tasks with some precedence relationship, onto a parallel machine is known to be NP-complete. This precedence relationship among tasks can be represented as Directed Acyclic Graph (DAG). In this paper, a scheduling algorithm has been proposed to schedule DAG tasks on Heterogeneous processor which uses Genetic algorithm to get optimal schedule. The scheduling problem is also considered. This study includes a search for an optimal mapping of the task and their sequence of execution and also search for an optimal configuration of the parallel system. An approach for the simultaneous optimization of all these three components of scheduling method using genetic algorithm is presented and its performance is evaluated in comparison with the Min-Min and Max-Min scheduling methods.