1.2 相關研究綜述

結合本書的研究背景和意義，本節將主要針對以下幾個方面的研究進行綜述。可重入生產系統的建模、多產品可重入生產系統的投料控制策略、可重入生產系統的推拉調度控制策略等。

1.2.1 可重入生產系統的基本研究模型

半導體制造系統一直被認為是當今最復雜的制造系統之一。鑒于半導體生產線的復雜特性，需要借助抽象化的模型語言建立仿真模型，才能對這樣一個復雜的生產系統進行研究。目前，國內外對可重入生產線研究的模型做了大量的研究工作，概況來說主要包括以下幾種：Petri網（petri networks）模型、排隊網（queuing networks）模型、流體（fluid networks）模型、連續模型（continuous model）、仿真模型等。以下分別簡述。

1． Petri網模型

Petri網模型能對生產系統進行系統建模、仿真和性能分析，是研究離散事件動態系統的一個重要工具。Petri網模型的優勢在于有比較完善的理論體系，同時可明確反映緩沖區、設備沖突和并發現象。然而，由于多重入生產系統為復雜的大規模制造系統，其龐大的規模使得Petri網模型的空間極度膨脹，帶來了局限性。因此，應根據特定的應用環境，對Petri網模型進行拓展。由此衍生出了帶多值標記的Petri網——Petri網（high level petri nets）應運而生，如謂詞變遷Petri網、著色Petri網、賦時Petri網、面向對象Petri網等，可以更好地對生產系統進行建模。

Zhou等（1998）[17]利用Petri網方法來對半導體制造系統進行建模、分析、模擬、調度和控制，同時，引入了時間Petri網對制造系統進行仿真、性能評估和調度控制的目的。Lin等（1999）[18]利用廣義隨機著色時間Petri網（GSCTPN）對晶圓制造系統進行建模。Kim和Deserochers（1997）[19]利用時間Petri網建立和分析了面向客戶的半導體制造系統，從客戶訂單到配送階段。同時，通過分析模型的行為特征來獲得生產周期，在制品狀態和負載能力。Odrey等（2001）[20]利用廣義隨機Petri網對多重入流建立了一個典型半導體生產系統模型，并在此基礎上進行了一些探討。Wang（2002）[21]將連續模型和離散模型的轉換相結合降低了模型的維數，從而建立了面向對象的混合Petri網模型。Lin等（2003）[22]利用Petri網建立了具有積極反饋回路的系統的一個不穩定充分條件，同時，利用緩沖區有界性的方法（buffer-boundness approach）研究多重入生產線的穩定性。Liu等（2003）[23]利用著色時間Petri網（CTOPN）對半導體制造系統進行研究，提出了多目標實時調度的方案，并通過仿真不同的調度規則證明了該模型的有效性。Zhai等（2006）[24]利用面向代理的有色賦時Petri網方法對半導體生產線進行建模，并且建立了一個分布的離散事件仿真平臺來評估半導體生產系統的性能。Chiang等（2006）[25]利用排隊著色Petri網（QCPN）對半導體生產線進行性能的評估和調度，同時提出了一個如何實現模型的優先規則機制。

2．排隊網模型

排隊網模型能夠直觀地描述晶圓生產線中的離散加工過程，并且能夠得到解析的性能評價表達式，還可以用來評價調度策略的穩定性。然而，在大批量多品種混合生產的模式下，隨著系統規模的增大和復雜度的增加，很難對模型求得解析解，也無法解決實際生產問題[26]。這是因為在分析可重入生產系統時，排隊網絡模型有以下幾個缺陷。

（1）通過引入不同的客戶類來處理多重入加工步時，隨著系統中加工機器數量的增加，模型的復雜度將會不斷增大。

（2）排隊網絡模型只能解決系統穩態下的優化控制問題，即所有的模擬結果只有在t→∞時才有效。

（3）排隊網絡模型必須忽視工廠中所有的臨時故障，臨時故障是不能通過排隊網絡模型來建模的。

