船舶平面分段流水線多目標模糊調(diào)度的改進粒子群算法

楊 志，柳存根

(1. 上海交通大學 船舶與海洋工程國家重點實驗室，上海 200240；2. 高新船舶與深海開發(fā)裝備協(xié)同創(chuàng)新中心，上海 200240)

0 引 言

隨著船舶大型化的發(fā)展，大型散貨船、油船、集裝箱船普遍呈現(xiàn)方形系數(shù)大、平行中體長等船型特點，因而平面分段的需求量大。為了提高平面分段的建造效率，多數(shù)大型船廠組建了平面分段流水線，適用于各種規(guī)格的鋼板及部件的裝焊。

近年來，關(guān)于流水線調(diào)度問題的研究層出不窮，主要以流水車間調(diào)度問題和混合流水車間調(diào)度問題為研究對象，并應(yīng)用諸如遺傳算法、粒子群算法、蟻群算法、禁忌搜索法、模擬退火法等智能優(yōu)化算法求解規(guī)模較大的、較復(fù)雜的調(diào)度問題[1–3]。在多數(shù)情況下，流水線調(diào)度問題的建模假設(shè)了加工時間和交貨期為精確值。但由于機器因素、工人因素、環(huán)境因素等的影響，加工時間實難確定，一般只能得到加工時間的大概數(shù)值和可能變化的范圍。另一方面，交貨期也并非完全固定，而是可能具有一定的彈性，表現(xiàn)為一個與需求方滿意度相關(guān)聯(lián)的時間區(qū)間。因此，可以認為加工時間和交貨期均模糊。多目標調(diào)度問題常見于實際生產(chǎn)，并受到學者重視。如Kahraman等[4]、Engine等[5]就分別應(yīng)用人工免疫算法和分散搜索算法求解了多目標的、帶模糊加工時間和模糊交貨期的流水車間調(diào)度問題。從調(diào)度的特點來看，一般的平面分段流水線的調(diào)度可以看作是流水車間調(diào)度問題。目前，關(guān)于平面分段流水線調(diào)度問題的研究相對較少[6–7]，且沒有考慮生產(chǎn)過程中的模糊性或不確定性。本文主要研究在模糊的加工時間和交貨期下，平面分段流水線的調(diào)度問題，建立平面分段流水線多目標模糊調(diào)度問題的數(shù)學模型，并設(shè)計一種改進的多目標粒子群算法對其進行求解。

1 問題描述

圖 1 面向縱骨先安裝法的平面分段流水線Fig. 1 Assembly line for panel blocks

平面分段是一類重要的船體分段，由鋼板及部件在流水線上裝焊而成。各船廠的平面分段流水線的工位設(shè)置不盡相同。本文以如圖1所示的1條面向縱骨先安裝法的平面分段流水線為例，研究其多目標模糊調(diào)度問題。該流水線配置了拼板、底板焊接、縱骨安裝、縱骨焊接、縱桁及肋板裝配、縱桁及肋板焊接、檢查運出等7個工位。在建分段經(jīng)由同步運輸輥由一個工位輸送至另一個工位。

平面分段流水線調(diào)度問題考慮如下：加工一批平面分段，任一分段的建造都須依次在各工位上完成相應(yīng)的工序；每個工位一次只能對一個分段進行加工且每一個分段一次只能在一個工位上進行加工；各工位間沒有緩沖工位，在建分段i需要在j-1工位上完成加工后才能進入j工位；在建分段i需要等其前一個在建分段在j工位上完成加工后才能進入j工位。另外，做出如下必要假設(shè)：所有分段可以在零時刻投入生產(chǎn)；加工過程中各平臺持續(xù)可用；分段在各工位的加工時間和交貨時間是模糊的，用模糊數(shù)表示；分段在各工位上加工前的準備時間包含于加工時間。

2 數(shù)學模型

基于以上描述與假設(shè)，建立平面分段流水線多目標模糊調(diào)度問題的數(shù)學模型。

2.1 符號表示

數(shù)學模型中的符號說明如下：

n為分段數(shù)量；m為工位數(shù)量；i為分段標號，

；j為工位標號，；為分段i在工位j上的模糊加工時間；為分段i的模糊交貨期；為分段i離開工位j的模糊時間；為分段i的模糊完工時間；為分段i的模糊完工時間相對于模糊交貨期的滿意度。

