基于改進(jìn)布谷鳥搜索算法的TFT-LCD制造調(diào)度方法①

劉庭宇,葉春明

(上海理工大學(xué) 管理學(xué)院,上海 200093)

由于資源消耗和環(huán)境影響,可持續(xù)性成為工業(yè)界的一個(gè)重要課題.其中,能源消耗和碳排放是制造業(yè)在綠色條件下運(yùn)作的兩個(gè)主要問題.Garetti 等[1]指出制造業(yè)占世界能源消耗的33%,碳排放總量的38%以上.隨著陰極射線管(CRT)被平板顯示器取代,薄膜晶體管液晶顯示器(TFT-LCD)面板在監(jiān)控設(shè)備、液晶電視、移動(dòng)電話和平板個(gè)人電腦等領(lǐng)域廣泛應(yīng)用,其需求迅速增長.與其他平板顯示類產(chǎn)品[2]相比,10 英寸TFT-LCD 及以上產(chǎn)品的年銷售總量占全球的50%以上.TFT-LCD 產(chǎn)品在生產(chǎn)過程中消耗大量的能源,電力約占75%,其中,機(jī)器運(yùn)轉(zhuǎn)所消耗的電力占45～50%[3].因此,如何通過生產(chǎn)調(diào)度,有效降低TFT-LCD 產(chǎn)品生產(chǎn)過程中的能源消耗和碳排放量,達(dá)到節(jié)能減排顯得尤為重要.

在TFT-LCD 生產(chǎn)調(diào)度研究領(lǐng)域,陣列工藝(array)階段包含大量可重入制造工藝,面板工藝(cell)階段包含大量并行機(jī)工藝,模塊工藝(module)階段可以看作柔性作業(yè)車間問題.在array 階段,Choi 等[4]提出了一種具有決策樹的實(shí)時(shí)調(diào)度機(jī)制,它消除了通過仿真運(yùn)行選擇調(diào)度規(guī)則所需的計(jì)算負(fù)擔(dān).Hong 等[5]提出一種兩相解碼遺傳算法,以最大限度地利用光刻階段,提高了機(jī)器利用率和生產(chǎn)系統(tǒng)的能力.在cell 階段,Lin 等[6]在考慮批量釋放時(shí)間的同時(shí)也考慮了調(diào)度規(guī)則的影響,并提出一種基于批量釋放時(shí)間的啟發(fā)式算法和基于隊(duì)列時(shí)間最大不匹配的摩擦機(jī)調(diào)度規(guī)則,提高了cell 階段的生產(chǎn)效率.Wu 等[7]建立了一種DBR 定制模型,并提出了一種利用轉(zhuǎn)鼓緩沖繩(DBR)系統(tǒng)對(duì)cell 階段進(jìn)行調(diào)度控制的方法,提高了cell 階段的生產(chǎn)效率.徐峰等[8]以最小化最大完工時(shí)間和交貨期最短為目標(biāo)函數(shù),使用精英保留和貪婪解碼相結(jié)合的遺傳算法進(jìn)行求解,縮短了cell 階段的生產(chǎn)時(shí)間.吳思思等[9]以最小化最大完工時(shí)間、機(jī)器等待時(shí)間和交貨期為目標(biāo),使用布谷鳥算法進(jìn)行求解,并首次在cell 階段引入學(xué)習(xí)退化效應(yīng),分析了學(xué)習(xí)退化效應(yīng)對(duì)調(diào)度結(jié)果的影響.在module 階段,Chou 等[10]提出一種多目標(biāo)混合遺傳算法來解決TFT-LCD 模塊裝配的調(diào)度問題,該問題是一種柔性作業(yè)車間調(diào)度問題:力求在滿足客戶需求的同時(shí),最大限度地減少制造時(shí)間和機(jī)器加工準(zhǔn)備時(shí)間.