Wein（1990）[27]利用多級排隊網絡模型，研究了兩個工作站臺的投料速率控制及調度優先級問題以解決工廠的調度問題。Kumar等（1994）[28]針對半導體制造系統利用排隊網絡方法做了大量的研究工作，但采用的排隊網絡方法很難得到解析解。Kumar and Kumar（2000）[29]利用排隊網絡模型用于半導體生產系統的設計和分析。Jeng等（2000）[30]利用馬爾可夫時間Petri網（markovian timed Petri nets）對半導體生產系統進行建模，考慮了加工過程的優先級、加工路徑的優先級、資源的重入和非搶占優先操作。Thomas和Shanthikumar（2002）[31]拓展了單階段馬爾科夫（markov）決策模型，解決了如何調度維修和計劃具有多產品多階段的半導體生產制造系統。針對Markov模型現有的研究結果都只是理論性的，尚無法解決實際半導體生產線的一些現實的問題[20]，[32]。

3．流體模型

流體模型很好地降低了生產系統的維數，有良好的魯棒性，適用于隨機環境。流體模型[2]，[33]來自交通流理論，是由Newell（1965，1973）[34]，[35]提出的。流體模型近似求解排隊問題，將隊列的長度視為一個連續的變量，并且它的變化率是由式（1-1）給出的。

其中：λ（t），μ（t）分別為物料的進入速率和系統的加工速率；q（t）為隊列中在制品的數量。將系統中的每個加工機器都看作一個獨立的隊列，每個隊列長度的特征都可以用式（1-1）表示。當系統中有多個這樣的隊列時，將前一個隊列物料離開的速率作為下一個隊列物料進入的速率，并將多個這樣的排隊模型連接起來，就形成了流體網絡模型。由此，流體網絡模型可以通過求解常微分方程（組）快速地得到計算結果，而且計算時間不受系統規模的影響。但是，流體模型也有其自身的缺點[7]。

（1）流體模型不能模擬系統的隨機性。式（1-1）的λ（t），μ（t）均為平均值，是一個完全確定的系統，不能反映隨機性。

（2）假定系統有恒定的產出率，流體模型是非常嚴格的。當系統達到穩定狀態時，系統隊列中將不會有任何工件在等待。并且當系統為非穩定狀態時，隊列將會出現維數爆炸。同樣，一個隊列的波動將不會傳送到任何隊列的上游或是下游，除非該隊列的長度為0。

（3）當流體網絡模型中的工件是一個連續的變量時，將每個加工機器視為一個獨立的離散隊列。因此，對于一個典型的芯片需要經歷上百道工序，將生產加工步視為一個連續的變量是合理的。

鑒于流體模型自身的特點，使得它只能在系統穩定性方面取得了一些成果，卻不能對系統的性能進行分析。對于無參Jackon網，Dai和Reiman（1994）[36]給出了一個結合近似分解法和交通流理論的耦合計算方法，來分析廣義Jackson網絡，并且通過模擬實驗表明耦合的計算方法相比其他近似算法具有更好的研究結果。Chen和Yao （1996）[37]指出，在給定任何一個滿足交通條件的情況下，從另外一個角度解決了多重入生產系統的穩定性問題。Dai和Weiss （1996，2000）[33]，[38]研究了具有確定路徑的兩站多級排隊網絡的流體模型，說明流體網絡模型是不穩定的，并且特別指出當流體模型穩定的時候，排隊網絡模型也是穩定的。Gottlich等（2005）[39]對供應鏈流體網絡模型進行了描述，推導出了常微分方程下的守恒定律，同時利用前向跟蹤法證明了模型解的存在性。Ciro D'Apice（2006）[40]對供應鏈的流體網絡模型做了論述，提出了一種離散—連續混合模型，同時討論了保證流量守恒的點是模型可能的解。Armbruster和Ringhofer（2005）[8]，[41]針對多重入供應鏈，通過引入一個隨機的相速度對標準模型進行拓展，得到對應動力學和流體模型的溫度和擴散的概念。

4．連續模型

為了能從整體上對半導體生產線的性能進行分析，為此引入連續建模的方法。Armburster等（2006）[11]利用χ語言［由Van Beek等（2006）[42]創立］建立了包含有一個序列的緩沖隊列和具有一定的生產周期和產能處理器的供應鏈，推導出了供應鏈中一個關于工件密度和流量的雙曲型守恒定律，即連續模型。連續模型不能從細節上反映生產系統的特征，但是有其獨有的優勢。

