運(yùn)用改進(jìn)的螢火蟲算法求解TFT-LCD 單元裝配調(diào)度問題

李瑞婷，葉春明，吳思思

（上海理工大學(xué) 管理學(xué)院，上海 200093）

TFT?LCD（thin film transistor-liquid crystal display）即薄膜晶體管液晶顯示器（液晶面板），近些年以其屏幕亮度高、制造費(fèi)用低及分辨率高等優(yōu)勢(shì)普遍應(yīng)用于手機(jī)、顯示器、平板電腦、臺(tái)式電腦、電視及電子手表等各類顯示領(lǐng)域。TFT?LCD具有性能優(yōu)良、功耗低、視角寬、價(jià)格低廉、發(fā)展空間較大等諸多優(yōu)點(diǎn)，是現(xiàn)代人類不可或缺的重要部分，也是促進(jìn)現(xiàn)代化全球經(jīng)濟(jì)增長(zhǎng)的亮點(diǎn)。但是，在大批量生產(chǎn)加工過程中，TFT?LCD 也存在著一些需要重視的問題，由于TFT?LCD 的廣泛應(yīng)用，市場(chǎng)的需求量劇增，如何優(yōu)化生產(chǎn)，提高效率的同時(shí)保證產(chǎn)品質(zhì)量，將是一個(gè)至關(guān)重要的問題。

結(jié)合上述關(guān)于TFT?LCD 的生產(chǎn)特點(diǎn)，提高其生產(chǎn)效率迫在眉睫。TFT?LCD 的生產(chǎn)流程具體包括以下3 個(gè)關(guān)鍵步驟：薄膜晶體管陣列制造階段（Array）、液晶面板組裝制造階段（Cell）、液晶模組組裝制造階段（Module）。在不同階段的生產(chǎn)加工過程中，同一產(chǎn)品的加工工藝并不相同，對(duì)于不同產(chǎn)品所需要的加工工藝階段也各不相同。單元裝配階段作為TFT?LCD 生產(chǎn)制造過程中的一個(gè)關(guān)鍵環(huán)節(jié)，如何保持單元裝配階段生產(chǎn)線的平衡以及提高其生產(chǎn)效率對(duì)整個(gè)TFT?LCD 生產(chǎn)線具有至關(guān)重要的作用。本文主要研究TFT?LCD 的單元裝配階段的調(diào)度問題。

TFT?LCD 的單元裝配調(diào)度問題通?？醋鳛榛旌狭魉囬g調(diào)度問題?；旌狭魉囬g問題是建立在流水車間問題基礎(chǔ)之上的，它只有在滿足特定約束條件下，通過合理地分配各個(gè)加工工藝并行機(jī)的全部任務(wù)，使調(diào)度指標(biāo)達(dá)到最優(yōu)。侯豐龍等[1]研究了TFT?LCD Module 階段的調(diào)度問題，考慮了不同學(xué)習(xí)因子和遺忘因子對(duì)最大完工時(shí)間的影響，在此基礎(chǔ)上建立了數(shù)學(xué)模型，并運(yùn)用布谷鳥算法對(duì)模型進(jìn)行求解。湯洪濤等[2]對(duì)于混合車間調(diào)度問題，將最小化最大完工時(shí)間作為調(diào)度目標(biāo)，并引入多Agent 協(xié)商機(jī)制和模擬退火算法與免疫算法相結(jié)合的方法，提出了基于分解策略的免疫遺傳算法。扈靜等[3]以追求裝配線平衡為研究目標(biāo)，設(shè)計(jì)了基于激素調(diào)節(jié)機(jī)制的改進(jìn)遺傳算法。王福吉等[4]為了運(yùn)用字符串編碼方法來(lái)確定解空間的范圍，設(shè)計(jì)了一種基于可行域搜索的遺傳算法。吳暉[5]針對(duì)Array 制造系統(tǒng)的高度不確定性特征，建立了Array 制造系統(tǒng)的仿真模型，并對(duì)第五代TFT?LCD 車輛調(diào)度問題進(jìn)行了研究。Kahraman等[6]提出了平行貪婪算法求解多處理機(jī)任務(wù)多階段混合流水車間調(diào)度問題。