綠色調(diào)度通過對(duì)資源的合理分配和優(yōu)化工件排序,以達(dá)到增效、節(jié)能、減排、降耗的目的,提高經(jīng)濟(jì)效益的同時(shí)實(shí)現(xiàn)制造過程的綠色化[11].在綠色調(diào)度研究領(lǐng)域,針對(duì)并行機(jī)調(diào)度問題,Cataldo 等[12]在計(jì)算總能耗時(shí)適當(dāng)考慮不同路徑移動(dòng)待加工零件所需的能耗,并采用模型計(jì)算最優(yōu)控制行為,以限制總能耗,使整體產(chǎn)量最大化.Wang 等[13]提出一種兩階段啟發(fā)式求解并行機(jī)調(diào)度問題的方法,該方法的目標(biāo)是使最大完工時(shí)間最小.Ji 等[14]提出了一種新的粒子群優(yōu)化算法,在最大完工時(shí)間在不超過一定水平的情況下,使資源消耗最小化.Li 等[15]提出了一種基于LPT 規(guī)則的啟發(fā)式求解方法,在機(jī)器總成本不超過給定閾值的約束下,使最大完工時(shí)間最小化.針對(duì)流水作業(yè)車間調(diào)度問題,Ding 等[16]提出了一種多目標(biāo)NEH 算法和一種改進(jìn)的多目標(biāo)迭代貪心算法來解決置換流車間低碳調(diào)度問題,旨在降低加工過程的能耗,從而減少碳排放.Zhai 等[17]利用時(shí)間序列模型對(duì)部分可再生能源的電價(jià)進(jìn)行逐時(shí)更新,將電價(jià)反饋到調(diào)度模型中,優(yōu)化能源成本.Huang 等[18]通過優(yōu)化維修流程,提高了能源效率,減少了兩階段多處理器流水車間調(diào)度問題中的最大完工時(shí)間.Lu 等[19]提出了一種混合多目標(biāo)回溯搜索算法來提高置換流車間調(diào)度問題的能源效率,該算法主要考慮了準(zhǔn)備階段和加工階段的能源消耗.

綜上所述,近些年隨著人們對(duì)環(huán)境的重視,綠色調(diào)度的研究越來越多,而在TFT-LCD 制造cell 階段調(diào)度問題上,大多數(shù)研究只考慮了經(jīng)濟(jì)效益,并未考慮對(duì)環(huán)境的影響.因此本文研究以最大完工時(shí)間和碳排放量為目標(biāo)的TFT-LCD 制造cell 階段綠色調(diào)度問題,在考慮機(jī)器選擇和工序的基礎(chǔ)上,增加了機(jī)器轉(zhuǎn)速的選擇,不同的機(jī)器轉(zhuǎn)速會(huì)影響加工時(shí)間的長短和碳排放量的多少.本文提出一種改進(jìn)布谷鳥搜索算法,通過在步長因子加入動(dòng)態(tài)系數(shù),提高算法的搜索效率和解的質(zhì)量,并構(gòu)建Pareto 最優(yōu)解集.

1 問題描述

1.1 TFT-LCD 裝配過程描述

薄膜晶體管液晶顯示器(TFT-LCD)的制造工藝由陣列工藝(array)、面板工藝(cell)和模塊工藝(module)等3 個(gè)基本工藝階段組成.除了材料成分外,TFT 的陣列工藝與半導(dǎo)體晶圓的陣列工藝非常相似.陣列工藝的主要原料是玻璃基板,經(jīng)過清洗、涂布、曝光、顯影、蝕刻等5-7 次加工.面板工藝包括許多組裝步驟來組裝TFT 玻璃基板和彩色濾光膜.模塊工藝是TFTLCD 制造工藝的最后一個(gè)階段,通過面板工藝生產(chǎn)的TFT-LCD 面板與所有其他必要部件組裝在一起,完成最終的TFT-LCD 產(chǎn)品.

