Research On Multi-objective Flexible Job Shop Scheduling Problem Based On Improved Genetic Algorithms

With continuous improvement of science and technology, increasingly fierce market competition is more and more competitive in the era of economic globalization.The production processes of enterprises need to efficient and stable operation and reasonable optimization configuration of resource. So enterprises get better economic benefits in competition. Flexible job shop scheduling problem is a very important problem of manufacture. Efficient scheduling scheme can reduce production costs,improve resource utilization and therefore has an important significance.Genetic algorithm has features of simpleness, universal and robustness. It is a widely used global optimization algorithm to solve flexible job shop problem, but there are still some deficiencies. This thesis focuses on genetic algorithm and improves the algorithm to better solve multi-objective flexible job shop problem. The main works of this thesis are as follows:1. Aiming at the problems of low efficiency, weak local search ability and easy early maturity of genetic algorithm for multi-objective problems. An improved genetic algorithm is proposed. This algorithm combines global capacity of genetic algorithm with local search capacity of chaos algorithm. The algorithm adopts a double-layer chromosome encoding scheme, two kinds of crossover and mutation based on process sequence and machine allocation, a kind of evaluation mechanisms of extreme value. This can effectively solve the problems of premature and weak local search of genetic algorithm. The simulation results of classic examples indicate that the proposed algorithm is superior to genetic algorithm for accuracy and convergence.2. Aiming at solving the multi-objective flexible job shop scheduling problem is difficult to determine the cause of weights in the problem of poor scheduling scheme,an improved genetic algorithm(DRSGA) based on dynamic random search is proposed. This algorithm translates all minimized job completing time and total machine loading into single minimized objective by the efficiency coefficient method.A double-layer chromosome encoding scheme based on two kinds of crossover and mutation of sequence and machine allocation is adopted, a variable influence space evaluation method can guarantee the uniform distribution of non-inferior solutions while the diversity of population is maintained. Finally, in order to avoid unnecessary search for critical paths, DRS method and Contest rules are employed to effectively adjust key process orders to minimize all job completing time. Thesimulation results indicate that the proposed algorithm has better accuracy and convergence and can effectively solve the multi-objective flexible job shop scheduling problem.3. In order to solve the scheduling problem of Flexible Job-shop Scheduling with Lot-splitting problem, a flexible batching scheduling algorithm based on an improved genetic algorithm is proposed. The algorithm designs a double chromosome coding method based on the job order, sub population and equipment. Random rules and heuristic method are adopted to initialize the population. Then the chromosome is normalized to expand the range of the neighborhood search, and the neighborhood search is done based on the key path. The simulation results indicate that the proposed algorithm has better accuracy and convergence and can effectively solve the multi-objective flexible job shop scheduling problem.