本文對(duì)TFT?LCD 的單元裝配生產(chǎn)線的混合流水車間調(diào)度問題展開研究，并討論了隨著學(xué)習(xí)因子和遺忘率的變化，工件的加工時(shí)間也會(huì)受到影響。Biskup[7]首次將學(xué)習(xí)效應(yīng)引入到調(diào)度領(lǐng)域，他認(rèn)為影響學(xué)習(xí)效應(yīng)的2 個(gè)因素為加工位置和學(xué)習(xí)效應(yīng)因子。Mosheiov 等[8]在Biskup 的基礎(chǔ)上研究了工件學(xué)習(xí)曲線調(diào)度模型，并且將學(xué)習(xí)因子作為隨工件種類的不同其學(xué)習(xí)因子也不同的量。Rudek[9]證實(shí)了同時(shí)具備學(xué)習(xí)效應(yīng)和遺忘效應(yīng)的單機(jī)器或雙機(jī)器車間調(diào)度問題都是NP?hard(nondeteministic polynomial)。

綜上所述，將學(xué)習(xí)遺忘效應(yīng)引入生產(chǎn)調(diào)度的研究并不多，目前學(xué)者們的研究主要集中在單機(jī)器或者雙機(jī)器的學(xué)習(xí)遺忘效應(yīng)的流水車間調(diào)度問題上。據(jù)此提出將學(xué)習(xí)遺忘效應(yīng)加入多機(jī)器的混合流水車間調(diào)度問題中，研究其對(duì)目標(biāo)函數(shù)的影響。螢火蟲算法是由劍橋?qū)W者Yang[10]在2005 年提出的，他提出這個(gè)算法的靈感來(lái)自自然界中螢火蟲在夜晚會(huì)發(fā)光這一獨(dú)特現(xiàn)象。螢火蟲算法具有適合并行處理、流程簡(jiǎn)單及穩(wěn)定性強(qiáng)等特點(diǎn)，被廣泛應(yīng)用于函數(shù)優(yōu)化、路徑規(guī)劃及社會(huì)科學(xué)等多個(gè)領(lǐng)域，但是，標(biāo)準(zhǔn)的螢火蟲算法也有其弊端，本文運(yùn)用改進(jìn)的螢火蟲算法來(lái)求解TFT?LCD單元裝配調(diào)度模型，并與其他算法進(jìn)行比較，驗(yàn)證了改進(jìn)的螢火蟲算法的合理性和優(yōu)越性。

1 模型描述

1.1 TFT?LCD 單元裝配工藝流程

TFT?LCD 單元裝配工藝在整個(gè)TFT?LCD 生產(chǎn)過程中起到了承上啟下的作用。它的生產(chǎn)線類型等同于混合流水裝配作業(yè)生產(chǎn)線，在混合流水裝配作業(yè)生產(chǎn)線中，工件的裝配過程可以采用并聯(lián)的加工方式，也可以采用串聯(lián)的加工方式。在實(shí)際加工生產(chǎn)中，帶生產(chǎn)支線的裝配作業(yè)調(diào)度其實(shí)就是一種并聯(lián)方式的生產(chǎn)調(diào)度。TFT?LCD 單元裝配工藝的流程圖如圖1 所示。

如圖1 所示，單元裝配是指將陣列制造階段加工完成的TFT 玻璃基板和濾光片基板進(jìn)行層層壓合，隨后對(duì)基板進(jìn)行切割，并將液晶材料充入兩塊基板之間，最后再進(jìn)行檢驗(yàn)的工藝流程。其完整的工藝流程包括如圖1 所示的11 道工序，TFT 玻璃基板的PI 涂布、定向摩擦、框膠形成、彩色濾光片的PI 涂布、定向摩擦、隔離子散布，再將經(jīng)過上述工藝加工好的TFT 玻璃基板和彩色濾光片進(jìn)行對(duì)位粘合、根據(jù)客戶需要的尺寸切割、真空除去液晶空盒中的空氣、注入液晶、封口、偏振片粘附，最后進(jìn)行通電檢查。

1.2 TFT?LCD 單元裝配調(diào)度模型

現(xiàn)對(duì)如圖1 所示的TFT?LCD 單元裝配調(diào)度問題進(jìn)行描述。

圖1 TFT-LCD 單元裝配工藝流程Fig.1 Cell stage process flow chart

有若干種不同類型的工件，它們由零件M 和零件N 分別經(jīng)過若干不同加工工藝后，最終裝配成工件Φ，在現(xiàn)實(shí)生產(chǎn)中將批（lot）作為生產(chǎn)的基本單位，任何一批工件都由許多相同工件組成，約束條件：

a.工件一旦開始加工就不允許中斷；

b.同一工件加工路徑是確定的，不同工件工序間加工順序不分先后；

c.忽略設(shè)備生產(chǎn)過程中可能出現(xiàn)的損壞延誤問題；

d.不考慮次品返工問題；

e.同一機(jī)器連續(xù)生產(chǎn)的兩批工件不屬于同種類型，不考慮設(shè)備準(zhǔn)備時(shí)間；

