Subscribe Now Subscribe Today
Research Article
 

Improved Artificial Immune Algorithm and its application on the Permutation Flow Shop Sequencing Problems



Haichang Gao and Xiyang Liu
 
Facebook Twitter Digg Reddit Linkedin StumbleUpon E-mail
ABSTRACT

Flow shop sequencing is one of the most well-known production scheduling problems and a typical NP-hard combinatorial optimization problem with strong engineering background. To efficiently deal with permutation flow shop sequencing problems, a novel algorithm, Artificial Immune Algorithm (AIA) is proposed which is inspired by the immune system of human to simulate the process of the interaction between antigens, antibodies and memory cells. The algorithm is tested on some benchmarks. Experimental results show AIA is quite flexible with satisfactory results and require fewer running time than Genetic Algorithms and Simulated Annealing.

Services
Related Articles in ASCI
Search in Google Scholar
View Citation
Report Citation

 
  How to cite this article:

Haichang Gao and Xiyang Liu, 2007. Improved Artificial Immune Algorithm and its application on the Permutation Flow Shop Sequencing Problems. Information Technology Journal, 6: 929-933.

DOI: 10.3923/itj.2007.929.933

URL: https://scialert.net/abstract/?doi=itj.2007.929.933

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 ti,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).

Meta-heuristic 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 Attoh-Okine, 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 set-up 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 NP-hard 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 bi,j is the beginning time of job i on machine j, fi,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:

Image for - Improved Artificial Immune Algorithm and its application on the Permutation Flow Shop Sequencing Problems
(1)

Image for - Improved Artificial Immune Algorithm and its application on the Permutation Flow Shop Sequencing Problems
(2)

Image for - Improved Artificial Immune Algorithm and its application on the Permutation Flow Shop Sequencing Problems
(3)

s.t.

Image for - Improved Artificial Immune Algorithm and its application on the Permutation Flow Shop Sequencing Problems
(4)

Image for - Improved Artificial Immune Algorithm and its application on the Permutation Flow Shop Sequencing Problems
(5)

where, i = 1,2,…,N; j = 1,2,…,M.

In the above mathematical models, Eq. 1 means the beginning time bi,j of job i on machine j is the maximum of the finishing time fi,j-1 of job i on machine j-1 and the finishing time fi-1,j of job i-1 on machine j; Eq. 2 means the finishing time fi,j is the summation of the beginning time bi,j and processing time ti,j of of job i on machine j; Eq. 3 means minimizing the finishing time fN,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 j-1; Eq. 5 means the beginning of job i on machine j can not perform until the finishing of job i-1 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

Image for - Improved Artificial Immune Algorithm and its application on the Permutation Flow Shop Sequencing Problems

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 Pc and Pm 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 Pc = 0.8. Jobs sequencing interchange was used with mutate probability Pm = 0.04.

Calculate fitness function value of antibodies: The fitness function is designed as the reciprocal of the maximum processing time fkmax, where fkmax denotes the maximum processing time of k antibodies. Without lose of generality, suppose {S1, S2, …, SN} be the sequencing order of jobs, the finishing time of N jobs on M machines flow shop sequencing problem can be calculated by:

Image for - Improved Artificial Immune Algorithm and its application on the Permutation Flow Shop Sequencing Problems
(6)

where, i = 2, 3, …, N; j = 2, 3, …, M. The maximum processing time fkmax and the fitness function value g(k) can be calculated separately:

Image for - Improved Artificial Immune Algorithm and its application on the Permutation Flow Shop Sequencing Problems
(7)

Image for - Improved Artificial Immune Algorithm and its application on the Permutation Flow Shop Sequencing Problems
(8)

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).

Image for - Improved Artificial Immune Algorithm and its application on the Permutation Flow Shop Sequencing Problems
(9)

Inspired by the theory, we can calculate the affinity ayv,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:

Image for - Improved Artificial Immune Algorithm and its application on the Permutation Flow Shop Sequencing Problems
(10)

where, Pi(j) is the allele probability on position j(As shown in Fig. 1, ks = 0 or 1. l = 2 if binary encoding was used). The information entropy of whole population can be calculated by Eq. 11. The affinity ayv,w between antibodies v and w can be calculated by Eq. 12. The value ayv,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.

Image for - Improved Artificial Immune Algorithm and its application on the Permutation Flow Shop Sequencing Problems
(11)

