李艷萍

(上海電機(jī)學(xué)院 機(jī)械學(xué)院， 上海 201306)

面向中國制造2025，個性化和小批量生產(chǎn)需求增加，制造變得日益復(fù)雜和多樣化[1]。車身制造由單一鋼材料車身向多材料車身轉(zhuǎn)變，裝配零部件材料增加，裝配連接工藝、裝配資源等也相應(yīng)增加[2]。車身裝配的多樣化和不確定性為車身復(fù)雜裝配帶來新的特點(diǎn)[3-4]。裝配順序確定是裝配系統(tǒng)設(shè)計(jì)規(guī)劃和裝配工藝實(shí)現(xiàn)的關(guān)鍵環(huán)節(jié)，裝配順序不僅決定本次裝配操作的復(fù)雜性，同時決定了系統(tǒng)傳遞復(fù)雜性流動的方向，直接影響產(chǎn)品的可裝配性、裝配質(zhì)量和成本[5]。基于復(fù)雜性分析的多材料車身裝配順序優(yōu)化，發(fā)揮裝配系統(tǒng)相關(guān)性信息傳遞復(fù)雜性的作用[6]，實(shí)現(xiàn)裝配系統(tǒng)復(fù)雜性的優(yōu)化配置。

本文在裝配系統(tǒng)復(fù)雜性分析基礎(chǔ)上，以傳遞復(fù)雜性為裝配任務(wù)節(jié)點(diǎn)間成本陣列，描述多材料車身裝配順序優(yōu)化問題，去除無效信息后的裝配順序優(yōu)化，可類似于帶約束的非對稱旅行商問題(Asymetric Traveling Salesman Problem with Precedence Constraint, ATSP-PC)，建立節(jié)點(diǎn)間有效傳遞復(fù)雜性總和最小的裝配順序優(yōu)化模型。隨著裝配節(jié)點(diǎn)數(shù)增多導(dǎo)致復(fù)雜性信息爆炸性增加，探索應(yīng)用定向爬山遺傳算法(Oriented Hill-Climbing based Genetic Algorithm，OHCGA)搜索得到問題求解。最后通過某型車身側(cè)圍裝配實(shí)例驗(yàn)證，該方法有效降低了裝配系統(tǒng)的復(fù)雜性，提高了裝配系統(tǒng)的性能，并保證多材料車身裝配的質(zhì)量。

1 多材料車身裝配順序優(yōu)化

1.1 車身裝配系統(tǒng)

多材料車身裝配順序不僅決定了裝配制造的過程，同時也決定了各裝配工位間復(fù)雜性的有效傳遞與傳播[5-7]。考慮包含多個車身零部件的裝配，將每個車身零部件裝配作為裝配任務(wù)節(jié)點(diǎn)，用節(jié)點(diǎn)間有向順序表示裝配約束關(guān)系。假定如圖1所示的9個節(jié)點(diǎn)分別對應(yīng)車身零部件裝配的子節(jié)點(diǎn)，其中，每一個任務(wù)節(jié)點(diǎn)用一個實(shí)線框表示，添加的虛擬節(jié)點(diǎn)“0” 用一個虛線圓圈表示，作為任務(wù)準(zhǔn)備節(jié)點(diǎn)，向開始任務(wù)節(jié)點(diǎn)提供物料配送和工具準(zhǔn)備，并且最終的裝配也要回到該準(zhǔn)備節(jié)點(diǎn)，以完成一個裝配順序和任務(wù)周期。令虛擬節(jié)點(diǎn)“0”的復(fù)雜性為零，且節(jié)點(diǎn)“0”到其他節(jié)點(diǎn)的裝配復(fù)雜性，其他節(jié)點(diǎn)到節(jié)點(diǎn)“0”的裝配復(fù)雜性均為零。基于復(fù)雜性分析的多材料車身裝配順序優(yōu)化目標(biāo)，就是尋找可行裝配序列中具有最小系統(tǒng)復(fù)雜性的裝配序列。

圖1 九任務(wù)節(jié)點(diǎn)裝配系統(tǒng)

1.2 裝配節(jié)點(diǎn)復(fù)雜性度量

