上述模型的目標函數為最小化生產周期,約束條件集式(3-1)為節點ε對應的刀個約束, FBMH1608HM331-T這些約束包括加工時間約束、加工模塊能力約束和機械手能力約束。約束條件集刻畫了集束型裝備機械手在生產周期內搬運作業之間的約束關系,決策變量凸和島分別表示搬運作業∫和搬運作業丿的開始時間,q lc為生產周期r的整數系數,瀘和3k為實數常量。約束條件集式為生產周期r的可行范圍約束,約束條件集式(3-3)為決策變量的非負約束。由于約束條件集式(3-1)具有特殊差分約束結構,可以通過圖論方法轉化為賦權有向圖。由此,上述線性規劃問題被轉化為有向賦權圖中最長路徑問題。由于砥權有向圖中弧的權值是Γ的線性函數r(D,若賦權有向圖中有正回路,即回路上所有弧的權值總和Ⅴ(D)0,則該問題無解;反之,則該問題有解。周期時間Γ則是在可行區間k,r]中,使賦權有向圖中不存在正回路的最小值。

   基于上述思想,Rostami等⒓l]提出基于圖論的多項式算法求解差分線性規劃問題,并設計三種剪枝技術用來減少解空間的大小,從而提高分支定界算法的整體效率。在其調度中,將機械手其中的一個臂作為臨時緩沖區使用,通過迭代算法使約束得到滿足。先不考慮晶圓駐留時間約束,并求得其生產周期Γ。然后進行搜索分析是否存在一個調度方案使得其生產周期為T,如果存在則求得一個可行解。若不存在,將Γ加1,再進行搜索,直到求得可行解為止。隨后本章參考文獻[22]推廣這一算法,來研究同時考慮晶圓滯留時間約束和雙臂機械手滯留時間約束的集束型裝備調度問題,也用來研究具有中間緩沖區的雙臂集束型裝備調度問題。該算法不僅適合雙臂機械手,而且也能夠解決復雜的二臂機械手調度問題,但理論上其復雜度是隨工序數指數增長的。當集束型裝各的工序數比較少時,該算法還是有效的。Carlicr等⒓劍把集束型設備調度問題分成兩個調度子問題來解決,然后提出精確的分支定界法來求得最優解。Jung㈣等提出基于Pc“i網的分支定界法,其節點的評估采用雙簡化算法代替求解線性規劃模型,其算法具有通用性。但該算法沒有考慮問題的結構特征,其計算效率一般。