TFT- LCD 制造中的cell 階段是將彩色濾光膜(CF)和TFT 玻璃基板兩個(gè)部件組裝在一起的組裝過程.通常彩色濾光膜是從外部供應(yīng)商購買的,而TFT 玻璃基板是由自己的陣列工廠生產(chǎn)的.在整個(gè)組裝過程中,TFT 玻璃基板和彩色濾光膜分別經(jīng)過配向膜印刷,摩擦,密封膠/隔離子涂布,粘接,切割,填充液晶,偏振片粘附和檢查等11 道工序.cell 階段可以看作非等效并行機(jī)的混合流水車間問題.cell 階段制造工藝流程如圖1 所示.

圖1 TFT-LCD 制造cell 階段制造工藝流程

1.2 TFT-LCD 制造cell 階段綠色調(diào)度模型建立

本文涉及的數(shù)學(xué)符號(hào)及含義如下:

n:工件類型數(shù)(i=1,2,···,n);

N:工件批數(shù),包括零件A,B 及裝配后工件C;

Jr/Jr* :第r/第r*批零件或工件(r=1,2,···,N),其中,r代表零件A,r*代表零件B;

Oj:工件第j道工序(j=1,2,···,a,a+1,···,b,b+1,···,c),其中零件A 批加工工序?yàn)閖=1,2,···,a,零件B 批加工工序?yàn)閖=a+1,···,b,裝配后工序?yàn)閖=b+1,···,c;

m:當(dāng)前工序下的第m臺(tái)機(jī)器(m=1,2,···,M);

vl:每臺(tái)機(jī)器的轉(zhuǎn)速(V=v1,v2,···,vl,···,vd),共d種轉(zhuǎn)速;

trjm:第r批工件第j道工序在第m臺(tái)機(jī)器上的開始加工時(shí)間;

Prjm:第r批工件第j道工序在第m臺(tái)機(jī)器上的基礎(chǔ)加工時(shí)間;

Prjml:第r批工件第j道工序在第m臺(tái)機(jī)器上以轉(zhuǎn)速l 加工的時(shí)間;

Drjm:第r批工件第j道工序在第m臺(tái)機(jī)器上的結(jié)束加工時(shí)間;

Wjml:第j道工序第m臺(tái)機(jī)器上以轉(zhuǎn)速l加工的單位能耗;

ljm:第j道工序第m臺(tái)機(jī)器上的單位空載能耗;

Sij:工序Oj不同類型工件之間轉(zhuǎn)換的準(zhǔn)備時(shí)間;

Xrjml:第r批工件第j道工序在第m臺(tái)機(jī)器以轉(zhuǎn)速l加工為1,否則為0;

Yjrr'm:在第j道工序,Jr先于Jr'在第m臺(tái)機(jī)器上加工為1,否則為0.

基于機(jī)器轉(zhuǎn)速的cell 階段綠色調(diào)度在滿足約束條件的前提下,不僅要考慮機(jī)器的選擇和工件的排序,也要考慮機(jī)器轉(zhuǎn)速的選擇.即在約束條件下對(duì)每一批工件,確定加工工序,選擇合適的機(jī)器和轉(zhuǎn)速,確保最終優(yōu)化目標(biāo)達(dá)到滿意解.模型中涉及的假設(shè)如下:

(1)某一時(shí)刻,每臺(tái)機(jī)器只能加工一批工件(在裝配工序中,零件A 和零件B 合成一批工件C),并且加工開始后,機(jī)器轉(zhuǎn)速保持不變.

(2)某一時(shí)刻,一批工件只能在一臺(tái)機(jī)器上加工,并且加工開始后,加工過程不能被中斷.

(3)所有機(jī)器在整個(gè)調(diào)度期間都是可用的(沒有機(jī)器故障).

(4)零件A、零件B 和裝配后工件C 的加工路徑事先確定.

