Abstract
A static job shop scheduling problem (JSSP) is a class of JSSP which is a combinatorial optimization problem with the assumption of no disruptions and previously known knowledge about the jobs and machines. A new hybrid algorithm based on artificial immune systems (AIS) and particle swarm optimization (PSO) theory is proposed for this problem with the objective of makespan minimization. AIS is a metaheuristics inspired by the human immune system. Its two theories, namely, clonal selection and immune network theory, are integrated with PSO in this research. The clonal selection theory builds up the framework of the algorithm which consists of selection, cloning, hypermutation, memory cells extraction and receptor editing processes. Immune network theory increases the diversity of antibody set which represents the solution repertoire. To improve the antibody hypermutation process to accelerate the search procedure, a modified version of PSO is inserted. This proposed algorithm is tested on 25 benchmark problems of different sizes. The results demonstrate the effectiveness of the PSO algorithm and the specific memory cells extraction process which is one of the key features of AIS theory. By comparing with other popular approaches reported in existing literatures, this algorithm shows great competitiveness and potential, especially for small size problems in terms of computation time.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Adams J., Balas E., Zawack D. (1988) The shifting bottleneck procedure for job shop scheduling. Management Science 34(3): 391–401
Aydin I., Karakose M., Akin E. (2010) An adaptive artificial immune system for fault classification. Journal of Intelligent Manufacturing 23(5): 1489–1499
Aydin M. E., Fogarty T. C. (2004) A simulated annealing algorithm for multi-agent systems: A job-shop scheduling application. Journal of Intelligent Manufacturing 15(6): 805–814
Baker K. (1974) Introduction to sequencing and scheduling. Wiley, New York
Beasley J. (1990) OR-library: Distributing test problems by electronic mail. The Journal of the Operational Research Society 41(11): 1069–1072
Binato S., Hery W. J., Loewenstern D. M., Resende M. G. C. (2002) A GRASP for job shop scheduling. Essays and Surveys in Metaheuristics 15: 59–79
Brucker P., Jurisch B., Sievers B. (1994) A branch-and-bound algorithm for the job-shop scheduling problem. Discrete Applied Mathematics 49(1–3): 107–127
Carlier J., Pinson E. (1989) An algorithm for solving the job-shop problem. Management Science 35(2): 164–176
Chandrasekaran M., Asokan P., Kumanan S., Balamurugan T., Nickolas S. (2006) Solving job shop scheduling problems using artificial immune system. International Journal of Advanced Manufacturing Technology 31(5–6): 580–593
Coello C. A. C., Rivera D. C., Cortes N. C. (2003) Use of an artificial immune system for job shop scheduling. Proceedings of the Second International Conference of Artificial Immune Systems 2787: 1–10
Dasgupta D., Yu S., Nino F. (2011) Recent advances in artificial immune systems: Models and applications. Applied Soft Computing 11(2): 1574–1587
de Castro L. N., Timmis J. (2002) Artificial immune systems: A new computational intelligence approach. Springer, New York
Eswaramurthy V. P., Tamilarasi A. (2009) Hybridizing tabu search with ant colony optimization for solving job shop scheduling problems. International Journal of Advanced Manufacturing Technology 40(9–10): 1004–1015
Ge H. W., Sun L., Liang Y. C., Qian F. (2008) An effective PSO and AIS-based hybrid intelligent algorithm for job-shop scheduling. IEEE Transactions on Systems Man and Cybernetics Part a-Systems and Humans 38(2): 358–368
Geyik F., Cedimoglu I. H. (2004) The strategies and parameters of tabu search for job-shop scheduling. Journal of Intelligent Manufacturing 15(4): 439–448
Girish B. S., Jawahar N. (2009) Scheduling job shop associated with multiple routings with genetic and ant colony heuristics. International Journal of Production Research 47(14): 3891–3917
Glover F., Greenberg H. J. (1989) New approaches for heuristic-search—a bilateral linkage with artificial-intelligence. European Journal of Operational Research 39(2): 119–130
González, M. A., Vela, C. R., González-Rodríguez, I., & Varela, R. (2012). Lateness minimization with Tabu search for job shop scheduling problem with sequence dependent setup times. Journal of Intelligent Manufacturing. doi:10.1007/s10845-011-0622-5.
Hart E., Timmis J. (2008) Application areas of AIS: The past, the present and the future. Applied Soft Computing 8(1): 191–201
Jain A., Meeran S. (1999) A state-of-the-art review of job-shop scheduling techniques. European Journal of Operations Research 113(2): 390–434
Jerne N. K. (1974) Towards a network theory of the immune system. Ann Immunol 125(1–2): 373–389
Kahraman C., Engin O., Yilmaz M. K. (2009) A new artificial immune system algorithm for multiobjective fuzzy flow shop. International Journal of Computational Intelligence Systems 2(3): 236–247
Kennedy J., Eberhart R. (1995) Particle swarm optimization. IEEE International conference on Neural Network 4: 1942–1948
Lageweg B. J., Lenstra J. K., Rinnooy Kan A. H. G. (1977) Job-shop scheduling by implicit enumeration. Management Science 24(4): 441–450
Lin T. L., Horng S. J., Kao T. W., Chen Y. H., Run R. S., Chen R. J. et al (2010) An efficient job-shop scheduling algorithm based on particle swarm optimization. Expert Systems with Applications 37(3): 2629–2636
Luh G. C., Chueh C. H. (2009) A multi-modal immune algorithm for the job-shop scheduling problem. Information Sciences 179(10): 1516–1532
Meeran S., Morshed M. (2011) A hybrid genetic tabu search algorithm for solving job shop scheduling problems: A case study. Journal of Intelligent Manufacturing 23(4): 1063–1078
Mobini M., Mobini Z., Rabbani M. (2011) An artificial immune algorithm for the project scheduling problem under resource constraints. Applied Soft Computing 11(2): 1975–1982
Niu Q., Jiao B., Gu X. S. (2008) Particle swarm optimization combined with genetic operators for job shop scheduling problem with fuzzy processing time. Applied Mathematics and Computation 205(1): 148–158
Nowicki E., Smutnicki C. (1996) A fast taboo search algorithm for the job shop problem. Management Science 42(6): 797–813
Pérez E., Posada M., Herrera F. (2010) Analysis of new niching genetic algorithms for finding multiple solutions in the job shop scheduling. Journal of Intelligent Manufacturing 23(3): 341–356
Puris, A., Bello, R., Trujillo, Y., Nowe, A., & Martinez, Y. (2007). Two-stage ACO to solve the job shop scheduling problem. In Proceedings of the congress on pattern recognition 12th Iberoamerican conference on progress in pattern recognition, image analysis and applications (Vol. 4756, pp. 447–456).
Timmis J. (2007) Artificial immune systems: Today and tomorrow. Natural Computing 6(1): 1–18
Twycross, J. (2007). Integrated innate and adaptive artificial immune systems applied to process anomaly detection. PhD thesis, The University of Nottingham, UK.
Wang L., Zheng D. Z. (2002) A modified genetic algorithm for job shop scheduling. International Journal of Advanced Manufacturing Technology 20(1): 72–76
Wang, W., & Brunn, P. (1994). Production scheduling and neural networks. In Operation Research Proceedings, 173–178.
Weckman G. R., Ganduri C. V., Koonce D. A. (2008) A neural network job-shop scheduler. Journal of Intelligent Manufacturing 19(2): 191–201
Wojtyla G., Rzadca K., Seredynski F. (2006) Artificial immune systems applied to multiprocessor scheduling. Parallel Processing and Applied Mathematics 3911: 904–911
Wolpert, D. H., & Macready, W. G. (1995). No free-lunch theorems for search. Working paper 95-02-010, Santa Fe Institute.
Xia W. J., Wu Z. M. (2006) A hybrid particle swarm optimization approach for the job-shop scheduling problem. International Journal of Advanced Manufacturing Technology 29(3–4): 360–366
Yahyaoui A., Fnaiech N., Fnaiech F. (2011) A suitable initialization procedure for speeding a neural network job-shop scheduling. IEEE Transactions on Industrial Electronics 58(3): 1052–1060
Yang S. X., Wang D. W., Chai T. Y., Kendall G. (2010) An improved constraint satisfaction adaptive neural network for job-shop scheduling. Journal of Scheduling 13(1): 17–38
Zhang R., Wu C. (2010) A hybrid immune simulated annealing algorithm for the job shop scheduling problem. Applied Soft Computing 10(1): 79–89
Acknowledgments
The authors gratefully acknowledge the financial support from the Research Grant Council of the HKSAR Government, P. R. China.
Open Access
This article is distributed under the terms of the Creative Commons Attribution License which permits any use, distribution, and reproduction in any medium, provided the original author(s) and the source are credited.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
Open Access This article is distributed under the terms of the Creative Commons Attribution 2.0 International License (https://creativecommons.org/licenses/by/2.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
About this article
Cite this article
Qiu, X., Lau, H.Y.K. An AIS-based hybrid algorithm for static job shop scheduling problem. J Intell Manuf 25, 489–503 (2014). https://doi.org/10.1007/s10845-012-0701-2
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10845-012-0701-2