Adaptive Hybrid Algorithms for the Sequence-Dependent Setup Time Permutation Flow Shop Scheduling Problem

In this paper, adaptive hybrid genetic algorithms (AHA₀ ~ AHA₃) are proposed for the sequence-dependent setup times permutation flow shop scheduling problem with the objectives to minimize makespan and total weighted tardiness, both of which will be considered separately. Each job is assigned an introduced inheriting factor, which indicates the probability that the job is copied to the same position of the offspring individual during crossover and is dynamically updated. Good genes and bad genes can be mined by inheriting factors. Probability-based Multi-Point Crossover (PMPC) is constructed to inherit good genes with high probabilities to the offspring and destroy bad genes with high probabilities. Inheriting factors determine such probabilities and the genetic algorithm evolves adaptively and is denoted as AHA₀. Three local search methods (LS1, LS2, and LS3) are separately integrated with AHA₀ and three hybrid algorithms AHA₁ ~ AHA₃ are developed. Compared with GA_RMA and CPSO (effective algorithms without integrating any local search), AHA₀ is the most effective. Another six hybrid algorithms are extended from IG_RS (the current best algorithm for the two considered problems) and CPSO by integrating with the three local search methods and they are compared with AHA₁ ~ AHA₃ comprehensively. Experimental results show that for the two considered problems, AHA₁ outperforms the other algorithms on small setup-time instances and AHA₃ is the most effective algorithm among the compared ones on big setup-time instances, while the computation time of AHA₁ is moderate among the LS1 integrated algorithms, so is AHA₃. The effects of the key factors or parameters on algorithms are analyzed as well.