(5)每道工序的加工時(shí)間由機(jī)器轉(zhuǎn)速和工件類型共同決定.

因此,本文建立基于機(jī)器轉(zhuǎn)速的TFT-LCD 制造cell 階段綠色調(diào)度模型,優(yōu)化目標(biāo)為最大完工時(shí)間Tmax和總碳排放量Ctotal.

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

約束條件:

式中,Z1和Z2為足夠大的正數(shù).式(1)中,Tmax代表最大完工時(shí)間;式(2)中,Ctotal代 表碳排放總量,ε為能耗與碳排放量之間的轉(zhuǎn)換系數(shù),通常取0.7559[20];式(3)表示在某一時(shí)刻,一批工件只能在一臺(tái)機(jī)器上加工;式(4)表示在某一時(shí)刻,一臺(tái)機(jī)器只能加工一批工件;式(5)表示任何一批工件在某一機(jī)器加工時(shí),都有相應(yīng)開始加工時(shí)間;式(6)表示在加工過程中,工件要嚴(yán)格按照事先確定的加工路徑進(jìn)行加工;式(7)表示任何一批工件的結(jié)束加工時(shí)間不能超過最大完工時(shí)間;式(8)表示同一臺(tái)機(jī)器前后兩批工件的開始加工時(shí)間約束;式(9)～式(11)表示同一臺(tái)機(jī)器加工不同工件批之間關(guān)系約束;式(12)、式(13)表示裝配工序時(shí),零件A 和零件B 同時(shí)在同一機(jī)器上加工.

2 改進(jìn)布谷鳥搜索算法

2.1 標(biāo)準(zhǔn)布谷鳥搜索算法描述

2.1.1 布谷鳥繁殖行為

由于布谷鳥的寄生特性,布谷鳥依賴于一些宿主種類并在宿主巢中下蛋.宿主鳥會(huì)把布谷鳥的蛋誤認(rèn)成自己的蛋,孵出布谷鳥的幼鳥.然而,并不是所有的布谷鳥蛋都不會(huì)被宿主鳥發(fā)現(xiàn),一旦發(fā)現(xiàn),宿主鳥會(huì)扔掉布谷鳥蛋或選擇別處重新筑巢.因此,布谷鳥會(huì)選擇一些與自身孵化方式相似的宿主鳥.

2.1.2 萊維飛行

除了布谷鳥的寄生特征外,Yang 等[21]提出的布谷鳥搜索算法(Cuckoo Search Algorithm,CSA)依賴于布谷鳥的覓食性質(zhì).布谷鳥的覓食模式受到一個(gè)重要因素的控制,這個(gè)因素被稱為萊維飛行,萊維飛行是了一種步長遵循重尾概率分布的結(jié)構(gòu)化隨機(jī)游走.很多動(dòng)物和昆蟲的覓食路徑也遵循以萊維飛行為特征的重尾概率分布的結(jié)構(gòu)化隨機(jī)游走[22].Yang 等[23]證明了用基于萊維飛行的結(jié)構(gòu)化隨機(jī)游走代替純隨機(jī)游走的布谷鳥搜索算法比許多現(xiàn)有的元啟發(fā)式算法(如粒子群算法、蜂群算法和差分進(jìn)化算法)更有效.

2.1.3 布谷鳥搜索過程

在布谷鳥搜索算法中,巢中的蛋是一種解決方案,布谷鳥蛋代表一種新的解決方案.為新一代選擇的鳥蛋質(zhì)量較好的鳥巢,對(duì)應(yīng)的是鳥蛋產(chǎn)生新布谷鳥的能力.布谷鳥搜索算法是基于以下假設(shè)構(gòu)建的:

(1)每只布谷鳥選擇一個(gè)宿主巢,然后隨機(jī)下蛋.

(2)為下一代選擇最好的鳥巢.

(3)巢的數(shù)量保持不變,宿主鳥可以以一定的概率pa∈[0,1]扔掉外來的蛋.