2.2 模糊加工時間

本(文以三角)模糊數(shù)描述模糊加工時間，表示為包含加工時間的最可能值（）、加工時間的下限值（）和加工時間的上限值（）等3個參數(shù)。模糊加工時間的隸屬函數(shù)表示如圖2（a）所示。

2.3 模糊交貨期

平面分段作為總段的中間產(chǎn)品，過早完工將增加倉儲成本，而拖期又會影響總段的裝配。本文以梯形模糊數(shù)刻畫模糊交貨期，表示為其隸屬函數(shù)表示如圖2（b）所示。其中，和分別表示交貨期的上、下限，完工時間在上、下限之外，最(不令人)滿意；與構(gòu)成理想的交貨期窗口完工時間在此窗口內(nèi)，最令人滿意。

圖 2 相關(guān)函數(shù)Fig. 2 Correlation function

2.4 模糊完工時間

假設(shè)表示一批分段的加工排序，分段i位于第k位。各分段的模糊完工時間可通過其在各工位的模糊加工時間計算得到，如下：

模糊完工時間與模糊加工時間具有相同的結(jié)構(gòu)，也用三角模糊數(shù)描述，表示為包含3個參數(shù)，分別為樂觀的完工時間（）、最可能的完工時間（）及悲觀的完工時間（）。

2.5 滿意度

完工時間總被希望切合于交貨期。在模糊調(diào)度問題中，滿意度極其重要，也是應(yīng)用最廣泛的指標之一[8]。它反映了模糊完工時間與模糊交貨期的切合程度。滿意度可通過式（7）計算，其表示如圖2（c）所示。

2.6 調(diào)度目標

根據(jù)模糊流水線調(diào)度的特點及實際生產(chǎn)的一般要求，本文以最小化最大完工時間，最大化平均滿意度為調(diào)度目標，如下：

3 模糊數(shù)運算

模糊流水線調(diào)度主要涉及模糊數(shù)的加法運算、取大運算、大小比較。對于三角模糊數(shù)其加法運算操作如下：

取大運算使用Lei近似準則[9]：

三角模糊數(shù)大小的比較采用以下3條準則[10]：

準則 1首先根據(jù)值的大小來比較2個三(角)模糊數(shù)的大小。

準則 2如果2個模糊數(shù)的值相等，則根據(jù)值的大(小)來比較2個三角模糊數(shù)的大小。

準則 3如果2個模糊數(shù)的值和值均相等，則根據(jù)值的大小來比較2個三角模糊數(shù)的大小。

4 改進多目標粒子群算法

4.1 粒子群算法

粒子群（PSO）算法是一種規(guī)則簡單、容易實現(xiàn)的進化算法。在PSO算法中，每一個粒子都具有速度和位置2個特征參數(shù)。其中，粒子的位置表征問題的解。PSO算法首先在可行解空間和速度空間隨機初始化粒子群，繼而通過不斷地更新各粒子的速度和位置搜尋最優(yōu)解。在D維搜索空間，粒子的速度和位置分別按式（12）和式（13）進行更新。

其中，分別表示粒子q在第k次迭代時的速度和位置。表示粒子q所經(jīng)過的最佳位置，表示粒子群體所發(fā)現(xiàn)的最佳位置。是慣性權(quán)因子，和常被分別稱作自學習因子和社會學習因子，和是介于（0，1）之間的隨機數(shù)向量。

需要指出，PSO算法在求解多目標問題上具有較大優(yōu)勢，主要表現(xiàn)在粒子群以內(nèi)在的并行方式同時搜索多個非支配解，從而容易得到多個Pareto最優(yōu)解。

4.2 按反Logistic曲線規(guī)律動態(tài)變化的慣性權(quán)重

本文提出慣性權(quán)重隨目標函數(shù)評價次數(shù)（Number of Function Evaluations，nFEs）按反 Logistic 曲線規(guī)律動態(tài)變化（inverse logistic inertia weight，ILIW），使在搜索初期能保持較長時間的較大值，以便算法維持較強的全局搜索能力；而在搜索后期使保持較長時間的較小值，以利于算法進行更精確的局部搜索。從而在一定程度上平衡算法的全局和局部搜索能力。慣性權(quán)重動態(tài)變化如下式：

其中，和分別為的最大值和最小值，為最大目標函數(shù)評價次數(shù)，為當前目標函數(shù)評價次數(shù)，a為常數(shù)（本文取值為3）。

