异构环境下相关任务调度免疫遗传算法的研究  

Immune Genetic Algorithm for Related Task Scheduling in Heterogeneous Environment

作　　者：叶菁[1] 陈国龙[1] 阮一文[1] 

机构地区：[1]福州大学数学与计算机科学学院

出　　处：《小型微型计算机系统》2011年第10期2124-2129,共6页Journal of Chinese Computer Systems

基　　金：国家自然科学基金项目(10871221;60673161)资助;福建省自然科学基金重点项目(A0820002)资助;教育部科学技术研究重点基金项目(206073)资助;福建省科技创新平台计划基金项目(2009J1007)资助;福建省教育厅基金项目(2007JB07024)资助

摘　　要：合理的调度可以在很大程度上提高异构系统资源的利用率,在研究现有任务调度算法的基础上,定义了异构环境下相关任务调度的数学模型,并基于分层和启发式算法的思想,提出最多度动态调度算法MDSA和最少入度动态调度算法LIDSA构造初始种群;借鉴生物免疫系统抗体多样性产生及保持机理,定义了基于抗体的矢量距离、亲合力及浓度相关的选择概率,并改进交叉算子,这样可以在进化过程中保留优秀个体,同时抑制抗体群早熟;提出了高度遍历解码算法HTDA,简化算法实现过程.仿真实验结果表明,本文算法与其它调度算法比较,更能有效地实现资源的分配,可以成功应用于异构环境下相关任务调度.Reasonable resource scheduling can greatly improve the utilization of the heterogeneous system resources.Firstly,the mathematical model of related task scheduling in heterogeneous environment is defined and then Most Degree Dynamic Scheduling Algorithm（MDSA） and Least In-Degree Dynamic Scheduling Algorithm（LIDSA） are proposed,based on the hierarchical and heuristic idea.Secondly,the selection probability based on the distance vector,affinity and concentration is defined and crossover operator is also improved,therefore they can retain high-quality anti-bodies and inhibit their prematurity in the process of evolution.Finally,this paper puts forward Height Traversal Decoding Algorithm（HTDA）,simplifying the implementation process of algorithm.Simulation results show that this algorithm is more effective to the allocation of resources compared with other algorithms,which can be successfully applied to related task scheduling in heterogeneous environment.

关 键 词：异构环境 免疫遗传算法 任务调度 

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