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.