(1）節點所對應的問題氣無解。FBMH2012HM221-T

   (2)問題氣有解但其值大于等于z值。若問題氣有可行解,則要比較此可行解與Z值的大小,若前者較小,貝刂更新Z值,并作為可行解的值。

   步驟4:當虍(Ⅳ時,則重復進行步驟2。

   (l)若從鮞中可知所有工件的順序,則枚舉樹A停止生長,并得到問題馬Ⅳ的可行解,若無可行解,則問題P無任何解。若此可行解滿足機械手能力約束關系式中的所有松弛約束,則該可行解便是問題P的最優解;若此可行解不完全滿足機械手能力約束關系式中的松弛約束,則枚舉樹C被激活,轉到步驟8。

   (2)若從鱺中僅知道部分工件的加工順序,則激活枚舉樹B,其根結點可以看成枚舉樹A的一個葉子節點,通過鮞便可確定該根節點的分支個數(Num=夕一昭),并進行分支,轉到步驟5。

   步驟5:從B樹中未被搜縈的節點(局部解)中選擇―個節點。若節點選擇不為空,確定其分支個數,并在此節點的下一層生成子節點,轉到步驟6;若在B樹中節點選擇為空,轉到步驟2。

   步驟6:計算每一個新生成的子節點的下限值(LB)。在剩余工件加工順序沒有枚舉完之前,每個節點上都對應著一個松弛問題,若節點滿足以下條件之一,則刪除該節點。