利用萊維飛行的布谷鳥第w個(gè)鳥巢第p+1 代的位置為:

式(14)中,是當(dāng)前解,α ＞0表示步長因子,大小取決于問題的規(guī)模.該值是常量,它具有固定的、有限的時(shí)間復(fù)雜度.布谷鳥隨機(jī)選擇宿主巢下蛋,采用基于萊維飛行的隨機(jī)游走.萊維飛行符合以下概率分布:

上述萊維分布服從重尾概率分布的階躍冪律.方差和均值都是無窮大.步長將搜索域劃分為局部搜索空間和全局搜索空間,為全局搜索提供了機(jī)會(huì),而不是停留在局部最小值上.由于布谷鳥搜索算法采用的是在萊維飛行中進(jìn)行全局隨機(jī)游走,因此能夠更快的在搜索空間內(nèi)達(dá)到最優(yōu).

2.2 改進(jìn)布谷鳥搜索算法描述

在標(biāo)準(zhǔn)布谷鳥搜索算法中,步長因子為固定的值.步長因子的大小會(huì)直接影響求解的速度和效率,當(dāng)步長因子過大時(shí),雖具備較好的全局搜索能力,收斂速度也快,但易錯(cuò)過全局最優(yōu)解或在全局最優(yōu)解附近震蕩;當(dāng)步長因子過小時(shí),收斂速度變慢,也易陷入局部最優(yōu)解中,該缺點(diǎn)限制了CSA 算法的快速收斂性,并有可能導(dǎo)致無法獲得高質(zhì)量的解.因此,為了更好實(shí)現(xiàn)全局快速搜索和局部精確搜索,朝著全局最優(yōu)解快速而穩(wěn)定的搜索,本文提出一種改進(jìn)布谷鳥搜索算法(Improved Cuckoo Search Algorithm,ICSA),在步長因子 α前加入動(dòng)態(tài)系數(shù) β,如式(16):

式(16)中,T_max表 示最大迭代次數(shù),Times表示當(dāng)前迭代次數(shù),ω ＞0 表 示變化率,控制減小的幅度,β0＞0表示最小動(dòng)態(tài)系數(shù),防止步長因子縮減到0,ω 和 β0的大小取決于問題的規(guī)模.可以看出,動(dòng)態(tài)系數(shù) β隨著迭代次數(shù)的增加而線性遞減,一方面,在搜索前期,有利于對(duì)全局進(jìn)行快速搜索,尋找優(yōu)質(zhì)解所在區(qū)域;在搜索后期,有利于加深對(duì)優(yōu)質(zhì)解周邊區(qū)域精確搜索,找到優(yōu)質(zhì)解;另一方面,動(dòng)態(tài)系數(shù)能夠有效的提高算法的搜索能力,平衡全局搜索和局部搜索的關(guān)系,通過迭代前期較大的動(dòng)態(tài)系數(shù),擴(kuò)大搜索空間,加強(qiáng)全局搜索的能力,迭代后期較小的動(dòng)態(tài)系數(shù),使得算法的局部搜索能力不斷加強(qiáng).因此,改進(jìn)布谷鳥搜索算法的更新位置公式為式(17):

相比于其他改進(jìn)方式,本文提出的改進(jìn)方式參數(shù)少,實(shí)現(xiàn)方式簡單,求解速度快.

2.3 構(gòu)建Pareto 最優(yōu)解集

與單目標(biāo)優(yōu)化問題不同的是,多目標(biāo)優(yōu)化問題目標(biāo)之間可能存在矛盾,這時(shí)可以構(gòu)建Pareto 最優(yōu)解集來解決.Pareto 最優(yōu)解集是指:在解集K中,對(duì)于解x、y,若解x的所有目標(biāo)函數(shù)值不劣于解y,且解x至少存在一個(gè)目標(biāo)函數(shù)值優(yōu)于解y,則稱x支配y,記作x?y,若解集K中不存在任一解的所有目標(biāo)函數(shù)值不劣于解x,且存在一個(gè)目標(biāo)函數(shù)值優(yōu)于解x,則稱解x為Pareto 最優(yōu)解集中的一個(gè)解.

