吳立輝 朱登潔 張 潔

1.河南工業(yè)大學，鄭州，450007 2.上海交通大學，上海，200240

0 引言

半導體晶圓制造系統(tǒng)是當今最為復雜的離散制造系統(tǒng)之一，具有多重入流、多品種大規(guī)模在制品、加工工序復雜、加工周期長、設備昂貴等特點［1］。一條典型的300mm晶圓制造系統(tǒng)通常有數(shù)千卡晶圓在制品（晶圓加工過程以“卡”為計量單位進行搬運，每個晶圓卡包括25片晶圓），每卡晶圓大概包括200～600道加工工序，20～40次重入各類型加工設備。為完成全部工序，每卡晶圓需要被搬運上千次，運輸?shù)木嚯x達12872～16090m（8～10英里）［2］。因此，自動化物料運輸系統(tǒng)成為晶圓制造系統(tǒng)的重要組成部分。其中，Intrabay物料運輸系統(tǒng)（簡稱Intrabay系統(tǒng)）是自動化物料運輸系統(tǒng)的主要組成部分，Intrabay系統(tǒng)運行效率的提高，對提高自動化物料運輸系統(tǒng)及晶圓制造系統(tǒng)的系統(tǒng)性能具有重要意義［3］。

Intrabay系統(tǒng)具有大規(guī)模、動態(tài)、實時性和隨機性等特點，國內外針對Intrabay系統(tǒng)調度問題進行了大量研究。Lin等［4］和 Hasenbein等［5］認為，Intrabay系統(tǒng)的調度策略對晶圓卡等待運輸時間、晶圓卡搬運時間等性能指標有顯著影響。Liu等［6］和Liao等［7］采用了數(shù)學規(guī)劃方法對小規(guī)模Intrabay系統(tǒng)調度問題進行全局優(yōu)化求解。Liao等［8］和 Wang［9］提出了一種分類優(yōu)先級規(guī)則的Intrabay系統(tǒng)調度方法，該方法可明顯縮短緊急晶圓卡的搬運時間。Lin等［10］將先到先服務規(guī)則用于Intrabay系統(tǒng)調度，并將推拉結合的策略用于物料運輸小車的配送。Le－anh等［11］提出了一種基于組合派發(fā)規(guī)則方法的Intrabay系統(tǒng)調度方法，晶圓卡平均等待時間和運輸小車有效利用率等指標得到明顯提高。然而，整數(shù)規(guī)劃方法主要適用于小規(guī)模的物料運輸問題優(yōu)化求解?；趩?多規(guī)則的啟發(fā)式調度方法通常適用于穩(wěn)態(tài)環(huán)境下的系統(tǒng)單/多目標優(yōu)化調度，難以滿足隨機、動態(tài)變化環(huán)境下的Intrabay系統(tǒng)多目標調度優(yōu)化需求。

本文在對Intrabay調度問題分析的基礎上，提出了一種基于模糊邏輯和匈牙利方法的Intrabay系統(tǒng)多目標實時調度方法，該方法實時響應運輸小車空載和晶圓卡請求運輸?shù)仁录?，對各動態(tài)事件時刻的Intrabay系統(tǒng)調度子問題進行多目標優(yōu)化求解。針對Intrabay系統(tǒng)調度子問題，在基于模糊邏輯方法對晶圓卡運輸優(yōu)先級排序的基礎上，采用匈牙利方法對Intrabay系統(tǒng)的運輸小車和晶圓卡進行優(yōu)化指派，并采用貪婪優(yōu)化的運輸小車搬運策略指導運輸小車搬運晶圓卡，從而形成優(yōu)化的Intrabay系統(tǒng)調度方法，提高了Intrabay系統(tǒng)和晶圓加工系統(tǒng)的多目標綜合性能。

1 Intrabay系統(tǒng)調度問題

Intrabay系統(tǒng)通常采用單閉環(huán)型軌道布局（圖1），由運輸導軌、存儲倉庫、晶圓加工設備裝/卸緩沖區(qū)和運輸小車組成，晶圓加工設備裝/卸緩沖區(qū)與晶圓加工設備相連，存儲倉庫與Intrabay系統(tǒng)連接。Intrabay系統(tǒng)有多臺運輸小車，負責將晶圓卡按加工工藝運輸?shù)礁骶A加工設備或存儲倉庫。Intrabay系統(tǒng)的運輸任務十分龐大，待搬運晶圓卡競爭運輸小車以及運輸小車之間堵塞等現(xiàn)象頻繁發(fā)生，晶圓卡搬運過程容易出現(xiàn)死鎖，使得Intrabay系統(tǒng)運行效率降低。因此，需通過Intrabay系統(tǒng)調度以合理安排運輸小車搬運晶圓卡，提高Intrabay系統(tǒng)和晶圓加工系統(tǒng)的多目標綜合效率。

