基于遺傳算法的汽車裝配線快速自動(dòng)平衡方法研究

摘 要：在關(guān)于汽車裝配線平衡問題的研究中，普遍存在建模與裝配線實(shí)際情況偏差大等問題。本文根據(jù)汽車裝配線的工藝特點(diǎn)建立符合裝配線實(shí)際需求的第一類平衡問題的數(shù)學(xué)模型，該模型引入操作區(qū)域、車身高度以及裝配約束條件等因子。以該模型為基礎(chǔ)設(shè)計(jì)了基于工位動(dòng)態(tài)分割的遺傳算法，并采用Java語(yǔ)言驗(yàn)證了該算法，開發(fā)裝配線快速自動(dòng)平衡軟件。算法不僅解決了裝配平衡問題與實(shí)際運(yùn)行狀態(tài)不符的問題，而且以此為基礎(chǔ)，開發(fā)了便于企業(yè)使用的軟件工具。本文以某段整車裝配工藝為對(duì)象，對(duì)算法和軟件進(jìn)行驗(yàn)證，取得了良好的效果。

關(guān)鍵詞：裝配線平衡；遺傳算法；自動(dòng)平衡

中圖分類號(hào)：U 466" " " " " " " 文獻(xiàn)標(biāo)志碼：A

隨著汽車市場(chǎng)競(jìng)爭(zhēng)日益激烈，車企必須具備柔性靈活的生產(chǎn)能力，提高效率，降低成本，從而提升競(jìng)爭(zhēng)力。裝配線平衡是進(jìn)行產(chǎn)能調(diào)整的主要方法。以前裝配線平衡研究與真實(shí)的汽車裝配線偏差較大，缺乏成熟的生產(chǎn)線平衡工具，對(duì)企業(yè)的實(shí)際指導(dǎo)意義有限。本文設(shè)計(jì)了更符合整車裝配線實(shí)際需求的數(shù)學(xué)模型和遺傳算法，在該算法基礎(chǔ)上開發(fā)了裝配線自動(dòng)平衡分析軟件，使企業(yè)能夠?qū)ρb配線進(jìn)行工藝調(diào)整，從而靈活調(diào)整產(chǎn)能，推廣價(jià)值較高。

1 裝配線第一類平衡問題建模

裝配線的平衡問題分為3類[1]，本文研究的問題屬于第一類，即給定裝配線的生產(chǎn)節(jié)拍CT，在滿足任務(wù)分配的約束條件的前提下使分配后的崗位數(shù)量最少，從而縮短工藝流程，降低生產(chǎn)成本。

汽車裝配線平衡的基本概念如下。

生產(chǎn)節(jié)拍CT：相鄰2個(gè)車身通過相同位置的間隔時(shí)間。生產(chǎn)節(jié)拍是企業(yè)根據(jù)對(duì)市場(chǎng)需求的預(yù)測(cè)確定的，由生產(chǎn)總時(shí)間以及生產(chǎn)總量計(jì)算得到。

任務(wù)Wi：染色體的第i個(gè)基因，即該序列的第i項(xiàng)任務(wù)。

任務(wù)集合S：1條裝配線上包括的全部工作任務(wù)的集合。

任務(wù)作業(yè)時(shí)間：完成第i項(xiàng)裝配任務(wù)所需時(shí)間，單位為s。本文的作業(yè)任務(wù)時(shí)間均采用時(shí)間測(cè)量方法（Method Time Measurement，MTM）進(jìn)行評(píng)估，任務(wù)最佳作業(yè)時(shí)間為5 s ～ 20 s ，便于作業(yè)重組。

崗位Pk：其包括若干項(xiàng)任務(wù)的裝配崗位，1個(gè)崗位對(duì)應(yīng)1名作業(yè)者。

崗位作業(yè)時(shí)間Tk：第k個(gè)崗位所承擔(dān)的所有任務(wù)作業(yè)時(shí)間之和，如公式（1）所示。

（1）

式中：Tk 為第 k 個(gè)崗位所承擔(dān)的所有任務(wù)作業(yè)時(shí)間之

和；S（k）為第k個(gè)崗位所承擔(dān)的任務(wù)集合；tm為第m項(xiàng)任務(wù)的作業(yè)時(shí)間。

崗位負(fù)荷率Lk：第k個(gè)崗位作業(yè)時(shí)間與生產(chǎn)節(jié)拍的比例，Lk=Tk/CT。Lk越大，作業(yè)重組水平越高。

操作區(qū)域：根據(jù)員工的作業(yè)位置將車身劃分為6個(gè)操作區(qū)域，操作區(qū)域?yàn)樽髠?cè)、右側(cè)、前部、后部、內(nèi)部和底部，車身操作區(qū)域劃分如圖1所示，每項(xiàng)任務(wù)對(duì)應(yīng)1個(gè)操作區(qū)域。

