整體式自動(dòng)化物料運(yùn)輸系統(tǒng)防擁堵調(diào)度策略

李明輝，徐 方，宋吉來(lái)

(1.中國(guó)科學(xué)院沈陽(yáng)自動(dòng)化研究所 機(jī)器人學(xué)國(guó)家重點(diǎn)實(shí)驗(yàn)室，遼寧 沈陽(yáng) 110016； 2.中國(guó)科學(xué)院 機(jī)器人與智能制造創(chuàng)新研究院，遼寧 沈陽(yáng) 110169；3.中國(guó)科學(xué)院大學(xué)，北京 100049； 4.沈陽(yáng)新松機(jī)器人自動(dòng)化股份有限公司 中央研究院，遼寧 沈陽(yáng) 110168)

0 引 言

半導(dǎo)體生產(chǎn)制造系統(tǒng)是當(dāng)今最復(fù)雜的離散制造系統(tǒng)之一，具有生產(chǎn)規(guī)模大、周期長(zhǎng)、工序復(fù)雜以及生產(chǎn)工序重入性多等特點(diǎn)[1]。傳統(tǒng)的晶圓盒搬運(yùn)多采用人工搬運(yùn)，但隨著晶圓尺寸的不斷增大，人工搬運(yùn)方式容易造成晶圓跌落和晶圓污染，自動(dòng)化物料運(yùn)輸系統(tǒng)(automatic material handling system，AMHS)應(yīng)運(yùn)而生。根據(jù)生產(chǎn)工藝的不同，具有相同或者相似生產(chǎn)功能的機(jī)臺(tái)會(huì)被放在同一個(gè)區(qū)域(Bay)中。AMHS由幾十甚至數(shù)百臺(tái)高空提升搬運(yùn)車(chē)(overhead hoist transfer，OHT)組成，分布在晶圓廠車(chē)間的Intrabay軌道和Interbay軌道上[2]。早期的AMHS要實(shí)現(xiàn)跨Bay晶圓盒的運(yùn)輸，需要通過(guò)每個(gè)Bay的存儲(chǔ)Stocker中轉(zhuǎn)，并且各個(gè)Bay的OHT只能在內(nèi)部軌道上往復(fù)運(yùn)行。整體式AMHS把Intrabay軌道和Interbay軌道直接相連，實(shí)現(xiàn)了機(jī)臺(tái)到機(jī)臺(tái)的直接運(yùn)輸，大大提高了搬運(yùn)車(chē)輛的運(yùn)輸效率。但是，整體式AMHS使得車(chē)輛能夠走出當(dāng)前Bay，在整個(gè)車(chē)間的運(yùn)輸軌道中行駛，因此車(chē)輛的運(yùn)輸控制變得更加復(fù)雜，車(chē)輛擁堵現(xiàn)象也發(fā)生的更加頻繁[3]。

針對(duì)整體式AMHS中經(jīng)常發(fā)生的擁堵問(wèn)題，本文分析了系統(tǒng)擁堵產(chǎn)生的原因，將OHT在裝卸端口的等待時(shí)間抽象為實(shí)時(shí)交通信息加入到算法的運(yùn)行代價(jià)統(tǒng)計(jì)中。在運(yùn)輸調(diào)度的兩個(gè)階段，任務(wù)指派和路徑規(guī)劃中均加入實(shí)時(shí)交通信息，使系統(tǒng)能夠更靈活應(yīng)對(duì)運(yùn)行中出現(xiàn)的擁堵問(wèn)題。

1 相關(guān)工作