本文結(jié)合雙元錦標(biāo)賽和動(dòng)態(tài)淘汰制2 種方法構(gòu)建Pareto 最優(yōu)解集.實(shí)現(xiàn)過程為:選擇解集K中的一個(gè)解x,將其與剩余解進(jìn)行比較,若存在解被x支配,則把該解從解集K中刪除,若存在解支配x,則直接把解x從解集K中刪除,若剩余解皆不支配x,則把解x加入Pareto 最優(yōu)解集中,并把解x從解集K中刪除,重復(fù)這一步驟,直至解集K為空集.若存在上代Pareto 最優(yōu)解集,合并兩代Pareto 最優(yōu)解集,繼續(xù)比較.若Pareto 最優(yōu)解集規(guī)模大于規(guī)定值,則使用聚焦距離進(jìn)行篩選.

2.4 改進(jìn)布谷鳥搜索算法步驟描述

改進(jìn)布谷鳥搜索算法遵循以萊維飛行為特征的重尾概率分布的結(jié)構(gòu)化隨機(jī)游走.萊維飛行為全局搜索提供了機(jī)會(huì),而改進(jìn)布谷鳥搜索算法在搜索前期,有利于對(duì)全局進(jìn)行快速搜索,尋找優(yōu)質(zhì)解所在區(qū)域;在搜索后期,有利于加深對(duì)優(yōu)質(zhì)解周邊區(qū)域精確搜索,找到優(yōu)質(zhì)解.在結(jié)合雙元錦標(biāo)賽、動(dòng)態(tài)淘汰制和聚焦距離篩選3 種方法之后,改進(jìn)布谷鳥搜索算法步驟如下:

(1)參數(shù)初始化.設(shè)置種群規(guī)模:z;最大迭代次數(shù):T_max;被宿主發(fā)現(xiàn)的概率:pa;Pareto 解的個(gè)數(shù):Z;步長因子:α;變化率:ω ;最小動(dòng)態(tài)系數(shù):β0.

(2)種群初始化.隨機(jī)選取z個(gè)鳥巢位置.

(3)計(jì)算鳥巢位置所對(duì)應(yīng)的兩個(gè)目標(biāo)函數(shù)值,構(gòu)建初始Pareto 最優(yōu)解集.

(4)根據(jù)式(17)得到下一代鳥巢位置,并計(jì)算其目標(biāo)函數(shù)值.

(5)每個(gè)新鳥巢隨機(jī)產(chǎn)生一個(gè)R,如果R大于被宿主發(fā)現(xiàn)的概率pa,返回步驟(4),否則,進(jìn)入步驟(6).

(6)比較兩代鳥巢目標(biāo)函數(shù)值,構(gòu)建新Pareto 最優(yōu)解集,如果Pareto 最優(yōu)解個(gè)數(shù)大于Z,那么使用聚焦距離進(jìn)行篩選.

(7)若達(dá)到最大迭代次數(shù)T_max,輸出最終Pareto最優(yōu)解集,否則,回到步驟(4).

3 實(shí)驗(yàn)與結(jié)果分析

3.1 TFT-LCD 制造cell 階段問題編碼

TFT-LCD 制造cell 階段綠色調(diào)度需要同時(shí)考慮當(dāng)前工件工序機(jī)器選擇、機(jī)器轉(zhuǎn)速選擇和工件在機(jī)器上加工順序,為此,本文設(shè)計(jì)一種基于機(jī)器選擇、轉(zhuǎn)速選擇和工序選擇相結(jié)合的三段式編碼方式,如圖2 所示.

圖2 三段式編碼方式

