zbMATH — the first resource for mathematics

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.

68W10 Parallel algorithms in computer science
68T01 General topics in artificial intelligence
68M10 Network design and communication in computer systems