Research On Scheduling Problems Based On Improved Genetic Algorithms

As a new optimization method, GA was widely used in the optimizations of many fields owing to the features of simplicity, easily handing and parallel processing. However GA theory is not perfect, such as there exist the problems of easily creating earliness and bad ability in local optimal, etc. Enlightened by distribution of creature living in nature, the mathematic model of the Distribution Population based Genetic Algorithm (DPGA) is proposed in this paper, and its convergence analysis are also given. DPGA is applied to optimize the Job-shop problem(JSP) and Flow-shop problems(FSP),and the modified GA based on heuristic rules is presented for the single machine scheduling problems with controllable processing times. The three problems are typically NP-hard, which means that it is impossible to find the global optimum in polynomial complexity. Good algorithms for this problem can promote productivity of enterprises. The simulation tests are made and the results demonstrate the efficiency of the above methods. The main content of this thesis includes the following:1. Enlightened by distribution of creature living in natural ecology environment, the mathematic model of the Distribution Population based Genetic Algorithm, and the convergence analysis of DPGA are given.2. The algorithms based on DPGA is designed for the JSP and FSP. The simulation tests for some benchmarks show the efficiency of the DPGA.3. The modified GA is presented to get the optimal results of the NP-hard single machine problem with controllable processing times and the NP-hard single machine problem with discretely controllable processing times. The good performance of the modified GA is reached.