（1）連續模型隨著生產系統中物料的數量、加工機器的數量、加工步驟的數量越多和工件的重入程度越高，即系統復雜度的增加，所得到的模擬結果越精確。

（2）連續模型的計算時間不受系統規模的影響，并且有成熟的方法來求解該模型，可以非常快速地得到數值結果。

（3）連續模型可以很好地反映系統的瞬態行為。

Anderson（1981）[43]針對作業車間調度，給出了一個新的連續模型，并且能夠有效地得到優化控制問題的解。Armburster等（2004）[12]利用交通流和空氣動力學模型，通過一個連續的密度變量和一個連續的完成度變量，建立了大規模可重入生產系統的連續模型。這一模型為非線性非局部的雙曲型守恒定律的變體，可以非常快速地得到精確的模擬結果[11]。Lee等（2002）[44]針對供應鏈模擬，提出了將離散事件仿真及連續建模方法相結合的組合方法對生產系統進行研究。Van den Berg等（2008）[45]針對生產流，提出了一種新的模型，即偏微分方程（PDE）模型。通過將三種不同的偏微分方程模型進行對比，以驗證所提出模型的有效性。另外，利用該PDE模型來設計一個模型預測控制器（MPC控制器），并且通過證明MPC控制器優于經典的推式策略。Zou等（2006）[46]針對像半導體這樣復雜的制造系統，提出了利用計算機輔助建模的方法，結合長時間尺度和短時間尺度來求解粗粒度偏微分方程。Sun和Dong（2008）[47]利用連接矩陣，基于供應鏈網絡物料流守恒定律，建立偏微分方程的連續模型，采用DG（discontinuous galerkin）方法來求解供應鏈網絡的生產流，同時指出所提出的建模方法是可以應用于大規模多重入生產線的情況。Jodlbauer和Stocher（2006）[48]研究了在連續型生產系統中Little's Law的形式。

通過以上的分析可以得知，建立不同的生產模型分別反映了生產系統的不同側面，不同的模型均在某一些方面表現出一定的優越性。然而，為了對大規模復雜制造系統的整體性能進行評估，同時對生產系統提出合理的動態實時調度策略，應采用連續的建模方法。

1.2.2 可重入生產系統投料策略的研究現狀

可重入生產系統的投料控制一般分為兩類。一類是靜態策略，即根據事先設定的速率進行物料投放，而不考慮制造系統當前的生產狀況。如固定時間間隔投料策略（CONRIN）、隨機投料或按隨機分布泊松流投料策略等。該控制方法簡單易實施，但為開環系統，不能做到及時反饋到投料控制端。另一類是動態策略，主要是使用啟發式方法，根據生產線狀況實時決定具體的投料時間、投料量及投料品種的控制方式，并且考慮的指標往往是交貨時間和在制品水平。如固定在制品水平投料策略（CONWIP）、避免瓶頸設備饑餓投料策略（SA）、調節工作負載量投料策略（WR）等。動態投料策略的優點之一是能夠最小化生產過程中隨機事件的影響，根據現場狀況的變化及時調整投料量、投料時間及投料品種。目前此種方式仍然是研究的熱點。

