Iterative beam search algorithms for the permutation flowshop

We study an iterative beam search algorithm for the permutation flowshop (makespan and flowtime minimization). This algorithm combines branching strategies inspired by recent branch-and-bounds and a guidance strategy inspired by the LR heuristic. It obtains competitive results on large instances compared to the state-of-the-art algorithms, reports many new-best-so-far solutions on the VFR benchmark (makespan minimization) and the Taillard benchmark (flowtime minimization) without using any NEHbased branching or iterative-greedy strategy. The source code is available at: https://github.com/librallu/ dogs-pfsp . (c) 2021 Published by Elsevier B.V.

Automated summary

We examine an iterative beam search algorithm for the permutation flowshop problem, which combines branching strategies from recent branch-and-bounds algorithms and a guidance strategy inspired by the LR heuristic. The algorithm achieves competitive results on large instances and reports numerous new-best-so-far solutions on the VFR and Taillard benchmarks without using NEH-based branching or iterative-greedy strategies.