f.機(jī)器一批只能加工一種工件。

1.3 數(shù)學(xué)模型和參數(shù)設(shè)定

目標(biāo)函數(shù)

式中：Tmax為最小化最大完工時(shí)間；Tt為最小化加權(quán)延遲時(shí)間；Tij為機(jī)器的完工時(shí)間；dij為工件Jij的交貨時(shí)間；wij是工件Jij的延遲權(quán)重。

為了后續(xù)求解簡(jiǎn)便，將其轉(zhuǎn)化為單目標(biāo)處理，即令 f1(x)=Tmax，f2(x)=Tt，故

式中，w1，w2為自定義參數(shù)，取值為[0,1]，且w1+w2=1。

約束條件：式中：n 為工件種類總數(shù)；Ei表示第i 種工件種類，i =1,2,···,n，由于每種工件由零件M 和零件N組裝而成，Ei為零件M 批裝配產(chǎn)品；Ei*為零件N 批裝配產(chǎn)品；Ei+為零件M 批和零件N 批的裝配產(chǎn)品；Jij為工件種類Ei的第j 批工件，j =1,2,3,···,hi；hi表示第i 種工件的等待加工工件總批量；Ok表示第k 道工序，k=1,2,···,c,c+1,···,z,z+1,···,s；1到 c, c+1到 z, z+1到s 分別表示零件M，零件N 及裝配后零件的加工工序；指工序Oik的開始時(shí)間；Pijk，分別表示一般加工時(shí)間以及工序Oik的完工時(shí)間； Yi,j,k,m為決策變量。

式中，Mkm為第k 道工序的第m 臺(tái)機(jī)器。

式（1）表示目標(biāo)函數(shù)為最小化最大完工時(shí)間；式（2）表示全部工件的加權(quán)延遲時(shí)間最?。皇剑?）表示將多目標(biāo)問題轉(zhuǎn)換為單目標(biāo)問題處理；式（4）表示任一工件只允許在一臺(tái)機(jī)器上加工；式（5）表示一臺(tái)機(jī)器同一時(shí)刻只允許加工一批工件；式（6）表示零件M 前一道工序的總批數(shù)必須不少于后一道工序總批數(shù)；式（7）表示零件N 后一道工序總批數(shù)不多于前一道工序總批數(shù)；式（8）和式（9）表示裝配工序R 的總批數(shù)必須少于M 工件批和N 工件批的總批數(shù)；式（10）和式（11）表示裝配時(shí)M 批工件和N 批工件必須在同一機(jī)器上加工，且同時(shí)開始加工；式（12）表示每個(gè)工件必須要按照既定的先后順序進(jìn)行加工。

2 改進(jìn)的螢火蟲算法

2.1 螢火蟲算法描述

螢火蟲算法[11-12]作為一種新興的元啟發(fā)式群智能算法，目前主要應(yīng)用于解決優(yōu)化問題，但是，隨著科學(xué)技術(shù)的發(fā)展和研究的深入，它將會(huì)運(yùn)用到各個(gè)領(lǐng)域。該算法源于自然界螢火蟲在晚上的聚集活動(dòng)并自身發(fā)光的自然現(xiàn)象而產(chǎn)生的，并且有效地描述了螢火蟲自身亮度的變化以及吸引度的大小，通過模擬螢火蟲憑借亮度與吸引度去尋找它的伙伴這一類本能行為，實(shí)現(xiàn)了優(yōu)化目標(biāo)函數(shù)的目的。螢火蟲算法作為仿生群智能算法的一種，主要由2 個(gè)關(guān)鍵因素所決定，即自身發(fā)出光的亮度和它吸引同伴的能力。螢火蟲自身發(fā)出亮光的大小決定了個(gè)體所在位置的優(yōu)越性及其運(yùn)動(dòng)的方向，其運(yùn)動(dòng)的距離和它吸引同伴的能力有關(guān)，隨著亮度和吸引力的不斷刷新，從而實(shí)現(xiàn)目標(biāo)函數(shù)值優(yōu)化的過程?，F(xiàn)描述其優(yōu)化原理。

定義1螢火蟲的相對(duì)熒光亮度

式中：I0表示個(gè)體所在位置的最大熒光亮度；γ 是光強(qiáng)吸收系數(shù)，也可以將它設(shè)定為常數(shù)；rij是個(gè)體i 與個(gè)體j 之間的空間距離。

I0和目標(biāo)函數(shù)值呈正相關(guān)關(guān)系。若目標(biāo)函數(shù)值越優(yōu)，那么，螢火蟲亮度就越高。

定義2螢火蟲的吸引度

