Filtered beam search algorithm with partial backtracking and its application to job shop scheduling

Beam search is a heuristic algorithm originated from the method of branch and bound, which has aroused the interests of many investigators. Unfortunately the searching process, of it is apt to be led to a local extremum because it considers only local information when choosing the new branch. An improving strategy is proposed in this paper, which combines a partial backtracking procedure with the scheme of filtered beam search. With this backtracking strategy, some temporarily pruned nodes will be reserved and reevaluated, hence better potential solutions can survive and the searching process can effectively avoid from being trapped into a local extremum. Numerical experiments of 48 benchmark problems have been conducted to comparing the proposed algorithm (BBS) with the original filtered beam search algorithm, and the results indicate that BBS can improve the solution performance significantly.