异构集群独立任务调度问题的自适应免疫算法

An adaptive immune-based algorithm for independent task scheduling problem on heterogeneous workstation clusters

异构集群独立任务调度问题是一个典型的NP难题.面向这一难题,现有的启发式调度算法,如RC、DGA等都没能兼顾实时性与负载均衡能力.人工免疫是一个新的人工智能技术,在解决组合优化难题方面,表现出了较好的性能.文章建立了一个异构集群任务调度模型,基于免疫响应的克隆选择原理和亲和力成熟机制,提出了异构集群独立任务调度问题的自适应免疫算法(AIBA).在AIBA中,通过注入抗体和动态计算负载均衡阈值的方法,将LPT算法的实时性与人工免疫系统的组合优化能力有机地结合了起来.最后,通过模拟实验对算法进行了测试和比较.实验结果显示,与DGA相比,该算法具有自适应调整能力,能动态地兼顾实时性与负载均衡度指标,有很强的实用性.

A heterogeneous cluster of workstations （HCOW） has problems with independent task scheduling. The fact that the independent task scheduling problem on HCOW is NP-hard （non-deterministic polynomial-time hard） has motivated the development of many heuristic scheduling algorithms, such as RC and DGA. These heuristic algorithms, however, neglect either the real-time requirements or the load balance performance. An artificial immune system is a new intelligent problem-solving technique that is being used for particularly hard combinatorial optimization problems. Here, a task scheduling model of HCOW is introduced, and proposed is an adaptive immune-based algorithm （AIBA） for independent task scheduling on HCOW, which is based on clonal selection principle and affinity maturation mechanism of the immune response. In the AIBA, real-time performance of LPT algorithm and optimization qualities of AIS is assimilated by injection of antibody and dynamic computation of scheduling threshold （Th）. Simulations show that AIBA is able to map tasks onto machines so that a task＇s real-time requirements are satisfied and a more desirable load balance is also obtained. The new algorithm is more efficient than LPT and DGA.