下面介紹本章參考文獻[27]分支定界算法的案例,并且論述如何運用運籌學方法優化集束型裝備的晶圓排序和機械手搬運作業排序,FBMH2012HM121-T以獲取混流調度問題的最優調度方案。

   本節分支定界算法由三個嵌套的分支定界樹組成,分別稱為分支定界樹A、樹B和樹C。分支定界樹A負責隱枚舉一個周期內所有可能的初始工件(晶圓)分布G、=(co,cl,・・・,瓴l,CⅣ)o由前所述,由于集束型裝備采用循環生產模式且一個周期內每種類型的工件只

有一個進入和離開生產線,因此從鮞中可得知工件的加工順序。例如,對于Ⅳ吒,R=5的此類調度問題,假設C:=(l,0,0,2,0,0,3,0,0),則由其僅可知其中三種工件的加工順序為:工件1-工件3→工件2,而并不知道工件4和工件5相互之間的加工順序;假設C:(1,0,0,2,0,5,3,0,4),則由其可知所有5個工件的加工順序。綜上分析可知:若從A樹生成的初始工件分布(鮞)可得知所有工件的加工順序,則直接激活分支定界樹C;反之,則激活分支定界B樹并且接著A樹的枚舉工作繼續枚舉剩余工件的加工順序。當B樹枚舉完剩余工件的加工順序后,再激活分支定界樹C。在此,不難理解,A樹和B樹實質上都是在枚舉工件的加工順序,設計它們的目的是首先刪除不可能的初始工件分布和確保所有工件的加工順序己知。其次是在A樹或B樹枚舉完所有工件的加工順序之后,再由分支定界樹C負責隱枚舉保存下來的可能的初始工件分布和可能的所有工件的加工順序所對應的機械手搬運作業順序,這樣做可以縮小搜索空間和節省搜索時間。