杜士卿，朱光宇，徐文婕

(福州大學(xué)機(jī)械工程及自動(dòng)化學(xué)院，福建 福州 350108)

0 引言

混合流水車間調(diào)度問(wèn)題(hybrid flow-shop scheduling problem, HFSP)可以看作是經(jīng)典流水車間調(diào)度問(wèn)題和并行機(jī)調(diào)度問(wèn)題的結(jié)合. 在研究HFSP時(shí)，除了減少完工時(shí)間外，還應(yīng)考慮設(shè)備利用率及提高加工質(zhì)量和降低車間能耗. 近年來(lái)，許多學(xué)者對(duì)混合流水車間調(diào)度問(wèn)題進(jìn)行了研究. 王芳等[1]設(shè)計(jì)了一種高效分布估算算法來(lái)求解大規(guī)模調(diào)度問(wèn)題. 田云娜等[2]提出一種基于時(shí)間窗的蟻群算法來(lái)解決單目標(biāo)流水車間調(diào)度問(wèn)題. 宋代立等[3]提出一種三級(jí)遞階結(jié)構(gòu)的蟻群算法進(jìn)行求解. Mousavi等[4]設(shè)計(jì)了一種基于遺傳算法的解決方法. Zandieh等[5]提出了序數(shù)NSGA-II算法和雜交NSGA-II算法來(lái)進(jìn)行求解. 隨著綠色制造的出現(xiàn)，節(jié)能減排理念得到了廣泛的關(guān)注. 針對(duì)能耗問(wèn)題，Tang等[6]設(shè)計(jì)了一種改進(jìn)粒子群算法求解以完工時(shí)間和機(jī)器能耗為目標(biāo)的混合流水車間調(diào)度問(wèn)題. 加工質(zhì)量的好壞直接影響產(chǎn)品的生產(chǎn)成本和生產(chǎn)效率. 徐華等[7]將加工質(zhì)量作為一個(gè)優(yōu)化目標(biāo)，引入到了作業(yè)車間調(diào)度的研究中. 現(xiàn)有的混合流水車間調(diào)度優(yōu)化主要優(yōu)化以時(shí)間為對(duì)象的單維或兩維目標(biāo)問(wèn)題. 而在實(shí)際生產(chǎn)中，工件加工制造趨于多品種、 小批量，不僅要考慮完工時(shí)間，還應(yīng)綜合考慮設(shè)備利用、 質(zhì)量控制和能耗等問(wèn)題.

本研究建立以完工時(shí)間、 空閑時(shí)間、 加工質(zhì)量和通過(guò)減少機(jī)器能源消耗而降低生產(chǎn)費(fèi)用為目標(biāo)函數(shù)的多目標(biāo)混合流水車間調(diào)度(multi-objective hybrid flow-shop scheduling problem, MOHFSP)模型，并將最佳覓食算法[8]與直覺(jué)模糊集[9]結(jié)合，提出基于直覺(jué)模糊集相似度的最佳覓食算法(optimal foraging algorithm based on intuitionistic fuzzy sets similarity, IFS_OFA)用以求解該模型. 直覺(jué)模糊集在處理模糊性和不確定性等方面具有較強(qiáng)的靈活性和實(shí)用性[10-12]，以直覺(jué)模糊集相似度建立解的比較策略，且以該值作為適應(yīng)度值引導(dǎo)最佳覓食算法進(jìn)化，可以有效判斷Pareto解的優(yōu)劣和挖掘各個(gè)目標(biāo)之間的有效信息，并能夠消除目標(biāo)數(shù)量級(jí)和量綱的影響. 最后，通過(guò)測(cè)試實(shí)例和實(shí)際案例，表明本算法求解多目標(biāo)混合流水車間調(diào)度問(wèn)題(MOHFSP)的可行性和優(yōu)越性.

1 多目標(biāo)混合流水車間調(diào)度模型

1.1 問(wèn)題描述

混合流水車間調(diào)度問(wèn)題可以描述為：n個(gè)待加工工件有s道加工工序，每道工序有Mj臺(tái)并行機(jī)器(Mj≥1;j=1, 2, …,s)，且至少有一道工序存在并行機(jī)器；同一工序上各機(jī)器加工同一工件的加工時(shí)間有所不同，各個(gè)工件均要在每一道工序上進(jìn)行加工，工件排產(chǎn)到第j道工序時(shí)可以被加工該工序的Mj臺(tái)并行機(jī)器中的任意一臺(tái)機(jī)器加工.

