朱光宇，丁 晨

(福州大學 機械工程及自動化學院，福建 福州 350116)

0 引言

置換流水車間調度問題(Permutation Flow-shop Scheduling Problem, PFSP)是許多實際流水線生產調度的一個簡化模型，是研究較為廣泛的生產調度問題之一，許多生產制造、裝配、運輸等問題均可簡化為該模型，它在流水車間調度的基礎上，要求每臺機器上工件的加工順序均相同。為提高企業(yè)競爭力，生產者在選取調度方案時，需考慮的因素并不唯一，往往要求方案能夠在生產過程中使多個目標同時達到最優(yōu)。因此，多目標流水車間調度問題更加符合生產企業(yè)的現實情況，具有重要的應用價值。賀利軍等[1]設計了一種基于模糊關聯(lián)熵的粒子群算法，解決具有4個目標的流水車間調度問題。LU等[2]采用一種混合多目標回溯搜索算法，解決了兩目標的置換流水車間調度問題。鐘棱充等[3]針對目標函數為最小化碳排放總量和最大完工時間的流水車間調度問題，設計了一種混合布谷鳥算法求解。ARROYA等[4]將貪婪隨機自適應搜索策略應用于啟發(fā)式算法，解決了三目標的置換流水車間調度問題。不難看出，目前對于多目標流水車間調度問題的研究，多以2個或3個優(yōu)化目標為主，考慮3個目標以上的高維多目標流水車間調度問題較少。其原因在于：流水車間調度問題本身存在一定的求解難度，大部分都是NP-hard問題[5]；另外，隨著優(yōu)化問題目標維數的增大，采用傳統(tǒng)的多目標優(yōu)化算法在對目標空間進行搜索時，利用Pareto支配關系難以選擇最優(yōu)個體，算法的搜索能力急速下降。因此，高維多目標車間調度問題對調度算法的設計和實現造成了極大的挑戰(zhàn)。近年來，各類智能優(yōu)化算法不斷涌現，受到了國內外研究學者的廣泛關注。一些智能優(yōu)化算法已成功地應用于流水車間調度領域，主要包括粒子群算法、人工蜂群算法、果蠅優(yōu)化算法和遺傳算法等。

最優(yōu)覓食算法(Optimal Foraging Algorithm, OFA)[6]是一種基于生態(tài)行為理論—最優(yōu)覓食理論的群智能優(yōu)化算法，具有搜索能力強、機制簡單、參數少等優(yōu)點，已在白細胞分割[7]、群孔鉆削路徑優(yōu)化[8]、支持向量機的參數優(yōu)化[9]等問題中取得了良好的應用效果。然而，鮮有文獻將最優(yōu)覓食算法應用于生產調度優(yōu)化領域。

累積前景理論[10]是前景理論的拓展，它是一種同時考慮決策者風險偏好的多屬性決策方法，在各個領域得到了一定應用。閆書麗等[11]設計了一種基于灰靶思想和累積前景理論的決策方法，用于求解動態(tài)風險決策問題。王正新等[12]將多指標灰關聯(lián)方法與累積前景理論融合，分析了決策者風險態(tài)度對多指標決策的影響。曲霞[13]在累積前景理論的基礎上，引入最大熵理論建立了一種水庫防洪調度決策模型。目前，尚未有研究者將累積前景理論應用于求解多目標流水車間調度問題。

針對多目標流水車間調度問題，本文將累積前景理論和最優(yōu)覓食算法相結合，提出一種基于累積前景理論的最優(yōu)覓食算法(Optimal Foraging Algorithm based on Cumulative Prospect Theory, CPT-OFA)。算法將灰色關聯(lián)分析法應用于累積前景理論中，構造了前景價值函數，以此建立Pareto解的綜合前景價值模型。通過綜合前景價值來探尋Pareto解與各個目標之間的有效信息，有效消除優(yōu)化問題中目標量綱和數量級的影響。在算法的進化過程中，采用綜合前景價值作為算法的適應度值來引導算法進化，以價值的大小來判斷Pareto解的好壞，對包括最大完工時間、最大延遲時間、庫存成本和拖期成本在內的4個目標進行優(yōu)化。最后，通過仿真對比實驗對CPT-OFA算法性能進行驗證，結果表明CPT-OFA在解決流水車間調度問題時具有顯著優(yōu)勢。

