TFT-LCD模塊組裝調(diào)度問(wèn)題的改進(jìn)灰狼優(yōu)化算法

姚遠(yuǎn)遠(yuǎn)，葉春明，楊 楓

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

1 引 言

TFT-LCD(thin-film transistor-liquid crystal display)，全稱“薄膜晶體管液晶顯示器”，俗稱為“液晶面板”，是液晶顯示屏家族中的一個(gè)高端品種，廣泛應(yīng)用于手機(jī)、平板電腦、筆記本電腦和電視等各類顯示領(lǐng)域.TFT-LCD屬于半導(dǎo)體顯示產(chǎn)業(yè)的一種，是資金和技術(shù)密集型產(chǎn)業(yè)，面對(duì)激烈的市場(chǎng)競(jìng)爭(zhēng)壓力，亟需提高生產(chǎn)力和運(yùn)營(yíng)效率.模塊組裝作為TFT-LCD生產(chǎn)的最后一個(gè)環(huán)節(jié)，將直接決定產(chǎn)品能否按時(shí)交貨，并影響客戶滿意度.本文將對(duì)最小化最大完工時(shí)間的TFT-LCD模塊組裝調(diào)度問(wèn)題進(jìn)行研究.

Chou和Chien等[1]提出了一種多目標(biāo)混合遺傳算法求解TFT-LCD模塊組裝調(diào)度問(wèn)題，并考慮了工件交付期和機(jī)器準(zhǔn)備時(shí)間等因素.文獻(xiàn)[2]使用布谷鳥(niǎo)搜索算法求解極小化工件最大完工時(shí)間為目標(biāo)的TFT-LCD模塊組裝調(diào)度問(wèn)題，分析探討學(xué)習(xí)效應(yīng)和遺忘效應(yīng)對(duì)模塊組裝調(diào)度問(wèn)題的影響.現(xiàn)實(shí)中的TFT-LCD模塊組裝調(diào)度問(wèn)題可以抽象成為一種柔性作業(yè)車間調(diào)度問(wèn)題(flexible job-shop scheduling problem，F(xiàn)JSP).FJSP是經(jīng)典的作業(yè)車間調(diào)度問(wèn)題的一種延伸，具有更廣泛的應(yīng)用背景和更大的求解難度，已經(jīng)被證明是一種具有NP難特性的組合優(yōu)化問(wèn)題，該問(wèn)題的求解算法研究已成為車間調(diào)度領(lǐng)域的熱點(diǎn).張騰飛等[3]提出了一種改進(jìn)遺傳算法求解FJSP問(wèn)題，并證明了其有效性和實(shí)用性.

Mirjalili等人[4]在2014年提出了一種新穎的灰狼優(yōu)化算法(grey wolf optimizer，GWO).通過(guò)模擬自然界中灰狼種群的社會(huì)領(lǐng)導(dǎo)層級(jí)機(jī)制和捕食行為機(jī)制提出，實(shí)驗(yàn)結(jié)果表明在求解精度和穩(wěn)定性上GWO要顯著優(yōu)于PSO、DE和GSA算法.GWO算法目前已被廣泛應(yīng)用于多個(gè)領(lǐng)域，其中，在車間調(diào)度領(lǐng)域，Lu等人[5，6]將多目標(biāo)的GWO算法用于求解焊裝生產(chǎn)車間中的實(shí)際調(diào)度問(wèn)題.

本文將采用灰狼優(yōu)化算法解決TFT-LCD模塊組裝調(diào)度問(wèn)題.首先，構(gòu)建了以最小化最大完工時(shí)間為優(yōu)化目標(biāo)的TFT-LCD模塊組裝調(diào)度問(wèn)題數(shù)學(xué)模型；其次，針對(duì)基本GWO算法進(jìn)行了一系列設(shè)計(jì)和改進(jìn)，提出了一種改進(jìn)灰狼優(yōu)化算法(IGWO)，并對(duì)所設(shè)計(jì)的IGWO算法的算法復(fù)雜度和收斂性進(jìn)行了分析；然后，通過(guò)對(duì)FJSP問(wèn)題的不同規(guī)?；鶞?zhǔn)算例的仿真實(shí)驗(yàn)，對(duì)IGWO算法的計(jì)算性能和有效性進(jìn)行了驗(yàn)證；最后，將所提出的IGWO算法應(yīng)用于解決實(shí)際生產(chǎn)活動(dòng)中的一個(gè)TFT-LCD模塊組裝調(diào)度問(wèn)題.

2 TFT-LCD模塊組裝調(diào)度問(wèn)題描述及數(shù)學(xué)模型

2.1 問(wèn)題描述

