Research On Flexible Job-shop Scheduling Problem Based On Evolutionary Algorithm

With the increasingly market competition, the Flexible Job-shop SchedulingProblem (FJSP) has been concerned by more and more people in the field ofmanufacturing system. Effective scheduling methods can greatly improve theproduction benefit and utilization factor. Evolutionary algorithm (EA) hasincomparable advantages over traditional methods in solving FJSP.FJSP has two sub-problems: the scheduling sub-problem and the routingsub-problem. Designing efficient chromosome encoding scheme is the key to solvingFJSP when using EA. Traditional combinatorial double-encoding scheme needs todesign special crossover strategy, then float-based weight encoding scheme onscheduling sub-problem is designed. It makes encoding framework have betterportability and be conducive to implantation of evolutionary strategy. Usingdifferential evolution (DE) design optimization algorithm, effectively avoids theillegal individuals. Utilizing Non-dominated Sorting Genetic Algorithm (NSGA)framework can achieve good convergence with no local search. Furthermore, givingthe definitions of Parallel Decision and Equivalent Parallel Decision expands thestudy of FJSP into decision space.When we utilize Multiobjective Evolutionary Algorithm (MOEA) to solve thenon-simple real problems, such as FJSP, we find simple crossover and mutationstrategy is difficult to ensure the accuracy of the results. This paper proposes a hybridevolutionary algorithm for solving Multi-objective FJSP (MOFJSP). From the studyon the characteristics of MOFJSP, a novel MOEA with two types of local searchmechanism (MOEA/C) is introduced. Instead of random local search, our local searchmechanisms can help MOEA to reach the Pareto Front effectively by using theinformation of good individuals for deep seeking. Besides a heuristic initializationstrategy which can avoid absence of resource is proposed in this paper. Experimentalresults indicate that MOEA/C approach the real Pareto Front accurately and quicklyon some famous benchmarks.In the real production environment, there exist unexpected events, so we must dodynamic scheduling to adapt to the environment. The normal dynamic schedulingprocess is constructed and a new mechanism of man-computer cooperation is putforward. In this mechanism, the Equivalent Parallel Decision is set into the man procedure and the DE-NSGA is set into the computer procedure. This new dynamicscheduling strategy can guide the related theory, method, technology and tools in theresearch and development.