A branch-and-bound algorithm with cyclic best-first search for the permutation flow shop scheduling problem

摘要

The permutation flow shop scheduling problem is one of the fundamental problems in scheduling with many practical applications. In this paper, we propose a branch-and-bound algorithm for solving it exactly. The algorithm uses an iterated local search to quickly find a good initial solution, followed by a cyclic best-first search with dynamic bi-directional branching to find the optimal solution and prove its optimality. In computational experiments we analyze the effects of the cyclic best-first search and the dynamic branching strategy, and show that our approach is able to combine preferable characteristics of the current best exact algorithms.