圖1 Intrabay系統(tǒng)布局示意圖

Intrabay系統(tǒng)調度問題有如下假設和約束：①晶圓卡每道工序的加工時間是確定的；②每個晶圓卡在加工設備上完成當前工序后，根據(jù)加工工藝等待運輸小車搬運到下一工序晶圓加工設備或存儲倉庫；③存儲倉庫的容量足夠大；④每個運輸小車1次只能搬運1個晶圓卡；⑤各運輸小車互相獨立，且運行過程中不能互相穿越；⑥為避免運輸小車沖突，每段運輸導軌任意時刻只允許一臺運輸小車運行；⑦晶圓卡部分加工工序間的等待時間具有時效性約束；⑧晶圓卡搬運過程中存在死鎖。

2 Intrabay系統(tǒng)多目標實時調度方法

Intrabay系統(tǒng)多目標實時調度方法框架如圖2所示。該方法實時響應運輸小車空載和晶圓卡請求運輸?shù)仁录瑢Ω鲃討B(tài)事件時刻的Intrabay系統(tǒng)調度子問題進行求解。針對Intrabay系統(tǒng)調度子問題，首先，利用模糊邏輯方法快速響應和動態(tài)推理決策的優(yōu)點［13］，建立基于模糊邏輯的晶圓卡運輸優(yōu)先級動態(tài)決策模型，該模型根據(jù)晶圓交貨期滿足率參數(shù)、晶圓卡的等待時間參數(shù)和In－trabay系統(tǒng)的負載參數(shù)，對等待搬運晶圓卡的運輸優(yōu)先級進行動態(tài)決策，從而提高晶圓交貨期滿足率和晶圓產出量，減少晶圓卡總的運輸時間和晶圓加工周期。其次，利用匈牙利算法快速全局優(yōu)化求解的優(yōu)點［14］，對空閑運輸小車和高優(yōu)先級的晶圓卡進行優(yōu)化指派，減少搬運過程中運輸小車的臨時性堵塞，從而縮短晶圓卡被運輸小車搬運時間和晶圓加工周期，提高運輸小車搬運量。再次，根據(jù)優(yōu)化指派結果，提出基于貪婪優(yōu)化的運輸小車搬運策略，該策略根據(jù)當前晶圓卡所處加工設備和下一工序加工設備（目標加工設備）的狀態(tài)，指導相應運輸小車選擇推/拉的搬運策略，以減少加工設備的空載等待時間；在推/拉式搬運過程中，運輸小車根據(jù)晶圓卡目標加工設備的輸入端口的狀態(tài)，選擇晶圓卡的臨時存儲位置，避免晶圓卡目標加工設備的輸入端口負載導致運輸小車無法卸載晶圓卡的死鎖現(xiàn)象，從而提高運輸小車搬運量和晶圓產出量。

圖2 Intrabay系統(tǒng)的多目標實時調度方法框架

2.1 基于模糊邏輯的晶圓卡運輸優(yōu)先級動態(tài)決策模型

基于模糊邏輯的晶圓卡運輸優(yōu)先級動態(tài)決策模型建立過程包括：定義輸入/輸出變量、確定輸入/輸出變量的隸屬度函數(shù)，建立模糊推理規(guī)則表，確定模糊推理策略、規(guī)則聚合策略和解模糊化策略等。晶圓卡運輸優(yōu)先級動態(tài)決策模型的輸出變量為晶圓卡運輸優(yōu)先級，模糊推理策略采用Mamdani方法，規(guī)則聚合策略選用最大－最小規(guī)則，解模糊化策略采用最大隸屬度函數(shù)方法［15］。Mamdani推理策略、最大－最小規(guī)則聚合策略和最大隸屬度函數(shù)的解模糊化策略的具體描述請參考文獻［16］。

2.1.1 輸入變量

晶圓卡運輸優(yōu)先級動態(tài)決策模型的輸入變量包括：晶圓交貨期滿足率參數(shù)、晶圓卡的等待時間參數(shù)和Intrabay系統(tǒng)的負載參數(shù)，分別定義為x1、x2和x3。

