過濾束搜索(∏ltered Beam scarch)算法是以分支定界法為基礎(chǔ),并結(jié)合分派規(guī)則的一種近似算法。LPO2506I-822LC分支定界法是通過計(jì)算從一個(gè)點(diǎn)出發(fā)的所有可行排序的目標(biāo)函數(shù)值的下界,并與一個(gè)已知排序的目標(biāo)函數(shù)值的下界進(jìn)行比較,從而獲得新的出發(fā)點(diǎn)的枚舉算法。對(duì)于大型調(diào)度問題其計(jì)算量非常大,需要的計(jì)算時(shí)間不可接受。過濾束搜索算法是分支定界算法的修正算法,即在任意給定每一水平上,它不是對(duì)所有的點(diǎn)都要估計(jì)目標(biāo)函數(shù)值,而是對(duì)最有希望的點(diǎn)進(jìn)行估值,在這個(gè)水平上的其他點(diǎn)被永久忽視。被保留點(diǎn)的數(shù)目稱為束寬(Bcam ⅥⅡdth)。確定哪些點(diǎn)是最有希望的點(diǎn)是算法的關(guān)鍵。這種算法存在“粗略的估值快,但有可能丟掉好的排序;而徹底的估值將花費(fèi)不能接受的時(shí)間”的矛盾。Oechsner等[10剄提出過濾束搜索算法用來確定晶圓加工排序,并用商業(yè)仿真軟件CluSim對(duì)算法進(jìn)行仿真驗(yàn)證。