Abstract
Scheduling a directed acyclic graph (DAG) which represents the precedence relations of the tasks of a parallel program in a distributed computing system (DCS) is known as an NP-complete problem except for some special cases. Many heuristic-based methods have been proposed under various models and assumptions. A DCS can be classified in two types according to the characteristics of the processors on a network: a distributed homogeneous system (DHOS) and a distributed heterogeneous system (DHES). This paper defines a general model for a DHOS and a DHES and presents a genetic algorithm (GA) to solve the task scheduling problem in the defined DCS. The performance of the proposed GA is compared with the list scheduling algorithm in a DHOS and with the one-level reach-out greedy algorithm (OLROG) in a DHES. The proposed GA has shown better performance in various environments than other scheduling methods.
| Original language | English |
|---|---|
| Pages | 301-305 |
| Number of pages | 5 |
| Publication status | Published - 1997 |
| Event | Proceedings of the 1997 2nd High Performance Computing on the Information Superhighway, HPC Asia'97 - Seoul, South Korea Duration: 1997 Apr 28 → 1997 May 2 |
Other
| Other | Proceedings of the 1997 2nd High Performance Computing on the Information Superhighway, HPC Asia'97 |
|---|---|
| City | Seoul, South Korea |
| Period | 97/4/28 → 97/5/2 |
All Science Journal Classification (ASJC) codes
- Computer Science(all)