Improved Meta-Heuristics with a Sarsa Algorithm for Scheduling Distributed Permutation Flow Shops

This work studies the distributed permutation flow-shop scheduling problems (DPFSP) for minimizing the maximum completion time (makespan). First, a mathematical model is established for the DPFSP. Second, four meta-heuristics, named genetic algorithm (GA), particle swarm optimization (PSO), artificial bee colony (ABC), and differential evolution (DE), are used and improved to solve the problems. Third, the Nawaz-Enscore-Ham (NEH) heuristic is employed to initialize the factory allocation scheme. Then, six local search operators are designed based on problem-specific knowledge. Two Sarsa-based strategies are developed to enhance the exploitation of meta-heuristics by optimizing factory allocation and choosing appropriate local search operators, respectively. Finally, to validate the effectiveness of the proposed algorithms, we solve 72 benchmark instances. The performance of the two Sarsa-based strategies is evaluated. Comparisons and discussions show that the improved ABC with the Sarsa strategy for local search selection is the best one among the 16 algorithms.