整體式AMHS的運(yùn)輸調(diào)度可以分為兩個(gè)階段，第一階段是運(yùn)輸任務(wù)指派，第二階段是運(yùn)輸路徑規(guī)劃。針對(duì)運(yùn)輸任務(wù)指派問(wèn)題，吳立輝等[4]提出了基于模糊邏輯控制的動(dòng)態(tài)調(diào)度方法，實(shí)時(shí)采集晶圓交貨日期、晶圓等待時(shí)間和系統(tǒng)搬運(yùn)負(fù)載等信息，通過(guò)模糊邏輯動(dòng)態(tài)調(diào)整調(diào)度規(guī)則，從而實(shí)現(xiàn)實(shí)時(shí)有效搬運(yùn)晶圓。夏蓓鑫等[5]使用多目標(biāo)動(dòng)態(tài)調(diào)度方法，首先建立了多目標(biāo)成本模型，使用基于模糊理論的改進(jìn)方法去動(dòng)態(tài)調(diào)整模型中的權(quán)值，最后使用匈牙利算法進(jìn)行求解。Pan Cong等[6]以車(chē)輛到待搬運(yùn)晶圓盒距離為目標(biāo)，針對(duì)Interbay物料運(yùn)輸系統(tǒng)使用改進(jìn)的匈牙利算法進(jìn)行實(shí)時(shí)運(yùn)輸任務(wù)指派，并且提出帶有旁路的軌道構(gòu)型設(shè)計(jì)，降低了擁堵發(fā)生的概率。針對(duì)運(yùn)輸路徑規(guī)劃問(wèn)題，或者更明確為路徑規(guī)劃中的擁堵甚至死鎖問(wèn)題。Robert Schmaler等[7]為了控制擁堵的生成，對(duì)每段軌道的利用率定義了限制。通過(guò)不斷地迭代，最終使每段軌道的利用率相對(duì)保持一個(gè)均衡，達(dá)到預(yù)防擁堵的目的。Sangmin Lee等[8]開(kāi)發(fā)了擁堵監(jiān)督系統(tǒng)軟件，進(jìn)行擁堵等級(jí)的量化和監(jiān)督，然后根據(jù)擁堵標(biāo)準(zhǔn)去優(yōu)化路徑策略。Illhoe Hwang等[9]提出了基于Q(λ)>-learning的動(dòng)態(tài)路徑算法，該算法是一個(gè)路徑導(dǎo)引算法，能夠根據(jù)當(dāng)前判定的擁堵?tīng)顩r和擁堵等級(jí)，動(dòng)態(tài)選擇最優(yōu)的路徑。Zhou Qi等[10]針對(duì)自動(dòng)化物料運(yùn)輸系統(tǒng)中即將發(fā)生的死鎖難以被發(fā)現(xiàn)問(wèn)題，提出了基于圖論中的關(guān)鍵鏈和共享點(diǎn)來(lái)構(gòu)建死鎖檢測(cè)模型，同時(shí)提出了一種高效率并且有效的死鎖避免策略。綜上所述，大部分作者都是將晶圓調(diào)度問(wèn)題分成兩個(gè)問(wèn)題來(lái)研究，要么在任務(wù)指派階段考慮生產(chǎn)系統(tǒng)的系統(tǒng)指標(biāo)，比如晶圓交貨期、系統(tǒng)搬運(yùn)負(fù)載等，作為任務(wù)指派的目標(biāo)成本；要么只關(guān)注路徑規(guī)劃過(guò)程中的擁堵或者死鎖問(wèn)題。本文專(zhuān)注于解決整體式AMHS中車(chē)輛擁堵這一問(wèn)題，實(shí)時(shí)監(jiān)測(cè)系統(tǒng)中的交通狀況，在系統(tǒng)調(diào)度的兩個(gè)階段均考慮擁堵?tīng)顩r，為車(chē)輛分配任務(wù)并動(dòng)態(tài)規(guī)劃相應(yīng)的運(yùn)行路線。

2 基于實(shí)時(shí)交通信息的動(dòng)態(tài)調(diào)度方法

