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

In this paper, adaptive hybrid genetic algorithms (AHA(0) similar to AHA(3)) 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(0). Three local search methods (LS1, LS2, and LS3) are separately integrated with AHA(0) and three hybrid algorithms AHA(1) similar to AHA(3) are developed. Compared with GA_RMA and CPSO (effective algorithms without integrating any local search), AHA(0) 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(1) similar to AHA(3) comprehensively. Experimental results show that for the two considered problems, AHA(1) outperforms the other algorithms on small setup-time instances and AHA(3) is the most effective algorithm among the compared ones on big setup-time instances, while the computation time of AHA(1) is moderate among the LS1 integrated algorithms, so is AHA(3). The effects of the key factors or parameters on algorithms are analyzed as well.