TFT-LCD制造流程主要包括三個(gè)階段：TFT陣列(Array)/彩色濾光(CF，color filter)，液晶成盒(Cell)(也稱作LCD組裝)，以及模塊組裝(Module)，如圖1所示.其中，TFT Array / CF流程與半導(dǎo)體晶圓制造過(guò)程相似，區(qū)別是所使用的原材料不同.LCD組裝主要是組裝薄膜晶體管基板和彩色濾光器基板，并在二者之間注入液晶.Module是TFT-LCD生產(chǎn)的最后一個(gè)階段，在這個(gè)過(guò)程中需要把LCD面板與其他需要定制的零部件組裝成最終產(chǎn)品，Module階段包含五個(gè)工站(見(jiàn)圖2)，分別把集成電路、印刷電路板、驅(qū)動(dòng)板、背光源和底盤等組裝到LCD面板上，具體操作如下：

圖1 TFT-LCD制造流程圖Fig.1 TFT-LCD process flow

1)焊接集成電路和印刷電路板：將集成電路和印刷電路板元件焊接到LCD面板上；

2)3D襯底層壓：當(dāng)客戶需求的是3D類型面板時(shí)，在液晶成盒流程之后，需要先對(duì)LCD面板進(jìn)行3D玻璃襯底層壓處理；

3)半成品包裝：當(dāng)客戶需求的是半成品時(shí)，無(wú)需在LCD面板上組裝其他的定制電子元器件，只需將半成品進(jìn)行包裝交付給客戶；

4)組件裝配和測(cè)試：在LCD面板上組裝其他的定制電子元器件以完成成品裝配，并對(duì)成品的可靠性進(jìn)行檢測(cè)；

5)3D校準(zhǔn)：針對(duì)3D類型的產(chǎn)品，還必須對(duì)其成像情況進(jìn)行校準(zhǔn).

TFT-LCD模塊組裝調(diào)度問(wèn)題與FJSP問(wèn)題相類似.例如，圖2所示的模塊組裝車間中有5個(gè)工件在8臺(tái)機(jī)器上加工，每個(gè)工件的加工路徑各不相同，根據(jù)客戶需求的不同，工件可分為半成品和成品兩種，每個(gè)工站有一臺(tái)或多臺(tái)不同型的并行機(jī)器，各臺(tái)機(jī)器的加工速度不同，工序只需在每個(gè)工站的一臺(tái)機(jī)器上加工，且每臺(tái)機(jī)器都可以完成該操作.

圖2 TFT-LCD模塊組裝階段工件加工路徑圖Fig.2 Process flow for the TFT-LCD module assembly phase

2.2 數(shù)學(xué)模型建立

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

n：工件總數(shù)；

m：機(jī)器總數(shù)；

i，h：工件序號(hào)，i，h=1，2，…，n；

j：機(jī)器序號(hào)，j=1，2，…，m；

ni：工件i的工序總數(shù)；

k，g：工序序號(hào)，k，g=1，2，…，ni；

Oik：工件i的第k道工序；

Aik：工序Oik的可選加工機(jī)器集；

pikj：工序Oik在機(jī)器j上的加工時(shí)間；

M：一個(gè)足夠大的正數(shù)；

可以將TFT-LCD模塊組裝調(diào)度問(wèn)題描述為有n個(gè)工件需要在m臺(tái)不同型的平行機(jī)上進(jìn)行加工；每個(gè)工件i包含ni道工序，并且各道工序的加工次序事先給定；工件i的第k道工序Oik能夠在可選加工機(jī)器集Aik中的任何一臺(tái)機(jī)器上完成加工；工序Oik在機(jī)器j上的加工時(shí)間為pikj.

該問(wèn)題的求解包括兩個(gè)方面的子問(wèn)題(機(jī)器選擇子問(wèn)題和工序排序子問(wèn)題)，其調(diào)度目標(biāo)是為每一道工序選擇最合適的加工機(jī)器，并確定每一臺(tái)機(jī)器上各道工序的最優(yōu)加工順序及開(kāi)始加工時(shí)間，使整個(gè)系統(tǒng)的性能指標(biāo)達(dá)到最優(yōu).模型中涉及的假設(shè)有：

1)每臺(tái)機(jī)器在同一時(shí)刻只能加工一道工序；

2)每道工序同一時(shí)刻只能在一臺(tái)機(jī)器上加工，且一旦開(kāi)始加工不能中斷；

3)不同工件之間有相同的優(yōu)先級(jí)；

4)不同工件的工序之間沒(méi)有先后順序約束，同一工件的工序之間有先后約束；

5)所有工件和機(jī)器在零時(shí)刻都準(zhǔn)備就緒.

