運用改進的螢火蟲算法求解TFT-LCD 單元裝配調度問題

李瑞婷，葉春明，吳思思

（上海理工大學 管理學院，上海 200093）

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

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

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

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

綜上所述，將學習遺忘效應引入生產調度的研究并不多，目前學者們的研究主要集中在單機器或者雙機器的學習遺忘效應的流水車間調度問題上。據此提出將學習遺忘效應加入多機器的混合流水車間調度問題中，研究其對目標函數的影響。螢火蟲算法是由劍橋學者Yang[10]在2005 年提出的，他提出這個算法的靈感來自自然界中螢火蟲在夜晚會發光這一獨特現象。螢火蟲算法具有適合并行處理、流程簡單及穩定性強等特點，被廣泛應用于函數優化、路徑規劃及社會科學等多個領域，但是，標準的螢火蟲算法也有其弊端，本文運用改進的螢火蟲算法來求解TFT?LCD單元裝配調度模型，并與其他算法進行比較，驗證了改進的螢火蟲算法的合理性和優越性。

1 模型描述

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

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

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

1.2 TFT?LCD 單元裝配調度模型

現對如圖1 所示的TFT?LCD 單元裝配調度問題進行描述。

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

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

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

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

c.忽略設備生產過程中可能出現的損壞延誤問題；

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

e.同一機器連續生產的兩批工件不屬于同種類型，不考慮設備準備時間；

f.機器一批只能加工一種工件。

1.3 數學模型和參數設定

目標函數

式中：Tmax為最小化最大完工時間；Tt為最小化加權延遲時間；Tij為機器的完工時間；dij為工件Jij的交貨時間；wij是工件Jij的延遲權重。

為了后續求解簡便，將其轉化為單目標處理，即令 f1(x)=Tmax，f2(x)=Tt，故

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

約束條件：式中：n 為工件種類總數；Ei表示第i 種工件種類，i =1,2,···,n，由于每種工件由零件M 和零件N組裝而成，Ei為零件M 批裝配產品；Ei*為零件N 批裝配產品；Ei+為零件M 批和零件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的開始時間；Pijk，分別表示一般加工時間以及工序Oik的完工時間； Yi,j,k,m為決策變量。

式中，Mkm為第k 道工序的第m 臺機器。

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

2 改進的螢火蟲算法

2.1 螢火蟲算法描述

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

定義1螢火蟲的相對熒光亮度

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

I0和目標函數值呈正相關關系。若目標函數值越優，那么，螢火蟲亮度就越高。

定義2螢火蟲的吸引度

式中：β0表示2 個螢火蟲彼此之間距離等于零時螢火蟲i 對螢火蟲j 的吸引力。

定義3螢火蟲i 被吸引向螢火蟲j 移動的位置更新

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

2.2 混沌螢火蟲算法

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

2.3 算法改進

混沌是普遍存在于非線性系統中的一種現象，具有隨機性、規則性及遍歷性等特點，能在其取值范圍內按其自身規律不重復地歷經所有可能狀態，所以，混沌搜索是一種新穎并且高效的優化工具?；煦缢阉鞯脑恚和ㄟ^某個特定格式迭代產生混沌序列，然后通過載波的方式將其引入優化空間。相關研究表明，邏輯自映射函數易于計算，且其生成的混沌序列遍歷性較常用的Logistic 映射更優[13]。因此，本文選用邏輯自映射函數產生混沌序列，待尋優問題的數學表達式為

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

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

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

此時，對新個體進行評價。若對應的函數值更優，則保留該個體；否則，直接進行下輪混沌搜索，直至達到混沌搜索次數。改進的混沌螢火蟲算法的主要步驟如圖2 所示。

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

2.4 算法復雜度分析

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

基本螢火蟲算法需要更新螢火蟲的最大熒光亮度和位置，同樣需要計算適應度值及保留最優個體，其計算時間復雜度

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

3 TFT?LCD 單元裝配調度問題求解

3.1 編碼設計與解碼過程

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

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

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

在解碼過程中，首先將螢火蟲的位置轉化為一個有序的工作表，隨后根據工作表和工藝要求對每個操作以其最早允許加工時間逐個開始加工，最終就會產生目標函數值。

3.2 仿真實驗與分析

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

表1 3 臺機器產品加工時間表Tab.1 Machine processing time min

