%0 Journal Article
%T A Static Scheduling Algorithm on DAG Partition-Reconfiguration in the Network of Workstations<br>基于DAG图解-重构的机群系统静态调度算法
%A ZHOU Jia-xiang
%A ZHENG Wei-min
%A <br>周佳祥
%A 郑纬民
%J 软件学报
%D 2000
%I 
%X Static task scheduling on network of workstations is well-known to be an NP-co mplete problem in a strong sense. Some heuristic algorithms have been proven to be sub-optimal under some restrictive conditions. In this paper, the authors pr esent a heuristic algorithm named DAG (directed acyclic graph) partition and sub -graph reconfiguration algorithm, which is a fast and effective one used in par allel task scheduling. The complexity of this algorithm is O(log|V|I1518 ×(|V|+|E|)). It adopts recursion to implement DAG partition and sub-graph re configuration, then builds task clusters to carry out the task scheduling. At th e same time, it even optimizes the number of processors to some degree for it ha s not been solved before. The performance has been observed in a representative example compared with other existing scheduling schemes in terms of several valu able factors. The experimental results show that this algorithm is feasible.
%K Task scheduling
%K DAG (directed acyclic graph)
%K task cluster
%K predecessor task
%K o ptimal predecessor task
%K NOW (network of workstations)<br>任务调度
%K 有向无环图
%K 任务群
%K 前驱任务
%K 最优前驱任务
%K 机群系统.
%U http://www.alljournals.cn/get_abstract_url.aspx?pcid=5B3AB970F71A803DEACDC0559115BFCF0A068CD97DD29835&cid=8240383F08CE46C8B05036380D75B607&jid=7735F413D429542E610B3D6AC0D5EC59&aid=EBB17FE75CB4119F&yid=9806D0D4EAA9BED3&vid=708DD6B15D2464E8&iid=5D311CA918CA9A03&sid=FB3C6F66BC48DD45&eid=E26AA41AE15D3061&journal_id=1000-9825&journal_name=软件学报&referenced_num=5&reference_num=7