基于任务复制的调度算法  

Task duplication based scheduling algorithm

作　　者：张建军[1,2] 李庆华[1] 瞿勇[2] 

机构地区：[1]华中科技大学计算机学院,湖北武汉430074 [2]海军工程大学理学院,湖北武汉430033

出　　处：《计算机工程与设计》2009年第8期1896-1899,2029,共5页Computer Engineering and Design

基　　金：国家自然科学基金项目(60273075);海军工程大学自然科学基金项目(HGDJJ05005)

摘　　要：任务调度是并行分布式计算系统中最具挑战性的NP完全问题之一。基于任务复制的调度是一种有效的调度方法。在通信开销较小的情况下,现已有许多算法能产生最优调度。但其最优条件要么比较苛刻,要么比较复杂。因此,针对这些算法存在的问题,提出一个新的基于任务复制的聚集调度(TDCS)算法,不仅其最优条件简单、宽松,而且该算法具有更小的时间复杂度O(log),其中,和分别表示任务集中任务的个数和最大入度。Task Scheduling is one of the most challenging NP-complete problems in parallel and distributed computing systems. Duplication based scheduling （DBS） is an efficient approach to the scheduling problems. Although there are some algorithms that are able to find an optimal schedule under relatively short communication time, conditions of which are either restricted or complex. A new task duplication based clustering scheduling algorithm （TDCS） is presented, which can generate an optimal schedule with a simple and loose condition. The time complexity of the proposed algorithm is O （dvlogd）, where v represents the number of tasks and d represents the maximum indegree of tasks respectively.

关 键 词：最优调度算法 任务复制 最优条件 任务聚集 Fork—Join任务图 

分 类 号：TP316[自动化与计算机技术—计算机软件与理论]