最大完工時(shí)間關(guān)系著各個(gè)工件的生產(chǎn)周期，是FJSP研究中應(yīng)用最廣泛的性能指標(biāo)之一，因此，本文將對(duì)最小化最大完工時(shí)間的TFT-LCD模塊組裝調(diào)度問(wèn)題進(jìn)行研究，在文獻(xiàn)[1]的數(shù)學(xué)模型基礎(chǔ)上，給出如下混合整數(shù)規(guī)劃模型.

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

(1)

約束條件：

(2)

(3)

(4)

xikj≤aikj，?i，k，j

(5)

(6)

?i，k，h，g，j，Oik≠Ohg

(7)

(8)

yikhgj+yhgikj=xikjxhgj，?i，k，h，g，j，Oik≠Ohg

(9)

xikj∈{0，1}，?i，k，j

(10)

yikhgj∈{0，1}，?i，k，h，g，j，Oik≠Ohg

(11)

(12)

(13)

公式(1)表示目標(biāo)函數(shù)為最小化最大完工時(shí)間；約束(2)定義了最大完工時(shí)間Cmax；約束(3)和(4)表示工序次序約束，保證每個(gè)工件按照指定的工序次序進(jìn)行加工；約束(5)和(6)保證每道工序只能被分配到可選加工機(jī)器集中的一臺(tái)機(jī)器上加工；約束(7)和(8)是析取約束，規(guī)定當(dāng)工序Oik和Ohg被分配到同一臺(tái)機(jī)器j上加工時(shí)，兩道工序相互之間不能重疊；另外，當(dāng)不同工件的兩道工序被分配到同一臺(tái)機(jī)器j上加工時(shí)，約束(9)決定了兩道工序之間的先后順序；約束(10)、(11)定義了決策變量的取值范圍；約束(12)定義了工序Oik的完工時(shí)間為非負(fù)數(shù)；約束(13)定義了工序Oik的加工開(kāi)始時(shí)間.

模型中約束條件的處理主要反映在后文算法的編碼和解碼過(guò)程中，用兩段式來(lái)對(duì)灰狼個(gè)體進(jìn)行編碼，機(jī)器選擇部分采用按工序排列的機(jī)器編碼，工序排序部分采用隨機(jī)鍵編碼，解碼時(shí)對(duì)機(jī)器選擇部分從左到右依次讀取并轉(zhuǎn)換成機(jī)器順序矩陣和時(shí)間順序矩陣，對(duì)工序排序部分通過(guò)對(duì)隨機(jī)數(shù)進(jìn)行升序排列可以得到工件順序，以及相應(yīng)的工序順序，并采用工序插入式方法生成活動(dòng)調(diào)度.通過(guò)解碼過(guò)程，可以得到每臺(tái)機(jī)器上工序的加工順序，以及相應(yīng)的加工開(kāi)始時(shí)間和結(jié)束時(shí)間.

3 改進(jìn)灰狼優(yōu)化算法

3.1 基本灰狼優(yōu)化算法簡(jiǎn)介

灰狼優(yōu)化算法是由Mirjalili等人[4]提出的一種基于種群的隨機(jī)優(yōu)化算法，作為一種仿生群體智能優(yōu)化算法，GWO算法通過(guò)模仿自然界中灰狼群體的社會(huì)領(lǐng)導(dǎo)層級(jí)機(jī)制和捕食行為提出.首先隨機(jī)生成一組候選解，每次迭代選出種群中最優(yōu)的三個(gè)解(alpha、beta和delta)，由它們帶領(lǐng)整個(gè)種群向搜索空間的最優(yōu)解方向移動(dòng).其他灰狼個(gè)體omega追隨alpha、beta和delta尋找更好的解.灰狼種群的包圍捕食行為可以通過(guò)下述數(shù)學(xué)公式描述.

(14)

(15)

(16)

(17)

(18)

(19)

(20)

(21)

(22)

(23)

(24)

(25)

上述公式中參數(shù)A和C決定灰狼優(yōu)化算法的全局探索和局部開(kāi)發(fā)，當(dāng)|A|>1時(shí)種群進(jìn)行全局探索，當(dāng)|A|<1時(shí)進(jìn)行局部尋優(yōu).另外，隨機(jī)生成參數(shù)C可以有效避免算法陷入局部最優(yōu)值.已有研究表明基本GWO算法具有搜索效率高、收斂速度快，及能夠有效避免陷入局部最優(yōu)等優(yōu)點(diǎn)[4].

3.2 改進(jìn)灰狼優(yōu)化算法求解TFT-LCD模塊組裝調(diào)度問(wèn)題

3.2.1 編碼和解碼

