海洋平臺組塊甲板片體生產(chǎn)線協(xié)同調(diào)度方法

中圖分類號：TP18 文獻(xiàn)標(biāo)志碼：A 文章編號：2095-2945(2025)14-0021-06

1，2*，‘，1，1，1，3(1.海洋石油工程股份有限公司，天津 300461；2.哈爾濱工程大學(xué) 船舶工程學(xué)院，哈爾濱150001;3.哈爾濱工程大學(xué)機(jī)電工程學(xué)院，哈爾濱150001）

Abstract:Flexibleassemblylineproductionisacommonproductionorganizationmethod，andthecolaborativescheduling technologyisstudiedacordingtothespecificneedsofcollborativeschedulingofdeckandsheetmixedproductionlineandthe applicationofinteligentrealizationtechnologyofdeckandsheetproductionline.Thecollborativeschedulingmodelofthedeck sheetproductionlinewasestablishedfromthreeaspects:therelevantparametersoftheproduction line，theoptimizationobjective function，theproductionconstraintsandtheassumptions.Inthispaper，animprovedgeneticalgorithmisproposedtosolvethe problem，whichadoptsamulti-layercodingmethodtoensurepopulationdiversityandavoidtheprecociousmaturityofthe algorithm.Asingle-objectiveimprovementalgorithmisdesignedtominimizethemaximumcompletiontimetoreducetheamount ofcomputation.Throughexamplesimulationexperiments，theefectivenessandsuperiorityofthealgorithmareverifedby comparingwiththetraditionalmanualorchestration.Finallthestandardproductionprocessinformationisusedtopreparethe assembly and welding plan.

Keywords:colaborativeschedule；geneticalgorithm；orchestratetheplan；weldingplan；flexibleassemblylineworkshop scheduling

柔性流水車間調(diào)度問題（Flexible Flow ShopSchedulingProblem，F(xiàn)FSP）自提出以來已經(jīng)得到了廣泛而深入的研究。柔性流水作業(yè)問題中，工廠生產(chǎn)n 個(gè)工件，每個(gè)工件的加工均有 m 個(gè)階段：在第1個(gè)階段， m 臺同型機(jī)中的任一臺均可以加工這些工件；任意2個(gè)階段之間的緩沖區(qū)大小是無限的。如果目標(biāo)函數(shù)是時(shí)間表長度，問題可表示為 FFm∣|C_max ；如果目標(biāo)函數(shù)是總完工時(shí)間，則該問題可表示為 。

Johnson給出了問題 F2||C_maxF2|| 的最優(yōu)解，即著名的SPT(1)-LPT(2)規(guī)則。由于問題 Fm||C_maxFm|| 的重要性，研究人員進(jìn)一步設(shè)計(jì)了多個(gè)求解該問題的啟發(fā)式算法，Liu等提出了一種新的啟發(fā)式方法，將偏度用于構(gòu)建新的工作差異化優(yōu)先級規(guī)則，并開發(fā)了一種基于時(shí)間表的平局打破規(guī)則。車間流水線調(diào)度智能算法由于對自標(biāo)函數(shù)要求不高、適應(yīng)能力強(qiáng)等優(yōu)點(diǎn)受到研究者的青睞[4-8]。彭菁等針對有限緩沖區(qū)批量流水車間分批調(diào)度問題，綜合考慮提前懲罰和延期懲罰為目標(biāo)建立模型并改進(jìn)標(biāo)準(zhǔn)布谷鳥算法求解。李健等[為提高柔性作業(yè)車間調(diào)度效率，構(gòu)建一種具有柔性作業(yè)車間調(diào)度問題約束條件的馬爾科夫決策過程，針對工件與機(jī)器的同時(shí)選擇問題，提出一種協(xié)同智能體強(qiáng)化學(xué)習(xí)方法進(jìn)行求解。而基于MAS（Multi-Agent Sys-tem)方法的車間調(diào)度是DAI在生產(chǎn)制造領(lǐng)域的一個(gè)重要應(yīng)用。魏鑫針對傳統(tǒng)MAS方法建模時(shí)存在的貪婪性和單目標(biāo)優(yōu)化的不足，提出一種基于改進(jìn)合同網(wǎng)協(xié)議的區(qū)間協(xié)同拍賣動態(tài)調(diào)度算法，對改進(jìn)模型中的個(gè)體Agent間的優(yōu)化行為進(jìn)行協(xié)調(diào)。楊博見等[2為提高調(diào)度策略對工件到達(dá)密度變化的適應(yīng)能力，構(gòu)建了基于多Agent系統(tǒng)的柔性制造動態(tài)調(diào)度系統(tǒng)。

本文研究甲板片體生產(chǎn)線柔性流水作業(yè)問題，制定甲板片體預(yù)制過程中各種構(gòu)件加工計(jì)劃和各種構(gòu)件裝焊計(jì)劃。在構(gòu)件加工計(jì)劃制定方面，提出了一種基于改進(jìn)遺傳算法的生產(chǎn)線協(xié)同調(diào)度算法，并采用實(shí)例參數(shù)，驗(yàn)證本文算法的有效性和優(yōu)越性。在構(gòu)件裝焊計(jì)劃制定方面，根據(jù)標(biāo)準(zhǔn)生產(chǎn)過程信息，利用計(jì)算機(jī)模擬編制裝焊計(jì)劃，便于后續(xù)展開精細(xì)排產(chǎn)工作。

1甲板片體生產(chǎn)線協(xié)同調(diào)度方法

1.1 參數(shù)說明

甲板片生產(chǎn)調(diào)度問題涉及3個(gè)有限集合。 ① 集合 ：表示 m 臺機(jī)器的集合。機(jī)器集合 M 中有 m 臺機(jī)器，工件 j 有多個(gè)加工工序的稱為多工序機(jī)。 ② 集合 ：表示 n 個(gè)工件的集合，這些工件需要在這 m 臺機(jī)器上加工。如果工件 j 需要多次在機(jī)器上加工，則用 (i，j) 表示一個(gè)工件 j 在機(jī)器 i 上的加工，稱為工序 (i，j) 。一個(gè)工件的所有工序均加工完成，則認(rèn)為該工件的加工完成。工件集合 J 中的每個(gè)工件，需要一系列參數(shù)來描述，其中加工時(shí)間，即工件 j 的工序 (i，j) 在機(jī)器 i 上加工所需的時(shí)間，用 P_ij 表示；就緒時(shí)間，即工件可以開始加工的時(shí)間，可以用 r_j 表示，如果所有的工件都同時(shí)就緒，可以認(rèn)為 r_j=0 ；交貨期 d_j 指工件 j 的加工應(yīng)該結(jié)束的時(shí)間。 ③ 集合 ：表示 s 種資源的集合，機(jī)器在加工過程中需要其中的若干種資源。在資源足夠的情況下，可以忽略該集合（及其約束），但在實(shí)際生產(chǎn)過程中，該集合一般不可忽略。

1.2 模型建立

將甲板板、型材、小尺寸板3種構(gòu)件生產(chǎn)問題相結(jié)合可以得到甲板片體生產(chǎn)協(xié)同調(diào)度的基本模型。其中甲板片體通常具有較大的空間尺度，因此將其與其他2種構(gòu)件混合生產(chǎn)顯然是不符合實(shí)際的，可以將甲板片體和其余2種構(gòu)件分別考慮、分別建立模型。

1.2.1 甲板板

分別考慮同類型的構(gòu)件制造過程，甲板板只有2個(gè)制造階段(2個(gè)工序)，由于其尺寸較大，可以假設(shè)每個(gè)階段只有一臺機(jī)器進(jìn)行操作，于是該問題變?yōu)?F2||C_max 問題。對于該問題，根據(jù) $\\operatorname { S P T } ( 1 ) \\Ebot \\operatorname { P T } ( 2 )$ 規(guī)則，其算法實(shí)現(xiàn)為：首先設(shè)問題的 n 個(gè)工件是 1，2，?，n ，構(gòu)造集合： 和 ;接著，將 X 中的工件按 p_1j 的非遞減次序排列，得到有序集合 X^* ；將 Y 中的工件按 p_2j 的非遞增次序排列，得到有序集合 Y^* ；最后，將集合 X^* 和 Y^* 合并得到有序集合 [X^*，Y^*] ，即為問題的最優(yōu)時(shí)間表。

1.2.2 型材及其他板件

由于上述 SPT(1)-LPT(2) 規(guī)則無法應(yīng)用到具有2個(gè)以上生產(chǎn)階段的排序與調(diào)度，因此二者可合并為柔性流水車間調(diào)度問題。注意到型材有5個(gè)生產(chǎn)階段，小尺寸板有4個(gè)主要生產(chǎn)階段，為了便于建立統(tǒng)一的模型，可以手動為小尺寸板增加一個(gè)虛擬的理料階段，但所有零件在此階段的制造用時(shí)為0或1的極小值。因此可以建立如下柔性流水車間調(diào)度模型

C_max>C_is，i=1，2，^?，n，

，工件 i 在階段 k 的機(jī)器 j 上加工，其他

，工件 i₁ 在階段 k 上先于 i₂ 加工，其他

C_ik=S_ik+P_ik，i=1，?，n;k=1，?，s，

S_i(k+1)-S_ik>P_ik，i=1，?，n;k=1，?，s，

Y_ki1i2+Y_ki2i1?1，i=1，?，n;k=1，?，s，

S_i1k-C_i2k+L×(3-Y_ki2i1-X_i1kj-X_i2kj)≥0，

式中： L 為一足夠大的常數(shù)。式(1)是調(diào)度性能指標(biāo)，即本文的適應(yīng)度函數(shù)；式(2)代表整個(gè)加工任務(wù)的總完工時(shí)間大于等于在最后階段任意工件的加工完成時(shí)間；式(3)和式(4)是2個(gè)變量的0\\~1變量約束；式（5）是任意工件在任意階段的加工完成時(shí)間表達(dá)式；式(6)代表每個(gè)工件在任意階段均只能在該階段的一臺機(jī)器上加工；式(7）代表任意工件需完成上一階段的加工才能開始下一階段的加工；式(8)和式(9)代表一臺機(jī)器在同一時(shí)刻只能加工一個(gè)工件。

1.2.3 甲板片體生產(chǎn)線優(yōu)化目標(biāo)函數(shù)

對于中間產(chǎn)品制造環(huán)節(jié)和裝焊工位吊裝作業(yè)環(huán)節(jié)，最小化最大完工時(shí)間作為優(yōu)化自標(biāo)函數(shù)均有利于

模型求解，因此目標(biāo)函數(shù) 。

2基于改進(jìn)遺傳算法的生產(chǎn)線協(xié)同調(diào)度方法

2.1 算法選取

本文設(shè)計(jì)了一種采用多層編碼方式的改進(jìn)遺傳算法，改進(jìn)遺傳算法進(jìn)化部分基本流程是：交叉一合并一選擇一變異。其整體流程如圖1所示。

2.2 編碼解碼方式

引入矩陣編碼的概念，設(shè)計(jì)適用于生產(chǎn)車間調(diào)度問題的矩陣元素編碼方式。其中，矩陣行表示工件編號，列表示加工設(shè)備，用矩陣元素是否為空來表示工件是否在某一設(shè)備上加工，矩陣元素大小表示其在該設(shè)備上的加工順位。對于有 n 個(gè)待加工工件，每個(gè)產(chǎn)品均需依次流經(jīng) m 道工序，且每道工序上存在 M_j(j= 1，2，?，m) 臺并行機(jī)的FFSP問題，構(gòu)造的 n×m 維編碼矩陣為

式中：初始化種群 中的元素 x_ij 用隨機(jī)生成的實(shí)數(shù)表示。其中 x_ij 的取值范圍： M_e]，i=1，2，?，n，j=1，2，?，mM_e 表示第 e 道工序的

并行機(jī)數(shù)。

2.3 算法改進(jìn)

2.3.1 種群初始化

對于初始化種群 中的元素 x_ij ，整數(shù)部分表示工件選擇的機(jī)臺號，小數(shù)部分表示對應(yīng)機(jī)臺上待加工工件的加工順序。因此，產(chǎn)品 i 的第 j 道工序在第Int(x_ij) 號機(jī)臺上加工。當(dāng) i≠k 時(shí)，易存在 Int(x_ij)=Int 的現(xiàn)象，即在工序 j 上工件 ∴k 選擇同一機(jī)臺加工。對于選擇同一機(jī)臺加工的工件，在第一道工序按照 x_i1 的升序依次加工。在非第一道工序，則根據(jù)各個(gè)工件在上一道工序的完工時(shí)間確定加工順序，基本規(guī)則是：本道工序在同一機(jī)臺上加工的工件，按在上一道工序完工時(shí)間的先后順序依次進(jìn)行加工；若完工時(shí)間相同，則按照 x_ij 的升序依次加工。這里不再將編碼矩陣展開成一串元素生成對應(yīng)的染色體，而是將每個(gè)編碼矩陣看作一個(gè)染色體，即調(diào)度問題的一個(gè)可行解。

2.3.2 選擇操作

將初始種群與交叉產(chǎn)生的新種群進(jìn)行合并，生成規(guī)模數(shù)為 2N 的新種群。本文提出的選擇操作是對種群中每2個(gè)鄰域個(gè)體的適應(yīng)度值進(jìn)行比較，適應(yīng)度低的個(gè)體直接被淘汰，適應(yīng)度高的個(gè)體被選擇并成為下一次迭代的父代個(gè)體。對于 2N 規(guī)模種群依次進(jìn)行選擇操作，每次操作包括了 N 次數(shù)據(jù)比較過程。將選擇得到的優(yōu)秀個(gè)體存儲到下一次迭代的父代種群中，并標(biāo)注種群的最優(yōu)個(gè)體。

2.3.3 交叉操作

改進(jìn)算法首先隨機(jī)生成規(guī)模為 N 的初始種群，再對初始種群中的個(gè)體執(zhí)行基于矩陣行列的交叉操作。交叉操作的具體步驟如下。

步驟1：個(gè)體選擇。在個(gè)體不可重復(fù)選擇的前提下，隨機(jī)選擇2個(gè)個(gè)體。

步驟2：交叉方式選擇。隨機(jī)分配個(gè)體交叉方式，該操作有行交叉和列交叉2種交叉方式。

步驟3：交叉位置。選擇行交叉，交叉位置可在[1，n-1 范圍任意位置；選擇列交叉，交叉位置可在[1， m- 1]范圍任意位置。

步驟4：交叉操作。對2個(gè)個(gè)體在交叉位置后面的行列進(jìn)行互換，組合生成2個(gè)新的個(gè)體。

步驟5：生成新種群。將個(gè)體交叉后生成的新個(gè)體存儲到新種群中。

2.3.4 變異操作

本文采用以一定概率對染色體隨機(jī)指定某一位或某幾位基因進(jìn)行變異的方法，具體操作步驟如下。

步驟1：對種群每個(gè)個(gè)體的變異概率進(jìn)行隨機(jī)賦值，取值范圍[0，1];

步驟2：對于某個(gè)個(gè)體，若隨機(jī)生成的變異概率小于變異參數(shù) P_m ，則對該個(gè)體依次執(zhí)行步驟3、步驟4操作，反之結(jié)束該變異過程；

步驟3：隨機(jī)生成個(gè)體變異點(diǎn)的數(shù)量及每個(gè)變異點(diǎn)的位置ixj。ij表示矩陣的第 i 行第 j 列。變異個(gè)體的變異點(diǎn)數(shù)量較小，通常為1或2；

步驟4：對個(gè)體變異點(diǎn)進(jìn)行隨機(jī)賦值，新值是該工序可選擇的并行機(jī)號范圍內(nèi)任意實(shí)數(shù)，但不可與變異前的值相同。

值得注意的是，為了確保每一代產(chǎn)生的最優(yōu)個(gè)體不會因?yàn)樽儺惗魇В诖耍瑹o論種群中最優(yōu)個(gè)體是否被執(zhí)行變異操作，都需將選擇后標(biāo)注的最優(yōu)個(gè)體重新賦值到變異后種群的對應(yīng)序位。

2.3.5 算法終止準(zhǔn)則

通常生產(chǎn)車間調(diào)度問題是目標(biāo)函數(shù)的最大、最小值問題，因而不適合采用解集區(qū)間的方法來判定算法是否收斂。這里提出的改進(jìn)方法需要設(shè)定2個(gè)參數(shù)：最大迭代次數(shù)MF，自標(biāo)函數(shù)值不改進(jìn)情況下的最大迭代次數(shù) s 若算法滿足以下任何一個(gè)條件： ① 算法迭代次數(shù)大于MF； ② 在最大迭代次數(shù)范圍內(nèi)，最優(yōu)個(gè)體的目標(biāo)函數(shù)值在 s 次連續(xù)迭代過程中沒有得到任何改進(jìn)，則算法終正。

3 實(shí)例驗(yàn)證與對比

3.1 驗(yàn)證實(shí)例參數(shù)

對甲板片體生產(chǎn)線進(jìn)行協(xié)同調(diào)度的前提是獲取甲板片體生產(chǎn)過程中的相關(guān)產(chǎn)線參數(shù)、機(jī)器參數(shù)、工件信息。現(xiàn)假設(shè)生產(chǎn)一定數(shù)量的H型鋼用于仿真實(shí)驗(yàn)，其具體的加工需求及機(jī)器信息見表1。除H型鋼外，還需要生產(chǎn)一定數(shù)量的筋板、插入板、環(huán)板等板材，與H型鋼不同的是，板材通常以一整塊鋼板為單位進(jìn)行處理。因此，現(xiàn)同樣假設(shè)有一批板材要進(jìn)行處理，且從同一塊板材切割出的板件歷經(jīng)同樣的工序進(jìn)行處理，其生產(chǎn)需求信息見表2。其中，“處理路線\"表示對來自同一塊原材料鋼板的所有構(gòu)件的處理方式，不同的處理方式對應(yīng)不同的處理時(shí)間。

3.2改進(jìn)遺傳算法編排計(jì)劃

分別用改進(jìn)遺傳算法和傳統(tǒng)人工2種方式編排這批構(gòu)件的生產(chǎn)計(jì)劃，改進(jìn)遺傳算法主要參數(shù)設(shè)置為種群規(guī)模80，算法迭代次數(shù)為200，最大迭代次數(shù)為500，變異概率為0.2，結(jié)果如圖2(a）所示，可以看出算法調(diào)度的結(jié)果為 745min 。

在傳統(tǒng)人工調(diào)度中，工人在對構(gòu)件生產(chǎn)過程進(jìn)行安排時(shí)，通常會觀察某個(gè)工序中是否有機(jī)器出現(xiàn)空閑，如果有機(jī)器空閑，則把構(gòu)件放到該機(jī)器上進(jìn)行生產(chǎn)，如此循環(huán)往復(fù)，直到所有構(gòu)件在該工序處理完畢。下面在同樣的生產(chǎn)任務(wù)下，用計(jì)算機(jī)對這種方法進(jìn)行模擬，結(jié)果如圖2(b)所示，可以看出人工調(diào)度的結(jié)果為 771min 。

由圖2(a）和圖2(b)結(jié)果可以看出，在相同條件下，利用改進(jìn)遺傳算法對構(gòu)件生產(chǎn)過程進(jìn)行調(diào)度，可以將整個(gè)生產(chǎn)流程的總時(shí)間縮短 26min ，提高了生產(chǎn)效率。

3.3單層片體裝焊計(jì)劃制定

傳統(tǒng)的甲板片體裝焊過程無法形成相應(yīng)的文件材料（如裝焊網(wǎng)絡(luò)圖或順序表），同時(shí)也沒有相應(yīng)的裝焊計(jì)劃，不利于展開精細(xì)化的派工。因此需要結(jié)合甲

板片體構(gòu)件裝焊網(wǎng)絡(luò)圖，以及構(gòu)件的標(biāo)準(zhǔn)裝焊時(shí)間排出裝焊計(jì)劃。

3.3.1 構(gòu)件裝焊順序

在協(xié)同調(diào)度軟件中，繪制裝焊網(wǎng)絡(luò)圖的前提是已知甲板片體各個(gè)構(gòu)件的裝焊順序，包括各個(gè)構(gòu)件焊接任務(wù)的前后及并行關(guān)系。圖3以一個(gè)虛擬的甲板片體為例，說明構(gòu)件裝焊計(jì)劃的制定過程。該甲板片體共包含104個(gè)構(gòu)件，各個(gè)構(gòu)件的編號已經(jīng)用帶圈數(shù)字標(biāo)出。

3.3.2 構(gòu)件裝焊計(jì)劃

在實(shí)際生產(chǎn)過程中，資源（如焊機(jī)、工人），場地（如存在干涉的情況）等存在一定的限制，所以接下來需要從生產(chǎn)執(zhí)行系統(tǒng)中獲取各個(gè)構(gòu)件的標(biāo)準(zhǔn)裝焊時(shí)間信息，以及場地資源信息，進(jìn)行計(jì)劃編制。現(xiàn)在假設(shè)有主梁和次梁焊機(jī)各2臺，各個(gè)構(gòu)件的標(biāo)準(zhǔn)裝焊時(shí)間見表3。

在生產(chǎn)過程中，若提供該片體的建造工期約束以及完工截止時(shí)間，就可以獲得片體的開工時(shí)間。在此基礎(chǔ)上，利用構(gòu)件的標(biāo)準(zhǔn)裝焊時(shí)間和機(jī)器調(diào)試移動等時(shí)間就可以獲取到甲板片體裝焊過程的初步計(jì)劃，進(jìn)一步，添加假期、法定節(jié)假日等停工時(shí)間并增加一定時(shí)間裕度即可編制出該片體的裝焊計(jì)劃，以便用于后續(xù)排產(chǎn)。圖4所示為只考慮到構(gòu)件標(biāo)準(zhǔn)裝焊時(shí)間的片體裝焊計(jì)劃甘特圖，橫軸表示時(shí)間，單位為小時(shí)，縱軸表示機(jī)器編號。

4結(jié)論

本文設(shè)計(jì)了一種改進(jìn)遺傳算法求解甲板片體生產(chǎn)線協(xié)同調(diào)度問題，采用多層編碼方式，改進(jìn)選擇、交叉、變異算子，有效增強(qiáng)算法的全局搜索能力、改善種群的多樣性和優(yōu)質(zhì)性，避免算法早熟。利用計(jì)算機(jī)模擬人工調(diào)度過程，將兩者調(diào)度結(jié)果進(jìn)行對比，體現(xiàn)算