在投料規則中，Wein（1988）[49]通過對幾種不同的投料策略進行比較分析，在某種程度上投料策略比調度策略更重要。Spearman等（1990）[50]提出了定量在制品（constant WIP，CONWIP）方法，給出了CONWIP相比推式系統和拉式系統的實踐優勢，同時指出了支持該系統的理論依據并且通過仿真對系統的性能進行研究。Stidham （1985）[51]從控制和優化的角度出發，綜述了通過靜態（開環）和動態（閉環）模型來控制排隊系統的投入量。在Brownian模型的基礎之上，Glassey和Lozinski（1988）[52]，[53]引入了一個避免饑餓（starvation avoidance，SA）的投料策略，通過圖表來說明這個概念，并且在半導體晶圓制造的加工車間取得了良好的控制效果。在實際的半導體制造系統中，瓶頸設備并不都是靜止不動的，而是隨產品的種類及數量的不同出現多個瓶頸設備甚至出現瓶頸漂移的現象。Leachman等（1988）[54]對SA策略進行了擴展，以適應瓶頸設備位置變化及有多個瓶頸設備的情形。盡管該方法提供了較好的思想，但在實際生產中卻很難得到應用。Wein（1992）[55]針對多站點多級排隊網絡，利用Brownian運動控制問題，導出了啟發式投料策略。由于Wein提出的投料策略是復雜的而且調度規則也是動態的，Duenyas（1994）[56]基于CONWIP與靜態調度策略相結合的方法，對投料策略的性能進行測試，并且指出利用簡單的投料規則也是有效的。Rodriguez（1997）[57]針對Mini-Fab模型設計了一種閉環系統的投料策略控制器，研究了穩定的CAF狀態反饋策略。李莉等（2006）[14]提出了半導體生產線投料策略的系統動力學模型，并以生產線簡化模型為例，給出了投料方法的計算流程并進行了仿真模擬。同時指出，系統動力學的投料策略有改進系統性能的潛力。Marca La等（2010）[58]通過連續建模的方法作為非線性優化問題的約束，研究了兩種典型的控制問題：需求跟蹤問題和庫存積壓問題。

綜上所述，各種投料策略均有一定的合理適用范圍，投料策略須考慮訂單的選擇、訂單的生產周期、交貨時間的緊急度、加工工藝路徑的長短等，因此在實際應用中需要根據生產線的實際情況決定采取何種投料策略。

1.2.3 可重入生產系統調度策略的研究現狀

半導體市場競爭激烈，企業要不斷地提高產能降低制造周期，以使企業更快速地響應市場需求。對實際生產線而言，有效的投料控制策略能夠改善生產狀況，提高企業績效。然而，由于生產過程中存在大量不確定性因素，單純依靠投料策略往往無法有效控制芯片廠的整個制造過程，需要相應的生產調度來進一步控制。根據使用方法的不同，主要有基于以下幾種模型建立的調度方法。

1．基于Brownian模型

Harrison和Wein（1990）[59]利用Brownian模型研究了一個具有兩個單臺服務站的多級閉環排隊網絡，主要是對工作站進行調度以最大化平均產出量，得到了一種使負載平衡的調度規則（workload balancing policy，WBP）。Chevalier和Wein（1993）[60]將它推廣到多臺服務器多級閉環排隊網絡，但Brownian模型計算量大，且得不到唯一封閉形式的解。Wein（1992）[61]研究了多機臺多類閉環排隊網絡，針對多維Brownian模型，利用線性規劃來減少負荷形式的控制問題，計算復雜度遠高于兩機臺情況。趙麗娜等（1999，2000）[62]，[63]針對閉環可重入生產系統，設計了并行順流定級法（parallel priority ordered downstream，PPOD），利用線性規劃方法對性能邊界的計算結果及仿真結果證明了該方法良好的適應性。

2．基于Markov模型

Kumar等（1993）[64]基于Markov排隊論建立半導體生產線的排隊模型，描述了幾種不同的調度策略并給出了一些有關系統穩定性的模擬結果。Li等（1996）[65]將半導體生產線近似為Markov模型，提出了一種最低庫存量變化的調度（MIVS），以降低半導體晶圓廠的生產周期的均值和方差。同時，將該調度策略與其地調度策略相比，表明具有更大的調度優越性。鄭應平與王利存（2001，2002）[66]，[67]利用Markov決策模型，提出了可應用于可重入生產系統調度的遞階增強型學習算法，并且通過仿真表明該調度策略明顯優于兩種啟發式調度策略。

3．基于Petri網模型

Cavalier等（1997）[68]介紹了一種用著色標記Petri網的方法對柔性半導體制造系統進行調度，同時改善了生產系統的性能。Jeng等（2000）[30]針對具有加工優先級、路徑優先級、資源重入及可操作的半導體制造系統，利用馬爾科夫時間Petri網方法來建立模型。Park等（2001）[69]利用有色Petri網來開發一個分布的晶圓控制器的事件驅動。由于路徑的靈活性和輔助資源的共享，這個方法結合了制造系統的詳細操作特性，包括配料、安裝、返工、維護、機器故障和復雜資源的動態配置問題，同時通過小規模試驗驗證了該方法的有效性。喬非等（2004）[70]建立了有色Petri網的分層調度模型，并且進一步研究了該調度模型的實現方法。

