Abstract

Scheduling problems are difficult types of production arrangement problems that enumerated among NP-Complete problems. Some of evolutionary algorithms such as Genetic Algorithm, Ant Colony Optimization etc. have been used to solve this problem. In new years, Artificial Immune Algorithm is used to solve optimization problems such as routing and scheduling. One of complex scheduling problems is Job-shop Scheduling problem. In this article we use immune system concepts of human body, to implement a new artificial immune algorithm for solving Job-shop scheduling problem. A new population generation method was proposed based on G&T algorithm. We use two mutation methods, namely Shift Change method and Inverse method in Job-shop scheduling for first time. Moreover, we describe a vaccination method named MCV, to make maximum advance in solutions, and then achieve to more than one optimal solution concurrently and release from local optimum. Finally, we test our method on the very famous benchmark of JSP, namely FT06, then show experimental results and get some conclusions.

References

• Weijun, X. ; Zhiming, W. ; Wei, Zh. and Genke, Y. , 'A New Hybrid Optimization Algorithm for the Job-shop Scheduling Problem', American Control Conference, Boston, 2004
• Ma, J. ; Zhu,Y. and Shi, g. , 'Immune Genetic Algorithm for Flexible Job-shop Scheduling Problem', International Conference on Automation and Logistics, Hong Kong and Macau, IEEE, 2010
• Hart, E. ; Webb, A. ; Ross, P. and Lawson, A. 'A role for immunology in next generation robot controllers'. In Artificial Immune Systems: Proceedings of ICARIS 2003, pages 46–57, Springer, 2003
• Taylor, D. and Corne, D. 'An investigation into negative selection algorithm for fault detction in refrigeration systems'. In Artificial Immune Systems: Proceedings of ICARIS 2003, pages 34–45. Springer, 2003
• Wu, J. Y. : Artificial immune system for solving constrained global optimization problems. In: Artificial Life 2007, ALIFE 2007, Honolulu, HI, pp. 92–99, 2007
• Neal, M. 'Meta-stable memory in an artificial immune network'. In Artificial Immune Systems: Proceedings of ICARIS 2003, pages 168–181, Springer, 2003
• Yaqin, Zh. ; Beizhi, L. ; Jianguo, Y. and Qingxia,W. , 'An Immune Algorithm For Batch Job-Shop Scheduling With Multi-Objectives', International Technology and Innovation Conference, 2006
• Musilek, P. ; Lau, A. ; Reformat, M. and Wyard-Scott, L. , 'Immune programming', Journal on Information Sciences, Elsevier, 2005
• Tsai, J. T. ; Ho, W. H. ; Liu, T. K. and Chou, J. H. ,'Improved immune algorithm for global numerical optimization and job-shop scheduling problems', Apples Mathematics and Computation Conference, pp. 406-424,Elsevier, 2007
• Darmoul, S. ; Pierreval, H. and Gabouj, S. H. , 'Scheduling Using Artificial Immune System Metaphors: A Review', IEEE, 2006
• Hart, E. ; Timmis, J. , 'Application Areas of AIS:The Past, The Present and The Future', ICARIS2005, pp. 483-497, Springer, 2005
• Zhang, R. and Wu, Ch. , 'A Hybrid Immune Simulated Annealing Algorithm for the Job Shop Scheduling Problem', Journal of Applied Soft Computing, pp. 79-89, Elsevier, 2010
• Murata, T and Ishibuchi, H. , 'Performance Evaluation of Genetic Algorithms for Flowshop Scheduling Problems', IEEE, 1994
• Bondal, Akshata A. , 'Artificial Immune Systems Applied to Job Shop Scheduling', A thesis presented to the faculty of the Russ College of Engineering and Technology of Ohio University, 2008
• Bernandino, H. S. , Barbosa, H. J. C. , 'Artificial Immune Systems for Optimization', Nature-Inspired Algorithms for Optimisation, pp. 389–411, Springer, 2009
• Hart, E. , Ross, P. , 'An Immune System Approach to Scheduling in Changing Environments', Genetic and Evolutionary Computation Conference - GECCO 1999, Orlando, Florida, USA, pp. 1559-1565, 1999
• Aickelin, U. ; Burke, E. and Mohamed Din, A. , 'Investigating Artificial Immune Systems For Job Shop Rescheduling In Changing Environments', Poster Proceeding of ACDM, 2004
• Coello Coello, Carlos A. ; Daniel Cortés Rivas and Nareli Cruz-Cortés, 'Job Shop Scheduling using the Clonal Selection Principle', ACDM 2004, Springer, Bristol, U. K. , 2004
• Xu, X. ; Wang, W. and Guan, Q. , 'Adaptive Immune Algorithm for Solving Job-Shop Scheduling Problem', ICNC 2005, LNCS 3611, pp. 795 – 799, Springer-Verlag, 2005
• Zuo, X. Q. , Fan Y. Sh. , 'Solving The Job Shop Scheduling Problem By An Immune Algorithm', International Conference on Machine Learning and Cybernetics, IEEE, 2005
• Ge, H. W. ; Sun, L. and Liang, Y. Ch. , 'Solving Job-Shop Scheduling Problems by a Novel Artificial Immune System', Conference on Artificial Intellignce, LNAI 3809, pp. 839 – 842, Springer-Verlag, 2005
• Luh, G. Ch. and Chueh, Ch. H. , 'A Multi-Modal Immune Algorithm for the Job-Shop Scheduling Problem', Journal of Information Science, pp. 1516-1532, Elsevier, 2009
• Hong, Lu, 'A Novel Artificial Immune Algorithm for Job Shop Scheduling', International Conference on Computational Intelligence and Natural Computing, IEEE, 2009
• Wei, Q; Qiaoyun, L; Chuanbao, J. and Jie, S. , 'Immune Genetic Algorithm and Its Application on Job Shop Scheduling', International Workshop on Education Technology and Computer Science, IEEE, 2010
• Yagmahan, B. and Yenisey, M. M. , 'Scheduling Practice and Recent Developments in Flow Shop and Job Shop Scheduling', Computational Intelligence in Flow Shop and Job Shop Scheduling, pp. 261-300, Springer, 2009
• Bagheri, A. ; Zandieh, M. ; Mahdavi, I. ; Yazdani, M. , 'An artificial immune algorithm for the flexible job-shop scheduling problem', Journal of Future Generation Computer Systems, pp. 533-541, Elsevier, 2010
• Watson, J. P. , 'Empirical Modeling and Analysis of Local Search Algorithm for the Job-Shop Scheduling Problem', Chapter2, Ph. D. Dissertation, 2003
• Yaqin, Zh. ; Beizhi, L. ; Jianguo, Y. and Qingxia,W. , 'Study on Modeling of Job Shop Scheduling with Multi-resource Constraints', International Conference on Artificial Intelligence and Computational Intelligence, pp. 313-317, IEEE, 2010
• Yang, J. ; Gong, M. ; Jiao, L. and Zhang, L. , 'Improved Clonal Selection Algorithm Based on Lamarckian Local Search Technique', Congress on Evolutionary Computation, IEEE, 2008
• Pongchareon, P. ; Chainate, W. and Pongchareon, S. ,'Improving Artificial Immune System Performance: Inductive Bias and Alternative Mutations', ICARIS 2008, pp. 220-231, Springer, 2008
• Jiao L. ; Wang L. , 'A Novel Genetic Algorithm Based on Immunity', transactions on systems, man, and cybernetcis-part A:systems and humans, Vol. 30, No. 5, IEEE, 2000
• Giffler, B. and Thompson, G. ; 'Algorithms for solving production scheduling problems'; operation research, Vol. 8, pp. 487-503, 1960
• Yang, Sh. , 'An improved adaptive neural network for job-shop scheduling', in proceeding of International conference of IEEE, pp. 1200-1205, 2005
• Murugesan, R. and Sivasakthi, K. , 'Positive Selection Based Modified Clonal Selection Algorithm for Solving Job Shop Scheduling Problem', Applied Mathematical Sciences, Vol. 6, No. 46, PP. 2255 - 2271, 2012