Hybrid Artificial Immune System for Job Shop Scheduling Problem
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.
[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.
[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.
@article{"International Journal of Business, Human and Social Sciences:62894", author = "Bin Cai and Shilong Wang and Haibo Hu", title = "Hybrid Artificial Immune System for Job Shop Scheduling Problem", 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", volume = "5", number = "11", pages = "1687-6", }