式中：β0表示2 個(gè)螢火蟲彼此之間距離等于零時(shí)螢火蟲i 對(duì)螢火蟲j 的吸引力。

定義3螢火蟲i 被吸引向螢火蟲j 移動(dòng)的位置更新

式中：xi，xj是螢火蟲個(gè)體i 和j 所處的空間位置； ?是步長(zhǎng)因子，為[0,1]上的常數(shù)；rand 為[0,1]之間均勻分布的隨機(jī)數(shù)。

2.2 混沌螢火蟲算法

通過大量研究表明，當(dāng)初始的螢火蟲算法經(jīng)過反復(fù)迭代尋優(yōu)接近尾聲時(shí)，大部分螢火蟲都聚集在局部以及全局極值點(diǎn)附近，隨著距離的逐漸減小，螢火蟲之間的吸引力逐漸變大，這種情況將會(huì)導(dǎo)致算法的局部尋優(yōu)能力下降，在算法迭代次數(shù)有限的情況下，無(wú)法達(dá)到精度的要求。綜上所述，基本的螢火蟲算法容易陷入局部最優(yōu)，一旦到達(dá)局部最優(yōu)極值點(diǎn)附近，算法出現(xiàn)了收斂速度慢且在極值點(diǎn)附近震蕩的問題。為解決此類問題，提高算法的尋優(yōu)精度，利用混沌運(yùn)動(dòng)的普遍性、隨機(jī)性等特點(diǎn)，在螢火蟲算法的基礎(chǔ)上，引入了混沌思想，從而提高螢火蟲種群的多樣性和尋優(yōu)的遍歷性。

2.3 算法改進(jìn)

混沌是普遍存在于非線性系統(tǒng)中的一種現(xiàn)象，具有隨機(jī)性、規(guī)則性及遍歷性等特點(diǎn)，能在其取值范圍內(nèi)按其自身規(guī)律不重復(fù)地歷經(jīng)所有可能狀態(tài)，所以，混沌搜索是一種新穎并且高效的優(yōu)化工具。混沌搜索的原理：通過某個(gè)特定格式迭代產(chǎn)生混沌序列，然后通過載波的方式將其引入優(yōu)化空間。相關(guān)研究表明，邏輯自映射函數(shù)易于計(jì)算，且其生成的混沌序列遍歷性較常用的Logistic 映射更優(yōu)[13]。因此，本文選用邏輯自映射函數(shù)產(chǎn)生混沌序列，待尋優(yōu)問題的數(shù)學(xué)表達(dá)式為

式中：ni表示n 類粒子第i 個(gè)個(gè)體；表示第*維的個(gè)體ni。

個(gè)體ni處于多維空間內(nèi)，將ni在第q 維的位置表示為，則∈(,)。表示在第q 維的第i 個(gè)A 類粒子，wiq表示在第q 維的第i 個(gè)w 粒子。由于定義域限制，使用式（17）將xi的所有搜索空間維度映射至定義域（?1，0）∪（0，1）

得到經(jīng)過載波操作后的混沌變量序列，再使用式（18）將其映射回原空間。

此時(shí)，對(duì)新個(gè)體進(jìn)行評(píng)價(jià)。若對(duì)應(yīng)的函數(shù)值更優(yōu)，則保留該個(gè)體；否則，直接進(jìn)行下輪混沌搜索，直至達(dá)到混沌搜索次數(shù)。改進(jìn)的混沌螢火蟲算法的主要步驟如圖2 所示。

圖2 混沌螢火蟲算法流程圖Fig.2 Improved firefly algorithm flow chart

2.4 算法復(fù)雜度分析

算法復(fù)雜度是評(píng)估算法性能的一個(gè)重要指標(biāo)，它決定了算法的執(zhí)行效率，并且在很大程度上影響著計(jì)算機(jī)的求解能力。由上面的算法流程容易看出，改進(jìn)的螢火蟲算法花費(fèi)的計(jì)算時(shí)間主要在算法的迭代進(jìn)化過程中。假設(shè)求解問題的問題規(guī)模為D，種群規(guī)模為Q，迭代次數(shù)為W。在每一次的進(jìn)化迭代過程中，算法主要的計(jì)算量包含螢火蟲位置更新與局部鄰域搜索兩部分。在螢火蟲位置更新部分，對(duì)種群中的螢火蟲進(jìn)行共30 次的位置更新操作，且每10 次取一個(gè)平均值。其最復(fù)雜情況下的最大計(jì)算時(shí)間復(fù)雜度為3WO（QD），計(jì)算適應(yīng)度值以及保留最優(yōu)個(gè)體的時(shí)間復(fù)雜度分別為WO（QD）和WO（Q），所以，該部分總的計(jì)算時(shí)間復(fù)雜度為4WO（QD）+WO（Q）；在局部鄰域搜索部分，需要對(duì)種群中30%的螢火蟲進(jìn)行混沌搜索，最大的時(shí)間復(fù)雜度為0.3WO（QD），計(jì)算適應(yīng)度值及保留最優(yōu)個(gè)體的計(jì)算時(shí)間復(fù)雜度分別為0.3WO（QD）和0.3WO（Q），所以，該部分總的計(jì)算時(shí)間復(fù)雜度為0.6WO（QD）+0.3WO（Q），因此，整個(gè)改進(jìn)的螢火蟲算法的計(jì)算時(shí)間復(fù)雜度