1 PFSP問題描述及高維多目標模型的建立

1.1 PFSP問題描述

置換流水車間調度問題描述為：m臺機器依據相同的工藝路線對n個獨立的工件進行加工，所有機器上工件的加工順序均相同,并約定每個工件不能在同一時間內在不同的機器上加工，每臺機器不能在同一時間內加工多個工件，每個工件在各臺機器上所需加工時間均已知，期望獲得工件的最優(yōu)加工序列使得多個性能指標共同達到最優(yōu)。設機器集合為M={1，2，…，m}，工件集合為Job={1，2，…，n}。在收到客戶訂單后，生產商必須在規(guī)定時間內完成所有工件的加工并運送給客戶。由于受到客戶交貨期和本身庫存能力的影響，超過交貨期生產的工件將會給生產商帶來拖期成本；提前完工的工件在運輸之前將會給生產商帶來庫存成本。拖期成本、庫存成本都與時間成正比關系，每當加工完成規(guī)定數量的工件時即開始運輸，且每批工件的裝運時間是相應批次中最后一個工件的完工時間。

1.2 高維多目標模型的建立

在實際生產中，生產商在選取調度方案時既要考慮客戶服務滿意度，也要考慮企業(yè)內部降低生產成本的期望。因此，針對車間調度問題，本文以最大完工時間、最大延遲時間、庫存成本和拖期成本為目標函數，建立高維多目標模型。其中，最小化最大完工時間有利于提高企業(yè)的生產效率；最小化最大延遲時間有利于提高客戶滿意度；而最小化拖期成本和庫存成本有利于提高企業(yè)的經濟效益。

設X={x1，x2，…，xn}是n個決策變量的向量，表示可行的工件加工順序。F(X)={f1(X)，f2(X)，…，fM(X)}稱為Pareto前沿或目標向量，fk(X)是第k個目標的函數值。高維多目標模型表示如下：

F=min(f1，f2，f3，f4)。

(1)

其中：

f1=max{Cim|i∈1，2，…，n}；

(2)

f2=max{(0，(Cim-Di))|i∈1，2，…，n}；

(3)

(4)

(5)

s.t.

C11≥T11；

(6)

C1k≥C1(k-1)+T11，k=2，…，m；

(7)

Ci1≥C(i-1)1+Ti1，i=2，…，n；

(8)

Cik≥max{Ci(k-1)，C(i-1)k}+Tik，

i=2，…，n，k=2，…，m；

(9)

Sj≤h，j=1，2，…，b。

(10)

式中：f1為工件的最大完工時間，f2為最大延遲時間，f3和f4分別為所有工件的庫存成本和拖期成本，Cim為工件i在機器m上完成最后一道工序的時間，Di和Li分別為工件i的交貨時間和裝運時間，βi和δi分別為工件i的庫存成本和拖期成本，Tik為工件i在機器k上的加工時間，Sj第j批工件的實際運輸量，h和b分別為單批次最大運輸量和運輸次數。

2 改進的最優(yōu)覓食算法

2.1 標準最優(yōu)覓食算法描述

最優(yōu)覓食算法將尋優(yōu)過程模擬為動物的覓食過程。根據動物的覓食行為來設計搜索操作，通過迭代對種群內個體覓食位置進行更新，從而實現對目標空間的搜索。

(11)

個體選擇過程如下：根據最優(yōu)覓食理論,動物在覓食的過程中只存在兩種類型的獵物，即有利可圖Ⅰ型與無利可圖Ⅱ型。動物在覓食之前往往會對獵物進行識別，從而選擇對自身有利的獵物。在最優(yōu)覓食算法中，假定位置更新后的個體Xt+1為Ⅰ型獵物，當前位置的個體Xt為Ⅱ型獵物。對于最小化問題，采用下式判斷Xt+1與Xt之間的好壞：

