×

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.

MSC:
68W10 Parallel algorithms in computer science
68T01 General topics in artificial intelligence
68M10 Network design and communication in computer systems
PDF BibTeX XML Cite