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

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