Login | Register

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.

[thumbnail of MR04364.pdf]
Preview
Text (application/pdf)
MR04364.pdf - Accepted Version
2MB

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 > Gina Cody School 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
Identification Number:QA 402.5 D27 2004
ID Code:8384
Deposited By: Concordia University Library
Deposited On:18 Aug 2011 18:24
Last Modified:13 Jul 2020 20:04
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

Downloads per month over past year

Research related to the current document (at the CORE website)
- Research related to the current document (at the CORE website)
Back to top Back to top