INTRODUCTION
The flow shop sequencing problem is a production planning problem: N jobs have to be processed in the same sequence on M machines; the processing time of job i on machine j is given by t_{i,j}(i = 1…N, j = 1…M). These times are fixed, non negative and some of them may be zero if some job is not processed on a machine. The flos shop sequencing problems are studied and developed deeply in recent years (Allahverdi, 2000).
Metaheuristic algorithms are recently widely used to solve the flow shop sequencing problem (Burdett and Kozan, 2000; Pelikan and Goldberg, 2002), especially in some difficulty problems that can’t be solved using traditional methods. The Artificial Immune Algorithm is developed on Somatic Theory (Dasgupta and AttohOkine, 1997) and Network Hypothesis (Chun, 1997). 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 job processing sequence; the fitness function is designed as the reciprocal of maximal flow time. New antibodies are produced by adopting the partially matched crossover operator and mutation operator permuted by job sequence. The promotion and suppression of antibodies are adjusted according to antibody affinity that is obtained from the maximal affinity value among antibodies.
MATHEMATICAL DESCRIPTION OF PERMUTATION FLOW SHOP SEQUENCING
The problem consists of minimizing the time and/or the costs between the beginning
of the execution of the first job on the first machine and the finishing of
the execution of the last job on the last machine. In this research the problem
of minimizing the time of sequencing constructs the objective function (Garey
et al., 1976).
For this problem the following assumptions are made (Tailland, 1990):
• 
Every job has to be processed at most once on machine 1, 2…m
(in this order). 
• 
Every machine processes only one job at a time. 
• 
Every job is processed at most on one machine at a time. 
• 
The operations are not preemptable. 
• 
The setup times of the operations are included in the processing
time and do not depend on the sequence. 
• 
The operating sequences of the jobs are the same on every machine and
the common sequence has to be determined. 
This problem is NPhard and can be solved exactly only for small sizes. It
consists of finding a sequence σ that minimizes the makespan M(σ).
So the number of possible schedules is n!.
Suppose b_{i,j} is the beginning time of job i on machine j, f_{i,j}
is the finishing time of job i on machine j. The mathematical model for the
flow shop sequencing problem can be described as follow:
s.t.
where, i = 1,2,…,N; j = 1,2,…,M.
In the above mathematical models, Eq. 1 means the beginning
time b_{i,j} of job i on machine j is the maximum of the finishing time
f_{i,j1} of job i on machine j1 and the finishing time f_{i1,j}
of job i1 on machine j; Eq. 2 means the finishing time f_{i,j}
is the summation of the beginning time b_{i,j} and processing time t_{i,j}
of of job i on machine j; Eq. 3 means minimizing the finishing
time f_{N,M} of last job N on last machine M; Eq. 4
means the beginning of job i on machine j can not perform until the finishing
of job i on machine j1; Eq. 5 means the beginning of job
i on machine j can not perform until the finishing of job i1 on machine j.
THE ARTIFICIAL IMMUNE ALGORITHM
The immune algorithm selects thickness and affinity as the optimality criterions
of individuals and accordingly reproduces the individuals that have small thickness
and large fitness. The algorithm increases the ability to fight premature by
calculating individuals’ multiplicities. The flow of Artificial Immune
Algorithm can be described as:
Algorithm: AIA
Generation of antibodies initialization: The immune system distinguishes
invading of antibodies, which corresponding to the input data of the optimization
problem. The objective function Eq. 3 is the antibodies of
immune algorithm in flow shop sequencing problem. The constraint condition has
been given in Eq. 4 and 5.
The initialization antibodies were given by generating N antibodies randomly, where N is the population size and it is fixed equal to the number of jobs. The jobs were encoding by nature number (1, 2, …, N). One random arrangement of N jobs forms one antibody, which denotes one solution of flow shop sequencing. The maximum value of N is 600 in this study.
Proliferation of antibodies population: The antibody population crossover and mutate according to their corresponding probability P_{c} and P_{m} and generate new antibodies. The population (N’ antibodies) which has been expanded is called proliferate antibody population. New individual was selected using proportion selecting method. Meanwhile the best individual was kept, which can speed up the searching process. Portion Match Crossover (PMX) was used with crossover probability P_{c} = 0.8. Jobs sequencing interchange was used with mutate probability P_{m} = 0.04.
Calculate fitness function value of antibodies: The fitness function
is designed as the reciprocal of the maximum processing time f^{k}_{max},
where f^{k}_{max} denotes the maximum processing time of k antibodies.
Without lose of generality, suppose {S_{1}, S_{2}, …, S_{N}}
be the sequencing order of jobs, the finishing time of N jobs on M machines
flow shop sequencing problem can be calculated by:
where, i = 2, 3, …, N; j = 2, 3, …, M. The maximum processing time f^{k}_{max}
and the fitness function value g(k) can be calculated separately:
Calculation of antibodies affinity: Entropy is the measure of information
and uncertainty of a random variable. Formally, if X is a random variable, S(X)
the set of values that X can take and p(x) the probability function of X, the
entropy E(X) is defined as shown in Eq. 9 (Barbara et al.,
2002).
Inspired by the theory, we can calculate the affinity ay_{v,w}(v, w
= 1, 2, …, N’) between antibodies v and w to express the similarity between
them. In the N’ antibodies composed by U genes, the information entropy
on position j is:
where, P_{i}(j) is the allele probability on position j(As shown in
Fig. 1, k_{s} = 0 or 1. l = 2 if binary encoding
was used). The information entropy of whole population can be calculated by
Eq. 11. The affinity ay_{v,w} between antibodies
v and w can be calculated by Eq. 12. The value ay_{v,w}
is not the same for all pairs (v,w), it depends on actual antibodies. U is gene
numbers of antibody, as shown in Fig. 1.
The affinity between antibody v and antigen is given in Eq.
13. The objective function should take minimum value in flow shop sequencing,
so opt_{v} = obj, obj has been given in Eq. 3.
Promotion and suppression of antibodies: The promotion and suppression
of antibodies are adjusted according to antibody concentration that is obtained
from the maximal affinity value among antibodies. Get rid of the antibodies
whose value of ax_{v} (v = 1, 2, …, N) less than T(As shown in Eq.
14), where T is the least affinity between antibodies of parent population
and antigen.
The antibodies with maximal thickness were eliminated in turn until N antibodies
left. Antibody thickness C_{v} can be calculated by Eq.
(15).
where max ay_{v,w} is the maximal affinity between antibody v and others;
λ is the modify condition of thickness, range from 0.8 to 1. λ = 0.85
was selected in the study.

