智能制造焊接車間協同作業調度優化

周 珂，呂 民，夏自祥，李小冬

（1.濟寧學院機械工程系，山東 曲阜 273155；2.哈爾濱工業大學機電工程學院，黑龍江 哈爾濱 150001）

1 引言

隨著制造業不斷向智能制造邁進，產品的定制化屬性更加明顯。為了適應定制化生產、提高生產柔性，工業機器人、加工機床、自動化生產線等在發揮自身優勢基礎上協同作業。在焊接車間，機器人焊接、人工焊接等方式并存，部分工序可以由多種方式完成，有些工序可以同時由多臺設備和人員協同作業。隨著定制化產品的增多，生產過程柔性提高，如何合理有效的進行協同作業焊接調度成為智能制造中亟待解決的問題。

柔性作業車間調度問題是車間調度問題的擴展，其中加工工序存在至少一臺可供選擇的設備，不同設備完成該工序的時間存在不同[1]，國內外專家學者利用加工分段、瓶頸分區、設備聚類、合理緩沖等方法，建立了相應的調度模型并加以求解[2-4]。遺傳算法[5-6]、差分進化算法[7-10]在調度問題求解中有通用性較強、魯棒性良好等優勢，但在求解協同作業調度問題中易出現干擾方案，須對解碼不可行的干擾方案及時修正。

針對智能制造焊接車間中協同作業調度問題，利用部分焊接設備可移動協同作業的屬性，建立數學模型，以最小化最大完工時間和焊接能耗為目標開展調度優化研究。

2 可協同作業焊接調度問題描述

焊接車間內協同作業指的是不同焊接設備同時對同一焊接件進行焊接，協同作業可以縮短產品工期，加快定制化產品上市。焊接作業用時包括等待時間、運輸時間、焊接前的裝配時間、焊接預熱時間、焊接時間、熱處理時間、檢驗及補焊時間、焊接件拆卸時間等，使用不同設備、操作人員不同會導致焊接用時不同。

為建立焊接調度問題數學模型，定義基本變量，如表1 所示。

表1 變量及說明Tab.1 Variable and Description

協同作業焊接車間調度問題可描述為：存在N個待加工焊接件臺焊接設備焊接件Wi（i=1，2，…，N）在焊接車間的加工由Ni個焊接工序Pi1，Pi2，…，PiNi組成，焊接工序Pij可在中任何一臺焊接設備上完成（K為能夠完成工序Pij的設備總數），焊接工序Pi（j-1）至工序Pij的運輸時間為TTij，焊接工序Pij的加工等待時間為TLij，焊接工序Pij加工前的裝配時間為TAij，焊接工序Pij預熱時間為TPij，使用設備Ml時工序Pij所需的焊接時間為TWijt，焊接工序Pij焊接熱處理時間為THij，焊接工序Pij檢驗時間為TEij，焊接工序Pij補焊時間為TWPij，焊接工序Pij加工結束的拆卸時間為TDij。設備Ml單位時間能耗為ECl。焊接件Wi（i=1，2，…，N）的工序須符合工藝路徑要求，即Pi1→Pi2→…→PiJ。另外，焊接件在滿足工藝要求且設備可移動的條件下，可以同時進行若干工序，但焊接設備同一時刻只能有一個焊接件在加工，即：焊接過程須滿足不可中斷約束、焊接件唯一性約束。

（1）焊接件Wi（i=1，2，…，N）的焊接工序Pij，可在預先給定的焊機或機器人的任一臺設備上加工，且?Pij，使

（2）每個焊接件Wi（i=1，2，…，N）的工序須符合工藝路徑要求，即Pi1→Pi2→…→PiJ。

（3）焊接件的工藝路徑多樣（不同焊接件的工藝路徑可不同），即?Wk，Wj（k≠j），l，使得Mkl≠Mjl。

3 面向協同作業的焊接調度數學模型

求解焊接調度問題即是在滿足工期和焊接工序約束條件下，確定焊接件的每道工序的焊接方式、作業設備，并依次安排加工順序，以達到最小化最大完工時間Tmax和焊接能耗EC的目的。

式中：Ti—第i個焊接件的完工時間；TWl—第l臺焊接設備Ml的焊接時間；TWPl—第l臺焊接設備Ml的補焊時間。

這里的調度優化目標是完工時間短、焊接能耗低，目標函數為：

在該調度問題中，存在兩個決策過程：（1）將焊接件Wi（i=1，2，…，N）的工序Pij（i=1，2，…，N；j=1，2，…，Ni），分配給具備加工該焊接工序能力的設備，即中的某臺焊接設備進行加工；（2）確定焊接設備Ml（l=1，2，…，L）上相應焊接工序Pij的加工順序。

4 改進的差分算法設計

4.1 算法流程

智能制造環境下的柔性焊接調度問題屬于多目標優化問題，這類問題被證明是NP 難題。智能優化算法在求解這類問題中有結構較簡單、算法較易于實現、收斂較快速、魯棒性較強等優勢，差分進化算法屬于其中一種。差分算法采用實數編碼，通過父代向量差分矢量擾動產生新個體，并將評判更優良的個體納入種群完成迭代更新，逐漸得到所求問題的最優解。但是傳統差分進化算法在求解焊接調度優化問題時易陷入局部最優解，針對該問題求解在利用差分矢量求實驗個體方面按照工藝要求進行了修正，改進的差分算法流程，如圖1 所示。

算法流程如下：

（1）初始化算法參數，定義種群規模M，進化代數g=0。