1.2 假設(shè)條件

為便于研究，提出如下假設(shè)：

1) 在零時(shí)刻所有工件均可被加工；2) 每個(gè)工件的每道工序只能選擇一臺(tái)機(jī)器進(jìn)行加工，且每臺(tái)機(jī)器在同一時(shí)刻只能加工一個(gè)工件；3) 每個(gè)工件只有在前一道工序完成后才能進(jìn)入下一道工序；4) 工件的準(zhǔn)備和移動(dòng)時(shí)間包含在加工時(shí)間內(nèi).

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

在HFSP中，管理者不只考慮單一的目標(biāo)，往往需要在成本、 利用率、 質(zhì)量、 能耗等多個(gè)目標(biāo)間進(jìn)行權(quán)衡. 因此以完工時(shí)間f1、 空閑時(shí)間f2、 加工質(zhì)量f3和機(jī)器能源消耗f4為目標(biāo)函數(shù)，研究最小化這四個(gè)目標(biāo)的MOHFSP問(wèn)題，具體的數(shù)學(xué)模型如下：

min{f1,f2,f3,f4}

(1)

2 最佳覓食算法

Step1 初始化操作.

① 對(duì)于具有N個(gè)個(gè)體的種群P1，使用下式進(jìn)行初始化.

(2)

Step2 迭代操作.

① 設(shè)置初始迭代t=1，最大迭代次數(shù)為tmax.

(3)

(4)

Step3 終止操作.

當(dāng)達(dá)到最大迭代次數(shù)tmax時(shí)，終止迭代并輸出最優(yōu)個(gè)體Xbest和最優(yōu)目標(biāo)函數(shù)值Fbest.

3 直覺(jué)模糊集相似度

在多目標(biāo)優(yōu)化問(wèn)題中，單純的基于Pareto解優(yōu)先排序方法不能很好地解決高維多目標(biāo)優(yōu)化問(wèn)題. 利用直覺(jué)模糊集相似性測(cè)度衡量Pareto解與理想解間的相似程度，判斷Pareto解的優(yōu)劣，建立解的比較策略. 將理想解和Pareto解分別映射為直覺(jué)模糊集，然后求兩個(gè)直覺(jué)模糊集間的相似度，并以該相似度值作為算法的適應(yīng)度來(lái)引導(dǎo)算法進(jìn)化.

(5)

3) Pareto解直覺(jué)模糊集與理想解直覺(jué)模糊集的相似度. 使用公式(6)～(7)依次計(jì)算Pareto解直覺(jué)模糊集與理想解直覺(jué)模糊集的猶豫度πfi(j)和相似度S(IFS(j),IFS(0))，

πfi(j)=1-μfi(j)-γfi(j)

(6)

式(7)等號(hào)右側(cè)括號(hào)內(nèi)第1項(xiàng)和第2項(xiàng)為兩個(gè)直覺(jué)模糊集之間的歐式距離，第3項(xiàng)為兩個(gè)直覺(jué)模糊集的猶豫度之間的歐氏距離. 公式(7)既能描述兩個(gè)直覺(jué)模糊集之間的相似度，又能反應(yīng)直覺(jué)模糊集自身存在的不確定性.

4 基于直覺(jué)模糊集相似度的最佳覓食算法

針對(duì)MOHFSP存在的目標(biāo)維數(shù)高、 調(diào)度問(wèn)題離散化、 多臺(tái)機(jī)器并行處理的特點(diǎn)，建立直覺(jué)模糊集相似度的解比較策略，將直覺(jué)模糊集相似度作為適應(yīng)度值引導(dǎo)最佳覓食算法進(jìn)化，并提出基于直覺(jué)模糊集相似度的最佳覓食算法(IFS_OFA)，用于解決此問(wèn)題優(yōu)化.

4.1 編碼方案

