Evolutionary Algorithm with Precise Neighborhood Structure for Flexible Workshop Scheduling

Abstract:

In order to solve the problems of the existing neighborhood search based on critical path， such as too many invalid moves， too much blindness and optimization one objective， a more precise and effective neighborhood structure is designed， including the two-step operation of the same machine movement and the cross-machine movement. Based on which， the corresponding operation movement conditions are given and extended from the optimization of the maximum completion time to multi-objective optimization. Besides， to realize the complementary advantages of local and global search， the algorithm is mixed with the evolutionary algorithm， and the corresponding hybrid algorithm framework is given. Moreover， two internationally used case sets are tested， and the test results are compared with those of other algorithms to verify the effectiveness and efficiency of the proposed algorithm.

Key words:multi-objective optimization;workshop scheduling;neighborhood search;evolutionary algorithm