1.3 約簡方案

多材料車身零部件繁多、裝配結(jié)構(gòu)復(fù)雜，存在n個裝配節(jié)點(diǎn)的車身裝配，若不考慮車身裝配結(jié)構(gòu)的優(yōu)先級約束，則有n!個可行裝配序列，直接求解一般比較困難。依據(jù)多材料車身裝配操作復(fù)雜性的條件相關(guān)性，并考慮各裝配任務(wù)節(jié)點(diǎn)間的互相關(guān)性，約簡等價轉(zhuǎn)換以利于問題的求解[5-7]。

本文依據(jù)車身結(jié)構(gòu)及裝配約束的優(yōu)先級限制，識別裝配序列中各任務(wù)節(jié)點(diǎn)間的不可行單元，將其標(biāo)記為無效信息，清除它們以簡化問題求解。

步驟1依據(jù)裝配優(yōu)先關(guān)系識別任務(wù)節(jié)點(diǎn)i優(yōu)先于節(jié)點(diǎn)j的裝配，并在裝配復(fù)雜性成本陣列中標(biāo)記。

步驟2檢查裝配復(fù)雜性成本陣列的第i行，若其第j列未標(biāo)記，則表明i和j互不相關(guān)，任務(wù)i既可安排在任務(wù)j前，也可在其后被裝配，對應(yīng)的裝配節(jié)點(diǎn)間復(fù)雜性為Ii，j(節(jié)點(diǎn)i先于節(jié)點(diǎn)j裝配)或?yàn)镮j,i(節(jié)點(diǎn)j先于節(jié)點(diǎn)i裝配)。

步驟3所有未標(biāo)記的單元為不許可單元，標(biāo)記為∞。

上述過程隱含了一種簡化復(fù)雜性成本陣列而不改變問題解的方法，可設(shè)置步驟1標(biāo)記的單元為零，其對原始問題的唯一改變可通過設(shè)置一個常數(shù)來反映，而不改變問題的求解。表1為簡化的復(fù)雜性成本陣列。

表1 簡化的復(fù)雜性成本陣列

由于多材料車身裝配操作非獨(dú)立相關(guān)條件信息熵的存在，節(jié)點(diǎn)間裝配操作復(fù)雜性與順序和方向均相關(guān)，即，一般情況下Ii,j≠Ij,i。由此，多材料車身裝配順序優(yōu)化問題可類比于ATSP-PC[8-10]。

2 裝配順序優(yōu)化模型

多材料車身裝配順序優(yōu)化問題的目標(biāo)函數(shù)，為由節(jié)點(diǎn)i開始的順序路徑?jīng)Q定的有效復(fù)雜性成本和最小。從裝配節(jié)點(diǎn)i出發(fā)，合理地訪問集合N-S中的節(jié)點(diǎn)(n+1-|S|)，并最終返回到虛擬節(jié)點(diǎn)“0”結(jié)束，然后訪問從狀態(tài)(S,i)到狀態(tài)(S∪{j},j)發(fā)生狀態(tài)轉(zhuǎn)移的節(jié)點(diǎn)j(j∈D(S)，D(S)為由狀態(tài)(S,i)后有可能被訪問的點(diǎn)集組成的決策空間)。建立基于復(fù)雜性分析的多材料車身裝配順序優(yōu)化模型，以最小化裝配復(fù)雜性總和為優(yōu)化目標(biāo)函數(shù)，同時裝配順序優(yōu)化還受節(jié)點(diǎn)流動方向和任務(wù)節(jié)點(diǎn)復(fù)雜性約束，即

f(S∪{j},j)

s.t. (i) {0}?S?N,i∈S

S=N，i∈S{0}

m=1，2，…,M

(1)

3 OHCGA算法求解

