分布式环境下多任务调度问题的分析与求解  

Analysis and Solutions for Multitasks Scheduling in Distributed Environments

作　　者：何琨[1] 赵勇[1] 陈阳[1] 

机构地区：[1]华中科技大学控制科学与工程系系统工程研究所,武汉430074

出　　处：《系统工程理论与实践》2007年第5期119-125,共7页Systems Engineering-Theory & Practice

基　　金：国家自然科学基金(70471077;60673057);高等学校博士学科点专项基金(20020487046)

摘　　要：将约束条件归纳为任务约束、链路约束和资源约束,在允许任务复制的情况下,建立了问题的约束与目标的完整数学模型;提出了一种基于任务复制的模拟人类社会中关系演化过程的簇调度算法IREA,包括前沿调度、动态分簇和分离图三个子算法.IREA采用全新的优先级规则,定义了关系数、依赖度、归并度等表示簇的优先级.通过对两个经典算例的计算,发现IREA能求出比算例所在文献算法所得解更优的解;对MJD算例,还得到了一个不同于原文献所给理论最优格局的一个新的最优格局.This paper addresses the problem of static scheduling multitasks with precedence constraints represented as directed acyclic graphs for execution on distributed homogeneous environments. The problem is strong NP-complete, and efficient algorithms for it will have both highly theoretical value and highly practical value. The constraints are summed up to task constraints, link constraints and resource constraints. An integrated mathematical model with constraints and objective is set up. And a new heuristic approach named the Interpersonal Relationships Evolution Algorithm （IBEA） that is based on task duplication is proposed. IREA resembles the evolution of the interpersonal relationships within the human society, and includes three components： cutting edge algorithm, dynamic group algorithm and detach graph algorithm. The priority rules used are new. Relationship number, dependent degree and merge degree are defined for cluster＇s priority. It is found that IREA could get better solutions for two classic benchmarks than the algorithms which gave the benchmarks. Besides, IREA gets a different optimal solution compared with the theory optimal one for the MID benchmark.

关 键 词：调度算法 任务复制 有向无回路图 动态分簇 分离图 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]