蘭宏凱，楊 志，柳存根，張水明

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

0 引 言

隨著船舶逐步趨向于大型化，船舶平面分段數(shù)量也逐步增大，因此船舶平面分段的調度問題研究具有十分重要的意義。在實際船舶生產建造過程中，受到機器因素、人工因素和其他不可控因素的影響[1]，船舶平面分段的加工時間不可控。此外，船舶分段的具體加工時間和要求的交貨期均為一個區(qū)間，很難確定其精確值。因此船舶平面分段在建造過程中的關鍵時間節(jié)點都具有模糊性，為了更好地吸收數(shù)據(jù)的模糊性，指導實際的生產計劃，本研究對原始數(shù)據(jù)進行模糊化處理，從而開展模糊調度。平面分段由鋼板及部件在流水線上進行焊接而成，各個船廠的平面分段流水線的功能設置各有不同，本文以一條面向縱骨先安裝法的平面分段流水線為例。流水線上配置了拼板、底板焊接、縱骨安裝、縱骨焊接、縱桁及肋板裝配、縱桁及肋板焊接、檢查運出等7 個工位，其中拼板工位需要完成鋼板的定位和預先電焊；縱骨安裝通過安裝門架機完成；縱桁及肋板裝配由安裝門架機并由工人輔助完成；檢查運出工位需要對裝配和焊接質量進行檢查，最后由頂升裝置和平板車將分段運出。

目前針對流水線調度問題，很多學者提出了蟻群算法、禁忌搜索法、模擬退火法等智能優(yōu)化算法，主要的研究對象局限在流水車間調度問題和混合流水車間[2-3]。眾多的研究僅僅是針對流水線的靜態(tài)調度進行研究，并沒有考慮數(shù)據(jù)的模糊性和急件到達這種特殊工況。因此，本研究針對船舶平面分段單流水線面對急件任務情況下，設計一個多目標文化基因算法進行模糊調度。

1 問題描述

船舶平面分段單流水線反應式多目標調度問題考慮如下：流水線為單平面分段流水線，0 時刻開始按照既定調度方案加工，t 時刻急件任務到達。當急件任務到達時，正在流水線加工的分段繼續(xù)完成加工，未進入流水線的分段等待重新調度。當流水線上最后一個分段離開第一個工位時開始重調度方案的生產，并要求急件任務和原任務以最小化最大完工時間完成，并保證急件任務和原任務在要求的工期內完成。分段的開始加工時間采用三角模糊數(shù)表達，分段加工時間采用梯形模糊數(shù)表達。

問題假設：對于所有重調度分段，均可在啟動反應式調度時投入生產；加工過程中各工位持續(xù)可用；分段在各工位進行加工時不可中斷；分段在各工位的加工時間及其交貨時間模糊；分段在各工位上加工前的準備時間包含于加工時間；在建分段在各工位間的輸送時間不計。

2 數(shù)學模型

基于以上描述與假設，建立平面分段單流水線反應式模糊調度問題的數(shù)學模型。

2.1 符號說明

S 為重調度方案；

S′為原調度方案；

n′為原調度方案中參與重調度的分段（稱為再調度分段）的數(shù)量；

n′′為急件分段數(shù)量；

n 為重調度分段數(shù)量，重調度分段包括再調度分

U 為重調度分段集合；

Pb為當前正在單流水線的工位1 上加工的原調度方案中的分段；

Pbf為當前正在并行流水線f 的工位1 上加工的原調度方案中的分段；

AICDi為重調度分段i 的模糊完工時間與其模糊交貨期的一致性程度[4]。

2.2 模糊調度變量

在模糊調度中，通常以三角模糊數(shù)來表述模糊加工時間和模糊完工時間，表示為，包含時間的最可能值時間的下限值和時間的上限值等3 個參數(shù)。模糊加工時間的隸屬函數(shù)表示如圖1（a）。

2.3 數(shù)學模型

圖 1 （a）模糊加工時間的隸屬函數(shù)；（b）模糊交貨期的隸屬函數(shù)；（c）滿意度Fig. 1 （a） Membership function of the triangular fuzzy processing time；（b） membership function of the trapezoidal fuzzy due date；（c） agreement index （AI）

綜上所述，平面分段單流水線反應式模糊調度以最小化模糊makespan、最大化平均AICD、最大化平均AISS′為調度目標，數(shù)學模型[5]如下：

目標函數(shù)：

3 多目標文化基因算法

文化基因算法（Memetic algorithm，MA）將基于種群的全局搜索與基于個體的局部搜索有效結合，在保持遺傳算法的全局搜索能力的同時提高了其局部搜索能力。因此，MA 被廣泛應用于求解各類優(yōu)化問題，包括生產調度[6-7]及其他工程領域的相關問題，如路徑規(guī)劃[8]、資源分配[9]以及特征選取[10]等。本文提出一種多目標Memetic 算法（Multi-objective Memetic algorithm，MOMA）以求解平面分段單流水線多目標模糊調度問題。作為多目標進化算法，M O M A基于Pareto 最優(yōu)的概念進行設計。MOMA 以特定形式的向量表達調度解，引入2 種啟發(fā)程序生成初始解，并基于解的形式設計了交叉、變異等遺傳操作和局部搜索算子。下面對MOMA 解的表達、種群初始化、遺傳操作和局部搜索等內容進行詳細描述。