本文采用分段編碼法來(lái)對(duì)灰狼個(gè)體進(jìn)行編碼，灰狼個(gè)體由機(jī)器選擇部分(machines selection，MS)和工序排序部分(operations sequencing，OS)兩部分組成，兩部分長(zhǎng)度相等均為所有工件的工序總數(shù).如圖3所示，MS部分采用按工序排列的機(jī)器編碼[7]，每個(gè)位置用整數(shù)表示，分別按照工件和工件工序的順序進(jìn)行排列，每個(gè)整數(shù)代表當(dāng)前工序選擇的加工機(jī)器在可選加工機(jī)器集中的順序編號(hào)，而不是實(shí)際對(duì)應(yīng)的機(jī)器號(hào)，這樣可以保證經(jīng)過(guò)后續(xù)操作后產(chǎn)生的解仍是可行解；OS部分采用基于隨機(jī)鍵的編碼，各元素在[0，1]內(nèi)任意取值，這種編解碼方式能夠有效降低算法的求解難度，提高求解效率.

圖3 灰狼個(gè)體編碼Fig.3 Representation of the grey wolf vector

由于灰狼個(gè)體由兩部分組成，需要分別對(duì)這兩部分進(jìn)行解碼，主要是將OS部分解碼成對(duì)應(yīng)于MS部分的活動(dòng)調(diào)度.首先，對(duì)MS部分進(jìn)行解碼，從左到右分別讀取并轉(zhuǎn)換成機(jī)器順序矩陣和時(shí)間順序矩陣.其次，針對(duì)OS部分通過(guò)對(duì)隨機(jī)數(shù)進(jìn)行升序排列可以得到工件順序，以及相應(yīng)的工序順序.最后，采用工序插入式方法[8]將OS部分進(jìn)一步解碼成對(duì)應(yīng)于MS部分的活動(dòng)調(diào)度，已有研究表明對(duì)于最大完工時(shí)間評(píng)價(jià)指標(biāo)，活動(dòng)調(diào)度中一定存在最優(yōu)調(diào)度方案.經(jīng)過(guò)上述解碼過(guò)程，可以得到每臺(tái)機(jī)器上工序的加工順序，及其相應(yīng)的加工開(kāi)始時(shí)間和結(jié)束時(shí)間.

3.2.2 種群初始化

對(duì)算法而言，種群初始化是一個(gè)很重要的問(wèn)題，初始解的好壞對(duì)算法的求解速度和質(zhì)量有非常大影響.根據(jù)個(gè)體位置向量的表達(dá)形式，需要分別對(duì)MS和OS部分進(jìn)行初始化.在MS部分采用文獻(xiàn)[9]中提出的一種全局搜索、局部搜索和隨機(jī)產(chǎn)生相結(jié)合的初始化方法，簡(jiǎn)稱GLR初始化方法，并將三者的比例設(shè)置為60%、30%和10%；采用文獻(xiàn)[10]提出的基于搜索的方法對(duì)OS部分進(jìn)行初始化，具體操作方法是：針對(duì)每一個(gè)已生成的機(jī)器分配方案，隨機(jī)生成若干個(gè)工序排序方案，然后將每一個(gè)工序排序方案與該機(jī)器分配方案組合，選擇其中最優(yōu)的一個(gè)組合作為一個(gè)初始調(diào)度解，重復(fù)上述步驟，直到生成整個(gè)初始種群為止.

3.2.3 均勻交叉操作

由于MS部分必須保證每個(gè)元素的先后順序保持不變，因此在灰狼優(yōu)化算法的迭代過(guò)程中，對(duì)MS部分進(jìn)行均勻交叉操作(uniform crossover，UX).如圖4所示，在種群中隨機(jī)選擇兩個(gè)灰狼個(gè)體W1和W2，從左到右依次對(duì)MS部分的每個(gè)位置元素，生成一個(gè)隨機(jī)數(shù)rand，如果rand小于XOVR(交叉概率)，則對(duì)該位置元素執(zhí)行交叉操作，否則保持不變，從而產(chǎn)生兩個(gè)新個(gè)體NW1和NW2.接著從剩下的種群里再隨機(jī)選擇兩個(gè)灰狼個(gè)體重復(fù)執(zhí)行上述步驟，直到所有個(gè)體完成均勻交叉操作.實(shí)驗(yàn)發(fā)現(xiàn)交叉概率的取值越小求解效果越好，此處將XOVR取值為0.005.

圖4 MS部分均勻交叉操作Fig.4 Illustration of the uniform crossover scheme in machine selection vector

3.2.4 進(jìn)化種群動(dòng)態(tài)操作

