带部分回溯的过滤束搜索算法及其在Job Shop 问题中的应用

束搜索(Beam search)方法是在分枝定界方法基础上发展起来的一种启发式优化方法,由于这类方法在确定分枝搜索方向时仅考虑了当前的局部信息,因此易陷入局部极值.在过滤束搜索(filteredbeam search)方法的基础上提出了一种改进思路,即在局部评价和全局评价的基础上增加部分回溯.通过引入有效的部分回溯策略,部分被舍弃的结点被重新评估并最终找到更好的解,从而可避免过早陷入局部极值.通过对48个标准问题的计算和比较,结果显示改进后的方法能有效提高解的质量.

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.