A Novel Artificial Immune Algorithm for Job Shop Scheduling

The job shop scheduling problem (JSSP) is one of the most difficult problems, as it is classified as an NP-complete one. In this paper, by integrating chaos mechanism and niche technique, a novel artificial immune algorithm based on the clonal selection principle and idiotypic immune network theory exhibited in biological immune system is proposed to solve classical job shop scheduling problem. Taking advantages of the ergodic and stochastic properties of chaotic variable, an adaptive chaos mutation operator is designed by the combination of prior knowledge of antibody and evolution iterations. The operator can avoid blind search and enhance the convergence speed effectively. 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.