A Novel Immune-PSO Algorithm for Job Shop Scheduling

Abstract:

The job shop scheduling problem (JSSP) is one of the most difficult problems, as it is classified as an NP-complete one. Particle Swarm Optimization, a nature-inspired evolutionary algorithm, has been successful in solving a wide range of real-value optimization problems. However, little attempts have been made to extend it to discrete problems. In this paper, a new particle swarm optimization method based on the clonal selection algorithm is proposed to avoid premature convergence and guarantee the diversity of the population. Experimental results indicate that the proposed algorithm is highly competitive, being able to produce better solutions than GA and CLONALG in several cases, and is a viable alternative for solving efficiently job shop scheduling problem.

• Periodical: Advanced Materials Research (Volumes 129-131)
• Pages: 261-265
• DOI: https://doi.org/10.4028/www.scientific.net/AMR.129-131.261
• Online since: August 2010
• Authors: Lu Hong, Jing Yang
• Keywords: Artificial Immune System, Clonal Selection Algorithm, Job-Shop Scheduling Problem, Particle Swarm Optimization Algorithm (PSO)

References

[1] T. P. Bagchi: MultiObjective Scheduling by Genetic Algorithms. Kluwer Academic Publishers, New York(1999).

[2] K. R. Baker: Introduction to Sequencing and Scheduling. John Wiley & Sons, New York(1974).

[3] M. R. Garey and D. S. Johnson: Computers and Intractability: A Guide to the Theory of NP-Completeness (Series of Books in the Mathematical Sciences). W H Freeman & Co. (1979).

[4] J. Kennedy, R. Eberhurt: Particle Swarm Optimization. in Proc. IEEE International Conf. on Neural Networks, vol. 4, Nov. Dec(1997).

[5] R. C. Eberhart and Y. Shi: Evolving artificial neural networks. in Proc. Int. Conf. Neural Networks and Brain, Beijing, P.R. C(1998).

[6] P. Angeline: Evolutionary optimization versus particle swarm optimization: philosophy and performance difference. In: Proceedings of the Evolutionary Programming Conference, San Diago, USA(1998).

DOI: 10.1007/bfb0040811

[7] D. Dasgupta, and F. González: Artificial immune systems (AIS) research in the last five years. in Proc. Conf. Evolutionary Computation(2003), pp.123-130.

[8] L. De Castro, J. Fernando, and Von Zuben: The clonal selection algorithm with engineering applications. In Workshop Proceedings of GECCO'00, Workshop on Artificial Immune Systems and their Applications, LasVegas, USA(2000), pp.36-37.

[9] L. N. De Castro, and F. J. Von Zuben: Learning and optimization using the clonal selection principle. IEEE Trans on Evolutionary Computation, Special Issue on Artificial Immune Systems (2001), pp.239-251.

DOI: 10.1109/tevc.2002.1011539

[10] J. F. Muth and G. L. Thompson: Industrial scheduling. New Jersey: Prentice-Hall, Englewood Cliffs(1963), pp.120-150.