由于最佳覓食算法采用的實(shí)數(shù)編碼，最初用于解決連續(xù)函數(shù)的全局優(yōu)化問(wèn)題，而本問(wèn)題是離散優(yōu)化問(wèn)題. 因此，設(shè)計(jì)編碼方式是實(shí)現(xiàn)最佳覓食算法求解問(wèn)題的首要因素. 根據(jù)問(wèn)題的特點(diǎn)，編碼方式不僅要能表示出各個(gè)工件在每道工序中的加工順序，還要能表示出各工件在每道工序中所選擇的加工機(jī)器. 基于此，采用基于LOV(largest order value)規(guī)則[13]的雙層整數(shù)編碼，編碼長(zhǎng)度為2 × (n×s)，即為所有工件總工序數(shù)的2倍. 編碼的第一層為工序?qū)?，第二層為機(jī)器層.

假設(shè)有4個(gè)工件且每個(gè)工件有2道工序，第一道工序共有2臺(tái)并行機(jī)器(機(jī)器a1, 機(jī)器a2)，第二道工序有2臺(tái)并行機(jī)器(機(jī)器b1, 機(jī)器b2). 具體編碼形式如下：對(duì)于工序?qū)泳幋a，通過(guò)LOV規(guī)則將標(biāo)準(zhǔn)OFA算法的連續(xù)實(shí)數(shù)位置向量轉(zhuǎn)化成離散的加工工序序列. 例如，有一連續(xù)實(shí)數(shù)位置向量，通過(guò)LOV規(guī)則進(jìn)行排序，得到各自對(duì)應(yīng)的LOV值，然后LOV值每個(gè)元素都進(jìn)行以工件數(shù)n為模的求模運(yùn)算來(lái)得到各個(gè)工件的加工工序編碼，如圖1所示.

雙層編碼見(jiàn)圖2所示. 圖2中前8位為工序?qū)?，表示工件的加工順序，為工?→工件2→工件2→工件4→工件3→工件4→工件1→工件1. 9～16位為機(jī)器層，第9位上的數(shù)字2表示工件3的第一道工序選擇機(jī)器a2加工，第10位上的數(shù)字1表示工件2的第一道工序選擇機(jī)器a1加工，第11位上的數(shù)字2表示工件2的第二道工序選擇機(jī)器b2加工. 以此類推，則機(jī)器層編碼表示各個(gè)工件的每道工序所選擇的機(jī)器，依次為：機(jī)器a2→機(jī)器a1→機(jī)器b2→機(jī)器a1→機(jī)器b2→機(jī)器b2→機(jī)器a1→機(jī)器b1.

圖1 工序?qū)泳幋a示意圖Fig.1 Process layer coding diagram

圖2 雙層編碼示意圖Fig.2 Two-layer coding diagram

4.2 種群初始化方案

考慮到4.1節(jié)中編碼方案的特點(diǎn)，工序?qū)泳幋a部分采用隨機(jī)生成的方式，利用公式(2)將種群中的個(gè)體初始化成連續(xù)實(shí)數(shù)位置向量，再利用LOV規(guī)則將位置向量轉(zhuǎn)化成對(duì)應(yīng)的LOV值，然后轉(zhuǎn)化成對(duì)應(yīng)的加工工序編碼. 由于機(jī)器層編碼對(duì)優(yōu)化問(wèn)題的完工時(shí)間、 加工質(zhì)量以及機(jī)器能耗有很大影響，因此針對(duì)機(jī)器層編碼部分，采用權(quán)重法來(lái)計(jì)算機(jī)器的選擇概率，優(yōu)先選擇加工時(shí)間短、 加工質(zhì)量好且機(jī)器能耗小的機(jī)器，其具體步驟如下.

第一步，利用公式(8)計(jì)算每個(gè)工件各道工序?qū)?yīng)的并行機(jī)器集合中的機(jī)器選擇概率. 機(jī)器選擇概率越大，則越容易被選用.

(8)

4.3 IFS_OFA算法迭代過(guò)程

針對(duì)MOHFSP問(wèn)題，IFS_OFA算法迭代過(guò)程如下：

2) 使用單目標(biāo)OFA算法分別對(duì)完工時(shí)間、 空閑時(shí)間、 加工質(zhì)量和機(jī)器能源消耗4個(gè)目標(biāo)函數(shù)進(jìn)行單目標(biāo)優(yōu)化，構(gòu)造理想解函數(shù)值Y0，并將Y0映射為理想解直覺(jué)模糊集IFS(0).