（1）晶圓交貨期滿足率參數(shù)x1，表示Intrabay系統(tǒng)中的晶圓交貨期緊急程度，可描述為

式中，F(xiàn)ac為Intrabay系統(tǒng)中已完成加工晶圓的平均交貨期松弛系數(shù)；RTi為晶圓i距離指定交貨期的剩余時間；RPi為晶圓i剩余工序的加工時間；PTj為晶圓j各工序總的加工時間；CTj為晶圓j交貨周期；k為已完成加工的晶圓數(shù)量。

（2）晶圓卡的等待時間參數(shù)x2，表示晶圓卡在當前設備或存儲倉庫輸出端口的等待時間，可描述為

式中，AW為Intrabay系統(tǒng)中晶圓卡的平均等待時間；CWi為晶圓卡i的當前等待時間。

（3）Intrabay系統(tǒng)的負載參數(shù)x3，表示Intra－bay系統(tǒng)當前負載率的大小，可描述為

式中，NC為Intrabay系統(tǒng)中等待運輸?shù)木A卡的數(shù)量；NV為Intrabay系統(tǒng)中運輸小車的數(shù)量。

2.1.2 隸屬度函數(shù)和模糊規(guī)則表

基于模糊邏輯的晶圓卡運輸優(yōu)先級動態(tài)決策模型采用三角型和梯型隸屬度函數(shù)［17］，建立的輸入輸出變量隸屬度函數(shù)如表1所示。在調研獲取專家經驗的基礎上，采用實驗設計方法對各模糊語言變量的模糊值進行組合實驗，選取其中實驗結果較優(yōu)的輸入輸出模糊語言變量組合值建立的模糊規(guī)則表如表2所示。

表1 晶圓卡運輸優(yōu)先級動態(tài)決策模型輸入和輸出變量的隸屬度函數(shù)

表2 晶圓卡運輸優(yōu)先級動態(tài)決策模型的模糊規(guī)則表

2.2 基于匈牙利算法的物料運輸任務指派方法

設定運輸小車空載和晶圓卡請求運輸?shù)仁录r刻，Intrabay系統(tǒng)中有Nw個等待運輸?shù)木A卡和m個空載運輸小車。當Nw＞m時，選取優(yōu)先級較高的前m個晶圓卡作為物料運輸調度的晶圓卡子集合。則物料運輸調度的晶圓卡數(shù)量n可表示為n＝min（m，Nw）。m個運輸小車搬運n個晶圓卡的Intrabay系統(tǒng)調度子問題可描述為

式中，C0為晶圓卡運輸成本矩陣；Cij為運輸小車j搬運晶圓卡i所需要的運輸時間；Xij為匹配系數(shù)，當指定采用運輸小車j搬運晶圓卡i時，則對應的Xij值為1，否則為0。

以上Intrabay系統(tǒng)調度子問題可等效為運輸小車集合向晶圓卡集合派發(fā)的二部圖匹配問題。而匈牙利方法可快速獲得二部圖匹配問題的全局優(yōu)化解［18］，有效減少運輸小車的臨時性堵塞，適合該子問題的求解?；谛傺览椒ǖ木唧w求解過程可參考文獻［18］。

2.3 基于貪婪優(yōu)化的運輸小車搬運策略

基于貪婪優(yōu)化的運輸小車搬運策略采用推/拉結合的思想［19］，根據(jù)當前晶圓卡所處加工設備和目標加工設備的狀態(tài)，指導運輸小車選擇推/拉的搬運策略對當前晶圓卡進行搬運，如圖3所示。該方法的運行邏輯描述如下：

圖3 基于貪婪優(yōu)化的運輸小車搬運策略

（1）運輸小車判斷當前晶圓卡的目標加工設備屬性，當目標加工設備為存儲倉庫時，運輸小車將當前晶圓卡搬運至存儲倉庫；否則，進入步驟（2）。

（2）當有其他晶圓卡請求進入當前晶圓卡所處加工設備時，運輸小車基于推式的搬運策略將當前晶圓卡搬離其所處加工設備，搬運過程中，運輸小車根據(jù)當前晶圓卡的目標加工設備輸入端口的狀態(tài)空閑與否，選擇將晶圓卡搬運至目標加工設備或存儲倉庫，避免晶圓卡目標加工設備的輸入端口負載導致運輸小車無法卸載晶圓卡的死鎖現(xiàn)象。否則，當沒有其他晶圓卡請求進入當前晶圓卡所處加工設備時，進入步驟（3）。