車身高度：在整車裝配線中，不同線體會(huì)根據(jù)工藝特點(diǎn)設(shè)置不同的吊具高度。車身高度不同，定義車身高度屬性，高度={高，中，低}。每項(xiàng)任務(wù)對(duì)應(yīng)一個(gè)車身高度。

任務(wù)關(guān)系矩陣：不同操作任務(wù)存在裝配先后關(guān)系，本文采用任務(wù)關(guān)系矩陣P來記錄任務(wù)之間的裝配先后關(guān)系，如公式（2）所示[2]。

（2）

式中：如果執(zhí)行任務(wù)j前已完成任務(wù)i，則P（i，j）=1，否則P（i，j）=0。

基于上述基本概念，第一類裝配平衡問題的模型可描述為在滿足約束條件的前提下，將任務(wù)集合S包括的所有任務(wù)分配至一系列崗位上，目標(biāo)是尋求崗位數(shù)最小的任務(wù)分配方案，如公式（3）所示。

Minimize f（S，P，CT）=Nr " " " " " " " （3）

式中：f為任務(wù)集合的分割算法，本文采用遺傳算法；S為全部任務(wù)集合；CT為生產(chǎn)節(jié)拍；Nr為分割后的崗位數(shù)；Minimize為算法，目標(biāo)是尋找崗位數(shù)最小的解。

約束條件如下。任務(wù)的先后順序滿足任務(wù)約束矩陣；任意崗位的作業(yè)時(shí)間須小于等于生產(chǎn)節(jié)拍，如公式（4）所示。

Tklt;CT" " " " " " （4）

當(dāng)任務(wù)結(jié)合時(shí)操作區(qū)域應(yīng)滿足以下5個(gè)優(yōu)先原則。1）操作區(qū)域相同的2項(xiàng)任務(wù)為第一結(jié)合優(yōu)先級(jí)。2）雖然操作區(qū)域不同，但是操作區(qū)域同屬于（左側(cè)，前部，后部）或者（右側(cè)，前部，后部）的任務(wù)為第二結(jié)合優(yōu)先級(jí)。3）雖然操作區(qū)域不同，但是操作區(qū)域同屬于（左側(cè)，前部，后部，內(nèi)部）或者（右側(cè)，前部，后部，內(nèi)部）的任務(wù)為第三結(jié)合優(yōu)先級(jí)。4）底部區(qū)域的作業(yè)不能與其他操作區(qū)域的作業(yè)結(jié)合。5）左側(cè)區(qū)域的作業(yè)不能與右側(cè)區(qū)域的作業(yè)結(jié)合。如果同時(shí)滿足上述多項(xiàng)優(yōu)先原則，則先執(zhí)行高優(yōu)先級(jí)。車身高度屬性不同的任務(wù)不能進(jìn)行結(jié)合；如果某項(xiàng)任務(wù)為獨(dú)占崗位任務(wù)，則該任務(wù)必須單獨(dú)分配至一個(gè)崗位中，該崗位只能包括這一項(xiàng)任務(wù)；如果某項(xiàng)任務(wù)的綁定崗位屬性不為空，則該任務(wù)只能分配至指定崗位中。該約束針對(duì)裝配線中不可移動(dòng)的設(shè)備操作類任務(wù)，例如燃油加注等，避免再調(diào)整已固定設(shè)備。

2 構(gòu)建遺傳算法

2.1 編碼設(shè)計(jì)

將所有任務(wù)排列成1個(gè)符合任務(wù)關(guān)系矩陣的序列，該任務(wù)序列即對(duì)應(yīng)1條染色體，每項(xiàng)任務(wù)對(duì)應(yīng)1個(gè)基因，染色體長(zhǎng)度即基因數(shù)量等于任務(wù)數(shù)量，任務(wù)集合編碼成任務(wù)序列如圖2所示[3]。編碼后的1條染色體即1個(gè)任務(wù)序列，該序列共有n項(xiàng)任務(wù)。

2.2 初始化種群

