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

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

0 引 言

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

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

1 問(wèn)題描述

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

問(wèn)題假設(shè)：對(duì)于所有重調(diào)度分段，均可在啟動(dòng)反應(yīng)式調(diào)度時(shí)投入生產(chǎn)；加工過(guò)程中各工位持續(xù)可用；分段在各工位進(jìn)行加工時(shí)不可中斷；分段在各工位的加工時(shí)間及其交貨時(shí)間模糊；分段在各工位上加工前的準(zhǔn)備時(shí)間包含于加工時(shí)間；在建分段在各工位間的輸送時(shí)間不計(jì)。

2 數(shù)學(xué)模型

基于以上描述與假設(shè)，建立平面分段單流水線反應(yīng)式模糊調(diào)度問(wèn)題的數(shù)學(xué)模型。

2.1 符號(hào)說(shuō)明

S 為重調(diào)度方案；

S′為原調(diào)度方案；

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

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

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

U 為重調(diào)度分段集合；

Pb為當(dāng)前正在單流水線的工位1 上加工的原調(diào)度方案中的分段；

Pbf為當(dāng)前正在并行流水線f 的工位1 上加工的原調(diào)度方案中的分段；

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

2.2 模糊調(diào)度變量

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

2.3 數(shù)學(xué)模型

圖 1 （a）模糊加工時(shí)間的隸屬函數(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）

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

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

3 多目標(biāo)文化基因算法

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

3.1 解的表達(dá)

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

3.2 遺傳操作

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

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

具體步驟如下：

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

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

上述交叉操作能保留一個(gè)父代的某個(gè)子調(diào)度，同時(shí)能保留另一個(gè)父代中分段加工的相對(duì)先后關(guān)系，因此子代能較好地繼承父代的性征。上述交叉操作能產(chǎn)生無(wú)數(shù)對(duì)子代，實(shí)際算法操作中只需隨機(jī)產(chǎn)生其中的一對(duì)作為子代。

為保持種群的多樣性，對(duì)交叉操作產(chǎn)生的子代按概率pm實(shí)施變異操作，具體步驟如下：

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

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

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

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

3.3 局部搜索算子

Insert 鄰域結(jié)構(gòu)能有效地構(gòu)造流水車間調(diào)度問(wèn)題鄰域解。MOMA 中，按概率pls對(duì)個(gè)體施加基于Insert 鄰域結(jié)構(gòu)的局部搜索算子，局部搜索算子算法流程與參考文獻(xiàn)[11]基本一致。

3.4 算法流程

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

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

4 仿真試驗(yàn)

因?yàn)榉磻?yīng)式調(diào)度是在一般式調(diào)度結(jié)果的基礎(chǔ)上進(jìn)行運(yùn)算的，本研究收集到上海某船廠平面分段生產(chǎn)信息，計(jì)算單流水線的靜態(tài)調(diào)度結(jié)果。假設(shè)在0 時(shí)刻開(kāi)始生產(chǎn)，且在1 800 min 時(shí)接到急件任務(wù)如表1 所示，利用上文所述的MOMA 算法制定重調(diào)度方案。

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

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

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

圖 5 重調(diào)度方案仿真甘特圖Fig. 5 Rescheduling scheme simulation Gantt chart

5 結(jié) 語(yǔ)

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