（3）運輸小車基于拉式的搬運策略對當前晶圓卡進行搬運，當晶圓卡的目標加工設備輸入端口空閑時，運輸小車將該晶圓卡搬運至目標加工設備；當晶圓卡的目標加工設備輸入端口有負載時，運輸小車取消當前運輸任務，避免晶圓卡目標加工設備的輸入端口負載導致運輸小車無法卸載晶圓卡的死鎖現(xiàn)象。

3 仿真實驗分析

采用某300mm晶圓制造系統(tǒng)的Intrabay系統(tǒng)的生產數(shù)據(jù)，基于eM－Plant軟件建立Intrabay系統(tǒng)仿真模型，對提出的Intrabay系統(tǒng)多目標實時調度方法進行實驗分析。Intrabay子系統(tǒng)共包括28臺設備和2個存儲倉庫，運輸軌道長108m，運輸小車運行速度1m/s，晶圓卡裝載和卸載的時間為16s。設定Intrabay子系統(tǒng)共加工2種晶圓產品（A、B），每個晶圓卡重入Intrabay系統(tǒng)次數(shù)為5次，晶圓投料比例為3∶2，投料時間服從正態(tài)分布。Intrabay系統(tǒng)調度算法采用C＋＋語言實現(xiàn)，并通過eM－Plant軟件的C/C C＋＋接口調用。仿真實驗運行時間周期設定為15天；運輸小車數(shù)量分別選取為5臺、6臺、7臺，系統(tǒng)負載率分別選取為90%、100%和110%，共組成9種實驗場景。

為了驗證本文提出的多目標實時調度方法的有效性，將其與傳統(tǒng)的先到先服務規(guī)則（簡稱FEFS）和最高優(yōu)先級規(guī)則（簡稱HP）進行比較，F(xiàn)EFS和HP規(guī)則方法是晶圓制造工廠Intrabay系統(tǒng)調度中最常采用且被驗證為有效的調度方法［20－21］，比較的性能指標采用綜合性能指標函數(shù)D。實驗比較結果如圖4所示，從圖4可以看出，GDP方法在9種實驗場景下的綜合期望函數(shù)值都優(yōu)于傳統(tǒng)的FEFS和HP方法。在此基礎上，將多目標實時調度方法與FEFS、HP方法進行方差分析（簡稱ANOVA）比較（表3），從表3可知，多目標實時調度方法與FEFS、HP方法的F統(tǒng)計值分別為26.72和16.22，表明提出的多目標實時調度方法與FEFS、HP方法的綜合期望函數(shù)值有顯著差異。以上實驗結果表明：本文提出的Intrabay系統(tǒng)多目標實時調度方法的綜合性能明顯優(yōu)于傳統(tǒng)的FEFS和HP方法，驗證了該方法的有效性。

圖4 多目標實時調度方法與FEFS、HP方法的仿真實驗比較結果

表3 多目標實時調度方法與FEFS、HP方法的方差分析比較

4 結束語

本文提出了一種Intrabay系統(tǒng)的多目標實時調度方法。該方法實時響應運輸小車空載和晶圓請求運輸?shù)葎討B(tài)事件，并對各事件時刻的Intrabay系統(tǒng)調度子問題進行優(yōu)化求解。采用300mm晶圓制造系統(tǒng)的生產數(shù)據(jù)進行仿真實驗，并與傳統(tǒng)基于先到先服務和最高優(yōu)先級規(guī)則的Intrabay系統(tǒng)調度方法進行比較，實驗結果表明：在各種實驗場景下，本文提出的多目標實時調度方法在晶圓卡被運輸小車搬運時間、晶圓卡總的運輸時間、運輸小車搬運量、晶圓產出量、晶圓加工周期和晶圓交貨期滿足率等指標方面具有更優(yōu)的綜合性能，表明了本文提出的Intrabay系統(tǒng)多目標實時調度方法是有效的。在本文的研究基礎上，將進一步研究晶圓加工系統(tǒng)與物料運輸系統(tǒng)集成調度問題。

［1］Lin D P，Lee K M.A Review of the Research Meth－odology for the Re－entrant Scheduling Problem［J］.International Journal of Production Research，2011，49（8）：2221－2242.

