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

Analysis and Solutions for Multitasks Scheduling in Distributed Environments

将约束条件归纳为任务约束、链路约束和资源约束,在允许任务复制的情况下,建立了问题的约束与目标的完整数学模型;提出了一种基于任务复制的模拟人类社会中关系演化过程的簇调度算法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.