(12)

式中：λt+1∈[0,1]為服從均勻分布的隨機數，ft+1和ft分別為Xt+1和Xt的適應度值。若式(12)成立，則個體Xt+1被保留；否則，將保留個體Xt。

2.2 逆向搜索機制

在迭代過程中，最優(yōu)覓食算法采用招募的方式更新種群位置。該方式的局限性在于，若招募個體已陷入局部最優(yōu)解，則通過招募操作可能會導致被招募個體也陷入局部最優(yōu)解。此外，個體的位置更新主要受縮放系數k的影響，k值的大小隨著迭代次數的增加從0逐漸增加到1。在迭代初期，個體位置增量較小，種群的全局搜索能力較弱，易陷入局部最優(yōu)解。為了增強算法規(guī)避局部最優(yōu)解的能力，在招募操作的基礎上增加逆向搜索機制，其基本思想是在個體選擇后產生種群P時，生成其逆向種群OP，并根據適應度值的大小從兩個種群{P,OP}中選取N個較優(yōu)個體組成新種群，則此新種群將被用于下一次迭代搜索。逆向搜索機制的數學表達式如下：

Xop=La+Ua-X。

(13)

式中：La、Ua為X的上下界，Xop為X的逆向個體。

2.3 改進算法的流程

基于逆向搜索機制的最優(yōu)覓食算法流程如下：

步驟1初始化。迭代次數t=1，給定算法的最大迭代次數Tmax，隨機生成個體數量為N的初始種群。

步驟2計算種群中所有個體的適應度值并根據值的大小進行排序。

步驟3種群位置更新。根據式(11)對當前種群中每一個體的位置進行更新，并且計算位置更新后個體的適應度值。

步驟4個體選擇。根據式(12)將當前位置的個體與位置更新后的個體進行對比，選擇較優(yōu)個體。

步驟5種群重組。個體選擇后，所有被保留的個體組成種群P，根據式(13)生成其逆向種群OP，并按照適應度值的大小從種群集{P,OP}中選取排序前N個個體重新組成新種群，用于下一次迭代搜索。

步驟6若滿足終止條件，即達到最大迭代次數，則輸出優(yōu)化結果；否則，返回步驟3。

3 基于累積前景理論的最優(yōu)覓食算法

基于累積前景理論的最優(yōu)覓食算法首先將累積前景理論和灰色關聯(lián)分析方法融合，建立Pareto解的綜合前景價值模型；然后利用信息熵理論確定各目標的評價權重，采用前景價值作為最優(yōu)覓食算法的適應度值來引導算法進化，以價值的大小對Pareto解的優(yōu)劣進行評估。

3.1 累積前景理論基本描述

累積前景理論充分考慮決策者在面對收益和損失時的風險態(tài)度，通過設置參照點、確定價值函數和屬性權重的方式來建立綜合前景價值模型，從而對風險決策問題進行評估。

令F={f:Q→ζ}為所有前景集。自然狀態(tài)集Q通過不確定前景f映射到結果集ζ，表示任意事件Bd發(fā)生時會產生結果ξd。所有ξd構成一個嚴格遞增序列，即ξ1≤ξ2≤…≤ξh≤…≤ξD。取序列中點ξh為參考點，若優(yōu)于ξh則為正前景，反之為負前景。正、負前景價值分別為V(f+)和V(f-)，表示決策者在相應結果下的得與失。f的綜合前景價值為V(f)=V(f-)+V(f+)，其中：

(14)

價值函數v的具體形式為：

(15)

式中：0<α，β<1分別為決策者面對風險時的厭惡和偏好系數；θ為損失規(guī)避系數,一般取α=β=0.85，θ=2.25[10]。

收益和損失的概率權重函數π+和π-分別為：

(16)

(17)

式中：pd為事件發(fā)生的概率；參數0<γ，η<1分別體現了決策者對于收益和損失的態(tài)度，當參數γ=0.61，η=0.69[14]時，與經驗數據較為一致。

