Please use this identifier to cite or link to this item:
Title: Application of heuristic and metaheuristics to the bi-objective task scheduling problem on heterogeneous distributed computing systems
Researcher: Chitra P
Guide(s): Venkatesh P
Keywords: Directed Acyclic Graph
Genetic algorithm
Computing systems
Upload Date: 11-Jul-2013
University: Anna University
Completed Date: 04/07/2011
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.
Pagination: xx, 145p.
Appears in Departments:Faculty of Information and Communication Engineering

Files in This Item:
File Description SizeFormat 
01_title.pdfAttached File28.63 kBAdobe PDFView/Open
02_certificates.pdf813.13 kBAdobe PDFView/Open
03_abstract.pdf19.64 kBAdobe PDFView/Open
04_acknowledgement.pdf16.74 kBAdobe PDFView/Open
05_contents.pdf58.89 kBAdobe PDFView/Open
06_chapter 1.pdf74.67 kBAdobe PDFView/Open
07_chapter 2.pdf26.25 kBAdobe PDFView/Open
08_chapter 3.pdf383.42 kBAdobe PDFView/Open
09_chapter 4.pdf293.1 kBAdobe PDFView/Open
10_chapter 5.pdf241.81 kBAdobe PDFView/Open
11_chapter 6.pdf26.02 kBAdobe PDFView/Open
12_appendix.pdf571.87 kBAdobe PDFView/Open
13_references.pdf29.5 kBAdobe PDFView/Open
14_publications.pdf22.12 kBAdobe PDFView/Open
15_vitae.pdf13.75 kBAdobe PDFView/Open

Items in Shodhganga are protected by copyright, with all rights reserved, unless otherwise indicated.

Altmetric Badge: