Finish Time Maximization Method: an Anti-Sequence Algorithm to Scheduling Task Graphs for Multiprocessors

摘要

The problem of task scheduling on multiprocessors is NP-complete for most cases. Because of the intractability of the problem, heuristic ideas are used in most of the existed algorithms. In this paper, we propose an anti-sequence scheduling algorithm, FTM algorithm, of which the mapping strategy is based on an anti-topology order. After the description of the algorithm, we present an illustrating example and the experiment results for a group of task graphs. It is shown that the solution quality acquired by the proposed algorithm outperforms some other sequence scheduling algorithms.