A Novel Genetic Simulated Annealing Algorithm for No-wait Hybrid Flowshop Problem with Unrelated Parallel Machines

This paper studies the problem of scheduling N jobs in a hybrid flowshop with unrelated parallel machines at each stage. Considering the practical application of the presented problem, no-wait constraints and the objective function of total flowtime are included in the scheduling problem. A mathematical model is constructed and a novel genetic simulated annealing algorithm so-called GSAA are developed to solve this problem. In the algorithm, firstly a modified NEH algorithm is proposed to obtain the initial population. A two-dimensional matrix encoding scheme for scheduling solutions is designed and an insertion-translation approach are employed for decoding in order to meet no-wait constraints. Afterwards, to avoid GA premature and enhance search ability, an adaptive adjustment strategy is imposed on the crossover and mutation operators. In addition, a SA procedure is implemented for some better individuals from the GA solutions to complete re-optimization, where five neighborhood search structures are constructed including job based exchange, gene based exchange, gene based insertion, job based mutation, and gene based mutation. Finally, various simulation experiments in two scales of small-medium and large are established. Computational results show that the presented algorithm performs much more effectively compared with several heuristic algorithms reported in the literature.