4.4 外部檔案維護(hù)及更新

通過(guò)非劣排序和小生境技術(shù)中的擁擠距離來(lái)維護(hù)和更新外部檔案. 每次迭代完成后，將當(dāng)前解集與外部檔案集進(jìn)行混合，并計(jì)算其擁擠距離，保留具有較大擁擠距離的非劣解，剔除較小擁擠距離的非劣解，從而更新外部檔案，保持種群的多樣性和優(yōu)異性.

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

5.1 實(shí)驗(yàn)設(shè)置

為驗(yàn)證IFS_OFA算法的有效性，進(jìn)行兩部分實(shí)驗(yàn)，并與基于隨機(jī)權(quán)重的最佳覓食算法(random wight-based optimal foraging algorithm, RW_OFA)和經(jīng)典多目標(biāo)優(yōu)化算法NSGA-II進(jìn)行比較分析. 兩部分實(shí)驗(yàn)為：1) 采用文[3]和文[14]的9個(gè)不同規(guī)模的測(cè)試實(shí)例來(lái)進(jìn)行測(cè)試；2) 針對(duì)某PCB組裝車間的實(shí)際案例進(jìn)行仿真優(yōu)化. 其中，3種算法參數(shù)設(shè)置為：種群大小N=50，外部檔案大小Wmax=20，最大迭代次數(shù)tmax=100. NSGA-II算法的選擇概率GGAP=0.9，交叉概率Pc=0.6，變異概率Pm=0.8. PCB組裝車間中5種PCB樣板在每臺(tái)機(jī)器上的加工質(zhì)量、 運(yùn)行功率和空載功率如表1所示.

表1 實(shí)例數(shù)據(jù)

5.2 評(píng)價(jià)指標(biāo)

對(duì)于多目標(biāo)優(yōu)化問(wèn)題，一般從收斂性和多樣性兩個(gè)方面來(lái)衡量算法所得解集的優(yōu)劣. 采用如下兩個(gè)性能評(píng)價(jià)指標(biāo)：

1) 收斂性指標(biāo). GD(generational distance)指標(biāo)[15]，表征算法所得Pareto解集與理想解集之間的間隔距離，用來(lái)評(píng)價(jià)算法的收斂性. GD值越小，表明間隔距離越小，算法收斂性越好. GD計(jì)算方式見(jiàn)文[15].

2) 多樣性指標(biāo). MS(maximum spread)指標(biāo)[16]，表征算法求解得到的Pareto解集PFknown覆蓋真實(shí)Pareto最優(yōu)解集PFtrue的范圍，用來(lái)評(píng)價(jià)算法所得解集的多樣性. MS值越大，表明PFknown覆蓋PFtrue的范圍越大，算法所得解集多樣性越好. MS計(jì)算方式見(jiàn)文[16].

5.3 結(jié)果對(duì)比及分析5.3.1 測(cè)試實(shí)例的結(jié)果及分析

9個(gè)測(cè)試實(shí)例的實(shí)驗(yàn)結(jié)果如表2所示.

表2 測(cè)試實(shí)例性能評(píng)價(jià)指標(biāo)結(jié)果

Tab.2 Results of test instance performance evaluation index

實(shí)例序號(hào)n×s (m)GDNSGA-IIRW_OFAIFS_OFAMSNSGA-IIRW_OFAIFS_OFA16×2 (5)28.4824.1623.190.8450.8760.96226×4 (10)127.71100.6276.930.7580.8130.87536×8 (22)286.81336.64233.510.6170.8330.923430×2 (4)74.3675.0167.490.6820.8740.851530×4 (10)199.80177.19143.520.7110.8040.895630×8 (20)414.89599.65706.450.6230.7020.9307100×2 (5)166.54160.28142.190.6910.8920.9738100×4 (12)368.01312.66241.510.6600.8070.9039100×8 (24)1012.601461.69968.620.7850.7100.832

注：n×s(m)中，n表示工件數(shù)，s表示工序數(shù)，m表示機(jī)器總數(shù); 黑體字表示最佳值.

從表2中可見(jiàn)，除了實(shí)例6，在其余實(shí)例中，IFS_OFA算法的GD值均小于兩種比較算法，表明本算法具有良好的收斂性；除了實(shí)例4，在其余實(shí)例中，IFS_OFA算法的MS值均大于兩種比較算法，表明本文算法得到的Pareto解集覆蓋范圍更大，具有更好的多樣性.