Image for - Improved Artificial Immune Algorithm and its application on the Permutation Flow Shop Sequencing Problems
(12)

The affinity between antibody v and antigen is given in Eq. 13. The objective function should take minimum value in flow shop sequencing, so optv = obj, obj has been given in Eq. 3.

Image for - Improved Artificial Immune Algorithm and its application on the Permutation Flow Shop Sequencing Problems
(13)

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 axv (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.

Image for - Improved Artificial Immune Algorithm and its application on the Permutation Flow Shop Sequencing Problems
(14)

The antibodies with maximal thickness were eliminated in turn until N antibodies left. Antibody thickness Cv can be calculated by Eq. (15).

Image for - Improved Artificial Immune Algorithm and its application on the Permutation Flow Shop Sequencing Problems
(15)

where max ayv,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.

Image for - Improved Artificial Immune Algorithm and its application on the Permutation Flow Shop Sequencing Problems
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 η:

Image for - Improved Artificial Immune Algorithm and its application on the Permutation Flow Shop Sequencing Problems
(16)

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, Pc = 0.8 and Pm = 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 (Pentium-4 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.

Image for - Improved Artificial Immune Algorithm and its application on the Permutation Flow Shop Sequencing Problems
Fig. 2: Running times of three algorithms under eight combinations of N and M

Image for - Improved Artificial Immune Algorithm and its application on the Permutation Flow Shop Sequencing Problems
Fig. 3: Performances of three algorithms under eight combinations of N and M

Image for - Improved Artificial Immune Algorithm and its application on the Permutation Flow Shop Sequencing Problems
Fig. 4: Running times of three algorithms under ten complex combinations of N and M

Image for - Improved Artificial Immune Algorithm and its application on the Permutation Flow Shop Sequencing Problems
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 Pre-Research project of China under grant No. 51315050105 and the Defence Foundation of China under grant No. 9140A15050206DZ01.

REFERENCES

1:  Allahverdi, A., 2000. Minimizing mean flow time in a two-machine flowshop with sequence-independent setup times. Comput. Operat. Res., 27: 111-127.
Direct Link  |  

2:  Barbara, D., J. Couto and Y. Li, 2002. COOLCAT: An entropy-based algorithm for clustering. Proceedings of the 11th International Conference on Information and Knowledge Management, November 4-9, 2002, McLean, Virginia, USA., pp: 582-589

3:  Burdett, R.L. and E. Kozan, 2000. Evolutionary algorithms for flowshop sequencing with non-unique jobs. Int. Trans. Opeeat. Res., 7: 401-418.
Direct Link  |  

4:  Chun, J.S., 1997. Optimal design of synchronous motor with parameter correction using immune algorithm. Proceedings of the International Electric Machines and Drives Conference, May 18-21, 1997, Milwaukee, WI., USA., pp: TB2/2.1-TB2/2.3

5:  Dasgupta, D. and N. Attoh-Okine, 1997. Immunity-based system: A survey. Proceedings of the International Conference on System, Man and Cybernetics, October 12-15, 1997, Orlando, FL., USA., pp: 869-874

6:  Garey, M.R., D.S. Johnson and R. Sethi, 1976. The complexity of flow shop and job shop scheduleing. Math. Operat. Res., 1: 117-129.
CrossRef  |  

7:  Nawaz, M., E. Enscore Jr. and I. Ham, 1983. A heuristic algorithms for the m-machine n-job flow-shop sequencing problem. Omega. Int. J. Manage. Sci., 11: 91-95.

8:  Osman, I. and C. Potts, 1989. Simulated annealing for permutation flowshop scheduling. Omega, 17: 551-557.
CrossRef  |  Direct Link  |  

9:  Pelikan, M. and D.E. Goldberg, 2002. A survey of optimization by building and using probabilistic models. Comput. Optimizat. Appl., 21: 5-20.
Direct Link  |  

10:  Reeves, C.R., 1995. A genetic algorithms for flow shop sequencing. Comput. Operat. Res., 22: 5-13.
Direct Link  |  

11:  Taillard, E.D., 1990. Some efficient heuristic methods for the flow shop sequencing problem. Eur. J. Operat. Res., 47: 65-74.
CrossRef  |  Direct Link  |  

12:  Taillard, E., 1993. Benchmarks for basic scheduling problems. Eur. J. Operat. Res., 47: 278-285.
CrossRef  |  Direct Link  |  

©  2021 Science Alert. All Rights Reserved