改進啟發(fā)算法在半導體生產(chǎn)調(diào)度中的應用研究

高 強，郭大權(quán)，李 飛，王 巍

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

1 引言

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

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

2 國內(nèi)外研究現(xiàn)狀

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

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

3 調(diào)度問題概述

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

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

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

圖1 生產(chǎn)計劃分解流程

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

其步驟可總結(jié)如下：

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

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

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

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

4 構(gòu)建數(shù)學模型

設置參數(shù)如表1所示。

表1 參數(shù)設置

建立半導體混合計劃和調(diào)度的數(shù)學模型約束如下

(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)

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

5 解決方案

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

通過考慮最優(yōu)設備和工位，選擇加工設備和開始時間。最優(yōu)設備的選擇規(guī)則如下：

選擇最早開始生產(chǎn)工位的規(guī)則是

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

(7)

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

(8)

具有截止期的生產(chǎn)應該提前進行

(9)

無截止期的生產(chǎn)計劃的設備選擇規(guī)則如下所示

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

(10)

在開始生產(chǎn)時選擇設備T1，選擇完T1后，確定任務的開始時間，規(guī)則如下

(11)

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

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

建立混合計劃的優(yōu)先約束：

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

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

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

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

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

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

(12)

解決方案步驟如下：

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

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

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

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

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

7)若沒有排序決策滿足規(guī)則4，則尋求解決方案以獲得任務的半任務計劃，然后停止。否則跳轉(zhuǎn)到步驟6)；若符合規(guī)則5或6，則按照約束在該階段確定任務的處理開始時間，然后跳轉(zhuǎn)到步驟8)；若符合規(guī)則7，則回顧一下；若沒有順序決定符合規(guī)則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要優(yōu)于任務i′在工位j的設備k上生產(chǎn)，否則在任務i′之后生產(chǎn)，跳到步驟8)；

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

6 仿真運算結(jié)果

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

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

6.1 正交設計的特點和步驟

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

1)均勻分散

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

2)齊整可比

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

3)代表

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

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

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

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

3)組織實施測試；

4)測試結(jié)果分析。

6.2 正確的因素和表格選擇

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

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

正交表符號的解釋

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

L代表正交表；

T=正交表的行數(shù)也是試驗次數(shù)；

N=因素的數(shù)量；

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

T=nq，q=因數(shù)=基本列數(shù)。

1)組織實施測試

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

2)作為趨勢圖

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

表2 正交試驗結(jié)果表

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

圖2 趨勢圖

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

圖3 時間比較

在工廠應用操作后，性能指標如下：平均規(guī)劃時間為9.1秒；動態(tài)調(diào)整時間約為5.2秒。

7 結(jié)論

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