（2）基于負載均衡生成初始種群，種群內包括M個個體，每個個體由n維向量組成，Xi（0）=（Xi，1（0），Xi，2（0），Xi，3（0），…，Xi，n（0）），i=1，2，…，M。

（3）計算種群個體適應度值h（Xi）。

（4）判斷是否滿足終止條件，若滿足則輸出結果，若不滿足則執行（5）。

（5）選擇兩個父代個體，生成差分矢量Xp1（g）-Xp2（g）。

（6）選擇另一個體Xp3（g），與縮放的差分矢量求和生成實驗個體Hi（g）。

（7）解碼實驗個體Hi（g），判斷是否為可行解，即是否為可行調度方案。若方案可行，則進入（9）；若方案不可行，則進入步驟8進行實驗個體修正。

（8）修正不可行方案的實驗個體Hi（g），主要包括：對超出設備編號的焊接設備子串進行修正，對取值不在工藝要求范圍內的設備編號進行修正，對取值超出設備能力的工序編號進行修正。

（9）父代個體與實驗個體Hi（g）交叉生成新個體Vi（g）。

（10）基于適應度選擇個體。

（11）進化代數加 1，返回（3）。

圖1 改進的差分進化算法流程Fig.1 Improved Differential Evolution Algorithm Flow

4.2 算法設計

（1）編碼采用MSOS 編碼法對焊接調度進行編碼，所有種群都采用整數編碼，編碼為兩條子串，焊接設備串和焊接工序串。焊接設備串解決焊接工藝路徑問題，焊接工序串解決工序排序問題。在解碼時任意一個由MSOS 編碼所生成的染色體總是可以解碼成一套可行的焊接方案。此外，MSOS 編碼中的兩條子串分別代表設備及工序排序含義，反映焊接環節各工序所在設備和加工順序，且在編碼階段采用相互獨立的編碼方法，因此，可以使用符合各自特征的交叉和變異算子，分別對兩條子串進行操作。

（2）群體初始化根據負載均衡的原則生成初始種群：對于焊接設備子串，按照工序工藝要求以均衡負載的原則進行排列生成初始子串；對于焊接工序順序子串，依據焊接件的交貨期進行升序排列生成初始子串Xi（0）=（Xi，1（0），Xi，2（0），Xi，3（0），…，Xi，n（0）），i=1，2，…，M。

（3）適應度值為便于觀察，采用目標函數值的倒數并擴大100倍作為適應度值。

（4）變異隨機選擇兩個父代個體生成差分矢量Xp1（g）-Xp2（g）。選擇另一個體Xp3（g），與縮放的差分矢量求和生成實驗個體Hi（g）。

式中：F—縮放因子，一般取值范圍［0，2］。

根據智能制造焊接車間調度問題特點，設計自適應差分縮放因子，如式（7）所示。其中Fu、Fl為邊界值。

對于焊接車間調度問題，直接采用父代個體生成的差分矢量進行縮放生成實驗個體，可能會得到不可行解，即解碼后不能得到可實施的焊接調度方案。首先進行解碼檢測判斷：焊接設備子串中設備是否超出設備編號，焊接設備子串解碼是否承擔了不具備加工能力的工序等。然后，根據焊接設備臺數和工藝要求對得到的不可行解進行修正，修正后的實驗個體再進入交叉操作。

（5）交叉父代個體與實驗個體交叉產生新的個體。對于焊接設備子串，在與同一類型焊接設備組內任兩臺設備所對應的工序集中分別選擇一個工序，對應交叉。對于焊接工序子串，采用交換位置變異算子。隨機選擇任一焊接工序，在可行設備對應序列內隨機選擇兩個不同的變異點，交換兩個變異點的焊接順序。

（6）基于適應度選擇個體分別計算新個體和父代個體的適應度值，將適應度值高的個體選擇保留下來。

5 實例驗證及分析

表2 部分工序與加工要求Tab.2 Partial Data of Processes and Requirements

某工業集團焊接車間部分焊接件、工序等數據，如表2 所示。焊接工期單位為天，“-”表示該焊接設備不能完成該工序。該實例中共有10 個焊接件和10 臺可用設備，利用所述調度優化方法進行優化后，調度方案，如圖2 所示。不同算法迭代代數和完工時間數據整理后，如圖3 所示。

圖2 焊接調度方案Fig.2 Welding Scheduling Scheme

圖3 不同算法計算得到的完工時間數據Fig.3 Completion Time Data of Different Algorithms

由圖2 可以看出，協同作業可以縮短完工時間，但是也帶來了工位占用問題。不可移動的設備M5和M10在焊接結束后，由于協同作業設備M3尚未完成焊接，該工位仍被占用。即便如此，協同作業仍然比獨立作業完工時間明顯提前，如圖3 所示。提高了設備利用率，縮短了生產周期。

6 結論

針對智能制造焊接車間中部分工序可協同作業的問題，采用改進的差分進化算法，對協同作業焊接車間調度進行了優化。通過對不同算法進行計算對比，發現采用自適應差分縮放因子的差分算法在進化前期能夠保證種群多樣性、在進化后期能夠加快收斂速度，解決協同作業焊接調度問題可行且有效，為智能制造環境下定制化產品生產調度研究提供了參考。

在仿真實驗和實例驗證環節發現，個性化產品占比的提高對設計制造環節響應速度影響非常大，給調度優化帶來了困難。為提高響應速度和市場競爭力，下一步研究中將基于調度預測數據反饋至工藝設計環節，建立工序柔性的焊接調度數學模型進行優化。