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

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

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