多材料車身裝配順序優(yōu)化問題，隨著裝配節(jié)點(diǎn)增多，裝配序列急劇增多，計(jì)算復(fù)雜性也將隨著節(jié)點(diǎn)數(shù)的增多而爆炸式增加，需探索一種有效的方法求解問題。遺傳算法[11]模擬了自然選擇和生物進(jìn)化過程中的繁殖、交叉和變異現(xiàn)象，使適應(yīng)度高的個體基因在下一代種群中占有更高比例，通過自組織、自適應(yīng)、自學(xué)習(xí)的群體進(jìn)化，引導(dǎo)搜索向全局最優(yōu)解收斂。但由于其存在早熟現(xiàn)象使算法搜索很快收斂到局部最優(yōu)解而不是全局最優(yōu)解。爬山法[12]為一種局部搜索機(jī)制，從解空間的任意位置開始，快速收斂于局部最優(yōu)解，對求解單峰問題具有顯著效果。本文在遺傳算法基礎(chǔ)上引用OHCO，在每一代進(jìn)化操作中，定向地在產(chǎn)生優(yōu)秀個體的方向上生成更優(yōu)秀的個體取代當(dāng)前個體，引導(dǎo)算法有效地向全局最優(yōu)解收斂，改善算法搜索全局最優(yōu)解的能力[13]。實(shí)現(xiàn)過程如圖2所示。

圖2 OHCGA算法求解流程

OHCGA算法求解[13]。采用基于順序表示的遺傳基因Grefenstette編碼[14-15]。算法求解的適應(yīng)度函數(shù)，為目標(biāo)函數(shù)和各約束條件懲罰函數(shù)的

和[15]，即

F(C)=O(C)+P(C)+G(C)

(2)

式中:O(C)為裝配順序優(yōu)化的目標(biāo)函數(shù)；P(C)為各裝配節(jié)點(diǎn)超出約束條件的懲罰函數(shù)；G(C)為超出裝配人員可承受裝配操作復(fù)雜性的懲罰函數(shù)。

4 應(yīng)用實(shí)例

以某型多材料車身側(cè)圍為例，進(jìn)行基于復(fù)雜性分析的裝配順序優(yōu)化，圖3所示為該車身側(cè)圍零部件裝配模型。

圖3 某型車身側(cè)圍裝配模型

依據(jù)車身側(cè)圍裝配關(guān)系，推導(dǎo)出側(cè)圍裝配的優(yōu)先級：外板基礎(chǔ)上裝配內(nèi)板，然后裝配加強(qiáng)板、隔板，并依此建立側(cè)圍的裝配模型?？尚醒b配序列流向如圖4所示。對于裝配節(jié)點(diǎn)2～9區(qū)域，由裝配關(guān)系表示復(fù)雜性信息列表，依據(jù)裝配約束清除無效信息，得到任務(wù)間傳遞復(fù)雜性成本陣列。

多材料車身側(cè)圍裝配，其中，零部件選擇為工位裝配操作的首要任務(wù)，主要由本工位裝配操作信息決定，裝配夾具選擇為滿足本工位零部件的裝配要求，均為“進(jìn)給復(fù)雜性”；而裝配工藝、設(shè)備、工具及裝配順序選擇，需考慮受其上流工位影響的“傳遞復(fù)雜性”。因此，車身側(cè)圍裝配順序優(yōu)化，需分析度量裝配工藝、設(shè)備和工具等的選擇復(fù)雜性和裝配順序選擇復(fù)雜性。車身側(cè)圍裝配任務(wù)節(jié)點(diǎn)間的傳遞復(fù)雜性計(jì)算，如節(jié)點(diǎn)2(后大燈支座)對節(jié)點(diǎn)8(B柱內(nèi)板總成)，節(jié)點(diǎn)8可供選擇的材料主要包括普通碳素鋼、高強(qiáng)度鋼、鋁合金和復(fù)合材料，由各類材料的零部件選擇概率，對應(yīng)不同車身材料，主要存在點(diǎn)焊、自沖鉚、膠接與膠鉚復(fù)合4種連接工藝。則裝配工藝選擇條件熵復(fù)雜性為

圖4車身側(cè)圍裝配順序流向示意圖

(3)

式中：p(xk2,xk1)為零件選擇和工藝選擇的聯(lián)合概率；p(xk2|xk1)為不同工藝對應(yīng)零部件材料的條件選擇概率。各裝配操作條件選擇傳遞復(fù)雜性可由式(3)類似計(jì)算?？紤]各選擇復(fù)雜性的權(quán)重，由下式可得多材料車身側(cè)圍裝配節(jié)點(diǎn)2對節(jié)點(diǎn)8的傳遞復(fù)雜性公式：