3.2 累積前景理論的多目標灰關聯(lián)評價策略

將累積前景理論應用于多目標優(yōu)化問題時，本文引入灰色關聯(lián)分析法和信息熵理論，建立基于灰關聯(lián)評價策略的綜合前景價值模型。通過該模型有效地建立起Pareto解與前景價值的聯(lián)系，探尋Pareto解與各目標之間的有效信息。設Xi的Pareto前沿為Fi={fi1，fi2，…，fij，…，fiM}，其中fiM表示Xi的第M個目標函數值,i=1，…，N。以下是基于灰關聯(lián)評價策略的綜合前景價值模型建立過程：

(1)標準化處理

為了有效消除目標量綱和數量級不同的影響，對每個目標值進行標準化處理。處理方式如下：

(18)

式中：uij為子目標值fij的標準化處理值；fmax(j)和fmin(j)分別為第j個目標的最大值和最小值。

(2)確定參照點

決策者在進行決策時，通常會根據某些參考點來衡量決策的得失程度。可借鑒優(yōu)劣解距離(Technique for Order Preference by Similarity to an Ideal Solution, TOPSIS)方法[15]的思想，選取正負理想方案作為評價指標的參照點，用來衡量Pareto解的優(yōu)劣，即：

(19)

(3)正負關聯(lián)系數的確定

采用灰色關聯(lián)分析法選取正負理想方案作為參考數列，則Xi與正負理想方案U+和U-關于第j個目標的正負關聯(lián)系數可確定為：

(20)

(21)

(4)正負前景價值函數的構建

在累積前景理論價值函數的基礎上，構建Pareto解的前景價值函數：

(22)

(5)建立綜合前景價值模型

設Pareto解正負前景的屬性權重函數分別為π+(wj)和π-(wj)，則個體Xi的綜合前景價值Vi可表示為：

(23)

式中：wj為第j個目標的評價權重；π+(wj)和π-(wj)可根據式(16)和式(17)分別計算得到；綜合前景價值Vi是正負前景值之和，前景價值越大，表示Pareto解的質量越好。

為了確定各目標的評價權重wj，本文引入信息熵理論來有效避免因主觀因素導致的分配權重偏差。具體計算過程如下：

步驟1利用目標函數值標準化處理后的值計算各目標所占比重。

(24)

步驟2計算各目標的信息熵。

(25)

步驟3計算各目標的評價權重。

(26)

式中：i=1，…，N，j=1，…，M。

從綜合前景價值模型的構建過程可以看出，綜合前景價值模型是在累積前景理論的基礎上，通過灰色關聯(lián)分析法逐步建立起Pareto解與前景價值之間的聯(lián)系，利用信息熵理論確定各目標的評價權重，以綜合前景價值的大小來評估Pareto解的優(yōu)劣程度，價值越大，則解的質量越好。因此，可采用前景價值作為進化算法的適應度值來引導算法求解多目標流水車間調度問題。

3.3 求解多目標流水車間調度問題的算法實現

本文將綜合前景價值模型與最優(yōu)覓食算法結合，用以求解包括最大完工時間、最大延遲時間、庫存成本和拖期成本4個目標在內的置換流水車間調度問題。由于流水車間調度問題中工件排序的編碼方式是離散化的，可采用LOV(largest-order-the value)方法[16]實現算法從連續(xù)實數到離散工序的轉化。算法的具體流程如下：

步驟1初始化種群。

步驟2計算綜合前景價值。

步驟3個體更新。

步驟4選擇操作。

步驟5種群重組。

根據式(13)生成子代種群P的逆向種群OP，按照前景價值的大小從兩個種群{P,OP}中選取排序前N個個體重新組成新種群，用于下一次迭代搜索。

步驟6外部檔案維護與更新。

將新種群和外部檔案合并，通過計算其擁擠距離并結合精英保留策略來對外部檔案進行修剪，刪除距離小的Pareto解，從而實現對外部檔案的更新。

