Open AccessDesign and Analysis of Multi - Heuristic Based Solution for Task Graph Scheduling Problem
Author(s) -
Ravreet Kaur*,
Gurvinder Singh
Publication year - 2019
Publication title -
international journal of engineering and advanced technology
Language(s) - English
Resource type - Journals
ISSN - 2249-8958
DOI - 10.35940/ijeat.f8680.088619
Subject(s) - computer science , critical path method , heuristics , scheduling (production processes) , dynamic priority scheduling , heuristic , mathematical optimization , schedule , artificial intelligence , mathematics , systems engineering , engineering , operating system
Heuristic based strategies have always been of interest for researchers to achieve sub-optimal solutions for various NP-Complete problems. Human evolution based methods have been an inspiration for research since ages. One of the many evolutionary strategies based on the principle of genetic algorithm have been able to provide much sought after sub-optimal solutions for various NP-Complete problems. One of the most sought after NP-Complete problem is Task graph scheduling i.e. optimally execute the schedule of tasks on available parallel and distributed environment so as to achieve efficient utilization of available resources. Task scheduling is a multi-objective combinatorial optimization problem, with key parameters being reduced completion time and effective load balance on the available resources. Various algorithms have been proposed by various authors to achieve the above mentioned goal with the help of various heuristics like list scheduling, task duplication and critical path based. The algorithms proposed by various authors like Highest Level First Execution Time (HLFET), Modified Critical Path (MCP), Duplication Scheduling Heuristic (DSH), Linear Clustering (LC) and Dynamic Critical Path (DCP), belonging to each heuristic mentioned before will be taken under study. Previously these algorithms have been individually reported to be efficient in some certain restricted environment parameters with certain limitations; offering very preliminary improvement on the state of art of one single type of environment. Designers face difficulty in choosing the optimal algorithm for the generalized environment. This paper will identify the gaps in existing literature that forms the base of every research focusing in the direction of improvement of task graph scheduling algorithms. Further, this paper will propose a hybrid meta-heuristic i.e. Genetic Algorithm based task graph scheduling solution and perform a comparative study of aforementioned algorithms.