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

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

1，2*，‘，1，1，1，3(1.海洋石油工程股份有限公司，天津 300461；2.哈爾濱工程大學 船舶工程學院，哈爾濱150001;3.哈爾濱工程大學機電工程學院，哈爾濱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 個工件，每個工件的加工均有 m 個階段：在第1個階段， m 臺同型機中的任一臺均可以加工這些工件；任意2個階段之間的緩沖區(qū)大小是無限的。如果目標函數(shù)是時間表長度，問題可表示為 FFm∣|C_max ；如果目標函數(shù)是總完工時間，則該問題可表示為 。

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

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

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

1.1 參數(shù)說明

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

1.2 模型建立

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

1.2.1 甲板板

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

1.2.2 型材及其他板件

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

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

，工件 i 在階段 k 的機器 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)度性能指標，即本文的適應度函數(shù)；式(2)代表整個加工任務的總完工時間大于等于在最后階段任意工件的加工完成時間；式(3)和式(4)是2個變量的0\\~1變量約束；式（5）是任意工件在任意階段的加工完成時間表達式；式(6)代表每個工件在任意階段均只能在該階段的一臺機器上加工；式(7）代表任意工件需完成上一階段的加工才能開始下一階段的加工；式(8)和式(9)代表一臺機器在同一時刻只能加工一個工件。

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

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

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

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

2.1 算法選取

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

2.2 編碼解碼方式

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

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

并行機數(shù)。

2.3 算法改進

2.3.1 種群初始化

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

2.3.2 選擇操作

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

2.3.3 交叉操作

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

步驟1：個體選擇。在個體不可重復選擇的前提下，隨機選擇2個個體。

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

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

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

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

2.3.4 變異操作

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

步驟1：對種群每個個體的變異概率進行隨機賦值，取值范圍[0，1];

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

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

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

值得注意的是，為了確保每一代產(chǎn)生的最優(yōu)個體不會因為變異而流失，在此，無論種群中最優(yōu)個體是否被執(zhí)行變異操作，都需將選擇后標注的最優(yōu)個體重新賦值到變異后種群的對應序位。

2.3.5 算法終止準則

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

3 實例驗證與對比

3.1 驗證實例參數(shù)

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

3.2改進遺傳算法編排計劃

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

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

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

3.3單層片體裝焊計劃制定

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

板片體構(gòu)件裝焊網(wǎng)絡圖，以及構(gòu)件的標準裝焊時間排出裝焊計劃。

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

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

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

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

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

4結(jié)論

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