A genetic algorithm for two-stage no-wait hybrid flow shop scheduling problem

Considering the practical application and the computational complexity of the two-stage no-wait hybrid flow shop scheduling problem, this paper proposes a genetic algorithm (GA). Based on the description of the problem and its properties, some constructive heuristics are first proposed to obtain the upper bound. Then the implementation details of the proposed GA are illustrated, in which the results of heuristics are employed into the initial population. Next, a preliminary computational test with factorial design is conducted to tune the key parameters of four versions of the proposed genetic algorithms resulting from combinations of different crossover and mutation operators. With the tuned parameters, the performance of the proposed genetic algorithms is evaluated in terms of the mean percentage deviation of the solution with respect to the lower bound value, through an extensive computational experiment. The results with different problem configurations demonstrate the effectiveness and efficiency of the proposed genetic algorithm and also demonstrate that the GA performs relatively better when the LOX (two-point linear order crossover) operator and the swap mutation operator are used.