表2 產品批量數Tab.2 Work-piece type and lot size

表3 各工序機器數Tab.3 Machine numbers in each process

表4 工件交貨期及加權延遲Tab.4 Work-piece basic information

運用螢火蟲智能算法求解TFT-LCD 單元裝配調度問題仿真實驗操作系統為Windows 7,CPU Intel（R）Core（TM）i 5?5200 U 及8 G 內存，采用Matlab R2014a 進行算法編程。采用螢火蟲算法參數設置：種群規模為50，迭代次數為100，光強吸收系數為1，隨機因子為0.5，算法獨立運行10 次。

由表5 可知，在單元裝配調度問題中，螢火蟲算法（FA）求解得到的最大完成時間優于遺傳算法中的貪婪解碼（GD）和靜態解碼?精英保留（SD?ES），而加入混沌搜索機制的螢火蟲算法（ICFA）與標準螢火蟲算法（FA）相比更加具有優勢，圖4 為ICFA 算法與FA 算法的結果對比圖。

如圖4 所示，橫坐標表示迭代100 次后，算法獨立運行10 次；縱坐標表示最大完工時間。Cmax1表示標準的螢火蟲算法，Cmax 表示加入混沌搜索螢火蟲算法。Cmax 曲線明顯優于Cmax1 曲線，Cmax1 曲線波動幅度較大，而Cmax 曲線趨于平穩狀態，說明改進的螢火蟲算法（ICFA）結果優于螢火蟲算法（FA），并且穩定性較好。

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

圖4 ICFA 和FA 最大完工時間對比Fig.4 Comparison between the Cmaxs of ICFA and FA

表6 為4 種方法得到的目標函數值，從表中可以看出，螢火蟲算法（FA）要優于遺傳算法中的貪婪解碼（GD）以及靜態解碼?精英保留（SD?ES）。另外，加入混沌搜索后的螢火蟲算法的結果優于標 準的螢火蟲算法。

表6 4 種方法得到的目標函數最優值Tab.6 Objective function obtained by four methods

圖5 為加入混沌搜索后的螢火蟲算法（ICFA）與標準的螢火蟲算法（FA）目標函數值的對比圖，從圖中可以看出，改進后的螢火蟲算法結果(Obj1)明顯 優于標準螢火蟲算法(Obj)，且結果的穩定性更好。

圖5 ICFA 和FA 算法目標函數最優值對比Fig.5 Comparison between the optimal ralues of objective functions of ICFA and FA

綜上所述，同一實驗數據，加入混沌搜索后的螢火蟲算法在求解最大完工時間以及目標函數值時，其結果都要優于標準的螢火蟲算法的求解結果。從運行結果比較得出，改進后的螢火蟲算法的解最優，能取得最短的完工時間，從而可以保證工件能夠按時交貨。

4 TFT?LCD Cell 階段調度問題模型

4.1 學習效應對TFT?LCD 單元裝配階段影響分析

學習效應是1936 年美國康奈爾大學的Wright[15]在研究飛機制造過程中勞動時間與產量之間的規律時發現的，并首次在制造業中提出經驗曲線。Yelle[16]在1979 年第一次采用另一個名稱——學習曲線來定義經驗曲線，最初的學習曲線的表達式為

式中：Y 為第x 個零件的加工時間；X 為累積加工量；T1為第一個工件的加工時間；a 為學習因子，a<0。

學習曲線如圖6 所示。

圖6 學習曲線Fig.6 Learning curve

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

綜上所述，在生產作業車間中，學習因子和遺忘效應與工件加工位置和工件等待時間有關，本文在借鑒文獻[17]的學習效應模型的基礎上，建立了針對混合流水車間的學習遺忘效應模型。

4.2 學習遺忘效應對TFT?LCD 單元裝配調度問題的影響

在TFT?LCD 單元裝配調度問題中，學習效應和遺忘效應是共存的，由于加工機器的不同，學習率和遺忘率也會有所不同。當學習率l 分別取0.7，0.8，0.9，1 時，與之相對應的學習因子a 就取?0.515，?0.322，?0.152，0，遺忘率b 分別取0.1，0.2，0.3。

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

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

圖7 具有不同學習率和遺忘率的目標函數變化趨勢Fig.7 Objective function curves with different learning and forgetting rates

5 結束語

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