Multi-objective fuzzy flexible job shop scheduling using memetic algorithm

Multi-objective flexible job shop scheduling problem with fuzzy processing time and fuzzy due date is a complicated combinatorial optimization problem. In this paper, a genetic global optimization is combined with a local search method to construct an effective memetic algorithm (MA) for simultaneously optimizing fuzzy makespan, average agreement index and minimal agreement index. First, a hybridization of different machine assignment methods with different operation sequence rules is proposed to generate a high-performance initial population. Second, the algorithm framework similar to the non-dominated sorting genetic algorithm II (NSGA-II) is adopted, in which a well-designed chromosome decoding method and two effective genetic operators are used. Then, a novel fuzzy Pareto dominance relationship based on the possibility degree and a modified crowding distance measure are defined and further employed to modify the fast non-dominated sorting. Next, a novel local search is incorporated into NSGA-II, where some candidate individuals are selected from the offspring population to experience variable neighbourhood local search by using the selection mechanism. In the experiment, the influence of four key parameters is investigated based on the Taguchi method of design of experiment. Finally, some comparisons are carried out with other existing algorithms on benchmark instances, and demonstrate the effectiveness of the proposed MA.