Abstract
Scheduling dependent tasks is one of the most challenging versions of the scheduling problem in parallel and distributed systems. It is known to be computationally intractable in its general form as well as several restricted cases. As a result, researchers have studied restricted forms of the problem by constraining either the task graph representing the parallel tasks or the computer model. Also, in an attempt to solve the problem in the general case, a number of heuristics have been developed. In this paper, we study the scheduling problem for a fixed number of processors m. In the proposed work, we approach the problem by recursively reducing the m-processor scheduling to (m-1)-processor scheduling until we apply the optimal two-processor scheduling algorithm when m equals two. This is accomplished by identifying a maximal chain C in the task graph G and merging the (m-1) processor scheduling of (G-C) and the 1-processor scheduling of C. A number of experiments were conducted to compare the suggested approach with the standard list-scheduling algorithm. Based on the outcome of the conducted experiments, the proposed algorithms outperformed or matched the performance of the list heuristic almost all the time.
Original language | English (US) |
---|---|
Title of host publication | Proceedings of the IASTED International Conference on Parallel and Distributed Computing and Systems |
Editors | T. Gonzalez |
Pages | 429-436 |
Number of pages | 8 |
Volume | 16 |
State | Published - 2004 |
Event | Proceedings of the 16th IASTED International Conference on Parallel and Distributed Computing and Systems - Cambridge, MA, United States Duration: Nov 9 2004 → Nov 11 2004 |
Other
Other | Proceedings of the 16th IASTED International Conference on Parallel and Distributed Computing and Systems |
---|---|
Country/Territory | United States |
City | Cambridge, MA |
Period | 11/9/04 → 11/11/04 |
Keywords
- Heuristics
- Optimal algorithms
- Parallel Processing
- Task Scheduling
ASJC Scopus subject areas
- General Engineering