為了找到更好的工序排序方案，對(duì)基本GWO算法實(shí)施進(jìn)化種群動(dòng)態(tài)操作(evolutionary population dynamics，EPD)[11].EPD操作就是將種群中差的個(gè)體移除，即在每次迭代時(shí)，將種群中較差的一半灰狼個(gè)體位置移除，并以相等概率在alpha、beta和delta周圍，以及搜索空間中的隨機(jī)位置，重新隨機(jī)生成灰狼個(gè)體的新位置.位置更新式如下：

(26)

(27)

(28)

(29)

(30)

其中，β是一個(gè)[1，2]之間的參數(shù)，根據(jù)文獻(xiàn)[12，13]中的設(shè)定，取β=1.5，u和v服從正態(tài)分布如下所示：

(31)

其中

(32)

3.2.5 IGWO算法流程

為了將灰狼優(yōu)化算法用于求解TFT-LCD模塊組裝調(diào)度問(wèn)題，本文對(duì)基本GWO算法進(jìn)行了GLR機(jī)器選擇部分初始化、基于搜索的方法工序排序部分初始化、工序插入式方法解碼、均勻交叉操作和進(jìn)化種群動(dòng)態(tài)操作五個(gè)方面的改進(jìn)，改進(jìn)后的灰狼優(yōu)化算法能夠有效解決所研究的問(wèn)題，將其簡(jiǎn)稱為IGWO.圖5展示了運(yùn)用IGWO求解TFT-LCD模塊組裝調(diào)度問(wèn)題的算法流程.

圖5 IGWO算法流程圖Fig.5 Flowchart of the IGWO

3.2.6 算法復(fù)雜度和收斂性分析

Mi={x|x∈M，f(x)=Fi}

(33)

其中，i=1，2，…，|F|，于是有：

(34)

對(duì)于任意的兩個(gè)元素xi∈Mi，xj∈Mj，有

(35)

易知，F(xiàn)1可以認(rèn)為是全局最優(yōu)解F*，而且適應(yīng)度等于F*的個(gè)體都應(yīng)該在M1里面.

在算法的迭代過(guò)程中，灰狼種群數(shù)量N保持不變，P={x1，x2，…，xN}.令P為一個(gè)集合，包含所有種群，由于種群中灰狼分為alpha、beta、delta和omega四類，那么可能的種群的數(shù)目為

(36)

那么為了判斷種群的優(yōu)劣，可以定義P的適應(yīng)度函數(shù)為

F(P)=max{f(xi)|i=1，2，…，N}

(37)

同樣，根據(jù)適應(yīng)度的不同又可以把P劃分為|F|個(gè)非空子集Pi(i=1，2，…，|F|)，|Pi|表示集合Pi的規(guī)模.集合P1包括所有適應(yīng)度為F1的種群.

令pij(i=1，2，…，|F|;j=1，2，…，|Pi|)表示Pi中第j個(gè)種群.在位置更新算式的作用下，pij轉(zhuǎn)移到pkl的概率為Prij，kl，Prij，k表示從pij到pk中任意一個(gè)種群的轉(zhuǎn)移概率，Pri，k表示從pi到pk中任意一個(gè)種群的轉(zhuǎn)移概率，有

(38)

定義1.一個(gè)方陣A∈Rn×n稱為：

1)非負(fù)矩陣，若aij≥0，?i，j∈{1，2，…，n}；

2)本原矩陣，若A非負(fù)，并且存在一個(gè)整數(shù)k≥1，使得Ak>0；

定義2.對(duì)于進(jìn)化算法，如果收斂于全局最優(yōu)解，那么它的充分必要條件是

(39)

其中，Pr表示概率，Pt表示第t代種群.

定理1.改進(jìn)的灰狼優(yōu)化算法搜索過(guò)程是一個(gè)時(shí)齊的Markov鏈.

證明：改進(jìn)的灰狼優(yōu)化算法是在有限維的種群空間M中搜索的，下一代種群Pt+1與前面0至t代種群無(wú)關(guān)，所以一個(gè)已知種群到另一個(gè)特定種群的條件概率在任何時(shí)候都不受原來(lái)變化的影響.由Markov鏈原理可知，改進(jìn)的灰狼優(yōu)化算法搜索過(guò)程具備Markov的無(wú)后效性.因此改進(jìn)的灰狼優(yōu)化算法的搜索過(guò)程是一個(gè)時(shí)齊的Markov鏈.

(40)

定理3.在改進(jìn)的灰狼優(yōu)化算法中，對(duì)?i，k∈{1，2，…，|F|}，有

(41)

該定理說(shuō)明，擇優(yōu)選擇策略使得灰狼群體的適應(yīng)度在進(jìn)化過(guò)程中只能是保持不變或提升，不會(huì)出現(xiàn)適應(yīng)度退化的情況.