3.1 解的表達

本文以一個基因串來表示平面分段單流水線多目標調度的一個解。為了反映分段在流水線上的分配情況，在包含全部待加工分段的序列中，b 中工件的序列即為工件加工順序。

3.2 遺傳操作

選擇（selection）、交叉（crossover）和變異（mutation）是3 個用于生成子代種群的遺傳操作。選擇操作采用基于非支配等級和擁擠距離的二元錦標賽方法，從父代種群中選出優(yōu)秀個體。對于非支配等級不同的2 個個體，優(yōu)先選擇非支配等級低的個體；對于非支配等級相同的2 個個體，優(yōu)先選擇擁擠距離大的個體。隨后，對選出的父代個體按概率pc進行配對交叉。交叉操作如圖2 所示。

圖 2 交叉操作示例Fig. 2 Example of the crossover operator

具體步驟如下：

步驟1令子代1 繼承父代1 的隨機一段序列，子代2 繼承父代2 的隨機一段序列。

步驟2填子代1 的空位時，從左至右掃描父代2，將子代1 中未繼承的基因（平面分段號）依次填入空位；填子代2 的空位時，從左至右掃描父代1，將子代2 中未繼承的基因（平面分段號）依次填入空位。

上述交叉操作能保留一個父代的某個子調度，同時能保留另一個父代中分段加工的相對先后關系，因此子代能較好地繼承父代的性征。上述交叉操作能產生無數(shù)對子代，實際算法操作中只需隨機產生其中的一對作為子代。

為保持種群的多樣性，對交叉操作產生的子代按概率pm實施變異操作，具體步驟如下：

步驟1隨機選擇兩位置d 和k，要求

步驟2將位置d 處的基因插入到位置k 處的基因之前。

變異操作示例見圖3。在變異前的序列中隨機選擇2 個位置，分別命名為k，d。將d 位置處的序列插入到k 處序列的前面位置，保持其他序列的先后順序不變，位置依次順延。

圖 3 變異操作示例Fig. 3 Example of mutation operator

3.3 局部搜索算子

Insert 鄰域結構能有效地構造流水車間調度問題鄰域解。MOMA 中，按概率pls對個體施加基于Insert 鄰域結構的局部搜索算子，局部搜索算子算法流程與參考文獻[11]基本一致。

3.4 算法流程

基于上述各節(jié)對MOMA 各部分內容進行的詳細描述，該算法的流程如圖4 所示。

圖 4 MOMA 流程圖Fig. 4 Flowchart of the MOMA

4 仿真試驗

因為反應式調度是在一般式調度結果的基礎上進行運算的，本研究收集到上海某船廠平面分段生產信息，計算單流水線的靜態(tài)調度結果。假設在0 時刻開始生產，且在1 800 min 時接到急件任務如表1 所示，利用上文所述的MOMA 算法制定重調度方案。

因為MOMA 算法是智能優(yōu)化算法，運算結果具有一定的隨機性，因此本研究通過多次計算，生成多組計算方案，并利用AHP 法對多組調度方案進行選擇，確定最終方案。利用MOMA 算法對重調度任務獨立求解10 次，然后對求得的10 組結果進行整合，剔除支配解，形成新的解集合。采用AHP 發(fā)在新的非支配解集中選取重調度方案，輸入AHP 法的目標權重矩陣，計算出3 個目標對應的權重為[0.5499，0.2402，0.2098]，選擇出對應的調度方案為17→18→23→19→1→20→24→14→13→6→9→21→22→2→7，3 個目標值對應為[8960，0.6382，0.7377]。

表 1 急件任務模糊化加工信息Tab. 1 Expedited task fuzzy processing information

運用滿意度的定義計算本算例的滿意度為0.680 77，以AICD 代替目標滿意度，計算其相對誤差為6.67%。最大完工時間makespan 仿真結果為8 757，相對誤差為2.27%。仿真得到的目標值與調度方案計劃的目標值的相對偏差保持在較小的范圍內，因此可認為求得的模糊調度方案能保證較高的可靠性。對調度方案進行仿真，繪制出仿真甘特圖如圖5 所示，反映了調度方案仿真執(zhí)行的進程狀態(tài)，為船舶平面分段流水線反應式調度問題提供決策支持。

圖 5 重調度方案仿真甘特圖Fig. 5 Rescheduling scheme simulation Gantt chart

5 結 語

本文研究了船舶平面分段單流水線反應式模糊調度，面對急件任務的工況提出單流水線模糊調度的數(shù)學模型。通過設計一種多目標文化基因算法MOMA，對船舶平面分段模糊化加工信息數(shù)據(jù)進行計算。目標值與調度方案計劃的目標值的相對偏差保持在較小的范圍內，通過甘特圖仿真分段加工過程，為船舶平面分段單流水線反應式調度問題提供決策支持。