4.3 解的表達

PSO算法中粒子的位置為連續(xù)值矢量，本文采用ROV（ranked-order-value）規(guī)則[11]將粒子的連續(xù)位置轉(zhuǎn)換為離散的工件排序在ROV規(guī)則下，位置分量值由小到大依次映射到順序值1到n，形成工件排序。

4.4 外部檔案及其維護

設(shè)立具有特定規(guī)模的外部檔案（external archive，EA）以保存算法在搜索過程中獲得的非支配解，即所有的。通過對EA的維護使算法得到的非支配解能盡量位于或靠近Pareto前沿，并且分散地分布于Pareto前沿。EA的維護操作主要包括：1）將所有新的非支配解加入EA，并從當前EA中移除所有被支配成員；2）若當前EA中的非支配解個數(shù)未超過其容量，則維持EA，否則執(zhí)行步驟3；3）采用基于擁擠距離（Crowding Distance, CD）的非支配解動態(tài)維護策略：①計算各非支配解的擁擠距離[12]；②按式（15）為各非支配解分配適應(yīng)值；③基于適應(yīng)值采用輪盤賭的方法選擇一個非支配解移出EA，轉(zhuǎn)步驟2。

其中，CD為擁擠距離，為常數(shù)（本文取值為4）。如此，擁擠距離越小的非支配解越可能被移出。動態(tài)維護策略不僅能保證非支配解的分布性，也能有效避免因一次移除過多密集區(qū)域的粒子而可能誤刪最優(yōu)解的問題。

4.5 變鄰域搜索算子

插入（Insert）、互換（Swap）和逆序（Inverse）是求解流水車間問題的3種常用鄰域結(jié)構(gòu)。為了系統(tǒng)地應(yīng)用3種鄰域結(jié)構(gòu)，本文將其隨機排列構(gòu)造變鄰域搜索（variable neighborhood search, VNS）算子，并直接作用于工件排序。具體而言，在某次調(diào)用VNS算子時，3種鄰域結(jié)構(gòu)隨機按6種順序中的1種（如Swap、Insert、Inverse的操作順序）依次調(diào)整工件排序，直到目標函數(shù)值有所改進或達到基于變鄰域搜索的最大目標函數(shù)評價次數(shù)（，本文設(shè)置為30）或目標函數(shù)評價次數(shù)達到。需要指出，工件排序改進之后必須根據(jù)工件排序重新排列各粒子位置矢量中的位置分量值，以保證位置矢量在ROV規(guī)則下與改進后的工件排序相對應(yīng)。VNS算子通過作用于和所有（即所有外部檔案成員）實現(xiàn)嵌入到多目標PSO算法，以增強算法的局部改良性搜索能力。V N S算子分別按概率和均以一定的規(guī)律隨的增大而減小，本文中

4.6 的選取

在更新各粒子速度時，需要從EA中為其選取一個。考慮到解得分布性，本文按式（16）為各EA成員分配適應(yīng)值，并基于適應(yīng)值采用輪盤賭的方法為各粒子選取一個。

其中，CD為擁擠距離，為常數(shù)（本文取其值為2）。如此，擁擠距離越大的EA成員越可能被選作某粒子更新速度時的。

5 調(diào)度實例求解

5.1 模糊數(shù)據(jù)

本文調(diào)度實例求解的對象為某船廠擬建造的一批（20個）不同尺寸平面分段。其中，加工時間的最可能值（）取相同或極相似分段歷史加工時間的均值，加工時間的下限值（）和加工時間的上限值（）則分別隨機取值于區(qū)間和區(qū)間基于歷史數(shù)據(jù)及相關(guān)工程師意見，本文對、、和分別定值為0.85，0.90，1.10和1.25。模糊交貨期由平面分段的需求方（如總段建造車間）提出。

5.2 算法對比

