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

Volume

1

fYear

1996

fDate

3-6 Jan 1996

Firstpage

666

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;

fLanguage

English

Publisher

ieee

Conference_Titel

System Sciences, 1996., Proceedings of the Twenty-Ninth Hawaii International Conference on ,

Conference_Location

Wailea, HI

Print_ISBN

0-8186-7324-9

Type

conf

DOI

10.1109/HICSS.1996.495518

Filename

495518