Research On Methods Based On Gene Expression Programming For Dyanmic Scheduling

With the increasing rapid development of global economy, the competition between manufacturing enterprises is more intense. In order to enhance their competitiveness, manufacturing enterprises inereasingly concern on how to sehedule the activities in the shop floor so that custormer demands are satisfied. Dynamic scheduling problems have become one of the hot topics in the research of manufacturing system. Gene Expression Programming (GEP) is a new envolutionary algorithm proposed recently.In the paper, GEP is introduced into the research of dynamic scheduling approaches in order to improve the agility, steadiness and robustness of schedules in shop floor.Dynamic events always occur in the shop floor because of the variational custormer demands. It is important to respond to dynamic events rapidly and to make reasonable scheduling decisions. A dynamic scheduling framework which is based on the basic evolution principle of GEP is proposed. According with the framework, GEP learns to construct efficient scheduling rules (SRs) off line. Then, the GEP-constructed SRs are used to implement the reactive scheduling in shop floor in the combination with on-line heuristics. In order to solve the encoding problem, an indirect encoding scheme which maps a SR into a GEP chromosome is proposed. In addition, a fitness function which is suitable for unsupervisory learning is proposed in order to evaluate the fitness of chromosomes.Single machine scheduling problem is the basic scheduling problem. Based on the dynamic scheduling framework proposed above, the approach for dynamic scheduling problem with job release dates on single machie (DSMP) is investigated. An on-line heuristic for DSMP is proposed, in which the constructing method for the candidate job set is improved. GEP-based method for the construction of SRs is also proposed, in which the chromosome is encoding and decoding with the single-gene chromosome, which makes the SRs consturted quickly and expressed compactly. Simulation experiments are conducted to evaluate the performance of the proposed method. Experiment results show that it is efficient and superior to other methods.Job shop scheduling problem is the classical scheduling problem, which is researched extensively. The dynamic scheduling approach for DSMP is extended and applied to the dynamic scheduling problem with job release dates in job shop (DJSP). An on-line heuristic for DJSP is proposed, which decomposes the original DJSP into a number of sub problems. Each sub problem, in fact, is a dynamic single machine scheduling problem with job release dates. The on-line heuristic for DJSP not only makes the constraint conditions in job shop satisfied, but also harmonizes the actions between multiple machines based on the states and constraints in the system. GEP-based SRs constructing method is also proposed, in which the chromosome is encoding and decoding with the multi-gene chromosome, which makes the excellent segments of gene builded easily and transferred to offspring extensively. Simulation experiments are conducted to evaluate the performance of the proposed method in the comparison with other methods. Results show that the proposed method is effective and overperform other methods.Flexible job shop scheduling problem is one of the extension of job shop scheduling problem and its complexity is higher. The dynamic scheduling method for DJSP is extended and applied to the dynamic scheduling problem with job release dates in flexible job shop (DFJSP). An on-line heuristic for DFJSP is proposed, which decomposes the original DFJSP into two sub problems:routing problem and sequencing problem. Therefore, the complexiby of the original scheduling problem is reduced. GEP-based SRs constructing method is also proposed, in which the chromosome is encoding and decoding with the two-sub component chromosome, which makes the exsit genetic operators applied directly on the chromosomes without illegal offspring creating. In order to evaluate the performance of the proposed dynamic scheduling approach, a variety of processing conditions are considered in the simulation experiments. The results show that GEP-based approach can construct simultaneously more efficient machine assignment rules and job dispatching rules for DFJSP than other approaches.Based on the research work mentioned above, dynamic scheduling prototype system oriented to real-world production workshop is designed and developed. The system architecture and function modules are described briefly. In additioan, the application example of the system is exhibited.Finally, the research results achieved in the dissertation is summarized and future work is prospected.