Breadcrumb

 
 

H2GS : a hybrid heuristic-genetic scheduling algorithm for static scheduling of tasks on heterogeneous processor networks

Title:

H2GS : a hybrid heuristic-genetic scheduling algorithm for static scheduling of tasks on heterogeneous processor networks

Daoud, Mohammad (2004) H2GS : a hybrid heuristic-genetic scheduling algorithm for static scheduling of tasks on heterogeneous processor networks. Masters thesis, Concordia University.

[img]
Preview
PDF - Accepted Version
2896Kb

Abstract

The majority of published static scheduling algorithms are only suited to homogeneous processor networks. Little effort has been put into developing scheduling algorithms specifically for heterogeneous processors networks. It is easy to prove, using counterexamples, that the best existing heterogeneous scheduling algorithms [1, 12] generate sub-optimal schedules. Hence, there is much room for the development of better scheduling algorithms for heterogeneous processor networks. This report presents and tests a novel hybrid scheduling algorithm (H2GS) that utilizes both deterministic and stochastic approaches to the problem of scheduling. H2GS is a two-phase algorithm. The first phase implements a heuristic algorithm (LDCP) that identifies one near-optimal schedule. This schedule is used, together with a small number of other schedules as the initial population of the second customized genetic algorithm (called GATS). The GATS algorithm proceeds to evolve even better schedules. The most important contributions of our research are: (i) the development of a new hybrid algorithm, which primes a customized genetic algorithm with a near-optimal schedule produced by a heuristic (LDCP); (ii) The hybrid algorithm succeeds in generating task schedules with completion times that are, on average, 6.2% shorter than those produced by the best existing scheduling algorithm, on the same set of test data.

Divisions:Concordia University > Faculty of Engineering and Computer Science > Electrical and Computer Engineering
Item Type:Thesis (Masters)
Authors:Daoud, Mohammad
Pagination:viii, 80 leaves : ill. ; 29 cm.
Institution:Concordia University
Degree Name:M.A. Sc.
Program:Electrical and Computer Engineering
Date:2004
Thesis Supervisor(s):Kharma, N
ID Code:8384
Deposited By:Concordia University Libraries
Deposited On:18 Aug 2011 14:24
Last Modified:18 Aug 2011 14:24
Related URLs:
All items in Spectrum are protected by copyright, with all rights reserved. The use of items is governed by Spectrum's terms of access.

Repository Staff Only: item control page

Document Downloads

More statistics for this item...

Concordia University - Footer