步驟7判斷是否滿足終止條件。

若滿足最大迭代次數Tmax的要求，則停止算法搜索，并輸出優(yōu)化結果；否則t=t+1，返回步驟3。

4 仿真實驗與結果分析

本文采用10個不同規(guī)模的置換流水車間測試實例[17]以及某印刷電路板生產廠的應用案例來測試CPT-OFA算法性能，并選取NSGA-Ⅲ[18]、SIFS_GA(similarity of intuitionistic fuzzy sets GA)[19]、GrEA(grid based evolutionary algorithm)[20]作為對比算法，以驗證所提算法的可行性與有效性。其中，NSGA-Ⅲ是一種基于參考點的非支配排序的多目標優(yōu)化算法；SIFS_GA是最近提出的一種基于直覺模糊集相似度的遺傳算法；GrEA是一種采用網格支配策略的多目標優(yōu)化算法。

各算法共同的參數設置如下：外部檔案數Wmax=20，種群個數N=20，最大迭代次數Tmax=120，對于每個測試問題，采用不同的初始種群優(yōu)化10次。置換流水車間測試實例的基本參數設置如下：單位庫存成本βi=1，單位拖期成本δi=2，單批次最大運輸量h=5。

4.1 性能評價指標

采用間隔距離(SP)、當代距離(GD)與C指標3個評價指標驗證所提算法CPT-OFA的性能。

(1)多樣性指標 間隔距離，用以評價算法所得解集在目標空間的分布情況。計算公式為：

(27)

(2)收斂性指標 當代距離，用以評價算法所得解集與理想解的接近程度。計算公式為：

(28)

式中di為第i個非支配解與理想解之間的歐式距離。GD值越小，則Pareto解與理想解越接近，收斂性越好。

(29)

4.2 流水車間測試實例結果分析

本文借鑒文獻[17]的方法生成10個不同規(guī)模的流水車間測試實例，規(guī)模從m=5臺機器、n=10個工件到20臺機器、100個工件。采用CPT-OFA和3種對比算法分別對測試實例進行多目標優(yōu)化，將得到的優(yōu)化結果進行分析比較，最后確定性能最優(yōu)算法。仿真結果為各算法運行10次的平均值，如表1和表2所示，其中理想解函數值由各目標的單目標最優(yōu)解函數值組成。

表1 10個置換流水車間測試實例的仿真實驗結果(最好的優(yōu)化解用加粗強調)

續(xù)表1

表2 各算法覆蓋率指標比較結果

續(xù)表2

表1結果顯示：在實例1和實例2中，CPT-OFA有3個目標優(yōu)于GrEA和NSGA-Ⅲ,2個目標優(yōu)于SIFS_GA;在其他實例中，CPT-OFA獲得的多目標優(yōu)化解均優(yōu)于GrEA、NSGA-Ⅲ和SIFS_GA；這表明在求解多目標流水車間問題時，CPT-OFA采用前景價值引導算法進化能得到比其他3種算法更好的多目標優(yōu)化解。在多樣性指標SP方面，實例1、2、5、10中，CPT-OFA的SP值大于SIFS_GA，但是小于其他兩種算法；在其他實例中，CPT-OFA的SP值均小于其他3種算法，表明CPT-OFA獲得的Pareto解集分布的均勻性優(yōu)于其他算法。在收斂性指標GD方面，CPT-OFA的GD值均小于其他3個算法，表明CPT-OFA所獲得的Pareto解集更接近理想解，其收斂性最優(yōu)。

