Self-evolving Artificial Immune System via Developing T and B Cell for Permutation Flow-shop Scheduling Problems

Artificial Immune System is applied as a Heuristic Algorithm for decades. Nevertheless, many of these applications took advantage of the benefit of this algorithm but seldom proposed approaches for enhancing the efficiency. In this paper, a Self-evolving Artificial Immune System is proposed via developing the T and B cell in Immune System and built a self-evolving mechanism for the complexities of different problems. In this research, it focuses on enhancing the efficiency of Clonal selection which is responsible for producing Affinities to resist the invading of Antigens. T and B cell are the main mechanisms for Clonal Selection to produce different combinations of Antibodies. Therefore, the development of T and B cell will influence the efficiency of Clonal Selection for searching better solution. Furthermore, for better cooperation of the two cells, a co-evolutional strategy is applied to coordinate for more effective productions of Antibodies. This work finally adopts Flow-shop scheduling instances in OR-library to validate the proposed algorithm.

Authors:

• Pei-Chann Chang
• Wei-Hsiu Huang
• Ching-Jung Ting
• Hwei-Wen Luo
• Yu-Peng Yu

Keywords:

• Artificial Immune System
• Clonal Selection
• Flow-shop Scheduling Problems
• Co-evolutional strategy

References:

[1] F. Campelo, F. G. Guimar˜aes, and H. Igarashi, "Overview of Artificial
Immune Systems for Multi-objective Optimization," EMO 2007,
Lecture Notes in Computer Science, pp. 937-951, 2007.
[2] J. S. Chun, H. K. Jung and S. Y. Hahn, "A Study on Comparison of
Optimization Performances between Immune Algorithm and other
Heuristic Algorithms," IEEE Transactions on Magnetics, vol. 34, No.
5, September 1998.
[3] J. T. Tsai, W. H. Ho, and T. K. Liu, and J. H. Chou, "Improved immune
algorithm for global numerical optimization and job-shop scheduling
problems," Applied Mathematics and Computation 194 (2007) pp.
406-424, 2007.
[4] V. Cutello, G. Nicosia, M. Pavone, J. Timmis, "An Immune Algorithm
for Protein Structure Prediction on Lattice Models," IEEE Transactions
on Evolutionary Computation, vol. 11, no. 1, pp. 101-117, 2007.
[5] J. O. Kephart, "A biologically inspired immune system for computers,"
Proceedings of Artificial Life IV: The Fourth International Workshop
on the Synthesis and Simulation of Living Systems, MIT Press.
pp. 130-139, 1994.
[6] L. N. de Castro, J. Timmis, "Artificial Immune Systems: A New
Computational Intelligence Approach," Springer. pp. 57-58, 2002.
[7] C.A.C. Coello, N.C. Cortés, "Hybridizing A Genetic Algorithm with
An Artificial Immune System for Global Optimization," Engineering
Optimization, Volume 36, Number 5, pp. 607-634(28), 2004.
[8] J. D. Farmer, N. Packard, A. Perelson, "The immune system, adaptation
and machine learning," Physica D, vol. 2, pp. 187-204, 1986.
[9] H. Bersini, F. J. Varela, "Hints for adaptive problem solving gleaned
from immune networks," Parallel Problem Solving from Nature, vol.
496, pp. 343-354, 1991.
[10] P.C. Chang, S.H. Chen and K.L. Lin, " Two Phase Sub-Population
Genetic Algorithm for Parallel Machine Scheduling problem" Expert
Systems with Applications, vol. 29(3), pp. 705-712, 2005.
[11] S. H. Chen, "The Self-Guided Genetic Algorithm," PhD thesis, Yuan Ze
University, Taoyuan, 2008.
[12] D. Dasgupta (Editor), "Artificial Immune Systems and Their
Applications," Springer-Verlag, Inc. Berlin, January 1999.
[13] C. R. Reeves, "A Genetic Algorithm for Flowshop Sequencing,"
Computers and Operations Research, vol. 5, pp. 5-13, 1995.
[14] T. Bagchi, "Multiobjective Scheduling by Genetic Algorithms,"
Springer ,1999.
[15] K. Baker, "Introduction to sequencing and scheduling," Wiley, 1974.
[16] J. Framinan, J. Gupta, R. Leisten, "A review and classification of
heuristics for permutation flow-shop scheduling with makespan
objective," Journal of the Operational Research Society, vol. 55(12),
pp.1243-1255, 2004.
[17] D. Zheng, L. Wang, "An Effective Hybrid Heuristic for Flow Shop
Scheduling," The International Journal of Advanced Manufacturing
Technology, vol. 21(1), pp. 38-44, 2003.
[18] S. R. Hejazi, S. Saghafian, "Flowshop-scheduling problems with
makespan criterion: a review," International Journal of Production
Research, vol. 43(14), pp. 2895-2929, 2005.
[19] R. Ruiz, C. Maroto, "A comprehensive review and evaluation of
permutation flowshop heuristics," European Journal of Operational
Research, vol. 165(2), pp. 479-494, 2005.
[20] C. Reeves, T. Yamada, "Genetic Algorithms, Path Relinking, and the
Flowshop Sequencing Problem," Evolutionary Computation, vol. 6(1),
pp. 45-60, 1998.
[21] S. Iyer, B. Saxena, "Improved genetic algorithm for the permutation
flowshop scheduling problem," Computers and Operations Research,
vol. 31(4), pp. 593-606, 2004.
[22] X. Wang, T. C. E. Cheng, "A heuristic approach for tow-machine
no-wait flowshop scheduling with due dates and class setups,"
Computers and Operations Research, vol. 33(5), pp. 1326-1344, 2006.
[23] A. Jaszkiewicz, "Genetic local search for multi-objective combinatorial
optimization," European Journal of Operational Research, vol. 137(1),
pp. 50-71, 2002.
[24] H. Ishibuchi, T. Yoshida, T. Murata, "Balance between genetic search
and local search in memetic algorithms for multiobjective permutation
flowshop scheduling," Evolutionary Computation, IEEE Transactions
on vol. 7(2), pp. 204-223, 2003.
[25] T. Muruta, H. Ishibuchi, "Performance evolution of genetic algorithms
for flowshop scheduling problems," Proceedings of First IEEE
International Conference on Evolutionary Computation, 1994.
[26] C. L. Chen, R. V. Neppalli, N. Aljaber, "Genetic algorithms applied to
the continuous flow shop problem," Computers & Industrial
Engineering, vol. 30(4), pp. 919-929, 1996.
[27] P. C. Chang, J. C. Hsieh, C. H. Liu, "A case-injected genetic algorithm
for single machine scheduling problems with release time,"
International Journal of Production Economics, vol. 103(2), pp.
551-564, 2006.
[28] P. C. Chang, S. H. Chen, V. Mani, "Parametric Analysis of Bi-criterion
Single Machine Scheduling with a Learning Effect," International
Journal of Innovative Computing, Information and Control, vol. 4(8),
pp. 2033-2043, 2008.
[29] V. Cutello and G. Nicosia, "An Immunological Approach to
Combinatorial Optimization Problems," Lecture Notes in Computer
Science, Springer vol. 2527, pp. 361-370, 2002.
[30] L. N. de Castro and F. J. Von Zuben, "Artificial Immune Systems: Part
I -Basic Theory and Applications," School of Computing and Electrical
Engineering, State University of Campinas, Brazil, No. DCA-RT 01/99,
1999.
[31] J. H. Holland, "Genetic Algorithms and the Optimal Allocation of
Trials,". SIAM J. Comput, vol. 2(2), pp. 88-105, 1973.
[32] D. E. Goldberg, "Genetic Algorithms in Search, Optimization and
Machine Learning," Addison-Wesley, Reading, MA , 1989.