基本螢火蟲算法需要更新螢火蟲的最大熒光亮度和位置，同樣需要計(jì)算適應(yīng)度值及保留最優(yōu)個(gè)體，其計(jì)算時(shí)間復(fù)雜度

由式（20）可以得到，算法的計(jì)算時(shí)間復(fù)雜度僅與求解問題的問題規(guī)模D，種群規(guī)模Q 和迭代次數(shù)W 有關(guān)。對(duì)比式（21）可以得到，相對(duì)于基本螢火蟲算法，改進(jìn)的螢火蟲算法并沒有明顯地增加算法的計(jì)算時(shí)間復(fù)雜度。

3 TFT?LCD 單元裝配調(diào)度問題求解

3.1 編碼設(shè)計(jì)與解碼過程

螢火蟲算法主要用于解決的是連續(xù)優(yōu)化問題，但是，TFT?LCD 單元裝配調(diào)度這一類混合流水作業(yè)車間調(diào)度問題屬于工件排序問題，即為離散調(diào)度問題。根據(jù)此類情況，需要建立連續(xù)空間到離散空間的映射，本文采用兩段式編碼[14]和IMM 編碼[13]相結(jié)合的方式進(jìn)行編碼設(shè)計(jì)。兩段式編碼的優(yōu)點(diǎn)主要是便于解決連續(xù)型參數(shù)的優(yōu)化問題。由于兩段式編碼不能直接用于多機(jī)器混合流水調(diào)度問題，故運(yùn)用兩者相結(jié)合的方式進(jìn)行編碼設(shè)計(jì)。兩段式編碼過程如圖3 所示。

圖3 兩段式編碼方式Fig.3 Two segments encoding method

如圖3 所示，首先設(shè)定好每批工件對(duì)應(yīng)的工序和機(jī)器。將第二條染色體的工件批數(shù)設(shè)置為5 批，且每批都有2 個(gè)工序，彩色框中的數(shù)字表示每批工件每道工序相對(duì)應(yīng)的加工機(jī)器。在第一條染色體中，彩色框中的數(shù)字為工件加工批數(shù)，每個(gè)數(shù)字出現(xiàn)次數(shù)表示工序數(shù)。第二行小數(shù)是由迭代數(shù)據(jù)降序排列后得到。如在第二條染色體中，O2在m=2 上加工的為J2，J3，J5，且2，3，5 在第一條染色體中首次出現(xiàn)的順序?yàn)?，5，3，故它們加工的先后順序也應(yīng)為J2，J5，J3。m 為機(jī)器，J 為工件。所以，第二條染色體是按照第一條染色體設(shè)定好的參數(shù)并經(jīng)過迭代后進(jìn)行降序排序，由此確定加工順序。為了實(shí)現(xiàn)連續(xù)型到離散型的映射，隨后采用IMM 編碼方式，它是基于隨機(jī)鍵并借助中間媒介的一種編碼方法，其中包含2 個(gè)過程：從實(shí)數(shù)集合xi到工件排序πi的階段以及從工件排序πi*到實(shí)數(shù)集合xi*的階段。先將隨機(jī)獲得的實(shí)數(shù)集合 xi={xi1, xi2, ···, xin}按降序進(jìn)行排列，得到了中間集合 ?i={?i1, ?i2, ···, ?in}，隨后依據(jù) πi,?ij= j 的 準(zhǔn) 則,取 得 中 間 介 質(zhì) 為 ?i′，最 后 一 步xi'再按照?i'選取初始實(shí)數(shù)集合xi的第j 個(gè)數(shù)。

在解碼過程中，首先將螢火蟲的位置轉(zhuǎn)化為一個(gè)有序的工作表，隨后根據(jù)工作表和工藝要求對(duì)每個(gè)操作以其最早允許加工時(shí)間逐個(gè)開始加工，最終就會(huì)產(chǎn)生目標(biāo)函數(shù)值。