圖2 中,在基于機(jī)器編碼中,下行數(shù)字表示工件編號(hào),上行數(shù)字表示當(dāng)前工件加工機(jī)器編號(hào),表示的機(jī)器依次是{m3,m5,m1,m4,m2,m3,m4,m1};在基于轉(zhuǎn)速編碼中,下行數(shù)字表示機(jī)器標(biāo)號(hào),上行數(shù)字表示當(dāng)前機(jī)器轉(zhuǎn)速編號(hào),表示的轉(zhuǎn)速依次是{v3,v2,v5,v3,v5,v1,v4,v2};在基于工序編碼中,數(shù)字表示工件編號(hào),出現(xiàn)頻次表示當(dāng)前工序數(shù),表示的工序依次是{O21,O31,O11,O41,O12,O32,O22,O42}.第一段編碼確定當(dāng)前工件工序的加工機(jī)器,第二段編碼確定當(dāng)前加工機(jī)器的轉(zhuǎn)速,第三段編碼確定工件工序的加工順序,三段編碼相結(jié)合確保所求解可行.

3.2 測(cè)試實(shí)例和對(duì)比算法

Ding 等[16]提出了一種關(guān)于加工時(shí)間和能耗之間的假設(shè):對(duì)于確定的工序和機(jī)器,隨著轉(zhuǎn)速的變大,加工時(shí)間減少,能耗增加,即對(duì)于?vl＞vg,l,g∈{1,2,···,d}滿足Pr jml＜Pr jmg,Pr jml×Wjml＞Pr jmg×Wjmg.測(cè)試實(shí)例選取某車間的實(shí)際生產(chǎn)數(shù)據(jù)[8],產(chǎn)品類型及批量數(shù)如表1所示,工序機(jī)器數(shù)如表2 所示,不同工件工序在機(jī)器上的加工時(shí)間如表3 所示,不同類型工件在各工序之間轉(zhuǎn)換的準(zhǔn)備時(shí)間如表4 所示.需要增加機(jī)器轉(zhuǎn)速和能耗信息,v={1.00,1.30,1.55,1.80,2.00},Wjml=4×=1,顯然加工時(shí)間和能耗之間的關(guān)系滿足上述假設(shè).

表1 產(chǎn)品類型及批量數(shù)

表2 工序機(jī)器數(shù)

表3 不同工序加工時(shí)間(單位:分鐘)

表4 不同工序、不同類型工件之間轉(zhuǎn)換的準(zhǔn)備時(shí)間(單位:分鐘)

本文選擇標(biāo)準(zhǔn)布谷鳥搜索算法(CSA)和Deb 等[24]提出的帶精英策略的快速非支配排序遺傳算法(NSGAII)作為對(duì)比算法.由于原算法沒有對(duì)機(jī)器轉(zhuǎn)速選擇進(jìn)行編碼,對(duì)于CSA,采取與本文一致的編碼方式;對(duì)于NSGA-II,增加機(jī)器轉(zhuǎn)速的選擇、交叉和變異部分.兩種算法構(gòu)建Pareto 最優(yōu)解集的方法與本文一致.

3.3 結(jié)果分析

求解cell 階段綠色調(diào)度問題算法的運(yùn)行環(huán)境為:操作系統(tǒng)為Windows 10,處理器為Intel(R)Core(TM)i5-3210M,主頻為2.50 GHz,內(nèi)存為6 GB,編程環(huán)境為Matlab R2018a.

