Research On Gene Expression Programming And Its Application On Scheduling Problems

Scheduling Problems have plenty of practical application background and belong to a type of combinatorial optimization problem that is constrained by a series of constraints. With the development of modern manufacturing, scheduling problems are becoming one of the focuses of research and plentiful literatures appear. Researchers conduct further research on existing methods that optimize the scheduling, meanwhile they are also devoted to finding other effective optimizer. Gene Expression Programming (GEP), which evolves from Genetic Algorithm (GA) and Genetic Programming (GP), is a new technology solves problem optimally. Like GA and GP, GEP evolves according of the fundamental principle of"best is survived". The research on the technology of GEP and its application on scheduling problem such as Single Machine Problem (SMP), Flow Shop Problem (FSP) and Job Shop Problem (JSP) is the main work of the thesis.Firstly, the fundamental principle and mechanism, main applications in several fields and the improvements of GEP are introduced. And several potential research topics are also presented.Secondly, the indirect coding method in the context of GEP is studied, and a multilayer-chromosome coding scheme is proposed. The algorithm based on GEP for SMP is also designed and the evolution mechanism of GEP is utilized to found the optimal or near-optimal solution of the problem. The performance comparation between GEP and several classical heuristic rules is provided.Thirdly, the direct coding method in the context of GEP is studied, and a new combinatorial optimization model is established. The algorithm based on the model for FSP is proposed. The experiments conducted on FSP benchmark problems prove the efficiency of the proposed algorithm.Lastly, the technology of GEP is effective, however, it may be trapped into local optimum. In order to solve the premature convergence problem, a new mutate operator and a new strategy are proposed. Also the algorithm for JSP with improved mutate operator and evolve strategy is designed. The benchmark problems of JSP have investigated the performance of the improved algorithm.