3.2 仿真實(shí)驗(yàn)與分析

為了研究TFT?LCD Cell 階段調(diào)度問題，本文根據(jù)TFT?LCD 生產(chǎn)企業(yè)單元裝配的生產(chǎn)情況，結(jié)合此次調(diào)度問題，設(shè)定了產(chǎn)品批量數(shù)以及產(chǎn)品種類，其中，工件種類n=3，加工機(jī)器m=5，整個(gè)加工過程包含11 道工序，表1 為在3 臺(tái)機(jī)器M1，M2，M3上，3 種類型的產(chǎn)品所對(duì)應(yīng)的產(chǎn)品加工時(shí)間。例如，O11表示在第一道工序中，類型1 的產(chǎn)品在3 臺(tái)機(jī)器上的加工時(shí)間分別為12，11，10。表2 為3 種類型產(chǎn)品所對(duì)應(yīng)的批量數(shù)。表3 為各工序所對(duì)應(yīng)的機(jī)器數(shù)目。表4 為各類產(chǎn)品所對(duì)應(yīng)的交貨期及加權(quán)延遲。

表1 3 臺(tái)機(jī)器產(chǎn)品加工時(shí)間表Tab.1 Machine processing time min

表2 產(chǎn)品批量數(shù)Tab.2 Work-piece type and lot size

表3 各工序機(jī)器數(shù)Tab.3 Machine numbers in each process

表4 工件交貨期及加權(quán)延遲Tab.4 Work-piece basic information

運(yùn)用螢火蟲智能算法求解TFT-LCD 單元裝配調(diào)度問題仿真實(shí)驗(yàn)操作系統(tǒng)為Windows 7,CPU Intel（R）Core（TM）i 5?5200 U 及8 G 內(nèi)存，采用Matlab R2014a 進(jìn)行算法編程。采用螢火蟲算法參數(shù)設(shè)置：種群規(guī)模為50，迭代次數(shù)為100，光強(qiáng)吸收系數(shù)為1，隨機(jī)因子為0.5，算法獨(dú)立運(yùn)行10 次。

由表5 可知，在單元裝配調(diào)度問題中，螢火蟲算法（FA）求解得到的最大完成時(shí)間優(yōu)于遺傳算法中的貪婪解碼（GD）和靜態(tài)解碼?精英保留（SD?ES），而加入混沌搜索機(jī)制的螢火蟲算法（ICFA）與標(biāo)準(zhǔn)螢火蟲算法（FA）相比更加具有優(yōu)勢(shì)，圖4 為ICFA 算法與FA 算法的結(jié)果對(duì)比圖。

如圖4 所示，橫坐標(biāo)表示迭代100 次后，算法獨(dú)立運(yùn)行10 次；縱坐標(biāo)表示最大完工時(shí)間。Cmax1表示標(biāo)準(zhǔn)的螢火蟲算法，Cmax 表示加入混沌搜索螢火蟲算法。Cmax 曲線明顯優(yōu)于Cmax1 曲線，Cmax1 曲線波動(dòng)幅度較大，而Cmax 曲線趨于平穩(wěn)狀態(tài)，說明改進(jìn)的螢火蟲算法（ICFA）結(jié)果優(yōu)于螢火蟲算法（FA），并且穩(wěn)定性較好。

表5 4 種方法得到的最大完工時(shí)間Tab.5 Cmax obtained by four methods min

圖4 ICFA 和FA 最大完工時(shí)間對(duì)比Fig.4 Comparison between the Cmaxs of ICFA and FA

表6 為4 種方法得到的目標(biāo)函數(shù)值，從表中可以看出，螢火蟲算法（FA）要優(yōu)于遺傳算法中的貪婪解碼（GD）以及靜態(tài)解碼?精英保留（SD?ES）。另外，加入混沌搜索后的螢火蟲算法的結(jié)果優(yōu)于標(biāo) 準(zhǔn)的螢火蟲算法。

表6 4 種方法得到的目標(biāo)函數(shù)最優(yōu)值Tab.6 Objective function obtained by four methods

圖5 為加入混沌搜索后的螢火蟲算法（ICFA）與標(biāo)準(zhǔn)的螢火蟲算法（FA）目標(biāo)函數(shù)值的對(duì)比圖，從圖中可以看出，改進(jìn)后的螢火蟲算法結(jié)果(Obj1)明顯 優(yōu)于標(biāo)準(zhǔn)螢火蟲算法(Obj)，且結(jié)果的穩(wěn)定性更好。

圖5 ICFA 和FA 算法目標(biāo)函數(shù)最優(yōu)值對(duì)比Fig.5 Comparison between the optimal ralues of objective functions of ICFA and FA