(4)

式中：Hku為第ku類裝配操作的條件信息熵復(fù)雜性。αku為第ku(ku=k1,k2,…,K)類裝配操作的作用系數(shù)，若包含第ku類裝配操作，則令αku=1，否則αku=0。wku為第ku類裝配操作的權(quán)重，基于數(shù)據(jù)分析和粗糙集客觀評價，并結(jié)合專家知識綜合確定多材料車身裝配各操作復(fù)雜性權(quán)重[16]為

[wk1wk2wk3wk4wk5]-1=

[w零件w工藝w設(shè)備&工具w夾具w順序]-1=

[0.2160.231 0.114 0.126 0.313]-1

同理可得其他各裝配節(jié)點(diǎn)的有效傳遞復(fù)雜性度量?？紤]到計(jì)算方法的相似性和計(jì)算數(shù)據(jù)量繁多，用Matlab實(shí)現(xiàn)各節(jié)點(diǎn)有效傳遞復(fù)雜性的計(jì)算。車身側(cè)圍裝配2～9各節(jié)點(diǎn)間的傳遞復(fù)雜性見表2。

2～9的8個裝配任務(wù)節(jié)點(diǎn)，經(jīng)裝配約束分解后的可行裝配序列統(tǒng)計(jì)有560種，應(yīng)用OHCGA啟發(fā)式搜索求解，Windows系統(tǒng)下，Matlab 程序?qū)崿F(xiàn)了OHCGA對該問題的求解[17]。經(jīng)多次求解發(fā)現(xiàn)，當(dāng)遺傳代數(shù)N在100左右時可趨于穩(wěn)定，為求解穩(wěn)妥，取遺傳代數(shù)N=200。OHCGA搜索尋優(yōu)，進(jìn)化代數(shù)N=200的進(jìn)化過程如圖5所示。

求解得到傳遞復(fù)雜性最小的裝配順序，經(jīng)Grefenstette反編碼解碼后為：5→6→2→3→4→7→8→9，對應(yīng)的最小復(fù)雜性為20.99 bit。而依據(jù)裝配模型和裝配約束關(guān)系產(chǎn)生的可行裝配序列中，互信息熵表示的傳遞復(fù)雜性最大為35.83 bit，最優(yōu)裝配順序的傳遞復(fù)雜性低于最大傳遞復(fù)雜性，相對減少41.42%，可見該方法減少車身裝配系統(tǒng)復(fù)雜性的效果顯著。同理可得11～16節(jié)點(diǎn)的裝配順序優(yōu)化，對應(yīng)復(fù)雜性最小的裝配順序?yàn)椋?2→11→13→15→16→14。綜上，該側(cè)圍裝配操作復(fù)雜性最小的裝配順序?yàn)椋?→5→6→2→3→4→7→8→9→10→12→11→13→15→16→14。

表2 節(jié)點(diǎn)2～9中各節(jié)點(diǎn)間傳遞復(fù)雜性

圖5 爬山遺傳算法尋優(yōu)過程(N=200)

5 結(jié) 論

本文多材料車身裝配順序優(yōu)化，基于傳遞復(fù)雜性與裝配順序的相關(guān)性，將多材料車身裝配順序優(yōu)化問題類似于具有順序約束的ATSP-PC，并建立有效傳遞復(fù)雜性總和最小的裝配順序優(yōu)化模型。多材料車身復(fù)雜裝配順序優(yōu)化問題隨著裝配節(jié)點(diǎn)數(shù)的增多，其求解的信息量產(chǎn)生爆炸性增加而使問題的求解難度增加，應(yīng)用OHCGA啟發(fā)式搜索得到裝配順序優(yōu)化問題的求解。最后通過車身側(cè)圍復(fù)雜裝配實(shí)例驗(yàn)證了方法的可行性和有效性，合理裝配順序優(yōu)化的同時有效降低了車身裝配系統(tǒng)的復(fù)雜性，并使裝配系統(tǒng)性能得以優(yōu)化。