改進啟發算法在半導體生產調度中的應用研究

高 強，郭大權，李 飛，王 巍

(1.紅塔遼寧煙草有限責任公司，遼寧 沈陽 110002；2.中國科學院沈陽自動化研究所，遼寧 沈陽 110016)

1 引言

現代企業正在通過大型設備實現持續，高速和自動化。重點放在高品質，低成本，準時交付和小批量訂制生產。為提高競爭力，許多大型企業致力于開發可提高大型設備生產率、縮短運營間等待時間、節省材料和能源并能夠降低生產成本的計算機集成制造系統(CIMS)。生產調度是CIMS的關鍵組成部分。其任務是確定不同工位的開始生產時間和完成時間，以便企業提高生產效率，實現產量的提升。

近年來，半導體行業的高速發展，吸引了許多研究人員的目光，很多研究機構都在提高生產效率的方面進行了深入的研究。本文研究了半導體生產的調度優化問題，針對半導體封裝調度優化的問題提出了一種新的基于作業和資源動態優化的調度優化算法和解決方案。同時，通過建立階段模型和優化算法解決了生產優化的問題，降低了問題的復雜度。本文充分結合半導體生產的特點，同時，基于現有生產調度理論與實際生產應用的差距較大，該項目是以半導體封裝企業為實際研究對象，力爭為企業提供可行的生產調度優化方案和實用的系統提高生產效率。

2 國內外研究現狀

在過去幾年中，提出了小型工廠生產計劃過程的數學模型。半導體制造商正在越來越多地將多個芯片組裝成一個封裝，以最大化閃存的容量。通過關注瓶頸階段，同時滿足實際操作約束條件，找到半導體封裝設施的良好時間表。

Tsen[1]等人研究了加工時間可控的單機調度問題，該問題的目標是最小化總延遲時間和壓縮成本加權之和。建立了該問題的兩種線性規劃數學模型，提出一種凈壓縮收益算法(Net Benefit of Compression，NBC)并對該小規模車間調度問題進行求解。Kayvanfar[2，3]等人延續了TSeng的工作，并提出了一種凈壓縮及凈擴展收益算法(Net Benefit Compression-Net Benefit Expansion，NBC-NBE)求解該類問題。Yin和Wang[4]采用了啟發式算法來求解加工時間可控和學習效應的單機調度問題。該問題的目標是最小化完工時間、總完工時間和完工時間的絕對差異等成本函數。翟穎妮[5]等利用正交設計，識別生產過程中的瓶頸，對生產調度具有一定指導意義。但是結果的準確性依賴構造的正交表，該方法就不適用于多機器的瓶頸識別問題。ZHANG[6，7]通過放松調度問題分析機器的唯一性占用約束，得到一個新的優化模型，提出了一種基于約束轉換的作業車間先驗瓶頸識別方法。但是新的優化模型也屬于復雜的組合優化問題，求解過程復雜，因此不適用于大規模調度；CARLOS[8]等人對瓶頸等級進行了劃分以實現瓶頸漂移的預測；MILTON[9]等采用數學分析方法和仿真技術對瓶頸預測問題進行了研究。花季偉等[10]設計遺傳算法并且建立了批決策和批調度的計劃調度模型。

3 調度問題概述

半導體行業一直都面臨著最具挑戰性快速發展問題。本文主要基于工作和資源動態優化匹配半導體生產調度研究。半導體生產主要包括以下兩個階段：晶圓生產(前端)，封裝測試(也被稱為后端，后端)。其中，封裝測試(Assembly and Test Manufacturing，ATM)是中國半導體行業的第一次轉型，也是最適合中國行業發展的，也是目前中國半導體行業關注的焦點。

目前，國內大部分封測企業都實施了ERP、MES和EAP系統，這些系統可以提供透明管理的生產和提高生產效率。對半導體生產調度的研究已成為企業面臨的常見問題之一。

制造過程中存在各種異常情況，包括設備故障，處理時間不確定性，返工和緊急任務插入。生產調度應該允許計劃調整以適應生產中發生的異常情況。需要使用批次拆分調度策略來處理混合生產模式的計劃。批量調度策略是將整個任務分為半任務批量和全批量任務。然后根據傳感器的不同，會有兩批分批到半批次和整批任務，過程如圖1所示。

圖1 生產計劃分解流程

Hf是半批次計劃，Wf是全批次計劃，Hf?Ω∪Ω*，Wf?Ω∪Ω*。

其步驟可總結如下：

1)根據當前時間Tnow設置Hf，Wf；

2)根據任務，截止期傳感器和無截止期傳感器，把半批次進行二次分批，設置Hf為H0、H1和H2；

3)全批次任務也分批為H0，H1和H2；

4)把現有的任務截止期匯聚的時候要增加新的限制條件，有截止期的要有開始時間限制，沒有截止期的沒有限制。

