改进免疫算法在Flow Shop调度上的应用  

Application of a Modified Immune Algorithm to Flow Shop Scheduling Problem

作　　者：肖力[1] 

机构地区：[1]鄂州大学计算机系,湖北鄂州436000

出　　处：《计算机仿真》2008年第3期192-194,238,共4页Computer Simulation

基　　金：鄂州大学科学研究基金(20060005)

摘　　要：为了高效地解决Flow Shop问题,提出了一种利用免疫算法求解Flow Shop调度问题的方法。该算法是根据人或者其它高等动物的免疫系统机理设计的,将调度目标和约束条件作为抗原,将问题的解作为抗体,对抗体采用按工件加工顺序进行自然数编码,并把最大流程时间的倒数作为适应度函数,通过引入隔离小生境等技术提高了免疫算法的适应能力,保证了种群的多样性,克服了早熟收敛,提高了收敛速度。通过对Flow Shop问题的基准测试表明,该算法不仅在求解问题的规模上具有很好的可伸缩性,而且在运算时间上也低于禁忌搜索算法和模拟退火算法,从而验证了该算法的有效性。To efficiently deal with flow- shop scheduling problems, a novel algorithm, namely artifieial immune algorithm is proposed which is inspired by the immune system of human and other mammals to simulate the process of the interaction among antigens, antibodies and lymphoeytes. The implementation of the artificial immune algorithm on flow shop problems is as follows. The objective function and the part of inequality constraints serve as antigens and solutions serve as antibodies; the antibodies are encoded as natural number consistent with work piece processing sequence; the fitness function is designed as the inversion of mammal flow time. The proposed algorithm is tested on scheduling problem enehmarks. Experimental results show that the immune algorithm is quite flexible with satisfactory results,and requires less running time than Taboo searches and simulated anneal algorithms.

关 键 词：免疫算法 流水生产调度 抗原 抗体 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]