A genetic programming hyper-heuristic for the distributed assembly permutation flow-shop scheduling problem with sequence dependent setup times

In this paper, a genetic programming hyper heuristic (GP-HH) algorithm is proposed to solve the distributed assembly permutation flow-shop scheduling problem with sequence dependent setup times (DAPFSP-SDST) and the objective of makespan minimization. The main idea is to use genetic programming (GP) as the high level strategy to generate heuristic sequences from a pre-designed low-level heuristics (LLHs) set. In each generation, the heuristic sequences are evolved by GP and then successively operated on the solution space for better solutions. Additionally, simulated annealing is embedded into each LLH to improve the local search ability. An effective encoding and decoding pair is also presented for the algorithm to obtain feasible schedules. Finally, computational simulation and comparison are both carried out on a benchmark set and the results demonstrate the effectiveness of the proposed GP-HH. The best-known solutions are updated for 333 out of the 540 benchmark instances.

Automated summary

The paper introduces a GP-HH algorithm to address the DAPFSP-SDST problem by using genetic programming to generate heuristic sequences and incorporating simulated annealing for local search, achieving effective solutions and improving upon existing benchmarks.