车间流程的免疫调度算法

为了高效地解决车间流程(Flow Shop)问题,提出了一种利用免疫算法求解Flow Shop调度问题的方法.该算法是根据人或者其他高等动物的免疫系统机理设计的,将调度目标和约束条件作为抗原,将问题的解作为抗体,对抗体采用按工件加工顺序进行自然数编码,并把最大流程时间的倒数作为适应度函数,新抗体的繁殖是通过部分匹配交叉算子和按工件顺序互换的变异算子实现的,对抗体产生的刺激和抑制通过抗体浓度来调节,而抗体浓度通过计算抗体之间的最大亲和力获得.通过对Flow Shop问题的基准测试表明,该算法不仅在求解问题的规模上具有很好的可伸缩性,而且在运算时间上也低于遗传算法和模拟退火算法.

Artificial Immune Algorithm for Flow-Shop Scheduling

To efficiently deal with flow-shop scheduling problems, a novel algorithm, artifical immune algorithm is proposed which is inspired by the immune system of human and other mammals to simulate the process of the interaction between antigens, antibodies and lymphocytes. The implement of the artifical 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 that is consistent with workpiece processing sequence; the fitness function is designed as the inversion of maximal flow time. New antibodies are produced by adopting the partially matched crossover operator and mutation operator permuted by work-pieces sequence. The promotion and suppression of antibodies are adjusted according to antibody concentration that is obtained from the maximal affinity value among antibodies. The proposed algorithm is tested on scheduling problem benchmarks. Experimental results show that immune algorithm is quite flexible with satisfactory results, and requires fewer ruuning time than genetic and simulated anneal algorithms.