4 構建數學模型

設置參數如表1所示。

表1 參數設置

建立半導體混合計劃和調度的數學模型約束如下

(1)

XSI(i，j)，j′，k-Xijk≥ptijk，i∈Ω，SI(i，j，k)∈Ω

j=1，…，mi，j′∈ΘSI(i，j，k)

(2)

j=1，…，mi-1，j+1∈Θi

(3)

XSI(i，mi，k)，mSI(i，mi，k)-Xi，mi，k≥ptijk+adjtcast

i∈Ω，SI(i，j，k)∈Ω0，mSI(i，mi，k)∈ΘSI(i，mi，k)

(4)

Xi，j，k≥0，i∈Ω，j∈Θi

(5)

(6)

當最后一個設備結束時，相同的設備只能處理下一個任務。約束(2)表示處理時間的限制。約束(3)代表了工作秩序的約束。當最后一個結束時，相同的任務只能繼續下一個工位。約束(4)表示相鄰任務之間存在建立時間間隔。約束(5)表示決策變量是非負的。約束條件(6)表示有截止期的任務必須在截止期之前完成生產。

5 解決方案

5.1 基于時間和路徑的全任務混合計劃的解決方案

通過考慮最優設備和工位，選擇加工設備和開始時間。最優設備的選擇規則如下：

選擇最早開始生產工位的規則是

R1=min{sti，mi，kyi，mi，k}

(7)

根據規則R1選擇任務i的操作工位，當有多個工位時，選擇工位加工時間最短的工位，如下所示

(8)

具有截止期的生產應該提前進行

(9)

無截止期的生產計劃的設備選擇規則如下所示

T1={pti′jk≥∑(etijk-stSI(i，j，k)，j，k)}

(10)

在開始生產時選擇設備T1，選擇完T1后，確定任務的開始時間，規則如下

(11)

然后繼續使用T1選擇設備，確定任務在工位上的開始時間。

5.2 基于鎖定路徑的半批次混合計劃的解決辦法

建立混合計劃的優先約束：

1)若δ(i，j，k)→(i′，j，k)≥0，i∈Ω且δ(i′，j，k)→(i，j，k)<0，則任務i比任務i′具有更高優先級；

2)若δ(i′，j，k)→(i，j，k)≥0，i∈Ω且δ(i，j，k)→(i′，j，k)<0，則任務i′比任務i具有更高優先級；

3)若δ(i，j，k)→(i′，j，k)<0，i∈Ω且δ(i′，j，k)→(i，j，k)<0則沒有優先級約束滿足調度；

4)若δ(i，j，k)→(i′，j，k)≥0，i∈Ω且δ(i′，j，k)→(i，j，k)≥0，則它們有相同優先級；

當它們具有相同的優先級時，這兩項任務的選擇是基于調度順序的靈活性，調度順序的靈活性評估方法如下：

φ((i，j，k)(i′，j，k))

(12)

解決方案步驟如下：

1)獲得半任務集合H1，有截止期計劃集合H0和無截止期計劃集合H2，然后根據設備啟動時間得到降序排列圖；

3)計算δ(i，j，k)→(i′，j，k)和δ(i′，j，k)→(i，j，k)；

4)若其中一個排序決策滿足規則1至4，則獲得半任務集H1。從H1中選擇最早任務的開始時間，獲得下一階段的開始時間。計算δ(i，j，k)→(i′，j，k)和δ(i′，j，k)→(i，j，k)。若其中一個排序決策符合規則1或4，則根據約束在此階段符合任務的處理開始時間。然后跳到步驟5)；若符合規則1，則回顧一下；若沒有順序決定符合規則1，2或3，則跳轉到步驟7)；

5)添加新任務并跳到步驟 4)；

6)每個之前沒有分類邊界的任務要計算φ((i，j，k)(i′，j，k))。選擇最小的任務并安排時間。若δ(i，j，k)→(i′，j，k)≥δ(i′，j，k)→(i，j，k)，則任務i要優于任務i′在工位j的設備k上生產，否則在任務i′之后生產，跳到步驟5)；

7)若沒有排序決策滿足規則4，則尋求解決方案以獲得任務的半任務計劃，然后停止。否則跳轉到步驟6)；若符合規則5或6，則按照約束在該階段確定任務的處理開始時間，然后跳轉到步驟8)；若符合規則7，則回顧一下；若沒有順序決定符合規則1到8，則跳到步驟10)；

8)添加新任務并跳到步驟1)；

9)每個之前沒有分類邊界的任務要計算φ((i，j，k)(i′，j，k))。選擇最小的任務并安排時間。若δ(i，j，k)→(i′，j，k)≥δ(i′，j，k)→(i，j，k)，則任務i要優于任務i′在工位j的設備k上生產，否則在任務i′之后生產，跳到步驟8)；