Fig. 1: 
Information entropy of immune population allele 
Judgment of stopping criterion: The antibodies having maximal affinity
with antigen was put into memory cell to improve the efficiency of solution.
Judge whether iterative stopping criterion I is satisfied or not. The stopping criterion I is the maximal iterative number of fitness function. If the iterative number less than I, then the processing go back to process 3.3, otherwise stop the iteration.
The antibody with maximal affinity between antigen and the latest memory cell was selected as optimal solution.
RESULTS
The flow shop Benchmark problems brought forward by Tailland (1993) was used
in the study. N = 10, 20, 50, 100 and M = 10, 20, So there are eight combinations
of N and M(10x10, 10x20, 20x10, 20x20, 50x10, 50x20, 100x10, 100x20). These
test cases were used to validate the effectiveness of AIA used in flow shop
sequencing. The performance of algorithm was present by η:
where σ^{H} is the sequencing of Simulated Annealing suggested
by Osman and Potts (1989), Genetic Algorithm suggested by Reeves (1995) and
the Artificial Immune Algorithm in the study. σ^{B} is the optimal
sequencing of solution. The initialized parameters were generated using NEH
algorithm (Nawaz et al., 1983). The parameters of GA are: S = 40, P_{c}
= 0.8 and P_{m} = 0.04. The parameters of AIA are the same with GA except
the modify coefficient of antibody thickness λ = 0.85. The initial temperature
is set to 500 for SA. The machine used for testing is HP Workstation (Pentium4
2.4G CPU, 512M memory). The results were shown in Fig. 2 and
3. The datum is the average value of twenty executions in
each case.
It’s clearly; the AIA is superior to the SA of Osman and GA of Reeves
in the performance of searching for optimal solution and the running time is
less than the two latter algorithms especially in the large scale combinations
of N and M.

Fig. 2: 
Running times of three algorithms under eight combinations
of N and M 

Fig. 3: 
Performances of three algorithms under eight combinations
of N and M 

Fig. 4: 
Running times of three algorithms under ten complex combinations
of N and M 

Fig. 5: 
Performances of three algorithms under ten complex combinations
of N and M 
To validate the performance of AIA in solving the large scale problems, ten
No. x 3 problems used by Tailland (1990) were also performed, where the number
of jobs are N = 150, 200, 250, 300, 350, 400, 450, 500, 550 and 660. The experimental
results are shown in Fig. 4 and 5. We can
see the performance of AIA is superior to the other two obviously.
CONCLUSIONS
A novel algorithm, Artificial Immune Algorithm is proposed in this research to efficiently deal with flow shop sequencing problems. The algorithm is inspired by the immune system of human to simulate the process of the interaction between antigens, antibodies and memory cells. The proposed algorithm is tested on flow shop sequencing problem benchmarks. Experimental results show that immune algorithm is quite flexible with satisfactory results and require fewer running time than Genetic Algorithms and Simulated Annealing.
ACKNOWLEDGMENTS
The authors would like to thank the anonymous reviewers for their careful reading of this paper and for their helpful and constructive comments. This work was supported in part by the Defence PreResearch project of China under grant No. 51315050105 and the Defence Foundation of China under grant No. 9140A15050206DZ01.