晶圓物料運(yùn)輸?shù)恼{(diào)度包括靜態(tài)調(diào)度和動(dòng)態(tài)調(diào)度兩種類(lèi)型，靜態(tài)調(diào)度的特點(diǎn)是晶圓盒運(yùn)輸任務(wù)一旦分配給某一輛小車(chē)就不再改變，車(chē)輛的運(yùn)輸路徑在確定之后也不會(huì)變化，直至任務(wù)完成。動(dòng)態(tài)調(diào)度的特點(diǎn)是算法會(huì)實(shí)時(shí)監(jiān)測(cè)系統(tǒng)的狀態(tài)，當(dāng)系統(tǒng)狀態(tài)發(fā)生變化，出現(xiàn)更合適的指派方案，晶圓盒和車(chē)輛的對(duì)應(yīng)關(guān)系可以動(dòng)態(tài)調(diào)整。

2.1 整體式布局及其網(wǎng)絡(luò)模型

整體式AMHS把Intrabay軌道和Interbay軌道直接相連，打破之前通過(guò)存儲(chǔ)Stocker中轉(zhuǎn)的方式。先前具有運(yùn)輸和存儲(chǔ)功能的Stocker，只保留存儲(chǔ)功能，被放在中心循環(huán)與每個(gè)Bay的接口附近。目前大部分晶圓廠布局有單脊椎式、雙脊椎式、周邊式、混合布局等[11]，為了增加車(chē)輛的運(yùn)輸路徑，提高車(chē)輛運(yùn)輸效率，本文采用單脊椎式和周邊式混合布局，具體如圖1所示。然后根據(jù)晶圓廠構(gòu)型特點(diǎn)，我們使用圖理論來(lái)建立路徑網(wǎng)絡(luò)模型。假設(shè)G=(N,E)表示整個(gè)晶圓廠的路徑網(wǎng)絡(luò)，不同于大多數(shù)研究者的網(wǎng)絡(luò)劃分方式——把每個(gè)機(jī)臺(tái)和存儲(chǔ)Stocker的裝卸點(diǎn)作為圖的節(jié)點(diǎn)，本文在軌道的交叉路口切分，切分后的每一段路作為網(wǎng)絡(luò)圖的一個(gè)節(jié)點(diǎn)Ni，交叉口上的連接關(guān)系作為圖節(jié)點(diǎn)之間連接的邊Ej。路段作為圖的節(jié)點(diǎn)的方式，可以大大減少圖網(wǎng)絡(luò)中節(jié)點(diǎn)和邊的個(gè)數(shù)，從而提高程序運(yùn)行效率，但是能實(shí)現(xiàn)和先前網(wǎng)絡(luò)劃分相同的功能。

圖1 整體式晶圓廠布局

2.2 動(dòng)態(tài)交通信息的更新

根據(jù)建立的軌道網(wǎng)絡(luò)模型，圖網(wǎng)絡(luò)中邊的權(quán)重用來(lái)記錄系統(tǒng)中的動(dòng)態(tài)交通信息。系統(tǒng)可能發(fā)生擁堵的原因有兩種：一是在加工機(jī)臺(tái)的裝卸載端口，由于AMHS的軌道是單軌，不能發(fā)生超車(chē)現(xiàn)象，所以當(dāng)小車(chē)停在機(jī)臺(tái)的裝卸載口傳送晶圓盒時(shí)，就會(huì)堵塞后面的車(chē)輛，使得后面小車(chē)陸續(xù)停止等待，直到傳送完成才能繼續(xù)行駛；二是發(fā)生在軌道交叉路口，為避免車(chē)輛之間發(fā)生碰撞，轉(zhuǎn)彎行駛小車(chē)會(huì)主動(dòng)停止避讓直行小車(chē)。其中，交叉路口發(fā)生的擁堵一般可以很快解除，但是裝卸載處產(chǎn)生的擁堵需要計(jì)入交通統(tǒng)計(jì)。圖網(wǎng)絡(luò)邊的權(quán)重計(jì)算公式如下所示：

設(shè)車(chē)輛的平均運(yùn)行速度為V，軌道i的長(zhǎng)度為L(zhǎng)i，經(jīng)過(guò)軌道i的時(shí)間為T(mén)i，車(chē)輛的裝載或者卸載平均時(shí)間為T(mén)s，則當(dāng)軌道上只有一輛小車(chē)在裝卸晶圓盒時(shí)，有

Ti=Ts+Li/V

(1)

當(dāng)軌道上有n個(gè)小車(chē)在裝卸晶圓盒時(shí)，有

Ti=n·Ts+Li/V

(2)

當(dāng)小車(chē)停在裝卸載端時(shí)，會(huì)觸發(fā)信號(hào)使得該軌道的權(quán)值增加一個(gè)時(shí)間Ts；在離開(kāi)時(shí)，會(huì)使軌道權(quán)值減去時(shí)間Ts，保證實(shí)時(shí)交通信息的更新。

2.3 運(yùn)輸任務(wù)的動(dòng)態(tài)指派

在運(yùn)輸任務(wù)指派階段，晶圓盒所在機(jī)臺(tái)和車(chē)輛的對(duì)應(yīng)關(guān)系是動(dòng)態(tài)的，隨著交通狀況的變化，上一時(shí)刻機(jī)臺(tái)和車(chē)輛的最優(yōu)匹配在下一時(shí)刻可能已經(jīng)不是最優(yōu)的了。所以，當(dāng)系統(tǒng)中有新的運(yùn)輸任務(wù)生成或者某車(chē)輛把晶圓盒傳送給目的機(jī)臺(tái)后，就會(huì)觸發(fā)系統(tǒng)的重指派過(guò)程。AMHS中的車(chē)輛可以分為3種狀態(tài)：空閑車(chē)輛，指沒(méi)有任何任務(wù)在AMHS軌道上空載運(yùn)行的車(chē)輛；被指派車(chē)輛，指被分配目的地正在前往某機(jī)臺(tái)去接晶圓盒的車(chē)輛；運(yùn)載車(chē)輛，指裝載著晶圓盒前往下一工序加工機(jī)臺(tái)的車(chē)輛。當(dāng)系統(tǒng)條件發(fā)生變化時(shí)，空閑車(chē)輛和被指派車(chē)輛都可以參與運(yùn)輸任務(wù)的動(dòng)態(tài)指派過(guò)程。

2.3.1 動(dòng)態(tài)指派數(shù)學(xué)模型

假設(shè)在運(yùn)輸任務(wù)指派時(shí)刻t，系統(tǒng)中有m個(gè)待搬運(yùn)晶圓盒和n輛可以參與指派的小車(chē)。該指派問(wèn)題可以看作運(yùn)籌學(xué)中的0-1整數(shù)規(guī)劃問(wèn)題，優(yōu)化目標(biāo)為所有車(chē)輛到待運(yùn)輸晶圓盒的總行駛成本最小，其數(shù)學(xué)描述如下

(3)

(4)

(5)

(6)

其中，X為匹配系數(shù)矩陣，Xij∈{0,1},i=1,2…m,j=1,2…n。當(dāng)晶圓盒i被分配給小車(chē)j來(lái)搬運(yùn)時(shí)，Xij=1，否則Xij=0。C為車(chē)輛行駛到待搬運(yùn)晶圓盒所在機(jī)臺(tái)的成本矩陣，Cij即為小車(chē)j到晶圓盒i所在機(jī)臺(tái)的行駛成本值。

2.3.2 成本矩陣構(gòu)成

傳統(tǒng)的成本矩陣構(gòu)成大多基于車(chē)輛到達(dá)各待運(yùn)輸晶圓盒的最短距離，但是由于晶圓廠車(chē)輛繁多，交通狀況復(fù)雜多變，隨時(shí)可能發(fā)生交通擁堵，所以最短距離的路徑往往不能在最短時(shí)間內(nèi)到達(dá)。本文運(yùn)輸任務(wù)指派的目標(biāo)是所有可指派車(chē)輛到達(dá)待運(yùn)輸晶圓盒的總時(shí)間最少，采用基于實(shí)時(shí)交通信息的運(yùn)輸任務(wù)指派方案，把動(dòng)態(tài)交通信息下車(chē)輛到達(dá)晶圓盒的預(yù)計(jì)最短時(shí)間作為行駛成本值。

2.3.3 求解指派問(wèn)題

匈牙利算法[12]可以用來(lái)求解指派問(wèn)題，基本思想是修改矩陣的行或者列，經(jīng)過(guò)不斷修改后，直至使得矩陣的不同行、不同列至少有一個(gè)零元素，從而得到一個(gè)最優(yōu)匹配方案，這個(gè)方案使得當(dāng)前狀態(tài)下所有車(chē)輛的總行駛成本最小。匈牙利算法依據(jù)的原理是：對(duì)于一個(gè)矩陣，將其某一行(列)的元素加上或減去同一個(gè)常數(shù)，得到的新矩陣與原矩陣有相同的解。具體步驟如下所述：

步驟1判斷成本矩陣C是否為方陣，若為方陣則跳到步驟3；否則，執(zhí)行步驟2。

步驟2對(duì)于成本矩陣C：

(1)若m

(2)若m>n，則增加(m-n)列0元素。

步驟3對(duì)成本矩陣進(jìn)行變換，使每行每列至少有一個(gè)元素為0。

(1)讓成本矩陣的每行減去該行的最小元素；

(2)讓成本矩陣的每列減去該列的最小元素。

步驟4對(duì)每一行元素，若該行元素中只包含一個(gè)0，就標(biāo)記該0元素，然后對(duì)該0元素所在的列劃線；若該行沒(méi)有0元素或者包含兩個(gè)及其以上(已經(jīng)被劃去的0元素去掉)，則轉(zhuǎn)下一行。

步驟5對(duì)每一列元素，若該列元素中只包含一個(gè)0，就標(biāo)記該0元素，然后對(duì)該0元素所在的行劃線；若該列沒(méi)有0元素或者包含兩個(gè)及其以上(已經(jīng)被劃去的0元素去掉)，則轉(zhuǎn)下一列。

步驟6檢查被標(biāo)記0元素的個(gè)數(shù)：

(1)若個(gè)數(shù)等于行數(shù)，就找到了最優(yōu)解，跳到步驟7；

(2)若個(gè)數(shù)小于行數(shù)，找出沒(méi)有被劃線的元素的最小元素，對(duì)沒(méi)有被劃線的元素減去最小元素，對(duì)劃線元素交叉點(diǎn)上的元素加上最小元素，轉(zhuǎn)到步驟4。

步驟7求解結(jié)束，被標(biāo)記0元素位置對(duì)應(yīng)的匹配系數(shù)矩陣的值為1，其它為0。

2.4 運(yùn)輸路徑的動(dòng)態(tài)規(guī)劃

車(chē)輛的運(yùn)輸路徑動(dòng)態(tài)規(guī)劃也是一個(gè)重要的問(wèn)題。如果每輛小車(chē)總是通過(guò)最短路徑到達(dá)目的地，這些路徑就會(huì)很容易變成擁堵的，而有些路徑卻只有很少的車(chē)輛通過(guò)。如果小車(chē)不斷地進(jìn)入擁堵區(qū)域，擁堵只會(huì)變得越來(lái)越嚴(yán)重。所以本文在路徑規(guī)劃的過(guò)程中，不去找到達(dá)目的地距離最短的路徑，而會(huì)根據(jù)交通狀況尋找到達(dá)目的地時(shí)間最短的路徑。

2.4.1 路徑表示

當(dāng)小車(chē)從起始節(jié)點(diǎn)Ns接到晶圓盒，前往目標(biāo)節(jié)點(diǎn)Nd時(shí)，小車(chē)就會(huì)自動(dòng)計(jì)算一條前往目的機(jī)臺(tái)的路徑，表示如下

(7)

其中，P為小車(chē)的規(guī)劃路徑，f(Ni，Ni+1)表示節(jié)點(diǎn)Ni和節(jié)點(diǎn)Ni+1的連接邊，邊的值表示節(jié)點(diǎn)Ni+1所代表路段的實(shí)時(shí)交通信息值。

2.4.2 動(dòng)態(tài)路徑規(guī)劃

小車(chē)在前往目的機(jī)臺(tái)的過(guò)程中，規(guī)劃路徑會(huì)根據(jù)前方路徑的權(quán)重變化進(jìn)行動(dòng)態(tài)調(diào)整。在小車(chē)前進(jìn)的過(guò)程中，每次要離開(kāi)節(jié)點(diǎn)Ni時(shí)，就會(huì)觸發(fā)路徑規(guī)劃事件，調(diào)用Dijkstra算法進(jìn)行路徑規(guī)劃，確保Ni+1所代表的路段沒(méi)有發(fā)生變化；如果發(fā)生變化，就進(jìn)入Ni+1代表的新路徑軌道。圖2說(shuō)明了在每個(gè)交叉路口發(fā)生的動(dòng)態(tài)規(guī)劃場(chǎng)景，在小車(chē)剛進(jìn)入路段Nk時(shí)，小車(chē)的預(yù)計(jì)行駛路徑為Nk，Nm，Nm+1，…Nd。但在小車(chē)運(yùn)行過(guò)程中，Nm路段交通狀況發(fā)生變化，出現(xiàn)擁堵。在小車(chē)行駛到Nk路段末端時(shí)，通過(guò)運(yùn)行路徑規(guī)劃算法，得出Nk，Nn，Nn+1，…Nd為預(yù)計(jì)時(shí)間最短的路徑，小車(chē)駛出Nk路段后會(huì)直接進(jìn)入Nn軌道。

圖2 動(dòng)態(tài)路徑規(guī)劃

2.5 算法結(jié)構(gòu)圖

算法結(jié)構(gòu)如圖3所示，在調(diào)度系統(tǒng)運(yùn)行的過(guò)程中，由于不斷產(chǎn)生新的運(yùn)輸任務(wù)，每個(gè)指派周期調(diào)度系統(tǒng)都會(huì)重新統(tǒng)計(jì)所有空閑車(chē)輛和所有待運(yùn)輸任務(wù)，然后進(jìn)行指派；路徑規(guī)劃則是由每輛OHT小車(chē)在每個(gè)交叉路口根據(jù)系統(tǒng)統(tǒng)計(jì)的交通信息進(jìn)行動(dòng)態(tài)路徑規(guī)劃。

圖3 算法結(jié)構(gòu)

3 仿真驗(yàn)證與分析

為了驗(yàn)證本文防擁堵調(diào)度算法的有效性，本文在主頻2.6 GHz、內(nèi)存4 GB、Inter(R) Core(TM) i5-4210M CPU的個(gè)人筆記本上進(jìn)行實(shí)驗(yàn)驗(yàn)證。首先使用Plant Simulation 14.2仿真軟件建立了整體式AMHS仿真模型，其中運(yùn)輸任務(wù)指派仿真模型采用匈牙利算法求解，該算法使用C++語(yǔ)言實(shí)現(xiàn)，并封裝成動(dòng)態(tài)鏈接庫(kù)(.dll)文件被仿真軟件調(diào)用，車(chē)輛的路徑規(guī)劃算法使用軟件內(nèi)置的SimTalk 2.0語(yǔ)言進(jìn)行編寫(xiě)。

Plant Simulation是一個(gè)基于對(duì)象的仿真軟件，提供了一些內(nèi)嵌的仿真對(duì)象。在建立模型時(shí)，用戶可以修改內(nèi)嵌對(duì)象的設(shè)置用于模型搭建，表1列出了本文仿真用到的內(nèi)嵌對(duì)象及其用途。

表1 仿真模型元素

3.1 仿真模型布局及實(shí)驗(yàn)假設(shè)

仿真模型采用脊椎式和周邊式混合布局，包括一個(gè)Interbay內(nèi)循環(huán)軌道和一個(gè)Interbay外循環(huán)軌道，兩個(gè)循環(huán)軌道之間分布12個(gè)Intrabay加工區(qū)，Intrabay軌道和兩個(gè)循環(huán)軌道直接連接，構(gòu)成整體式自動(dòng)化物料運(yùn)輸系統(tǒng)。Interbay內(nèi)循環(huán)軌道長(zhǎng)寬為80 m×4 m，外循環(huán)軌道的長(zhǎng)寬為80 m×58 m，Intrabay軌道的長(zhǎng)寬為26 m×4 m。在Interbay內(nèi)循環(huán)設(shè)有10條捷徑供車(chē)輛換向。每個(gè)Intrabay加工區(qū)設(shè)有6個(gè)晶圓盒的加載端和6個(gè)卸載端，仿真運(yùn)行中系統(tǒng)生成從加載端到卸載端的運(yùn)輸任務(wù)、加載端到Stocker的運(yùn)輸任務(wù)、Stocker到卸載端的運(yùn)輸任務(wù)，運(yùn)輸任務(wù)包括Bay內(nèi)運(yùn)輸和跨Bay運(yùn)輸。仿真模型的布局如圖4所示。

圖4 整體式物料運(yùn)輸系統(tǒng)仿真模型

仿真模型將做如下實(shí)驗(yàn)假設(shè)：①由于小車(chē)的加減速時(shí)間所占比例較小，本文在仿真中忽略加減速時(shí)間，假設(shè)所有小車(chē)以平均速度v運(yùn)行；②我們假定在仿真運(yùn)行過(guò)程中，車(chē)輛、加工機(jī)臺(tái)和Stocker均不會(huì)發(fā)生故障；③為了更加專(zhuān)注于驗(yàn)證算法的優(yōu)劣，減少其它干擾因素，仿真中并沒(méi)有實(shí)現(xiàn)整個(gè)晶圓廠的工作流程，而是建立了From-To表，仿真晶圓盒從一個(gè)機(jī)臺(tái)被搬運(yùn)到下一加工機(jī)臺(tái)的整個(gè)流程。

3.2 混合布局對(duì)搬運(yùn)效率的影響

為了驗(yàn)證混合布局對(duì)晶圓搬運(yùn)效率的影響，本文同時(shí)建立了經(jīng)典的單脊椎式軌道布局進(jìn)行實(shí)驗(yàn)對(duì)比。分別取小車(chē)數(shù)量(輛)為15、20、25、30、35和40，使用基于距離的動(dòng)態(tài)調(diào)度算法進(jìn)行驗(yàn)證。運(yùn)輸性能的評(píng)價(jià)指標(biāo)選擇晶圓盒平均等待時(shí)間和平均運(yùn)輸周期。仿真運(yùn)行30天，重復(fù)3次。

通過(guò)圖5可以看出，在車(chē)輛數(shù)量為15-20的階段，兩種布局由于車(chē)輛不能及時(shí)響應(yīng)晶圓盒運(yùn)輸任務(wù)，導(dǎo)致大量晶圓盒運(yùn)輸任務(wù)堆積等待，平均等待時(shí)間要占總運(yùn)輸時(shí)間的70%-80%。隨著運(yùn)輸車(chē)輛的增多，晶圓盒平均運(yùn)輸周期快速下降，曲線在小車(chē)數(shù)量為25輛-30輛時(shí)開(kāi)始變得平緩，晶圓盒的平均等待時(shí)間也明顯降低，占比降到了總運(yùn)輸時(shí)間的20%-30%。相比較于單脊椎式布局，混合軌道布局對(duì)應(yīng)的曲線下降速度更快，最終達(dá)到平緩時(shí)，其對(duì)應(yīng)的晶圓盒平均運(yùn)輸周期也明顯低于單脊椎式軌道布局。雖然在30輛-40輛小車(chē)時(shí)平均等待時(shí)間相近，但是由于混合布局有更多的運(yùn)輸路徑，從一個(gè)加工區(qū)到達(dá)另一個(gè)加工區(qū)就會(huì)有更合適的路徑選擇，從而整體的平均運(yùn)輸周期明顯低于單脊椎式布局。

圖5 混合布局對(duì)運(yùn)輸性能的影響

3.3 防擁堵調(diào)度算法的有效性

根據(jù)本文2.2分析，交通擁堵產(chǎn)生的原因主要是由于小車(chē)停留在加工機(jī)臺(tái)的裝卸載端口裝卸晶圓盒，堵塞了后續(xù)小車(chē)的前進(jìn)道路。已知小車(chē)平均裝卸載時(shí)間為30 s，我們對(duì)軌道的動(dòng)態(tài)交通權(quán)值做以下設(shè)定，當(dāng)小車(chē)停止在軌道裝卸載端時(shí)，軌道的行駛成本時(shí)間增加30 s；當(dāng)小車(chē)開(kāi)始運(yùn)行，軌道的行駛成本時(shí)間減少30 s。但是由于其它車(chē)輛統(tǒng)計(jì)交通信息時(shí)，裝卸載車(chē)輛的實(shí)際停留時(shí)間已經(jīng)小于30 s，所以實(shí)際軌道成本的增加為α·30 s。

圖6設(shè)定運(yùn)輸小車(chē)數(shù)量為26輛，α分別取0-1中的數(shù)，以0.1等分，得出α值與晶圓盒平均運(yùn)輸周期之間的關(guān)系。通過(guò)觀察可以看出，當(dāng)α等于0的時(shí)候，調(diào)度不考慮系統(tǒng)的交通狀況，完全根據(jù)最短距離進(jìn)行分配指派和路徑規(guī)劃，其對(duì)應(yīng)的晶圓盒平均運(yùn)輸周期為04∶15。α值從0.1增到0.5，運(yùn)輸時(shí)間總體呈下降趨勢(shì)，在0.5時(shí)運(yùn)輸周期最短為04∶10。在α值從0.6增到1，運(yùn)輸周期呈上升趨勢(shì)，在α等于0.7時(shí)超過(guò)動(dòng)態(tài)最短距離調(diào)度方法。所以本文取α等于0.5進(jìn)行接下來(lái)的實(shí)驗(yàn)。

圖6 α值與晶圓盒平均運(yùn)輸周期之間的關(guān)系

在接下來(lái)的實(shí)驗(yàn)中，分別選擇20輛、22輛、24輛、26輛、28輛、30輛小車(chē)進(jìn)行實(shí)驗(yàn)，同時(shí)把本文提出的方法和基于距離的靜態(tài)調(diào)度方法和基于距離的動(dòng)態(tài)調(diào)度方法進(jìn)行對(duì)比驗(yàn)證，以下為3種方法的簡(jiǎn)要比較：

(1)基于距離的靜態(tài)調(diào)度方法(static scheduling based on distance，SSBD)：該方法是在調(diào)度發(fā)生時(shí)刻，根據(jù)當(dāng)前系統(tǒng)最優(yōu)匹配關(guān)系進(jìn)行運(yùn)輸任務(wù)分配指派，同時(shí)進(jìn)行車(chē)輛的路徑規(guī)劃。當(dāng)晶圓加工完成，會(huì)尋找距離該晶圓盒最近的空閑車(chē)輛，如果找到空閑車(chē)輛，就指派該車(chē)去運(yùn)輸晶圓盒；否則將該運(yùn)輸任務(wù)加入任務(wù)等待列表。當(dāng)出現(xiàn)空閑車(chē)輛，會(huì)去查找等待列表，執(zhí)行該任務(wù)。所有運(yùn)輸任務(wù)一旦被分配，就一定會(huì)由被分配車(chē)輛將任務(wù)執(zhí)行完，即使中間出現(xiàn)更優(yōu)的匹配結(jié)果，也不會(huì)改變。

(2)基于距離的動(dòng)態(tài)調(diào)度方法(dynamic scheduling based on distance，DSBD)：該方法可以隨著系統(tǒng)運(yùn)行狀況的變化，不斷更新指派結(jié)果。當(dāng)有新的運(yùn)輸任務(wù)生成或者有新的空閑車(chē)輛出現(xiàn)，系統(tǒng)會(huì)自動(dòng)運(yùn)行重調(diào)度程序，依據(jù)總運(yùn)行距離最短的原則，為運(yùn)輸任務(wù)重新分配運(yùn)載車(chē)輛。在運(yùn)輸晶圓盒前往目的機(jī)臺(tái)的過(guò)程中，運(yùn)輸路徑不會(huì)變化。

(3)基于實(shí)時(shí)交通信息的動(dòng)態(tài)調(diào)度方法(dynamic scheduling based on real-time traffic information，DSBRTI)：該方法可以不斷統(tǒng)計(jì)系統(tǒng)的交通狀況，動(dòng)態(tài)更新每條道路的行駛成本。當(dāng)有新的運(yùn)輸任務(wù)生成或者有新的空閑車(chē)輛出現(xiàn)時(shí)，系統(tǒng)會(huì)自動(dòng)運(yùn)行重調(diào)度程序，依據(jù)總運(yùn)行時(shí)間最短的原則，為運(yùn)輸任務(wù)分配運(yùn)載車(chē)輛。在路徑規(guī)劃階段，小車(chē)每當(dāng)要離開(kāi)當(dāng)前路段，就會(huì)調(diào)用路徑規(guī)劃算法，指導(dǎo)小車(chē)進(jìn)入下一軌道。

在仿真開(kāi)始之前，已經(jīng)建立了From-To表設(shè)置運(yùn)輸任務(wù)產(chǎn)生的時(shí)間及對(duì)應(yīng)的機(jī)臺(tái)，頻率為每分鐘出現(xiàn)6個(gè)-8個(gè)任務(wù)，仿真時(shí)間為100天，重復(fù)3次。圖7(a)為3種方法所對(duì)應(yīng)的晶圓盒平均運(yùn)輸周期，可以看出，動(dòng)態(tài)調(diào)度算法性能明顯優(yōu)于靜態(tài)調(diào)度算法。在小車(chē)數(shù)量到達(dá)26時(shí)，動(dòng)態(tài)調(diào)度方法的晶圓盒運(yùn)輸周期開(kāi)始趨于平穩(wěn)，而靜態(tài)調(diào)度方法仍保持著下降趨勢(shì)。對(duì)比DSBD，DSBRTI下降更加平滑，下降速度更快，其平均運(yùn)輸時(shí)間也明顯少于其它兩種調(diào)度方法。圖7(b)為3種方法所對(duì)應(yīng)的平均等待時(shí)間，在車(chē)輛數(shù)量為20輛-22輛時(shí)，DSBRTI和DSBD的平均等待時(shí)間分別占總運(yùn)輸時(shí)間的65%和70%，SSBD的平均等待時(shí)間占總運(yùn)輸時(shí)間的80%。隨著車(chē)輛數(shù)目的增多，DSBRTI和DSBD的平均等待時(shí)間占比快速下降，時(shí)間從06∶20下降到00∶45。但是SSBD的平均等待時(shí)間占比依舊為80%左右。可以得出結(jié)論，SSBD的平均運(yùn)輸周期遠(yuǎn)遠(yuǎn)高于DSBRTI和DSBD，是由于SSBD的平均等待時(shí)間占比居高不下，大部分晶圓盒運(yùn)輸任務(wù)無(wú)法被及時(shí)響應(yīng)，已加工完成的晶圓大量堆積。

表2為3種方法對(duì)應(yīng)的擁堵發(fā)生次數(shù)統(tǒng)計(jì)。可以看出，隨著車(chē)輛數(shù)目的增多，3種方法的擁堵發(fā)生次數(shù)也在逐漸增多，SSBD和DSBRTI的擁堵發(fā)生次數(shù)明顯少于DSBD。但是，SSBD是靜態(tài)調(diào)度，會(huì)出現(xiàn)很多空車(chē)行駛?cè)ソ舆h(yuǎn)處晶圓盒的情況，總的停車(chē)裝卸載次數(shù)更少，所以擁堵發(fā)生次數(shù)會(huì)比DSBD少。而DSBRTI既能保證較高的停車(chē)裝卸載次數(shù)、高運(yùn)輸效率，又有較低的擁堵率。綜合圖7和表2的統(tǒng)計(jì)，可以得出結(jié)論，DSBRTI的綜合性能優(yōu)于SSBD和DSBD。

