Solving Job Shop Scheduling Problem Based On Natural Computation

Job Shop Scheduling Problem (JSSP) is a typical NP-hard problem, and is one of the most difficult combinatorial optimization problems so far. JSSP also has great importance in engineering applications. Thus, JSSP has been concerned widely. Based on the deep analysis of the problem and combined with the results to date, this dissertation is focused on solving JSSP by making use of natural computation algorithm. The main work can be summarized as follows:(1) Based on the multi-population genetic algorithm (MGA), a multi-population genetic algorithm based on memory-base and Lamarckian evolution for job shop scheduling problem is proposed. The memory-base and Lamarckian local search operators are proposed for shortcomings of MGA that is easy to fall into local optima and poor ability of local search. Through the introduction of the memory-base, not only can it make individuals among sub-populations exchange information, but also it can maintain the diversity of population; the local search operator is adopted based on Lamarckian evolution to improve the individual's ability of local search. We use the simulated annealing algorithm that has a stronger global optimization ability to optimize the individuals of the memory-base, thus our algorithm alleviates the problem that the MGA often traps in local optima and improves the performance for solving JSSP.(2) Solving JSSP by clonal selection (CS) algorithm, if the initial distribution of the population is not ideal, its convergence rate is relatively slow, G&T algorithm can generate a better initial population to speed up the convergence rate. The main operator of clonal selection algorithm is mutation operator; therefore, how to choose a suitable mutation operator will have a great influence on performance. In this dissertation, three kinds of mutation operators (exchange, inversion, insertion) are adopted to optimize the population, and record the contribution of each mutation operator at the same time. In the process of clonal mutation, we choose the suitable mutation operator dynamically through the roulette. In addition, the mutant strength of a clonal individual should be inversely proportional to affinity of the individual, that is, the higher the affinity, the smaller the mutant strength; the lower the affinity, the bigger the mutant strength. For that reason, an adaptive mutant strength operator is proposed.(3) Differential evolution (DE) algorithm adopts floating-point encoding scheme and is succeed in solving global optimization problems over continuous space. For Job Shop Scheduling Problem, which is in discrete space, the discrete differential evolution (DDE) algorithm is designed in this dissertation. Based on the skeleton of DE algorithm, DDE algorithm inherits the advantages of DE. The experimental results demonstrate a rapid convergence rate of DDE in solving JSSP compared with the clonal selection and genetic algorithm on benchmark problems.(4) Clonal selection algorithm has the ability of local search and global search, which makes the algorithm maintain a good diversity of population, but for JSSP, the convergence rate of CS is relatively slow. Discrete differential evolution algorithm inherits the advantages of DE algorithm that has a rapid convergence rate; however, compared with clonal selection algorithm, DDE algorithm has a bad diversity of population, which makes DDE algorithm trap in local optima rapidly. We combine CS and DDE algorithm effectively, take full advantages of them and make up for their defects. The experimental results show that our algorithm is effective on Job Shop Scheduling Problem.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.