Hybrid Artificial Immune System for Job Shop Scheduling Problem

Authors: Bin Cai, Shilong Wang, Haibo Hu

Abstract:

The job shop scheduling problem (JSSP) is a notoriously difficult problem in combinatorial optimization. This paper presents a hybrid artificial immune system for the JSSP with the objective of minimizing makespan. The proposed approach combines the artificial immune system, which has a powerful global exploration capability, with the local search method, which can exploit the optimal antibody. The antibody coding scheme is based on the operation based representation. The decoding procedure limits the search space to the set of full active schedules. In each generation, a local search heuristic based on the neighborhood structure proposed by Nowicki and Smutnicki is applied to improve the solutions. The approach is tested on 43 benchmark problems taken from the literature and compared with other approaches. The computation results validate the effectiveness of the proposed algorithm.

Keywords: Artificial immune system, Job shop scheduling problem, Local search, Metaheuristic algorithm

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1081963

References:

[1] T. Yamada and R. Nakano, "A genetic algorithm applicable to large-scale job-shop problems," in Proc. of the 2nd International Conference on Parallel Problem Solving from Nature, Amsterdam, 1992, pp.283-292.
[2] P. J. M. van Laarhoven, E. H. L. Aarts, and J. K. Lenstra, "Job shop scheduling by simulated annealing," Operations Research, vol. 40, pp.113-125, 1992.
[3] E. Nowicki, C. Smutnicki C, "A fast taboo search algorithm for the job shop problem," Management Science, vol. 42, pp.797-813, 1996.
[4] E. Hart, P. Ross, and J. Nelson, "Producing robust schedules via an artificial immune system," in Proc. International Conference on Evolutionary Computing (ICEC'98), Seoul, Korea, 1998, pp. 464-469.
[5] C.A.C. Coello, D.C. Rivera, and N.C. Cortes, "Use of an artificial immune system for job shop scheduling," Artificial Immune Systems (ICARIS'2003), LNCS 2787, Springer-Verlag, 2003, pp. 1-10.
[6] C.A.C. Coello, D.C. Rivera, and N.C. Cortes. "Job shop scheduling using the clonal selection principle," Adaptive Computing in Design and Manufacture VI, Springer-Verlag, 2004, pp. 113-124.
[7] S. Binato, W. J. Hery, D. M. Loewenstern, and M. G. C. Resende, "A GRASP for job shop scheduling," in Essays and Surveys in Metaheuristics. Boston, MA: Kluwer, 2001, pp. 59-80.
[8] A. S. Jain and S. Meeran "Deterministic job-shop scheduling: past, present and future," European Journal of Operational Research, vol. 113, pp.390-434, 1999.
[9] L.N. de Castro, F.J. Von Zuben, "Learning and optimization using the clonal selection principle," IEEE Trans. Evolutionary Computation, vol.6, pp. 239-251, June 2002.
[10] L.N. de Castro, J. Timmis, "An artificial immune network for multimodal function optimization," in Proc. of the 2002 Congress on Evolutionary Computation, Honolulu, 2002, pp. 699-704.
[11] E. Hart and J. Timmis, "Application areas of AIS: The past, the present and the future," Applied Soft Computing, vol. 8, pp.191-201, 2008.
[12] J.T. Tsai, W.H. Ho, T.K. Liu and J.H. Chou, "Improved immune algorithm for global numerical optimization and job-shop scheduling problems," Applied Mathematics and Computation, vol. 194, pp. 406-424, 2007.
[13] H.W. Ge, L.Sun, Y. Liang and F. Qian, "An effective PSO and AIS-based hybrid intelligent algorithm for job-shop scheduling," IEEE Trans. on Systems, Man, and Cybernetics, vol. 38, pp. 358-368, March 2008.
[14] J. F. Goncalves , J. J. D. M. Mendes and M. G. C. Resende. "A hybrid genetic algorithm for the job shop scheduling problem," European Journal of Operational Research, vol. 167, p77-95, 2005.
[15] M. Chandrasekaran, P. Asokan, S. Kumanan, T. Balamurugan and S. Nickolas, "Solving job shop scheduling problems using artificial immune system," International Journal of Advanced Manufacturing Technology vol.31, pp.580-593, 2006.
[16] R. Cheng, M. Gen and Y. Tsujimura, "A tutorial survey of job-shop scheduling problems using genetic algorithms-I. representation," Computers & Industrial Engineering, vol. 30, pp. 983-997, 1996.
[17] M. Pinedo, Scheduling Theory, Algorithms, and System, 2nd ed. Prentice Hall, Upper Saddle River, New Jersey, 2002, pp. 21-25.
[18] C.Y. Zhang, Y.Q. Rao and P.G Li, "An effective hybrid genetic algorithm for the job shop scheduling problem," International Journal of Advanced Manufacturing Technology, vol.39, pp965-974, 2008.
[19] J. E. Beasley, "OR-Library: Distributing test problems by electronic mail," Journal of the Operational Research Society, vol. 41, no. 11, pp. 1069-1072, 1990.
[20] I. Sabuncuoglu and M. Bayiz, "Job shop scheduling with beam search," European Journal of Operational Research, vol. 118, no. 2, pp. 390-412, 1999.
[21] W. P. W. Nuijten and E. H. L. Aarts, "Computational study of constraint satisfaction for multiple capacitated job shop scheduling," European Journal of Operational Research, vol. 90, no. 2, pp. 269-284, 1996.
[22] J. Adams, E. Balas, D. Zawack, "The shifting bottleneck procedure for job shop scheduling," Management Science, vol.34, pp391-401, 1988.