定理4.改進(jìn)的灰狼優(yōu)化算法全局收斂.

證明：每個(gè)Pri，i=1，2，…，|F|可看作是時(shí)齊有限Markov鏈上的一個(gè)狀態(tài)，由定理1可知，算法的轉(zhuǎn)移概率矩陣表示為

(42)

其中，R>0，T≠0，S=1

根據(jù)定理2可知

(43)

其中，S∞=1，R∞=(1，1，…，1)T，因此Pr∞就是一個(gè)穩(wěn)定的隨機(jī)矩陣，且有

(44)

因此，無(wú)論當(dāng)前灰狼種群處于何種適應(yīng)度狀態(tài)，經(jīng)過(guò)無(wú)窮次進(jìn)化后都將以概率1收斂到最優(yōu)適應(yīng)度狀態(tài)，所以改進(jìn)的灰狼優(yōu)化算法是全局收斂的.

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

4.1 算法有效性驗(yàn)證

為了驗(yàn)證所提出的IGWO算法求解TFT-LCD模塊組裝調(diào)度問(wèn)題的有效性，本文選取與TFT-LCD模塊組裝調(diào)度問(wèn)題相類似的FJSP問(wèn)題的Kacem基準(zhǔn)算例[14]和Brandimarte基準(zhǔn)算例[15]進(jìn)行計(jì)算實(shí)驗(yàn)，此處將測(cè)試問(wèn)題的時(shí)間單位統(tǒng)一定為min.仿真環(huán)境為操作系統(tǒng)Win 7，處理器Intel Core i5-4210M CPU @2.60GHz，內(nèi)存4GB，采用MATLAB R2012a實(shí)施算法編程.算法的相關(guān)參數(shù)設(shè)置如下：將灰狼種群大小設(shè)置為50，最大迭代次數(shù)MaxT=500，交叉率XOVR=0.005，GS=0.6，LS=0.3，RS=0.1.

首先，通過(guò)對(duì)Kacem數(shù)據(jù)的五個(gè)不同規(guī)?；鶞?zhǔn)算例的仿真測(cè)試，對(duì)算法中幾種改善策略的有效性進(jìn)行驗(yàn)證.為此專門設(shè)計(jì)了四種改進(jìn)算法，分別命名為GWO_1、GWO_2、GWO_3和IGWO，其中IGWO為本文所提出的算法，各個(gè)算法中具體包含的改進(jìn)策略如表1所示.針對(duì)不同算例，每種算法各獨(dú)立運(yùn)行30次后進(jìn)行比較，結(jié)果如表2所示.其中，BEST表示算法運(yùn)行30次所獲得的最佳結(jié)果，AVG表示算法30次運(yùn)行結(jié)果的平均值，RPD表示相對(duì)百分比偏差，其計(jì)算公式為RPD=100(BEST-C*)/C*，Mean表示五個(gè)算例下各算法RPD的平均值.根據(jù)表2中結(jié)果，通過(guò)GWO_1和GWO_2的比較，可以發(fā)現(xiàn)GLR機(jī)器選擇部分初始化方法能夠顯著改善算法求解性能；GWO_3的數(shù)據(jù)結(jié)果表明均勻交叉操作和進(jìn)化種群動(dòng)態(tài)操作可以進(jìn)一步提升算法性能；IGWO的求解結(jié)果(尤其是15×10問(wèn)題)驗(yàn)證了該算法求解FJSP問(wèn)題的有效性.雖然對(duì)于10×7、10×10和15×10這三個(gè)問(wèn)題，IGWO未能找到已知最優(yōu)值，但是比較接近已知最優(yōu)值.針對(duì)BEST、AVG、RPD和Mean各個(gè)評(píng)價(jià)指標(biāo)，IGWO在四種改進(jìn)算法中都是效果最好的.

表1 GWO算法的不同改進(jìn)策略及命名Table 1 Versions of different improved GWO and names

通過(guò)表2中的評(píng)價(jià)指標(biāo)只能對(duì)各算法求解結(jié)果有個(gè)整體了解，不能對(duì)各算法的每次運(yùn)行結(jié)果進(jìn)行比較，為了更精確地比較各種算法的優(yōu)化性能，使用SPSS Statistics 19進(jìn)行威爾科克森符號(hào)秩檢驗(yàn)比較兩兩算法之間是否具有顯著差異.分別將IGWO與其它三種改進(jìn)算法進(jìn)行兩兩比較，結(jié)果如表3所示，如果P值小于0.05就表明兩種算法的優(yōu)化性能之間具有顯著差異.表3結(jié)果表明，除了較為簡(jiǎn)單的4×5問(wèn)題以外，所提出的IGWO算法的優(yōu)化性能明顯區(qū)別于其它三種改進(jìn)算法.另外，針對(duì)這五個(gè)基準(zhǔn)算例，本文還分別對(duì)四種算法的30次運(yùn)行結(jié)果分布情況繪制了箱線圖，如圖6所示，進(jìn)一步驗(yàn)證了IGWO算法的有效性.