圖7 3種方法運(yùn)輸性能的對(duì)比

表2 擁堵發(fā)生次數(shù)

4 結(jié)束語(yǔ)

本文針對(duì)整體式自動(dòng)化物料運(yùn)輸系統(tǒng)，使用脊椎式與周邊式相結(jié)合的軌道布局，增加了車(chē)輛運(yùn)輸路徑，提高了晶圓盒運(yùn)輸效率。以解決車(chē)輛擁堵問(wèn)題為目標(biāo)，針對(duì)擁堵問(wèn)題的產(chǎn)生原因——車(chē)輛停靠裝卸載晶圓盒阻礙了后方車(chē)輛的運(yùn)行，提出了基于實(shí)時(shí)交通信息的兩階段動(dòng)態(tài)調(diào)度算法。實(shí)驗(yàn)部分與基于距離的靜態(tài)調(diào)度算法和動(dòng)態(tài)調(diào)度算法進(jìn)行對(duì)比，首先得出動(dòng)態(tài)調(diào)度算法性能明顯優(yōu)于靜態(tài)調(diào)度算法；其次基于交通信息的動(dòng)態(tài)調(diào)度算法性能更加穩(wěn)定，比基于距離的動(dòng)態(tài)調(diào)度算法有更低的擁堵率，晶圓盒平均運(yùn)輸周期也更短。