10)若沒有排序決策滿足規則8，則尋求解決方案以獲得傳感器的半任務計劃，然后停止。否則，跳轉到步驟9)。

6 仿真運算結果

在現實世界中，影響測試結果的因素不止一個，不同因素對測試結果也有不同影響，當影響因素數量和水平提高時，如果綜合測試，測試次數會是測試急劇增加安排所有測試非常困難。如何科學地設計測試以獲得高可靠性測試數據是研究人員和工程師在實驗設計中需要解決的最大問題。

正交表是利用數學原理來生成一個很好的標準化表格。正交設計是使用正交表設計測試，這種設計方法被稱為正交優化。在數學中，兩個向量的內積之和為零，即a1b1+a2b2…anbn=0，則說這兩個向量是正交的。對于4因素和3等級測試，只需要9個測試，這9個測試通常是線性空間的一些正交點。由于正交表構造了均衡(均勻分散)的優勢，它可以用它來選擇一些具有強表示的實驗來獲得最佳或更好的值。

6.1 正交設計的特點和步驟

正交設計具有均勻分散，齊整可比的特點。

1)均勻分散

正交表中任何一列的數量級別相等(不同的數字代表不同的級別)。兩列之間各種級別的所有可能組合出現并等于出現次數。每個因素的一個等級等于另一個等級的其它等級的可能組合的數量，表明任何兩列之間的匹配是一致的。所謂均勻分散，是指利用正交表所選的組合水平的組合，各級的分配均勻。

2)齊整可比

巧妙的可比性意味著每個因素的每個等級都是可比的。因為在正交表中的每個因素的任何水平上，其它因素的所有水平都是平衡的。

3)代表

正交表中任何列的級別都會顯示，以便所有測試都包括所有因素的所有級別；任何兩列的所有水平組合都出現，允許任何兩個因素的組合成為一個全面的測試。由于正交表的平衡色散，可以看出正交設計點均勻分布在綜合測試點上，具有很好的代表性。因此，一些試驗的最佳條件應與綜合試驗的最佳條件一致。

正交設計的主要步驟如下：

1)根據目標和測試需求確定等級；

2)選擇合適的正交表并確定測試程序；

3)組織實施測試；

4)測試結果分析。

6.2 正確的因素和表格選擇

因素水平的選擇主要是根據研究目標來確定的，因此首先分析哪些因素會影響目標，并根據實驗成本和正交表確定最終因子。水平值的選擇基于實驗的經驗值來確定或隨機給定。

正交設計是選擇合適正交表的關鍵，正交表選擇直接影響實驗結果和實驗結果的分析。通常選擇正交表要經過三個步驟：一是根據研究內容確定研究因素和水平；其次，根據測試條件，確定試驗次數；三，上述情況選擇正交表L。

正交表符號的解釋

正交表的一般形式是Lt(nq)，符號如下：

L代表正交表；

T=正交表的行數也是試驗次數；

N=因素的數量；

Q=正交表的列數以容納最大數量的因子；

T=nq，q=因數=基本列數。

1)組織實施測試

將事先確定的實驗因素，列數的級別按照正交表的數量來安排因素和數值的高低，以便執行該表，根據實驗的實驗次數為了試驗n次。

2)作為趨勢圖

在本文中，選擇最小的正交表L4(23)來說明如何使用正交試驗結果作為趨勢圖。首先，將相同水平的相應實驗結果相同的因子相加，得到Ⅰ和Ⅱ的相應值，然后求出I/kj和Ⅱ/kj的平均值。最后，利用水平軸的因子和水平值，以及其相應的垂直軸平均值可以得出相應的趨勢。

表2 正交試驗結果表

為了進一步研究啟發式方法的效果，分析了參數變化的影響。如圖2所示，隨著調度規模的增加，算法性能不斷下降。同時，若有更多性能更好的設備和更多的設備，則算法的性能會不斷提高。

圖2 趨勢圖

對改進的調度算法和模型系統進行了比較。每個方案的完成時間如圖3所示有35個方案。使用改進算法，平均任務完成時間縮短12.1分鐘。改進的算法具有更好的性能。

圖3 時間比較

在工廠應用操作后，性能指標如下：平均規劃時間為9.1秒；動態調整時間約為5.2秒。

7 結論

本文針對半導體生產調度優化問題，在調度之前匹配作業和資源，降低了半導體生產調度問題的復雜性，體現了該方法的創新點和可行性。在本文中，根據實際產品流程的流程，描述調度過程。并在分析過程復雜性的基礎上，建立數學模型，提出傳感器調度算法解決難題。利用實際數據對算法進行測試，驗證改進的調度算法是有效的。文中的半導體生產時間表分析是在大型企業的工廠背景下進行的，具有一定的工程應用基礎。