Iterative beam search algorithms for the permutation flowshop
This work addresses scheduling optimization for manufacturing and logistics, but it is incremental as it builds on existing methods like branch-and-bound and LR heuristics.
The paper tackles the permutation flowshop problem for makespan and flowtime minimization by developing an iterative beam search algorithm that combines branching strategies from branch-and-bound methods and guidance from the LR heuristic. It reports competitive results, including many new-best-so-far solutions on the VFR and Taillard benchmarks.
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, reports many new-best-so-far solutions on the VFR benchmark (makespan minimization) and the Taillard benchmark (flowtime minimization) without using any NEH-based branching or iterative-greedy strategy. The source code is available at: https://gitlab.com/librallu/cats-pfsp.