為了提高種群質(zhì)量，本文采用半隨機(jī)的方式生成初始化種群。從無前序任務(wù)的任務(wù)集合或有前序任務(wù)但是前序任務(wù)已經(jīng)被分配完畢的任務(wù)集合中，按照操作區(qū)域優(yōu)先級(jí)原則進(jìn)行任務(wù)分配，包括以下5個(gè)步驟。1）從任務(wù)集合S中挑選無前序的任務(wù)，或者挑選雖然有前序任務(wù)但是前序任務(wù)已經(jīng)被編入染色的任務(wù)放入待選任務(wù)集合A中。2）判斷終止條件。如果待選任務(wù)集合A為空，那么終止。3）從待選任務(wù)集合A中隨機(jī)選擇1個(gè)任務(wù)Wi編入染色體。4）更新任務(wù)關(guān)系矩陣P，令P（i，j）=0，j=1，2，...，n，n為任務(wù)總數(shù)量。5）轉(zhuǎn)至步驟1），循環(huán)執(zhí)行上述步驟，直至任務(wù)集合S中的所有任務(wù)都編入染色體中，該染色體為種群的一個(gè)個(gè)體。

上述產(chǎn)生種群個(gè)體的過程并不是完全隨機(jī)的，而是對(duì)編入染色體的任務(wù)設(shè)置了選擇優(yōu)先級(jí)，將最有利于進(jìn)行后期動(dòng)態(tài)分割的任務(wù)優(yōu)先編入個(gè)體。種群初始化方法提高了種群個(gè)體的質(zhì)量，縮短了最優(yōu)解的產(chǎn)生時(shí)間。

2.3 解碼以及適應(yīng)度函數(shù)

解碼過程是將一個(gè)任務(wù)序列進(jìn)行動(dòng)態(tài)分割的過程[4]，分割過程須滿足模型的約束條件，崗位作業(yè)時(shí)間Tk須盡可能接近CT，即崗位負(fù)荷率Lk應(yīng)接近100%。分割的每一段任務(wù)子序列就是一個(gè)崗位。1個(gè)包括n項(xiàng)任務(wù)的任務(wù)序列分割為k個(gè)子序列，任務(wù)序列分割解碼過程如圖3所示。適應(yīng)度函數(shù)為f=1/Nr，1個(gè)任務(wù)序列分割的崗位數(shù)越大，適應(yīng)度值越小。

解碼過程有以下3個(gè)步驟。1）初始化。新建1個(gè)崗位Pk，令Tk=0，k=1。2）從左向右依次遍歷序列的每一項(xiàng)任務(wù)，假設(shè)當(dāng)前遍歷的是第i項(xiàng)任務(wù)，那么進(jìn)行如下判斷：判斷任務(wù)i的操作區(qū)域、車身高度、綁定崗位與未封閉的崗位Pk是否發(fā)生沖突。①如果沖突，則將Pk封閉并新建崗位Pk+1，將任務(wù)i存放至Pk+1，令Pk+1，進(jìn)一步判斷任務(wù)i是否為獨(dú)占崗位或該個(gè)體的最后1個(gè)任務(wù)，如果是，則封閉Pk+1。②如果不沖突，則進(jìn)一步判斷任務(wù)i是最后1個(gè)任務(wù)且Pk+1+tilt;CT，則令Tk=Tk+ti，并封閉Pk；如果任務(wù)i不是最后1個(gè)任務(wù)且Tk+tilt;CT，則令Tk=Tk+ti；如果任務(wù)i不是最后1個(gè)任務(wù)且Tk+ti=CT，則令Tk=Tk+ti，并封閉Pk；如果任務(wù)i不是最后1個(gè)任務(wù)且Tk+tigt;CT，則封閉Pk，并新建崗位Pk+1且令Tk+1=ti。3）重復(fù)執(zhí)行第2）步，直至該個(gè)體的所有任務(wù)都遍歷完畢。

2.4 選擇

本文采用經(jīng)典的輪盤賭選擇算法[5]，將個(gè)體的適應(yīng)度占種群適應(yīng)度總和的比例作為個(gè)體留下的概率。個(gè)體適應(yīng)度越大，保留的概率越大，其遺傳因子會(huì)在種群中擴(kuò)大。個(gè)體k選擇留下的概率P（k）如公式（5）所示。

（5）

式中：m為種群個(gè)體的數(shù)量；fk為個(gè)體k的適應(yīng)度；為種群中所有個(gè)體適應(yīng)度之和。

2.5 交叉

本文采用單點(diǎn)交叉法進(jìn)行染色體交叉操作[1]。步驟一：從種群中隨機(jī)選取2個(gè)待交叉?zhèn)€體X1和X2，隨機(jī)選取1個(gè)基因位k作為交叉點(diǎn)，X1在交叉點(diǎn)k之前的部分保持不變，作為新個(gè)體的第一部分，記作X1'1。步驟二：將個(gè)體X2中X1'1所含任務(wù)刪除，剩余任務(wù)按原來順序排列，作為新個(gè)體的第二部分，記作X1'2。步驟三：X11'與X1'2按順序結(jié)合，形成第一條新染色體X1'。步驟四：交換X1、X2的位置，用相同方法生成第二條新染色體X2'。步驟五：X1'和X2'替換種群中的X1和X2，完成交叉操作。

