A niche genetic algorithm for two-machine flowshop scheduling with family sequence-dependent setup times and a common due window

This paper presents a two-machine flowshop scheduling problem with family sequence-dependent setup times and a common due window. The objective is to minimize the sum of earliness and tardiness according to the common due window. The problem is found to be NP-hard. And a niche genetic algorithm (NGA) with sharing as the population diversity mechanism is developed for it, in which the distance of two chromosomes is defined to measure the similarity between them, preventing premature convergence of a standard genetic algorithm (SGA). Computational experiments in different scales show the effectiveness and efficiency of the algorithm.