An improved NSGA-II algorithm for multi-objective lot-streaming flow shop scheduling problem

Crossover and mutation operators in NSGA-II are random and aimless, and encounter difficulties in generating offspring with high quality. Aiming to overcoming these drawbacks, we proposed an improved NSGA-II algorithm (INSGA-II) and applied it to solve the lot-streaming flow shop scheduling problem with four criteria. We first presented four variants of NEH heuristic to generate the initial population, and then incorporated the estimation of distribution algorithm and a mutation operator based on insertion and swap into NSGA-II to replace traditional crossover and mutation operators. Last but not least, we performed a simple and efficient restarting strategy on the population when the diversity of the population is smaller than a given threshold. We conducted a serial of experiments, and the experimental results demonstrate that the proposed algorithm outperforms the comparative algorithms.