**Dynamic dispatching for interbay automated material handling with lot
targeting using improved parallel multiple-objective genetic algorithm**
Release Date: 10 March 2021
### 論文介紹：多目標平行遺傳算法在晶圓製造系統中的應用
#### 摘要
本文提出了一種改進的平行多目標遺傳算法（IPMOGA），用於解決晶圓製造系統中的車輛調度和多目標選擇問題。該算法利用平行策略、多目標演化過程和局部搜索策略，以提高解的質量和優化多個子目標。數值實驗結果顯示，該算法在綜合性能方面具有顯著優勢。
#### 第一章：引言
隨著晶圓尺寸從200mm增加到300mm，甚至發展到450mm，傳統的手動物料處理方法已經無法滿足晶圓加工的需求，因此自動化物料處理系統（AMHS）成為晶圓工廠中不可或缺的一部分。
AMHS通常由三個子系統組成：運輸軌道、 stocker和自動化車輛。運輸軌道通常是單軌系統，自動化車輛沿著軌道在不同stocker 之間轉移晶圓LOT。每個 stocker作為輸入/輸出端口，並為相應的機台內部系統臨時存儲晶圓LOT。
目前的針對AMHS的研究主要集中在**車輛調度**，包括車輛派遣和路徑規劃，但忽略晶圓LOT的目標地與各機台的關係（忽略了在進入目標區域之前對批次的目標選擇），例如，製程A的晶圓LOT動到製程B，但對於製程B，可能有多台機台可以進行該製程操作。如果可以將車輛調度與晶圓LOT的目標地選擇結合進行綜合調度的話，很有機會可以達到更好的安排（例如等待時間減少OR減少系統塞車情形），在綜合調度問題中，車輛調度與晶圓LOT目標選擇之間存在複雜的耦合關係，這大大增加了問題的複雜性。這種耦合關係意味著在選擇最佳路徑和目標區域時，必須同時考慮多個因素，如車輛的實時位置、機台的可用性和當前的生產負荷等。因此，簡單的線性加權方法難以滿足這些多目標優化的需求，需要更先進的算法來處理這種複雜的優化問題。
本文提出了一種改進的平行多目標遺傳算法（IPMOGA），用於解決晶圓製造系統中的車輛調度和晶圓LOT目標選擇問題。該算法利用平行策略、多目標演化過程和局部搜索策略，以提高解的質量和優化多個子目標。數值實驗結果顯示，該算法在綜合性能方面具有顯著優勢，為提升晶圓製造系統的運行效率提供了一種有效的解決方案。
#### 第二章：文獻回顧
在研究自動化物料處理系統（AMHS）中的**車輛調度(Dispatching)** 問題時，眾多學者提出了各種調度規則和方法。這些方法大致可分為單屬性調度規則、多屬性調度規則、層次調度規則和重新分配方法。
<u>單屬性調度規則</u>:
單屬性調度規則是最簡單的一類調度方法，通常根據單一屬性（如最短距離、最短時間等）來進行調度。Bozer和Hsieh（2005）提出了一種修改的最短旅行距離（MSTD）規則，該規則在考慮交付時間和當前車輛位置的基礎上進行調度。
<u>多屬性調度規則</u>:
多屬性調度規則同時考慮多個屬性來進行調度。Singh（2011）提出了創新的調度規則，並使用離散事件模擬評估了這些規則在多台自動導引車（AGV）上的性能。這些規則通過綜合考慮多個影響因素，能夠提供比單屬性調度規則更優的調度效果。
<u>層次調度規則</u>:
層次調度規則通常首先對晶圓批次進行優先級排序，然後根據專門設計的調度策略分配車輛。這些方法先確定需要優先處理的晶圓批次，然後再分配合適的車輛以最大化調度效率。某些研究中，首先使用模糊邏輯方法確定候選晶圓批次的優先級，然後基於匈牙利算法將空閒的運輸車輛分配給優先級較高的晶圓批次。
<u>重新分配方法</u>:
重新分配方法是指在運輸過程中根據實時狀況對車輛進行重新調度，以提高系統的靈活性和適應性。
AMHS系統除了車輛調度(Dispatching)以外還需要去安排車輛的路徑，**路徑規劃方法**可以分為靜態路徑規劃和動態路徑規劃。
<u>靜態路徑規劃</u>：
是在離線模式下計算各個位置之間的最優路徑，並在執行運輸任務時選擇預先確定的最優路徑。由於各位置之間的運輸路徑提前確定，靜態路徑規劃方法實施起來較為簡單，但相比動態路徑規劃方法缺乏靈活性。
<u>動態路徑規劃</u>：
主要用於避免車輛之間的衝突。Smolic-Rocak等（2009）提出了一種針對多AGV的動態路徑規劃方法，該方法通過插入適當的時間窗口和窗口重疊測試來評估特定路徑的可行性。Bartlett等（2014）開發了一種基於擁堵感知的動態路徑規劃策略，該策略隨著擁堵狀況的變化重新規劃車輛路徑，顯著減少了嚴重擁堵的頻率，並適度改善了穩態路徑性能。
此外，還有基於<u>強化學習的動態路徑規劃算法</u>，該算法利用實時信息指導每輛車輛避開擁堵並找到高效路徑。
**綜合調度**
儘管已有大量研究集中於車輛調度與路徑選擇，但涉及車輛調度與多目標選擇綜合調度的研究較少。
#### 第三章：問題描述與建模
在自動化物料處理系統（AMHS）中，所有的調度和計算程序都是基於物料處理過程的實時信息進行開發的。
綜合調度過程主要考慮三個部分：
1.LOT Targeting:
包含LOT晶圓的Priorty、製程順序、晶圓的時效性、Stocker的緩衝狀態
2.OHT dispatching:
其中有 m可用的 OHT 和 n 個晶圓批次隨時等待調度。調度問題可以表述為作為整數規劃模型。
3.OHT routing:
OHT 運輸過程是運輸LOT的處理過程，先經由特定路線到達目標處理區後裝載LOT到車輛上。花費時間過程也是整個處理週期的一部分。
**目標式：**
OHT分別有運行中的OHT與閒置的OHT，目標式的前半部份描述運行中OHT的成本包含LOT Targeting成本（製程表現）與路徑成本，後半部份描述閒置OHT的成本包含Dispatching與Routing
**限制式：**
1.晶圓批次只能選擇一個處理區域：
2.每個車輛只能選擇一條可行軌道：
3.每個OHT只能在候選路徑中的一個儲料器上裝載晶圓批次：
4.每條路徑只能對應一個等待交付的晶圓批次：
5.每個等待任務只能由一個OHT完成：
6.在任何時間段內，每條軌道上只能有一個OHT：
#### 第四章：基於IPMOGA的解決策略
介紹了改進的平行多目標遺傳算法的設計和實現：
- **4.1 平行策略**：現有4種平行策略手法：master-slave model, coarse-grained model, fine-grained model,and hybrid model, 論文提出的方法是基於coarse-grained model,將母體分成多個子集，每個子集在各自的處理器上運行GA。子集間會交換解（基因），引入更多的優秀個體，豐富群體的多樣性，可以防止早熟收斂，使其成為遺傳演算法中適應性最強、應用最廣泛的平行模型
- **4.2 遺傳操作算子**：描述了遺傳算法中的路徑編碼、初始解、交配和突變操作。
- 路徑編碼：節點集N:假設有5個節點{n0,n1,n2,n3,n4}
邊集E: 代表節點間的連接，例如
{(n0,n1),(n1,n2),(n2,n3),(n3,n4),(n0,n2),(n1,n3),(n2,n4)} 路徑序列編號：
(n0,n1)→1
(n1,n2)→2
(n2,n3)→3
(n3,n4)→4
(n0,n2)→5
(n1,n3)→6
(n2,n4)→7
多參數串聯編碼：
如果有多個OHT需要同時進行調度，可以使用多參數串聯編碼來表示每個OHT的路徑。假設有兩個OHT，每個OHT的路徑可以分別表示為兩個序列，例如
OHT1路徑:{1,2,3}
OHT2路徑：{5,3,4}
將兩個OHT的路徑串聯起來表示為一個染色體：
染色體:{1,2,3\ 5,3,4}
- 初始解：因為隨機產生的規則會產生大量不可用的路徑，論文以Dijkastra演算法尋找各Node到其他Node的最短路徑當作初始最佳路徑。
使用Dijkastra-Floyd算法計算出的最短路徑可能包括：
{n0,n1,n2,n3,n4}
{n0,n2,n4}
{n0,n1,n3,n4}
從中選擇部分最優路徑作為初始解：
初始解1：{n0,n1,n2,n3,n4}= {1,2,3,4}
初始解2：{n0,n2,n4}
初始解3：{n0,n1,n3,n4}
這些初始解以節點序列的形式表示，並將在後續的遺傳操作中進行優化。
- 交配和突變操作：
交配：將兩條染色體在相同的鏈接處進行交換。例如，對染色體 {1,2,3,4} 和 {5,6,7,4} 進行交叉操作，可能得到新的染色體{1,2,7,4} 和{5,6,3,4}。
突變：變異算子由三個操作組成。 (1)從染色體上隨機移除一個序號(不包括起始號和結束號)； (2)從染色體中隨機選擇一個節點插入新的序號； (3)在個體中隨機選擇一個序號，並替換為新的序號。
- **4.3 適應度評估**：介紹了適應度函數的設計，包括平均交付時間、最大交付時間和平均處理周期的計算方法。
#### 第五章：數值實驗
本章通過數值實驗驗證了所提出算法的有效性。實驗結果表明，IPMOGA在平均交付時間、最大交付時間和平均處理周期等方面顯示出顯著優勢，並與其他幾種常見調度策略進行了比較分析。
設計的場景有127台設備、23種製程
#### 第六章：結論與未來工作
本章總結了本文的主要貢獻，指出了IPMOGA在提升晶圓製造系統調度效率方面的潛力。
附件：
Sign in with Wallet
Connect another wallet