Job Shop Scheduling Problem Based On Immune Clonal Selection Algorithm

Job-Shop scheduling problem (JSSP) is a typical combinatorial optimization problem, which has practical significance and application prospect in engineering applications. After analyzing the existing methods about solving JSSP, the dissertation focuses on the immune clonal selection algorithm for JSSP. The encoding mode, neighborhood structure, clonal operator and immune clonal selection algorithm have all been improved. The main contributions can be summarized as follows:Based on the systematic analysis of the common code mode used in the evolution computation to solve JSSP, a new code mode is proposed. Operation-based code is commonly used when evolutionary algorithms are developed for solving JSSP, the many-for-one mapping between coding space and scheduling space leads to the code redundancy and reduces the diversity of population.Therefore, a scheduling code is proposed, as a new coding mode for JSSP. The scheduling code does not need decoding, and the many-for-one mapping between coding space and scheduling space is avoided.The neighborhood structure is discussed firstly, which is important for neighborhood search performance of evolution computation. And then the improved neighborhood structure is proposed. On this basis, in order to take advantage of scheduling code and improve the performance for solving JSSP, a clonal operator based on neighborhood search is designed, and the immune clonal selection algorithm based on neighborhood search (ICSA_NS) for JSSP is proposed. In the experiments, the benchmark JSSP problems are used to test the performance. All experimental results show that our method is effective.From the simulation experiment, we found that the cycle phenomenon around a solution may arise when the neighborhood search-based clonal operator is used in the immune clonal selection algorithm for JSSP. This phenomenon will reduce the efficiency of the algorithm. In this dissertation, a taboo strategy is proposed to solve this problem, and the immune clonal selection algorithm combinated with taboo strategy (ICSA_NS_TS) is proposed. In the search process, the found solutions should be memorized and prohibited in further search iteration, so an effective search in different directions can be ensured. A large number of JSSP problems have been tested, and the experimental results demonstrate the effectiveness of the algorithm.This research is supported by the National Research Foundation for the Doctoral Program of Higher Education of China under Grant No.20060701007 and the National Natural Science Foundation of China under Grant No.60703107.