%0 Journal Article
%T Filtered Beam Search Algorithm with Partial Backtracking and Its Application to Job Shop Scheduling<br>带部分回溯的过滤束搜索算法及其在Job Shop 问题中的应用
%A SHANGGUAN Chun-xia
%A ZHOU Hong
%A SHI Rui-feng
%A <br>上官春霞
%A 周　泓
%A 师瑞峰
%J 系统工程理论与实践
%D 2007
%I 
%X 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.
%K filtered beam search
%K partial backtracking
%K heuristics
%K job shop scheduling<br>过滤束搜索
%K 部分回溯
%K 启发式算法
%K 作业排序
%U http://www.alljournals.cn/get_abstract_url.aspx?pcid=01BA20E8BA813E1908F3698710BBFEFEE816345F465FEBA5&cid=962324E222C1AC1D&jid=1D057D9E7CAD6BEE9FA97306E08E48D3&aid=B1C8CB6F073CD37D&yid=A732AF04DDA03BB3&vid=DB817633AA4F79B9&iid=CA4FD0336C81A37A&sid=475189FCB44F11F6&eid=70AC2EF7F2065E09&journal_id=1000-6788&journal_name=系统工程理论与实践&referenced_num=0&reference_num=21