Title :
An augmentation-based algorithm for task scheduling in parallel systems
Author :
Vemulapalli, Raj ; Ali, Hesham H.
Author_Institution :
Cap Gemini America, Des Moines, IA, USA
Abstract :
The problem of scheduling tasks on parallel systems has been shown to be computationally intractable in its general form as well as many restricted cases. In this paper, we introduce a two-step augmentation-based algorithm for scheduling general task graphs in parallel systems. Several experimental studies have been conducted to compare the performance of the proposed technique with several known heuristics. The obtained results show that the augmentation-based algorithm out-performed other heuristics on most of the randomly-generated task graphs
Keywords :
computational complexity; graph theory; parallel algorithms; processor scheduling; software performance evaluation; computationally intractable problem; heuristics; parallel systems; performance; randomly-generated task graphs; task scheduling; two-step augmentation-based algorithm; Computer science; Concurrent computing; Costs; Distributed computing; Greedy algorithms; Heuristic algorithms; Optimal scheduling; Polynomials; Processor scheduling; Scheduling algorithm;
Conference_Titel :
System Sciences, 1996., Proceedings of the Twenty-Ninth Hawaii International Conference on ,
Conference_Location :
Wailea, HI
Print_ISBN :
0-8186-7324-9
DOI :
10.1109/HICSS.1996.495518