表2 不同改進(jìn)策略的算法求解結(jié)果對(duì)比Table 2 Statistical results of compared approaches over 30 independent runs on Kacem data

注：n表示工件數(shù)，m表示機(jī)器數(shù)，C*表示該問(wèn)題的已知最優(yōu)值，“*”表示找到已知最優(yōu)值，AVG和RPD結(jié)果均保留到小數(shù)點(diǎn)后2位.

為了進(jìn)一步驗(yàn)證本文提出的IGWO算法性能，分別將IGWO算法與文獻(xiàn)[8]提出的混合和聲搜索(HHS)算法，以及文獻(xiàn)[16]提出的人工蜂群(ABC)算法進(jìn)行比較研究，并對(duì)Brandimarte的十組數(shù)據(jù)進(jìn)行測(cè)試.表4給出了IGWO和HHS、ABC算法的十個(gè)算例對(duì)比結(jié)果.其中，BEST是算法30次運(yùn)行求得的最優(yōu)值，AVG是算法30次運(yùn)行結(jié)果的均值，SD表示算法運(yùn)行30次結(jié)果的標(biāo)準(zhǔn)偏差，#best表示算法取得最優(yōu)值的算例個(gè)數(shù).從表4可知，在3種對(duì)比算法中，HHS求解效果最好，能夠獲得最優(yōu)解的算例個(gè)數(shù)為10個(gè)；ABC次之，一共有8個(gè)算例取得最優(yōu)解；然而，本文提出的IGWO算法對(duì)其中的4個(gè)算例不能獲得最優(yōu)解，雖然沒(méi)有HHS和ABC算法的效果那么突出，但是針對(duì)BEST和AVG指標(biāo)，IGWO算法的求解結(jié)果和其他兩種算法相差并不是很大，表明本文提出的IGWO是求解FJSP問(wèn)題中工件最大完工時(shí)間的一種比較有競(jìng)爭(zhēng)力的算法，從而驗(yàn)證了算法有效性.

表3 威爾科克森符號(hào)秩檢驗(yàn)P值結(jié)果Table 3 P-values obtained from the Wilcoxon signed-rank test

注：N/A表示該算法不能和自己進(jìn)行對(duì)比，顯著性水平設(shè)為0.05.

4.2 實(shí)例驗(yàn)證

通過(guò)對(duì)不同規(guī)?；鶞?zhǔn)算例的仿真實(shí)驗(yàn)，驗(yàn)證了所提出的IGWO算法的有效性，接下來(lái)進(jìn)一步將IGWO算法用于解決實(shí)際生產(chǎn)活動(dòng)中的一個(gè)TFT-LCD模塊組裝調(diào)度問(wèn)題實(shí)例.本文選取文獻(xiàn)[17]中的一個(gè)小規(guī)模測(cè)試問(wèn)題實(shí)例進(jìn)行算法實(shí)用性研究，該測(cè)試問(wèn)題是基于一家臺(tái)灣TFT-LCD公司的實(shí)際生產(chǎn)數(shù)據(jù)而設(shè)計(jì).在該測(cè)試問(wèn)題中，有8個(gè)工件(共22道工序)被安排在模塊組裝車間的8臺(tái)機(jī)器上進(jìn)行加工，每個(gè)工件的加工路徑和工序數(shù)各不相同，相應(yīng)的加工路徑圖、每道工序可選擇的機(jī)器序號(hào)及其對(duì)應(yīng)的加工時(shí)間等相關(guān)信息可參考文獻(xiàn)[17]，加工時(shí)間單位為s.

圖6 不同算法分別求解Kacem五個(gè)算例的箱線圖Fig. 6 Box plots of compared approaches over 30 independent runs on Kacem data

表4 Brandimarte數(shù)據(jù)對(duì)比結(jié)果Table 4 Results of the ten BRdata instances

注：n表示工件數(shù)，m表示機(jī)器數(shù)，LB表示最優(yōu)解下界，UB表示最優(yōu)解上界，“*”表示已知最優(yōu)解，AVG和SD結(jié)果均保留到小數(shù)點(diǎn)后2位.

