Analysis and solutions for multitasks scheduling in distributed environments

作者：He Kun^*; Zhao Yong; Chen Yang

来源：Systems Engineering-Theory & Practice, 2007, 27(5): 119-125.

• scheduling algorithm
• task duplication
• directed acyclic graph
• dymanic clustering
• detach graph

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 (IREA) 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 MJD benchmark.

• 出版日期2007
• 单位华中科技大学