2.6 變異

為使變異后的染色體仍然屬于可行解，須保證變異后的染色體仍然滿足任務(wù)關(guān)系矩陣要求的裝配先后關(guān)系，因此本文采用移位變異法[6]，包括以下3個(gè)操作步驟。步驟一：隨機(jī)選擇一個(gè)待變異的個(gè)體以及該個(gè)體上的一項(xiàng)待變異任務(wù)。步驟二：根據(jù)任務(wù)關(guān)系矩陣從該個(gè)體中找到待變異任務(wù)的最后一個(gè)前X1序任務(wù)以及第一個(gè)后續(xù)任務(wù)，這2項(xiàng)任務(wù)之間的區(qū)間為可行區(qū)間。步驟三：將待變異的任務(wù)隨機(jī)插入可行區(qū)間，完成個(gè)體變異。

3 算法記憶自動(dòng)節(jié)拍平衡軟件開發(fā)

運(yùn)用Java對(duì)上述改進(jìn)后的遺傳算法進(jìn)行編程，開發(fā)裝配線體自動(dòng)節(jié)拍平衡軟件，軟件主界面如圖4所示。

以某整車廠總裝車間內(nèi)飾工藝為研究對(duì)象，由于市場(chǎng)需求變化，因此須將該線體從原設(shè)計(jì)60臺(tái)/h調(diào)整至50臺(tái)/h，生產(chǎn)節(jié)拍由60 s調(diào)整為72 s，要求快速制定新生產(chǎn)節(jié)拍中的任務(wù)分配方案，方案中的崗位數(shù)越少，說明該方案越好，產(chǎn)能調(diào)整成本越低。應(yīng)用自動(dòng)節(jié)拍平衡軟件進(jìn)行分析驗(yàn)證，快速自動(dòng)平衡結(jié)果見表1。

程序運(yùn)行的參數(shù)設(shè)置如下：種群大小為100，交叉概率為0.6，變異概率為0.01，迭代次數(shù)為500。當(dāng)次程序運(yùn)行至第4次時(shí)產(chǎn)生了較為精益的平衡方案，該方案的崗位數(shù)量為4人，平均作業(yè)負(fù)荷率為90.9%，整車裝配線體負(fù)荷率水平較高。

利用該軟件進(jìn)行自動(dòng)線平衡，耗時(shí)集中在前期準(zhǔn)備任務(wù)集合以及任務(wù)關(guān)系矩陣的過程中，但是每條線體只需準(zhǔn)備一次，后續(xù)可反復(fù)利用；單純軟件運(yùn)行耗時(shí)很短（運(yùn)行21 項(xiàng)任務(wù)、迭代 500 次，耗時(shí)約為3 min），效率高于使用傳統(tǒng)的人工平衡方法。

4 結(jié)語(yǔ)

本文根據(jù)整車生產(chǎn)廠裝配線的實(shí)際工藝特點(diǎn)建立了裝配線第一類平衡問題的數(shù)學(xué)模型，引入更符合整車裝配的約束因子，改進(jìn)了遺傳算法，利用Java開發(fā)了自動(dòng)平衡分析軟件，取得整車裝配線快速自動(dòng)作業(yè)平衡。以某整車廠總裝內(nèi)飾工段工藝為對(duì)象進(jìn)行分析，驗(yàn)證了該軟件的可行性和有效性，該軟件可廣泛應(yīng)用在制造業(yè)裝配線體平衡中，推廣價(jià)值很高。

參考文獻(xiàn)

[1]肖中華.基于改進(jìn)遺傳算法的汽車裝配線平衡問題研究[D].武漢：武漢科技大學(xué)，2010.

[2]鄒健.基于改進(jìn)遺傳算法的混流裝配線多目標(biāo)平衡優(yōu)化及仿真研究[D].錦州：遼寧工業(yè)大學(xué)，2021.

[3]揣博君.基于改進(jìn)遺傳算法的混流裝配線多目標(biāo)平衡研究[D].哈爾濱：東北林業(yè)大學(xué)，2018.

[4]吳爾飛.基于改進(jìn)遺傳算法的雙邊裝配線平衡[J].計(jì)算機(jī)集成制造系統(tǒng)，2007，13（2）：168-274.

[5]王倩.應(yīng)用改進(jìn)遺傳算法求解汽車雙邊裝配線平衡問題[J].機(jī)械工程師，2016（2）：5-8.

[6]李險(xiǎn)峰.基于改進(jìn)遺傳算法的汽車裝配生產(chǎn)線平衡問題研究[D].北京：北京科技大學(xué)，2017.