通過(guò)IGWO算法求得該實(shí)例問(wèn)題的最小化最大完工時(shí)間值為93000s，該結(jié)果與文獻(xiàn)[17]的實(shí)驗(yàn)結(jié)果一致，對(duì)應(yīng)的調(diào)度方案甘特圖如圖7所示.通過(guò)甘特圖可以清楚地看出每個(gè)工件的每道工序在哪一臺(tái)機(jī)器上進(jìn)行加工，及其相應(yīng)的加工開(kāi)始時(shí)間和完成時(shí)間，同時(shí)也可以了解到每臺(tái)機(jī)器加工了哪些工件，以及這些工件之間的加工先后順序.例如，圖7中的“101”表示第1個(gè)工件的第1道工序，“402”表示第4個(gè)工件的第2道工序，其他標(biāo)號(hào)的含義同上；第1臺(tái)機(jī)器加工了3道工序，分別是101、402和601；第7臺(tái)機(jī)器加工了303、803、702、202和403共5道工序.針對(duì)該調(diào)度方案，804在第8臺(tái)機(jī)器上加工，是最后一道被加工完成的工序，其加工完成時(shí)間為第93000s，即該實(shí)際案例問(wèn)題的最小化最大完工時(shí)間.

另外，本文還給出了IGWO算法求解實(shí)際案例問(wèn)題的尋優(yōu)曲線，如圖8所示.從圖8中可以看出最優(yōu)灰狼個(gè)體的迭代曲線變化情況，以及整個(gè)灰狼種群均值的尋優(yōu)曲線變化情況.在第1000次迭代時(shí)，種群均值基本收斂到一個(gè)穩(wěn)定值(108500s左右).從最優(yōu)灰狼個(gè)體的迭代曲線可以看出，最優(yōu)灰狼個(gè)體在迭代之初就表現(xiàn)出很好的求解效果(初始解為98000s)，這是由于IGWO算法中設(shè)計(jì)了非常有效的種群初始化方法(GLR機(jī)器選擇部分初始化、基于搜索的方法工序排序部分初始化)；在第222次迭代時(shí)，最優(yōu)灰狼個(gè)體找到了最優(yōu)解93000s，表明了本文提出的IGWO算法具有較快的收斂性，這歸功于基本GWO算法高效的灰狼個(gè)體位置更新方式、均勻交叉操作和進(jìn)化種群動(dòng)態(tài)操作.綜上所述，本文提出的IGWO算法能有效解決真實(shí)的TFT-LCD模塊組裝調(diào)度問(wèn)題.

圖7 IGWO算法求解實(shí)際案例問(wèn)題甘特圖Fig.7 Gantt chart of the real-world TFT-LCD module assembly scheduling case obtained by IGWO

圖8 IGWO算法求解實(shí)際案例問(wèn)題尋優(yōu)曲線Fig.8 Convergence curve in solving the real-world TFT-LCD module assembly scheduling case by IGWO

5 結(jié) 論

本文設(shè)計(jì)了一種改進(jìn)灰狼優(yōu)化算法解決以最小化最大完工時(shí)間為優(yōu)化目標(biāo)的TFT-LCD模塊組裝調(diào)度問(wèn)題，具體包含以下研究?jī)?nèi)容：

1)采用分段編碼方法對(duì)灰狼個(gè)體進(jìn)行編碼；采用工序插入式方法將工序排序部分解碼成對(duì)應(yīng)于機(jī)器選擇部分的活動(dòng)調(diào)度；使用GLR方法對(duì)機(jī)器選擇部分進(jìn)行初始化，以及基于搜索的方法對(duì)工序排序部分進(jìn)行種群初始化；在算法迭代過(guò)程中，對(duì)機(jī)器選擇部分執(zhí)行均勻交叉操作，并對(duì)工序排序部分進(jìn)行進(jìn)化種群動(dòng)態(tài)操作；同時(shí)，對(duì)所設(shè)計(jì)的改進(jìn)灰狼優(yōu)化算法的計(jì)算復(fù)雜度和收斂性進(jìn)行了分析.

2)通過(guò)對(duì)FJSP問(wèn)題的Kacem和Brandimarte基準(zhǔn)算例的數(shù)值實(shí)驗(yàn)，驗(yàn)證了所提出的IGWO算法的計(jì)算性能和有效性；另外，通過(guò)對(duì)實(shí)際生產(chǎn)活動(dòng)中的一個(gè)TFT-LCD模塊組裝調(diào)度問(wèn)題實(shí)例的測(cè)試，進(jìn)一步表明了本文提出的IGWO算法解決真實(shí)TFT-LCD模塊組裝調(diào)度問(wèn)題的實(shí)用性和有效性.

未來(lái)將對(duì)基于Pareto的多目標(biāo)灰狼優(yōu)化算法進(jìn)行研究，并運(yùn)用其解決更加復(fù)雜的離散車間調(diào)度問(wèn)題.