在相同的算法條件和計算環(huán)境下，分別應(yīng)用本文提出的改進多目標粒子群算法（MOPSO-ILIWVNS），僅不采用非支配解動態(tài)維護策略的多目標粒子群算法（MOPSO-ILIW-VNS-2），僅引入按反Logistic曲線規(guī)律變化的動態(tài)慣性權(quán)重多目標粒子群算法（MOPSO-ILIW），僅嵌入VNS算子的多目標粒子群算法（MOPSO-VNS），以及帶壓縮因子[13]的多目標粒子群算法（MOPSO-CF）求解平面分段流水線多目標模糊調(diào)度問題。其中，MOPSO-VNS與MOPSO的慣性權(quán)重相同，均為本文取，其他3種算法的最大慣性權(quán)重和最小慣性權(quán)重分別取值0.9和0.4。其他3種算法的最大慣性權(quán)重和最小慣性權(quán)重分別取值為0.9和0.4。上述所有算法的自學習因子相同，均為，社會學習因子也相同，均為。除MOPSO-ILIW-VNS-2外，其余算法均采用非支配解動態(tài)維護策略。各算法的最大目標函數(shù)評價次數(shù)均設(shè)為20 000，種群規(guī)模Ps均設(shè)為40，外部檔案最大規(guī)模sM均設(shè)為10。MOPSO-ILIW-VNS、MOPSO-ILIW-VNS-2及MOPSO-VNS中基于變鄰域搜索的最大目標函數(shù)評價次數(shù)均設(shè)為30。

引入C指標[14]、GD指標[15]和指標[12]分別從解的覆蓋度、收斂性和分布性3個方面評價5種算法。以和分別表示2種算法所求得的近似Pareto最優(yōu)解的集合，C指標通過將有序映射到0到1之間的數(shù)值，直觀反映2個集合中解的覆蓋（相同及被支配）關(guān)系。GD指標描述了所求得的近似Pareto前沿（OF）中的元素到Pareto前沿（PF*）的距離。GD=0表明OF 包含于PF*，這是令人滿意的。指標衡量了OF中元素分布的差異性和均勻性。若OF中元素具有理想的分布且包含PF*中的2個端部元素的距離，則。

本文應(yīng)用5種算法分別獨立地對實例進行100次求解，基于各算法的100次求解結(jié)果計算上述3個指標評價對5種算法進行評價。由于PF*未知，本文通過整合5種算法求解的所有OF構(gòu)造一個參考Pareto前沿作為PF*。在計算GD指標和指標時，本文對目標向量值進行標準化處理，使之取值于[1，2]區(qū)間，其中makespan以第3節(jié)準則1先做了去模糊化處理。

以A1，A2，A3，A4和A5分別表示MOPSO-ILIWVNS、MOPSO-ILIW-VNS-2、MOPSO-ILIW、MOPSOVNS和MOPSO-CF。分別整合各算法在100次求解中得到的近似Pareto最優(yōu)解集，形成對應(yīng)的，，，和五個集合。部分C指標如表1。其中，括號里的值為被支配的比例。MOPSO-CF（A5）上僅引入按反Logistic曲線規(guī)律動態(tài)變化的慣性權(quán)重，或者僅嵌入變鄰域搜索算子的有效性。從解的覆蓋度方面說明非支配解動態(tài)維護策略的有效性。與其他4個集合的比較則從解的覆蓋度方面證實了MOPSO-ILIWVNS（A1）的有效性和優(yōu)越性。

表 1 C指標Tab. 1 C- metric

5種算法各求得100個獨立的OF，進而獲得各算法的100個GD指標和100個指標，分布如圖3所示。表2羅列了部分GD指標和指標的Wilcoxon秩和檢驗的結(jié)果。其中，括號里的值為p值。表2和圖3顯示，A3和A4的兩指標均顯著優(yōu)于A5，說明在MOPSOCF（A5）上僅引入按反Logistic曲線規(guī)律動態(tài)變化的慣性權(quán)重，或者僅嵌入變鄰域搜索算子都有利于提高解的收斂性和分布性。A1的指標在0.1的顯著性水平下優(yōu)于A2，說明在0.1的顯著性水平下可接受非支配解動態(tài)維護策略有利于提高解的分布性的假設(shè)。A1的GD指標在至多為0.05的顯著性水平下優(yōu)于A3、A4和A5，且不亞于A2；A1的指標在至多為0.1的顯著性水平下優(yōu)于其他4種算法。因此，可認為MOPSOILIW-VNS（A1）在解的收斂性和分布性上都表現(xiàn)出優(yōu)越性。

圖 3 GD 指標和 Δ 指標的箱線圖Fig. 3 Boxplots of the GD and Δ indicators

表 2 GD指標和Δ指標的Wilcoxon秩和檢驗的結(jié)果Tab. 2 Results of the Wilcoxon rank-sum test for the GD and Δ indicators

