Static task Scheduling on Network of Workstations is a strong sense. Some heuristic algorithms have been proven to be sunse. Some heuristic algorithms have been proven to be sub-optimal. This paper presents a heuristic algorithm named DAG-based partitioning and reconfiguring algorithm, which is a fast and efficient one in parallel task scheduling. The complexity of this algorithm is O(log~|v| X(|V|+|E|)). It adopts recursion to implement partitioning DAG and reconfiguring sub-graphs. then building task clusters to carry out the task scheduling At the same time. it even optimizes the number of processors in some degree, which has not been soled before. The performance has been observed in a representative example by contrasting it with other existing scheduling schemes in terms of several valuable factors. The result shows that this algorithm is worthwhile.
展开▼
机译：工作站网络上的静态任务调度具有很强的意义。一些启发式算法已被证明是理想的。一些启发式算法已被证明是次优的。本文提出了一种启发式算法，称为基于DAG的分区和重新配置算法，这是一种并行任务调度中快速高效的算法。该算法的复杂度为O（log〜| v | X（| V | + | E |））。它采用递归实现分区DAG和重新配置子图。然后建立任务集群以同时执行任务调度。它甚至在某种程度上优化了处理器的数量，这在以前是从未有过的。通过在几个有价值的因素方面将其与其他现有的调度方案进行对比，可以在代表性示例中观察到性能。结果表明该算法是值得的。
展开▼
