Job Shop Scheduling Problem Based A New Coding Mode

Job shop scheduling problem (JSSP) is a very difficult combinatorial optimization problem, which is proved to be NP-hard. It has great importance in engineering application and academic study. The early study of JSSP has been mainly focused on the mathematical methods. With the development of computing rate and the request to scheduling efficiency, it is more important to gain better schemes at the cast of computing time. So, some heuristic methods have been widely used in JSSP.Based on the study of existed methods and basic theories of JSSP, the present coding/decoding modes are deeply analyzed, especially the operation based coding mode. A new coding mode for JSSP is proposed in the dissertation. This new mode is called scheduling coding mode,and is represented by a scheduling array and a time array of every operation's completion. Thus, the many-for-one mapping between the coding space and the scheduling space is avoided.Artificial immune system (AIS) has been a hotspot field of computing intelligence in recent years. In the bases of the deep study on the immune clonal selection method, an immune memory clonal selection algorithm based on the scheduling coding mode for job shop scheduling problems is proposed in this dissertation. This method constructs an antibody population and an antibody dead cell in reference to the characteristics of JSSP. The antibody population is divided into a memory cell and a normal antibody cell by the affinity of antigen and antibody. The memory cell keeps better antibodies of the antibody population. Every antibody of the antibody population is evolved by running our algorithm. After each generation, there is an interaction between the memory cell and the normal antibody cell. Some antibodies that could not become any better in the normal antibody cell are killed and substituted by new antibodies. An antibody dead cell is another antibody population whose size is fixed and much smaller than the original one. The antibody dead cell keeps the dead antibodies which are killed in every generation. When any antibody of the antibody population shows up again in the antibody dead cell, it will be killed and substituted by a new antibody very quickly. The method is proved to be effective by our experiments.