Exhaustive list-scheduling heuristic for dense task graphs

Exhaustive list-scheduling heuristic for dense task graphs

0.00 Avg rating0 Votes
Article ID: iaor20015
Country: Serbia
Volume: 10
Issue: 1
Start Page Number: 123
End Page Number: 136
Publication Date: Jan 2000
Journal: Yugoslav Journal of Operations Research
Authors:
Keywords: scheduling
Abstract:

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 over all feasible task priority lists is not too expensive for scheduling dense task graphs.

Reviews

Required fields are marked *. Your email address will not be published.