表2結果顯示：對于NSGA-Ⅲ,C(CPT-OFA,NSGA-Ⅲ)的值除實例1、2外均為1，而C(NSGA-Ⅲ, CPT-OFA)的值均接近0，表明CPT-OFA獲得的大多數解覆蓋了NSGA-Ⅲ的解；對于SIFS_GA，C(CPT-OFA,SIFS_GA)的值均遠大于C(SIFS_GA, CPT-OFA)的值，表明CPT-OFA獲得的解覆蓋SIFS_GA獲得解的比例遠大于SIFS_GA獲得的解覆蓋CPT-OFA獲得解的比例；對于GrEA,C(CPT-OFA,GrEA)的值均大于C(GrEA, CPT-OFA)的值，表明CPT-OFA的尋優(yōu)效果顯著優(yōu)于GrEA。另一方面，隨著規(guī)模的增大，C(CPT-OFA,SIFS_GA)和C(CPT-OFA,GrEA)值也接近1，表明在求解規(guī)模較大問題時CPT-OFA的性能更好。綜上可知，相比于其他算法，CPT-OFA在解決多目標流水車間問題時具有較強優(yōu)勢，并且更適用于解決規(guī)模較大的問題。

4.3 應用案例

某印刷電路板生產廠同時收到來自5個客戶的訂單，每個客戶要求該廠生產的印刷電路板工件類型均不同，但可通過相同的加工過程分別在9臺機器上進行流水線生產。為了提高廠家效益，本文采用CPT-OFA與3種對比算法以前述4個目標為出發(fā)點對流水線生產過程進行調度優(yōu)化，并將調度方案進行仿真，確定最優(yōu)調度方案。單位庫存成本βi和單位拖期成本δi均為1，印刷電路板的加工過程、機器編號以及工廠生產原始數據如表3所示。

表3 印刷電路板生產數據

各算法的優(yōu)化結果如圖1所示，可以看出，CPT-OFA的最大完工時間f1和庫存成本f3均小于其他3種算法；GrEA、SIFS_GA和NSGA-Ⅲ的最大延遲時間f2均小于CPT-OFA的值；CPT-OFA的拖期成本f4小于NSGA-Ⅲ，但是大于GrEA和SIFS_GA的值。若生產商優(yōu)先考慮縮短最大完工時間和降低庫存成本，則CPT-OFA的調度方案具有較大優(yōu)勢，其甘特圖如圖2所示。因篇幅所限，僅畫出CPT-OFA的甘特圖。

為了進一步分析工廠車間布局和印刷電路板工藝流程，本文采用Quest軟件對工廠流水生產線進行仿真建模。Quest是法國達索公司開發(fā)的用于分析車間布局和工藝路徑的商業(yè)化仿真軟件。分別輸入4種算法的調度方案，在Quest軟件中進行仿真運行，量化機器空閑時間與利用率，并對不同方案的仿真結果進行分析和對比。

圖3a為4種方案的9臺機器設備的利用率，可以看出CPT-OFA調度方案所有機器的利用率均高于NSGA-Ⅲ、SIFS_GA和GrEA的調度方案。圖3b為4種方案的9臺機器設備的空閑時間，可以看出CPT-OFA的調度方案所有機器的空閑時間均少于其他3種算法的調度方案。

綜上所述，根據Quest軟件仿真出的數據分析可得出結論，CPT-OFA為最優(yōu)調度方案，該方案可以在滿足工廠生產效益的基礎上，提高機器利用率，降低設備的空閑時間。

5 結束語

本文針對高維多目標置換流水車間調度問題，提出了CPT-OFA算法對其進行求解，得出以下結論：

(1)在累積前景理論中引入灰色關聯(lián)分析法、信息熵，建立基于多目標灰關聯(lián)評價策略的綜合前景價值模型，用其解決多目標置換流水車間調度問題，將累積前景理論應用于多目標優(yōu)化，擴展了其應用領域。

(2)對標準最優(yōu)覓食算法進行改進，引入了逆向搜索機制以提高算法規(guī)避局部最優(yōu)解的能力。

(3)通過對流水車間測試實例、實際應用的仿真，驗證了所提CPT-OFA算法性能的優(yōu)越性，在多目標流水車間調度問題上能夠獲得較好的Pareto解，且更適用于解決規(guī)模較大的問題。

本文工作僅表明CPT-OFA對置換流水車間調度問題的求解是有效的。未來將繼續(xù)關注CPT-OFA對柔性作業(yè)車間調度等其他生產調度問題的應用效果。