A DAG-based partitioning-reconfiguring scheduling algorithm in network of workstations

Static task scheduling on a network of workstations (NOW) is known to be an NP-complete problem in a strong sense. Some heuristic algorithms have been proven to be suboptimal. This paper presents a heuristic algorithm, called the DAG (directed acyclic graph)-based partitioning and reconfiguring algorithm, which is fast and efficient in parallel task scheduling. The complexity of this algorithm is O[log/sup |V|//spl times/(|V|+|E|)]. It adopts recursion to implement the partitioning of a DAG and the reconfiguration of sub-graphs, then builds task clusters to carry out the task scheduling. At the same time, it even optimizes the number of processors to some degree, which has not been solved before. The performance has been observed in a representative example by contrasting it with other existing scheduling schemes in terms of several variable factors. The results show that this algorithm is worthwhile.