4．基于流體網絡模型

Chen和Yao（1992）[71]研究了具有隨機中斷的流體網絡模型，同時研究了該模型的質量和相關性。在強大數定理（FSLLN）下，這個模型是排隊網絡系統的漸進行為。Connors（1994）[72]基于確定的流體網絡模型，給出了一種新的半導體調度控制方法。該方法的主要優點是提出了一個基于整體的狀態而不是基于局部信息的動態調度策略。同時，給出了一些有關流體模型的理論結果。Sharifnia（1995）[73]通過實際（離散）生產控制問題的連續流松弛法（continuous-flow relaxation），來操作生產系統使其盡可能接近理想化的策略。衛軍胡（2001）[74]基于流體網絡模型，結合離散事件仿真的方法，決策規則方法等提出多個模型交互的層次化結構模型和調度方法。

1.2.4 可重入生產系統推拉策略的研究現狀

半導體制造系統是最先進的工業生產過程之一。由于它的生產周期（幾個星期）和多重入流給生產計劃和控制帶來了更大的挑戰[75]-[77]。大多數時候，需求的波動變化相比工廠的生產周期是在一個更短的時間尺度上，使得采用初始調度策略來響應需求波動變得越來越難。特別是，對于一個恒定的平均需求量，以均值需求量開始。由于生產的隨機性和需求波動的變化，使得日產出量和需求量之間存在很大的差異。在實際生產中，為了減少它們之間的差值，給定一段時間內的生產目標，同時硅片在后期的加工過程中可以通過調度策略來加快或是減慢生產。由于半導體生產系統中的一個加工機器具有多個加工步，因此可以通過調度策略來重新設置所有加工步的優先級。

Sterman（2002）[78]指出在長的需求期和較大的需求波動的情況下，需要通過調整初始投料速率來彌補期望在制品水平的變化。Fowler等（2002）[79]針對工件負荷控制應用到半導體工廠的現狀進行了綜述。Bergamaschi等（1997）[80]將訂單發放看作流控制，做了完整的文獻綜述。同時，Panwakar和Iskander（1977）[81]和Blackstone等（1982）[82]均對分派策略做了深入的研究。常用的調度策略有：先入先出（FIFO）、最早交貨期（EDD）、加權最短加工時間（WSPT）、最小空閑時間（LS）和最小調整成本（LSC）。Aytug等（1994）[83]實現了動態調度策略研究。Atherton和Dayhoff（1986）[84]研究了純推式和拉式調度策略。目前幾乎沒有文獻提到在生產能力滿足的情況下，晶圓廠收到意外訂單時，產品出現激增或是短時間硅片的增加所帶來的影響。McKiddie（1995）[85]，Kato（1996）[86]和Dummler（2000）[87]對需求激增問題進行了初步的研究。Lu等（1994）[88]沒有考慮產出量問題，而是考慮了生產周期的均值和方差的性能與不同調度策略之間的函數關系。

離散事件模擬可以得到非常準確的模擬結果，在實際生產系統中也得到了廣泛的應用。然而，離散事件模擬不論是運行還是維修都非常耗時。利用連續的流體動力學方程的供應鏈模型近幾年成為研究的熱點[8]，[89]，[91]。對于大規模的生產系統，以半導體生產線為例，Dieter等認為[11]，利用對應確定的連續模型可以進行離散事件模擬預測。對離散事件模擬來說，由于連續模型具有更豐富的解析結構，因此它可以有效地用于優化控制策略中[61]，[92]，[94]。然而，到目前為止，只有針對平均需求的長期預測的最優控制問題得到了研究。然而，對半導體工廠來說，存在另外一個更短的時間尺度，在這個時間尺度上的控制可以采用常用的調度策略[90]。最近，這個過程已經通過一系列的雙曲型偏微分方程進行建模。在這里，研究了該模型的解析性質，并且引入了一種基于調度策略的控制模型。