對枚舉樹的某些節(jié)點必須分支決策,即凡是界限小于迄今為止所有可行解最小下界的任何節(jié)點,都有可能作為分支的選擇對象。目前對于分支而言,主要有以下兩種方式。 FBMH1608HM221-T

   (1)從最新產(chǎn)生的最小下界分支。從最新產(chǎn)生的各子集中選擇具有最小下界的節(jié)點進行分支。這種分支法優(yōu)點是節(jié)省空間,但缺點是需要較多的分支運算,耗費的時間較多。

   (2)從最小下界分支。每次算完界限后,把枚舉樹上當前所有節(jié)點的界限進行比較,找出界限最小的節(jié)點,此節(jié)點即為下次分支的節(jié)點。優(yōu)點是檢查子問題較少,能較快地求得最佳解,缺點是要儲存很多子節(jié)點的界限及對應的耗費矩陣,花費很多內(nèi)存空間。在調(diào)度問題的研究上,分支定界算法一直是最重要的算法之一,例如,本章參考文獻[13~16]分別提出不同的分支定界算法,它們的不同主要表現(xiàn)為分支規(guī)則、定界機制和上界3個方面的差異。但是所有分支定界算法的主要缺陷在于缺乏足夠的下界以保證分支程序具有理想的效率。雖然很多有效的分解程序被提出以解決加快搜索,但仍要大量的計算去解決大規(guī)模復雜的調(diào)度問題[叼。本章參考文獻Ⅱ8~23]最先系統(tǒng)地研究具有滯留時間約束下的雙臂集束型裝各調(diào)度問題,并提出基于各種特定分支規(guī)則的分支定界算法。