6 結(jié) 語

本文研究了模糊的加工時間和交貨期下，平面分段流水線的調(diào)度問題。提出了一種引入按反Logistic曲線規(guī)律動態(tài)變化的慣性權(quán)重，并嵌入由3種鄰域結(jié)構(gòu)隨機排列構(gòu)造的變鄰域搜索算子，同時采用基于擁擠距離的非支配解動態(tài)維護策略的改進多目標粒子群算法MOPSO-ILIW-VNS來求解平面分段流水線多目標模糊調(diào)度問題。結(jié)合實例數(shù)據(jù)，通過對多種算法進行比較，從解的覆蓋度、收斂性和分布性等3方面證實了各項改進措施的有效性，以及MOPSO-ILIW-VNS算法的優(yōu)越性。作者將繼續(xù)開展并不斷深入關(guān)于船舶建造的多目標模糊調(diào)度研究。后續(xù)研究將考慮其他更復(fù)雜的船舶建造生產(chǎn)線（如非完全混合的平面分段流水線[7]）的多目標模糊調(diào)度問題。

[1]REZA HEJAZI S, SAGHAFIAN S. Flowshop-scheduling problems with makespan criterion: a review[J]. International Journal of Production Research, 2005, 43(14): 2895–2929.

[2]RUIZ R, VáZQUEZ-RODRíGUEZ J A. The hybrid flow shop scheduling problem[J]. European Journal of Operational Research, 2010, 205(1): 1–18.

[3]YENISEY M M, YAGMAHAN B. Multi-objective permutation flow shop scheduling problem: Literature review,classification and current trends[J]. Omega, 2014, 45: 119–135.

[4]KAHRAMAN C, ENGIN O, YILMAZ M K. A new artificial immune system algorithm for multiobjective fuzzy flow shop[J]. International Journal of Computational Intelligence Systems, 2009, 2(3): 236–247.

[5]ENGIN O, KAHRAMAN C, YILMAZ M K. A scatter search method for multiobjective fuzzy permutation flow shop scheduling problem: a real world application[M].Computational Intelligence in Flow Shop and Job Shop Scheduling. Springer Berlin Heidelberg, 2009: 169–189.

[6]HA T R, MOON C U, JOO C M, et al. A hybrid genetic algorithm for scheduling of the panel block assembly shop in shipbuilding[J]. Management Science, 2000, 17(1): 135–143.

[7]張志英, 李殿勤. 船舶平面分段的非完全混合流水線調(diào)度[J].計算機集成制造系統(tǒng), 2012, 18(11): 2435–2445.

[8]ABDULLAH S, ABDOLRAZZAGH-NEZHAD M. Fuzzy jobshop scheduling problems: A review[J]. Information Sciences,2014, 278: 380–407.

[9]LEI D. Fuzzy job shop scheduling problem with availability constraints[J]. Computers & Industrial Engineering, 2010,58(4): 610–617.

[10] SAKAWA M, KUBOTA R. Fuzzy programming for multiobjective job shop scheduling with fuzzy processing time and fuzzy duedate through genetic algorithms[J]. European Journal of operational research, 2000, 120(2): 393–407.

[11] LIU B, WANG L, JIN Y H. An effective PSO-based memetic algorithm for flow shop scheduling[J]. Systems, Man, and Cybernetics, Part B: Cybernetics, IEEE Transactions on, 2007,37(1): 18–27.

[12] DEB K, PRATAP A, AGARWAL S, et al. A fast and elitist multiobjective genetic algorithm: NSGA-II[J]. IEEE transactions on evolutionary computation, 2002, 6(2):182–197.

[13] CLERC M, KENNEDY J. The particle swarm-explosion,stability, and convergence in a multidimensional complex space[J]. IEEE transactions on Evolutionary Computation,2002, 6(1): 58–73.

[14] ZITZLER E, THIELE L. Multiobjective evolutionary algorithms: a comparative case study and the strength Pareto approach[J]. IEEE transactions on Evolutionary Computation,1999, 3(4): 257–271.

[15] VAN VELDHUIZEN D A, LAMONT G B. Multiobjective evolutionary algorithm research: A history and analysis[R].Technical Report TR-98-03, Department of Electrical and Computer Engineering, Graduate School of Engineering, Air Force Institute of Technology, Wright-Patterson AFB, Ohio,1998.