Authors: Davidović, Tatjana 
Affiliations: Mathematical Institute of the Serbian Academy of Sciences and Arts 
Title: Exhaustive list-scheduling heuristic for dense task graphs
Journal: Yugoslav Journal of Operations Research
Volume: 10
Issue: 1
First page: 123
Last page: 136
Issue Date: 1-Dec-2000
Rank: M50
ISSN: 0354-0243
The multiprocessor scheduling problem has usually been "solved" by using heuristic methods. A large number of such heuristics can be found in the literature, but none of them can efficiently be applied to the problem in its most general form. The efficiency of any scheduling heuristic depends on both the task graph structure and the multiprocessor system architecture. List-scheduling heuristics are the most common ones in use. They are based on the definition of the task priority list determining the order in which tasks will be scheduled (assigned to one of the processors). A task can be assigned to a processor in many different ways, but variations of the earliest start heuristics are the most frequent in use. In this paper a scheduling strategy based on the use of multiple task priority lists combined with several assignment heuristics is suggested in order to find optimal (near-optimal at the worst) solutions for a large class of arbitrary task graphs. It is shown that performing an exhaustive search overall feasible task priority lists is not too expensive for scheduling dense task graphs.
Keywords: Communication delay | Multiprocessors | Precedence graphs | Scheduling
Publisher: Faculty of Organizational Sciences, University of Belgrade

Show full item record


checked on May 17, 2024

Page view(s)

checked on May 9, 2024

Google ScholarTM


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.