3種算法的GD值箱線圖如圖3所示，用于分析每種算法的魯棒性. 由于篇幅所限，僅給出了小中大3種種群規(guī)模的實(shí)例結(jié)果. 箱線圖中間的紅線代表中位線，紅色“+”代表異常值；箱線圖越扁表示方差越小，穩(wěn)定性越高. 由圖3可知，IFS_GA算法對(duì)應(yīng)的箱線圖寬度最扁，表示算法在多目標(biāo)流水車間調(diào)度問(wèn)題中穩(wěn)定性良好；IFS_OFA算法的中位線明顯小于另外兩種算法，表明得到的Pareto解集質(zhì)量良好.

圖3 GD值箱線圖Fig.3 Boxplot of GD value

5.3.2 實(shí)際案例的結(jié)果及分析

某PCB制造企業(yè)需要組裝生產(chǎn)小批量、 多類型的PCB樣板，該P(yáng)CB樣板組裝生產(chǎn)車間的生產(chǎn)排序?qū)儆诨旌狭魉囬g調(diào)度問(wèn)題. 某生產(chǎn)實(shí)例要加工5種PCB樣板，每種PCB樣板主要包含的4道加工工序?yàn)椋杭村a膏印刷、 表面貼裝、 回流焊接和質(zhì)量檢測(cè). 每道工序上的并行機(jī)器數(shù)量分別為3、 2、 2、 2. 其中錫膏印刷機(jī)a1～a3在第一道工序上，貼片機(jī)b1和b2在第二道工序上，回流焊爐c1和c2在第三道工序上，光學(xué)檢測(cè)儀d1和d2在第四道工序上.

企業(yè)根據(jù)經(jīng)驗(yàn)制定的車間原始應(yīng)用調(diào)度方案的甘特圖如圖4(a)所示，最大完工時(shí)間為68.7 s. 采用NSGA-II算法和RW_OFA算法優(yōu)化求解得到的最優(yōu)調(diào)度方案甘特圖分別如圖4(b)和圖4(c)所示，最大完工時(shí)間分別為48.7和43.2 s. 采用IFS_OFA算法進(jìn)行求解，選取直覺(jué)模糊集相似度最大的解為最優(yōu)調(diào)度方案，其直覺(jué)模糊集相似度值為0.955，最大完工時(shí)間為34.7 s，甘特圖如圖4(d)所示. 對(duì)比圖4中的四種調(diào)度方案，可以看出IFS_OFA最優(yōu)調(diào)度方案明顯縮短了最大完工時(shí)間，且使各工件的加工工序更加緊湊，減少了機(jī)器的空閑時(shí)間. 由以上分析可知，針對(duì)MOHFSP問(wèn)題，本文提出的IFS_OFA算法明顯優(yōu)于NSGA-II算法和RW_OFA算法.

圖4 四種調(diào)度方案甘特圖Fig.4 Gantt chart of four scheduling schemes

6 結(jié)語(yǔ)

針對(duì)制造業(yè)中存在著工件加工趨于多品種、 小批量、 工藝復(fù)雜的特點(diǎn)，建立了考慮完工時(shí)間、 空閑時(shí)間、 加工質(zhì)量和機(jī)器能耗的多目標(biāo)混合流水車間調(diào)度模型. 為解決該問(wèn)題，提出一種基于直覺(jué)模糊集相似度的最佳覓食算法(IFS_OFA)，利用直覺(jué)模糊集相似度建立解比較策略，引導(dǎo)最佳覓食算法進(jìn)化. 同時(shí)，設(shè)計(jì)了一種基于LOV規(guī)則的雙層整數(shù)編碼方案，既能表示出各個(gè)工件在每道工序中的加工順序，也能表示出各個(gè)工件在每道工序所選擇的加工機(jī)器. 采用測(cè)試實(shí)例和PCB組裝車間的案例進(jìn)行實(shí)驗(yàn)分析，結(jié)果表明本算法具有良好的收斂性、 多樣性和穩(wěn)定性，能夠有效求解多目標(biāo)混合流水車間調(diào)度問(wèn)題.