Job Shop Scheduling Problem Resolving Based On Natural Computation

Job Shop Scheduling Problem (JSSP) is a very hard combinatorial optimization problem and has great importance in engineering applications. Based on the deep analysis of the problem and combined with the results to date, this paper conducts deeply research by making use of natural evolution ideas and the inherence of immune systems aimed for providing new resolution methods to the JSSP resolving and exploring new application areas of artificial immune system. Genetic algorithm, neighborhood search algorithm, clonal selection algorithm are the emphasis.Based on the study of existing methods and basic theories of JSSP, this paper starts with Genetic Algorithm. Not only the coding/decoding problem and the designing of genetic operator are deeply analyzed, but also a new kind of decoding method and a new kind of crossover operator to the job number based coding method are proposed.After the summarizing of neighborhood search algorithms, a new kind of extended Gantt char expression to the JSSP using minimum makespan objective function is proposed, subsequently a method to find all critical blocks is proposed. Base on the summarizing of the existing neighborhood structures, which is important to neighborhood search algorithms, two judgment rules are proposed and then a clonal operator based on the critical block neighborhood search is designed. And then the clonal selection algorithm using this clonal operator is discussed.At last, a super mutation anti-body clonal selection method applied to large scale JSSP is given, and the testing results show it's much better performance comparing to genetic algorithm.