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

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

(1.紅塔遼寧煙草有限責(zé)任公司，遼寧 沈陽(yáng) 110002；2.中國(guó)科學(xué)院沈陽(yáng)自動(dòng)化研究所，遼寧 沈陽(yáng) 110016)

1 引言

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

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

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

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

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

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

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

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

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

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

Hf是半批次計(jì)劃，Wf是全批次計(jì)劃，Hf?Ω∪Ω*，Wf?Ω∪Ω*。

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

1)根據(jù)當(dāng)前時(shí)間Tnow設(shè)置Hf，Wf；

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

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

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

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

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

表1 參數(shù)設(shè)置

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

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

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

5 解決方案

5.1 基于時(shí)間和路徑的全任務(wù)混合計(jì)劃的解決方案

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

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

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

(7)

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

(8)

具有截止期的生產(chǎn)應(yīng)該提前進(jìn)行

(9)

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

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

(10)

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

(11)

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

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

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

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

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

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

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

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

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

(12)

解決方案步驟如下：

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

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

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

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

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

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

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

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

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

6 仿真運(yùn)算結(jié)果

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

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

6.1 正交設(shè)計(jì)的特點(diǎn)和步驟

正交設(shè)計(jì)具有均勻分散，齊整可比的特點(diǎn)。

1)均勻分散

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

2)齊整可比

巧妙的可比性意味著每個(gè)因素的每個(gè)等級(jí)都是可比的。因?yàn)樵谡槐碇械拿總€(gè)因素的任何水平上，其它因素的所有水平都是平衡的。

3)代表

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

正交設(shè)計(jì)的主要步驟如下：

1)根據(jù)目標(biāo)和測(cè)試需求確定等級(jí)；

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

3)組織實(shí)施測(cè)試；

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

6.2 正確的因素和表格選擇

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

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

正交表符號(hào)的解釋

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

L代表正交表；

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

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

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

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

1)組織實(shí)施測(cè)試

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

2)作為趨勢(shì)圖

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

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

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

圖2 趨勢(shì)圖

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

圖3 時(shí)間比較

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

7 結(jié)論

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