Exhaustive last-scheduling heuristic for dense task graphs. (English) Zbl 0948.68226
The multiprocessor scheduling (task allocation) problem is considered. This is a NP-complete problem and because of that a lot of heuristics are developed for it’s solving. In this paper a new strategy is proposed to solve this problem. The proposed strategy is based on the use of multiple task priority lists combined with several assignment heuristics. In this way a new exhaustive list-scheduling heuristic is obtained. The advantage of this approach is the possibility to obtain optimal (near-optimal) solutions for a large class of arbitrary task graphs. Some examples and experimental results are presented also.
Reviewer: Dušan Tošić (Beograd)
MSC:
68W10 | Parallel algorithms in computer science |
68T01 | General topics in artificial intelligence |
68M10 | Network design and communication in computer systems |