［2］Govind N，Roeder T，Schruben L W.A Simulationbased Closed Queuing Network Approximation of Semiconductor Automated Material Handling Systems［J］.IEEE Transactions on Semiconductor Manufacturing，2011，24（1）：5－13.

［3］Agrawal G K，Heragu S S.A Survey of Automated Material Handling Systems in 300mm Semiconductor Fabs［J］.IEEE Transactions on Semiconductor Manufacturing，2006，19（1）：112－120.

［4］Lin J T，Wang F K，Yen P Y.Simulation Analysis of Dispatching Rules for An Automated Interbay Material Handling System in Wafer Fab［J］.International Journal of Production Research，2001，39（6）：1221－1238.

［5］Hasenbein J，Sigireddy S，Wright R.Taking a Queue from Simulation：The Many Rules of Scheduling Semiconductor Material Handling［J］.IEEE Transactions，2004，36（8）：39－43.

［6］Liu C Y，Liao D Y.An Optimal OHT Dispatching System for 300mm Semiconductor Manufacturing［C］//IEEE International Conference on Systems，Man and Cybernetics.Piscataway：IEEE Press，2004：1631－1636.

［7］Liao D Y，Jeng M D，Zhou M C.Application of Petri Nets and Lagrangian Relaxation to Scheduling Automatic Material－ handling Vehicles in 300mm Semiconductor Manufacturing［J］.IEEE Transactions on Systems，Man and Cybernetics－Part C：Applications and Reviews，2007，37（4）：504－516.

［8］Liao D Y，Wang C N.Differentiated Pre－emptive Dispatching for Automatic Materials Handling Services in 300mm Semiconductor Foundry［J］.International Journal of Advanced Manufacturing Technology，2006，29（9/10）：890－896.

［9］Wang C N.The Heuristic Dispatching Method of Automatic Material Handling System in 300mm Semiconductor Fabrication［J］.International Journal of Innovative Computer Information and Control，2009，5（7）：1927－1935.

［10］Lin J T，Wang F K，Chang Y M.A Hybrid Push/Pull Dispatching Rule for a Photo－bay in a 300mm Wafer Fab［J］.Robotics and Computer Integrated Manufacturing，2006，2（1）：47－55.

［11］Le－anh T，De－Koster M.On－line Dispatching Rules for Vehicle－based Internal Transport Systems［J］.International Journal of Production Research，2005，43（8）：1711－1728.

［12］Myers R H，Montgomery D C.Response Surface Methodology：Process and Production Optimization Using Designed Experiments（Wiley Series in Probability and Statistics）［M］.New York：Wiley Inter－Science Publications，2009.

［13］Vinodh S，Balaji S R.Fuzzy Logic Based Leanness Assessment and Its Decision Support System［J］.International Journal of Production Research，2011，49（13）：4027－4041.

［14］Goldberger J，Tassa T.A Hierarchical Clustering Algorithm Based on the Hungarian Method［J］.Pattern Recognition Letters，2008，29（11）：1632－1638.

［15］Azadegan A，Ghazinoory S，Samouei P.Fuzzy Logic in Manufacturing：A Review of Literature and a Specialized Application［J］.International Journal of Production Economics，2011，132（2）：258－270.

［16］李士勇.模糊控制［M］.哈爾濱：哈爾濱工業(yè)大學出版社，2011.

［17］Mok P Y，Kwong C K，Wong W K.Optimization of Fault－tolerant Fabric－cutting Schedules Using Genetic Algorithms and Fuzzy Set Theory［J］.European Journal of Operational Research，2007，177（26）：1876－1893.

［18］Wu L H，Mok P Y，Zhang J.An Adaptive Multiparameter Based Dispatching Strategy for Singleloop Interbay Material Handling Systems［J］.Computers in Industry，2011，62：175－186.

［19］Li B，Yang C J.Production Logistics System Based on a Hybrid Push/Pull Control Strategy in Maketo－order Environments［J］.International Journal of Innovative Computing Information and Control，2009，5（5）：1343－1350.

［20］Kuo C H，Wang C H，Huang K W.Behavior Modeling and Control of 300mm Fab Intrabays Using Distributed Agent Oriented Petri Net［J］.IEEE Transactions on Systems，Man and Cybernetics－Part A：Systems and Humans，2003，33（5）：641－648.

［21］Wang C N，Liao D Y.Expeditious Hot Lots Handling in 300mm Semiconductor Foundry［C］//IEEE International Conference on Systems，Man and Cybernetics.Piscataway：IEEE Press，2006：4677－4681.