綜上所述，同一實(shí)驗(yàn)數(shù)據(jù)，加入混沌搜索后的螢火蟲算法在求解最大完工時(shí)間以及目標(biāo)函數(shù)值時(shí)，其結(jié)果都要優(yōu)于標(biāo)準(zhǔn)的螢火蟲算法的求解結(jié)果。從運(yùn)行結(jié)果比較得出，改進(jìn)后的螢火蟲算法的解最優(yōu)，能取得最短的完工時(shí)間，從而可以保證工件能夠按時(shí)交貨。

4 TFT?LCD Cell 階段調(diào)度問題模型

4.1 學(xué)習(xí)效應(yīng)對(duì)TFT?LCD 單元裝配階段影響分析

學(xué)習(xí)效應(yīng)是1936 年美國(guó)康奈爾大學(xué)的Wright[15]在研究飛機(jī)制造過程中勞動(dòng)時(shí)間與產(chǎn)量之間的規(guī)律時(shí)發(fā)現(xiàn)的，并首次在制造業(yè)中提出經(jīng)驗(yàn)曲線。Yelle[16]在1979 年第一次采用另一個(gè)名稱——學(xué)習(xí)曲線來(lái)定義經(jīng)驗(yàn)曲線，最初的學(xué)習(xí)曲線的表達(dá)式為

式中：Y 為第x 個(gè)零件的加工時(shí)間；X 為累積加工量；T1為第一個(gè)工件的加工時(shí)間；a 為學(xué)習(xí)因子，a<0。

學(xué)習(xí)曲線如圖6 所示。

圖6 學(xué)習(xí)曲線Fig.6 Learning curve

在經(jīng)典的生產(chǎn)調(diào)度問題中，每個(gè)工件每一道工序的加工時(shí)間都是固定不變的，并不會(huì)考慮到工件加工時(shí)間會(huì)受到所在加工位置的影響。然而在實(shí)際生產(chǎn)中，由于工人會(huì)從前一個(gè)工件的加工生產(chǎn)中吸取經(jīng)驗(yàn)，后一個(gè)加工工件會(huì)比前一個(gè)工件所需加工時(shí)間要少，這就是學(xué)習(xí)效應(yīng)。但是，在實(shí)際的加工生產(chǎn)中，機(jī)器不可能一直保持高強(qiáng)度運(yùn)轉(zhuǎn)狀態(tài)，當(dāng)下一臺(tái)機(jī)器準(zhǔn)備要加工的工件還在上一臺(tái)機(jī)器加工時(shí)，就會(huì)產(chǎn)生空閑時(shí)間，并且還存在設(shè)備設(shè)置時(shí)間以及工件類型的改變這些影響加工時(shí)間的因素，這就有了遺忘效應(yīng)。Biskup[7]是第一位將學(xué)習(xí)效應(yīng)應(yīng)用于排序問題的學(xué)者，他指出，由于工人不斷地重復(fù)類似的加工工作，其熟練程度會(huì)越來(lái)越好，所以，后一個(gè)工件所需的加工時(shí)間就會(huì)比前一個(gè)工件加工時(shí)間少，加工時(shí)間與工件排序中其加工的位置相互之間為遞減的函數(shù)關(guān)系。

綜上所述，在生產(chǎn)作業(yè)車間中，學(xué)習(xí)因子和遺忘效應(yīng)與工件加工位置和工件等待時(shí)間有關(guān)，本文在借鑒文獻(xiàn)[17]的學(xué)習(xí)效應(yīng)模型的基礎(chǔ)上，建立了針對(duì)混合流水車間的學(xué)習(xí)遺忘效應(yīng)模型。

4.2 學(xué)習(xí)遺忘效應(yīng)對(duì)TFT?LCD 單元裝配調(diào)度問題的影響

在TFT?LCD 單元裝配調(diào)度問題中，學(xué)習(xí)效應(yīng)和遺忘效應(yīng)是共存的，由于加工機(jī)器的不同，學(xué)習(xí)率和遺忘率也會(huì)有所不同。當(dāng)學(xué)習(xí)率l 分別取0.7，0.8，0.9，1 時(shí)，與之相對(duì)應(yīng)的學(xué)習(xí)因子a 就取?0.515，?0.322，?0.152，0，遺忘率b 分別取0.1，0.2，0.3。