基于大量測(cè)試得到,當(dāng)變化率 ω為0.02,最小動(dòng)態(tài)系數(shù) β0為0.5 時(shí),算法性能最佳,因此ICSA 的6 個(gè)參數(shù),設(shè)計(jì)如下:種群規(guī)模z為50,最大迭代次數(shù)T_max為100,被宿主發(fā)現(xiàn)的概率pa為0.25,步長因子 α為0.1,變化率 ω為0.02,最小動(dòng)態(tài)系數(shù) β0為0.5;CSA 具有4 個(gè)參數(shù),設(shè)計(jì)如下:種群規(guī)模z為50,最大迭代次數(shù)T_max為100,被宿主發(fā)現(xiàn)的概率pa為0.25,步長因子α為0.1;NSGA-II 具有5 個(gè)參數(shù),設(shè)計(jì)如下:種群規(guī)模為50,最大迭代次數(shù)為100,選擇概率為0.9,交叉率為0.8,變異率為0.1.3 種算法Pareto 解的個(gè)數(shù)Z都為10.

每種算法各運(yùn)行30 次,每次運(yùn)行結(jié)果的最好解(取整)如表5 所示.

一方面,總共30 次運(yùn)行結(jié)果中,ICSA 在23 次運(yùn)行中得到了優(yōu)于CSA 和NSGA-II 的最好解,剩余7 次運(yùn)行結(jié)果也只是單個(gè)目標(biāo)值劣于CSA 或NSGA-II,沒有兩個(gè)目標(biāo)值都劣于CSA 或NSGA-II 的情況發(fā)生.另一方面,表5 中有4 次最大完工時(shí)間小于450,3 次碳排放總量小于10 000,均由ICSA 運(yùn)行得到,說明ICSA能夠得到更好的解.

圖3 是獨(dú)立運(yùn)行一次,不同算法求得的Pareto 解分布對(duì)比圖.圖中,叉號(hào)、五角、圓圈分別代表ICSA、CSA、NSGA-II 求得的解.可以看出,ICSA 所求解最好,CSA 次之、NSGA-II 最差.ICSA 的10 個(gè)解支配CSA 的8 個(gè)解和NSGA-II 的10 個(gè)解,即在最大完工時(shí)間相同的情況下,碳排放總量更小.因此,ICSA的表現(xiàn)要優(yōu)于CSA 和NSGA-II.另外,最大完工時(shí)間越短,碳排放量越高,因此在完工時(shí)間允許的情況下,選擇較低的轉(zhuǎn)速,可以有效的減少碳排放量.

圖3 3 種算法Pareto 解分布對(duì)比

綜上所述,結(jié)合表5 和圖3 可以得到,在求解基于機(jī)器轉(zhuǎn)速的TFT-LCD 制造cell 階段綠色調(diào)度問題上,ICSA 的求解質(zhì)量要高于CSA 和NSGA-II.

4 結(jié)論與展望

本文研究基于改進(jìn)布谷鳥搜索算法的TFT-LCD制造cell 階段綠色調(diào)度問題,建立以最小化最大完工時(shí)間和碳排放總量為目標(biāo)的數(shù)學(xué)模型.對(duì)基于機(jī)器選擇、轉(zhuǎn)速選擇和工序選擇相結(jié)合的三段式編碼后,應(yīng)用一種改進(jìn)布谷鳥搜索算法進(jìn)行求解,該算法在步長因子前加入動(dòng)態(tài)系數(shù),使其在搜索前期,快速對(duì)全局進(jìn)行搜索,在搜索后期,加深對(duì)局部進(jìn)行搜索,提高了解的質(zhì)量.并對(duì)某車間的實(shí)際生產(chǎn)數(shù)據(jù)進(jìn)行仿真,實(shí)驗(yàn)結(jié)果表明,相比于CSA 和NSGA-II,在最大完工時(shí)間相同的情況下,ICSA 可以有效的減少碳排放量.關(guān)于TFT-LCD 多目標(biāo)綠色調(diào)度的研究才剛剛開始,作者會(huì)繼續(xù)研究關(guān)于TFT-LCD 制造array 階段和module 階段綠色調(diào)度問題,同時(shí)作者將深入研究ICSA 和其他智能算法及改進(jìn)策略,為后續(xù)研究的問題提供算法支撐.