CFP last date
20 December 2024
Call for Paper
January Edition
IJCA solicits high quality original research papers for the upcoming January edition of the journal. The last date of research paper submission is 20 December 2024

Submit your paper
Know more
The week's pick
Responsive image
Improved Shuffled Frog Leaping Algorithm with Self-Adaptive Shuffling for Fuzzy Logic PD+G Controller Optimization in Robotic Manipulators

Duc Hoang Nguyen
Random Articles
Reseach Article

A Novel Artificial Immune Algorithm for Solving the Job Shop Scheduling Problem

by Mohsen Afshari, Hedieh Sajedi
journal cover thumbnail

International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 48 - Number 14
Year of Publication: 2012
Authors: Mohsen Afshari, Hedieh Sajedi
10.5120/7420-0464

Mohsen Afshari, Hedieh Sajedi . A Novel Artificial Immune Algorithm for Solving the Job Shop Scheduling Problem. International Journal of Computer Applications. 48, 14 ( June 2012), 46-53. DOI=10.5120/7420-0464

@article{ 10.5120/7420-0464,
author = { Mohsen Afshari, Hedieh Sajedi },
title = { A Novel Artificial Immune Algorithm for Solving the Job Shop Scheduling Problem },
journal = { International Journal of Computer Applications },
issue_date = { June 2012 },
volume = { 48 },
number = { 14 },
month = { June },
year = { 2012 },
issn = { 0975-8887 },
pages = { 46-53 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume48/number14/7420-0464/ },
doi = { 10.5120/7420-0464 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T20:44:05.739938+05:30
%A Mohsen Afshari
%A Hedieh Sajedi
%T A Novel Artificial Immune Algorithm for Solving the Job Shop Scheduling Problem
%J International Journal of Computer Applications
%@ 0975-8887
%V 48
%N 14
%P 46-53
%D 2012
%I Foundation of Computer Science (FCS), NY, USA
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
  1. 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
  2. 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
  3. 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
  4. 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
  5. Wu, J. Y. : Artificial immune system for solving constrained global optimization problems. In: Artificial Life 2007, ALIFE 2007, Honolulu, HI, pp. 92–99, 2007
  6. Neal, M. 'Meta-stable memory in an artificial immune network'. In Artificial Immune Systems: Proceedings of ICARIS 2003, pages 168–181, Springer, 2003
  7. 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
  8. Musilek, P. ; Lau, A. ; Reformat, M. and Wyard-Scott, L. , 'Immune programming', Journal on Information Sciences, Elsevier, 2005
  9. 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
  10. Darmoul, S. ; Pierreval, H. and Gabouj, S. H. , 'Scheduling Using Artificial Immune System Metaphors: A Review', IEEE, 2006
  11. Hart, E. ; Timmis, J. , 'Application Areas of AIS:The Past, The Present and The Future', ICARIS2005, pp. 483-497, Springer, 2005
  12. 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
  13. Murata, T and Ishibuchi, H. , 'Performance Evaluation of Genetic Algorithms for Flowshop Scheduling Problems', IEEE, 1994
  14. 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
  15. Bernandino, H. S. , Barbosa, H. J. C. , 'Artificial Immune Systems for Optimization', Nature-Inspired Algorithms for Optimisation, pp. 389–411, Springer, 2009
  16. 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
  17. Aickelin, U. ; Burke, E. and Mohamed Din, A. , 'Investigating Artificial Immune Systems For Job Shop Rescheduling In Changing Environments', Poster Proceeding of ACDM, 2004
  18. 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
  19. 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
  20. 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
  21. 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
  22. 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
  23. Hong, Lu, 'A Novel Artificial Immune Algorithm for Job Shop Scheduling', International Conference on Computational Intelligence and Natural Computing, IEEE, 2009
  24. 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
  25. 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
  26. 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
  27. Watson, J. P. , 'Empirical Modeling and Analysis of Local Search Algorithm for the Job-Shop Scheduling Problem', Chapter2, Ph. D. Dissertation, 2003
  28. 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
  29. 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
  30. Pongchareon, P. ; Chainate, W. and Pongchareon, S. ,'Improving Artificial Immune System Performance: Inductive Bias and Alternative Mutations', ICARIS 2008, pp. 220-231, Springer, 2008
  31. 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
  32. Giffler, B. and Thompson, G. ; 'Algorithms for solving production scheduling problems'; operation research, Vol. 8, pp. 487-503, 1960
  33. Yang, Sh. , 'An improved adaptive neural network for job-shop scheduling', in proceeding of International conference of IEEE, pp. 1200-1205, 2005
  34. 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
Index Terms

Computer Science
Information Sciences

Keywords

Artificial Immune System Job-shop Scheduling Problem Mutation Vaccination Receptor Editing Clonal Selection

Powered by PhDFocusTM