本文采用改進(jìn)的螢火蟲算法獨(dú)立運(yùn)行20 次，各算例隨機(jī)生成50 組數(shù)據(jù)，計(jì)算TFT?LCD 單元裝配階段調(diào)度問題在相同學(xué)習(xí)率、不同遺忘率的所有情況。從圖6 中可見，隨著學(xué)習(xí)率與遺忘率的變化，最大完工時(shí)間也隨之變化，說明學(xué)習(xí)遺忘效應(yīng)會(huì)影響最大完工時(shí)間。

在TFT?LCD Cell 階段調(diào)度過程中，遺忘效應(yīng)和學(xué)習(xí)效應(yīng)是共同存在的，所以，如果去單一考慮其中一個(gè)效應(yīng)，就會(huì)造成實(shí)驗(yàn)結(jié)果不準(zhǔn)確，導(dǎo)致資源沒有進(jìn)行合理的分配，從而影響了整個(gè)調(diào)度結(jié)果。圖7 中黑線、紅線、綠線表示在遺忘率b 分別為0.1，0.2，0.3 時(shí)，學(xué)習(xí)率分別為1，0.9，0.8，0.7 時(shí)對(duì)應(yīng)的目標(biāo)函數(shù)曲線，學(xué)習(xí)率1，0.9，0.8， 0.7 分 別 對(duì) 應(yīng) 的 學(xué) 習(xí) 因 子 為0， ?0.152，?0.322，?0.515。從圖中能夠明顯看出，3 條曲線的趨勢(shì)存在明顯差異，遺忘率越大，目標(biāo)函數(shù)值越大，目標(biāo)函數(shù)隨著遺忘率的增加而增加，兩者成正比關(guān)系，遺忘效應(yīng)的增加表明工件的等待時(shí)間會(huì)對(duì)最大完工時(shí)間產(chǎn)生較大的影響，這是符合實(shí)際情況的。同時(shí)可以發(fā)現(xiàn)，當(dāng)學(xué)習(xí)率較高時(shí)，最小化最大完工時(shí)間也隨之增大，在學(xué)習(xí)率l∈（0.7，0.8）時(shí)，即學(xué)習(xí)因子在（?0.515，?0.332）區(qū)間時(shí)，曲線呈現(xiàn)明顯的上升趨勢(shì)，即目標(biāo)函數(shù)上升趨勢(shì)明顯，這表明在加工生產(chǎn)中，有可能短時(shí)間內(nèi)大量設(shè)備出現(xiàn)故障使得生產(chǎn)中斷或者產(chǎn)品種類的變更等其他影響加工生產(chǎn)進(jìn)度的狀況出現(xiàn)，都會(huì)導(dǎo)致工期延長(zhǎng)。當(dāng)學(xué)習(xí)率越低，遺忘率的影響也就越小，這時(shí)最大完工時(shí)間也就越小。當(dāng)學(xué)習(xí)率大于0.8 時(shí)，曲線漸漸趨于平滑，表明隨著學(xué)習(xí)效果的持續(xù)下降，最大完工時(shí)間并不會(huì)呈直線型增長(zhǎng)，而是慢慢地趨于一個(gè)穩(wěn)定值。

圖7 具有不同學(xué)習(xí)率和遺忘率的目標(biāo)函數(shù)變化趨勢(shì)Fig.7 Objective function curves with different learning and forgetting rates

5 結(jié)束語(yǔ)

對(duì)TFT?LCD 單元裝配階段作業(yè)車間調(diào)度問題建立以最小化最大完工時(shí)間和加權(quán)延遲最小為目標(biāo)的數(shù)學(xué)模型，在對(duì)傳統(tǒng)調(diào)度問題研究的基礎(chǔ)上，考慮到在實(shí)際的機(jī)器運(yùn)行加工生產(chǎn)中，與理想存在較大的差距，引入學(xué)習(xí)效應(yīng)和遺忘效應(yīng)。同時(shí)討論了學(xué)習(xí)遺忘效應(yīng)對(duì)完工時(shí)間的影響，利用加入混沌搜索后的螢火蟲算法對(duì)模型進(jìn)行求解，通過與標(biāo)準(zhǔn)的螢火蟲算法比較，證明了改進(jìn)的螢火蟲算法在解決TFT?LCD Cell 階段調(diào)度問題時(shí)的有效性，具有良好的發(fā)展前景。本文的目標(biāo)函數(shù)針對(duì)性地考慮了加權(quán)延遲以及最大完工時(shí)間，在TFT?LCD 生產(chǎn)調(diào)度未來(lái)的研究中，考慮的問題也必須更加全面，在算法改進(jìn)方面未來(lái)也會(huì)嘗試更多的改進(jìn)方法，以期更好地解決在實(shí)際生產(chǎn)中存在的問題，進(jìn)一步提高生產(chǎn)效率，減少機(jī)器空閑時(shí)間。