多目標約束下裝配線再平衡研究

張于賢，梁師文，楊夢珂

(桂林電子科技大學(xué) 商學(xué)院， 廣西 桂林 541004)

裝配線規(guī)劃在現(xiàn)代復(fù)雜多變的大規(guī)模定制生產(chǎn)模式下扮演著重要的角色，裝配線平衡與否直接影響制造系統(tǒng)的生產(chǎn)效率。

為了獲得較高的裝配線平衡率，須在工藝條件約束下，對全部裝配工序按流水線節(jié)拍進行科學(xué)組合以使每個工位分配的負荷量充足且均衡。裝配線平衡問題主要分為三類[1]，但在低成本，高效率且個性化的市場需求下，以裝配線的工作站數(shù)為定值，求最小生產(chǎn)節(jié)拍的第II類裝配線平衡問題仍是制造業(yè)目前須解決的難題。近年來，國內(nèi)外學(xué)者針對第II類裝配線平衡問題已經(jīng)提出了諸多平衡數(shù)學(xué)模型及優(yōu)化算法，其中文獻[1-7]以最小生產(chǎn)節(jié)拍為目標函數(shù)構(gòu)建單目標裝配線數(shù)學(xué)模型，設(shè)計了各類算法對裝配線問題進行求解，通過實例驗證了算法的有效性和可行性。與單目標約束下的算法求解模型相比，盡管文獻[8-10]設(shè)計了多目標裝配線算法優(yōu)化模型，可增強求解效果的可靠性和有效性，但仍有不少問題待解決：平衡約束模型未能更全面的反應(yīng)實際生產(chǎn)現(xiàn)狀，研究與實際應(yīng)用依舊存在差距；智能算法雖然能夠?qū)ば蜃髯顑?yōu)性排序，但仍存在最優(yōu)解不符合裝配線平衡最優(yōu)準則的情形；多數(shù)文獻從算法優(yōu)化性能再改進入手提升求解效果，未能考慮到工序操作的復(fù)雜性和潛在的冗余性，且對瓶頸工序未能再深入地進行操作分析，使得裝配線平衡率再提高。本文提出了基于GA-IE兩階段法的裝配線多目標再平衡優(yōu)化模型。

1 第II類裝配線平衡問題描述

針對第II類裝配線平衡問題，設(shè)工作站數(shù)目為K，工序集合為N，ti為工序i的操作時間；t(SK)為第k個工作站的工序時間，為了使得生產(chǎn)節(jié)拍最小化，須將所有工序均衡地分配到各個工作站。構(gòu)建第II類裝配線平衡模型須基于以下假設(shè)：

產(chǎn)品的裝配工序時間已確定，工序邏輯優(yōu)先關(guān)系已知；全部工序均被分配在工作站且只被分配到其中的一個工作站；工作站的數(shù)目是確定的；各個工作站由傳送帶鏈接，其傳送速度一定，傳送時間可忽略不計并且每隔固定的節(jié)拍時間投放一個待裝配的零/部件。

為了解決單目標約束數(shù)學(xué)模型對裝配線平衡界定比較單一化且模型結(jié)果與實際生產(chǎn)應(yīng)用存在較大的偏差，提出多目標約束下的裝配線平衡數(shù)學(xué)模型對裝配線優(yōu)劣作出較全面的評價，其模型可表示如下：

1) 最小化裝配節(jié)拍：

(1)

2) 最小化平衡損失率：

(2)

3) 工作站間最小化平滑指數(shù)：

(3)

(4)

(5)

其中，式(1)表示以最大的裝配任務(wù)時間為裝配線節(jié)拍CT；式(2)表示最小裝配線平衡損失率E*；式(3)表示平滑指數(shù)H，即分配到各個工作站上的裝配任務(wù)時間總和與節(jié)拍的偏差，是衡量工作站負荷的指標；式(4)確保每項裝配任務(wù)僅能被分配到其中的一個工作站，且決策變量xik屬于0/1型，i=1,2,…,N；式(5)保證裝配任務(wù)被分配時必須遵循工序優(yōu)先級關(guān)系,PRE(j)表示按任務(wù)的先后順序，i先于任務(wù)j完成的任務(wù)集合。

2 遺傳算法設(shè)計

2.1 算法編碼設(shè)計

采用二進制編碼方式對裝配線平衡問題進行編碼，即通過二進制字符集{0,1}產(chǎn)生0/1字符串來表示問題空間的候選解。

譯碼過程是按照基因位次將工序分配到各個工作站，其操作步驟如下：

步驟2 以CT*為當(dāng)前節(jié)拍，并將工序集合N按照基因位次分配到K個工作站中，K個工作站的時間分別為T1,T2,…,Tm,…,TK；ifTm≤CT*，則CT*為該排序下的最小節(jié)拍，即可停止搜索；否則，進行步驟3；

步驟3 計算各工序的潛在增量Δpr， Δpr(r=1,2,…,K)表示第k+1個工作站的第1個作業(yè)元素時間；

步驟4 令CT=max{Tm}，CT*=min{Tm+Δpr}，ifCT≤CT*，則CT*是該排序下的最小節(jié)拍，停止搜索；否則，進行步驟2。

本文研究的問題屬于多目標函數(shù)情形，在求解最優(yōu)方案須將多目標問題轉(zhuǎn)化為單目標問題，通過考慮各目標函數(shù)式(1)、式(2)、式(3)將其設(shè)計成單目標評價函數(shù)f，定義如下：

fmin=α*CT+β*E*+γ*H

其中，α、β、γ為權(quán)重系數(shù)，且α+β+γ=1。

2.2 常規(guī)遺傳算法操作

1) 初始化種群

利用隨機法生成規(guī)模為Size的初始種群，其操作步驟如下：

步驟1 按照工序邏輯優(yōu)先關(guān)系矩陣對工序作有序分配；

步驟2 將矩陣中已分配的工序?qū)?yīng)的行和列均劃去，更新優(yōu)先約束矩陣；

步驟3 直至工序集合N中的所有元素均被分配完，則停止更新；否則重復(fù)步驟1和步驟2。

2) 選擇

采用簡單易操作的輪盤賭選擇法。其基本思路：染色體被選中的概率與其適應(yīng)度函數(shù)值成正比，其遺傳到下一代群體的概率為

其中，F(xiàn)(p)為染色體p的適應(yīng)度，輪盤旋轉(zhuǎn)pop_size次。

3) 交叉

采用具有較強搜素能力的部分映射交叉算子[11](Partial-Mapped Crossover，簡稱 PMX)，其操作步驟如下：

步驟1 隨機選擇一對染色體(父代)中幾個基因的起止位置，且被選位置相同；

步驟2 交換匹配基因；

步驟3 沖突檢測。根據(jù)交換的兩組基因建立一個映射關(guān)系，如圖1所示，以1-5-6映射關(guān)系為例，能夠發(fā)現(xiàn)步驟2結(jié)果中子代1存在兩個基因1，則須將其通過映射關(guān)系轉(zhuǎn)變?yōu)榛?，以此類推至沒有沖突為止。全部沖突基因均須映射，保證生成的新一對子代基因無沖突。

圖1 PMX交叉操作

4) 變異

為了增加種群的多樣性，采用交換-倒轉(zhuǎn)-插入變異方式，其操作步驟如下(圖2)：

步驟1 (交換)：隨機選擇1個染色體上的兩個不同的基因，再交換它們在操作序列的位次；

步驟2 (倒轉(zhuǎn))：隨機選擇1個染色體上的4個不同基因，再倒轉(zhuǎn)4個位置間序列的 順序；

步驟3 (插入)：隨機選擇1個染色體上的1個基因，再將它隨機插到操作序列的某個位置。

2.3 算法再改進切入點

為了解決常規(guī)遺傳算法(Genetic Algorithm，簡稱GA)在求解種群規(guī)模較大時，存在過早收斂，且生成解容易陷入局部最優(yōu)等問題，本文提出求解第II類裝配線平衡問題的改進遺傳算法，如圖3所示，其中改進遺傳算法采用兩個層面，第一層面，利用遺傳算法生成初始解，第二層面，嵌入具有“記憶”屬性的禁忌搜索算法(Tabu Search,簡稱TS)對初始解進行尋優(yōu)。

圖2 變異操作

圖3 改進遺傳算法流程

3 實例驗證

3.1 驗證算法的準確性

經(jīng)過測試，將遺傳算法參數(shù)設(shè)置為：種群數(shù)Size=30,遺傳代數(shù)MaxIt=300,交叉概率Pc=0.7,變異概率Pm=0.05,目標函數(shù)權(quán)重系數(shù)α=0.3，β=0.3，γ=0.4Z。而GA-TS算法在GA算法參數(shù)的基礎(chǔ)上增加禁忌長TL=7,懲罰系數(shù)MPC=8即可，這樣設(shè)置參數(shù)主要是控制參數(shù)一致性，有利于算法結(jié)果的可比性。

為了驗證遺傳算法和改進遺傳算法(GA-TS)的準確性，在Matlab環(huán)境下，用經(jīng)典的Jackson[12]和Buxey[13]平衡算例及某H產(chǎn)品裝配線平衡問題(表1)進行驗證，而分支定界法(B-and-B)求解平衡算例的結(jié)果作為GA算法和GA-TS算法運行結(jié)果的對比對象，算法運行結(jié)果如表2所示。

表1 H產(chǎn)品裝配工序順序

表2 算法對測試問題的運行結(jié)果

經(jīng)表2結(jié)果可看出，GA-TS算法、GA算法與分支定界法(B-and-B)在工作站數(shù)K相同的情形下求解Jackson和Buxey問題，GA-TS算法求解效果較好于GA算法和B-and-B算法得到最優(yōu)解，表明GA-TS算法、GA算法的求解結(jié)果均準確。

在不同工作站數(shù)K的情形下分別采用GA-TS算法和GA算法對H產(chǎn)品裝配線平衡問題進行優(yōu)化求解。當(dāng)工作站數(shù)取值相同時，GA-TS算法優(yōu)化求解的節(jié)拍CT、平滑指數(shù)H均低于GA算法的結(jié)果，且平衡率E*較好于GA算法得到的解，表明GA-TS算法得到的解更優(yōu)，效果更佳。

在實際生產(chǎn)中，給定的H產(chǎn)品工作站數(shù)K=10，GA算法獲得最優(yōu)解對應(yīng)的工位圖，如圖4所示，其中圖4中的[(39，15)，station1]表示編號為39且時間為15 s的工序被分配到工作站1。GA算法得到的最優(yōu)解節(jié)拍CT=120，平滑指數(shù)H=22.36，生產(chǎn)線平衡率E*=73.33%未達到裝配線平衡最優(yōu)準則要求，即生產(chǎn)線平衡率只有在85%以上時，生產(chǎn)系統(tǒng)是按照“一件流”的生產(chǎn)模式[14]運行。

為了滿足生產(chǎn)要求，在GA算法最優(yōu)解的基礎(chǔ)上，提出利用IE技術(shù)對H產(chǎn)品裝配線再改善思想，則構(gòu)成兩階段體系模型，其中第1階段，利用GA算法對裝配線平衡問題進行優(yōu)化求解，第2階段，應(yīng)用IE技術(shù)針對第1階段算法求解的不符合要求的最優(yōu)工位作瓶頸分析，并進行持續(xù)性改善，得到滿意的再平衡方案，如圖5所示。

圖4 GA算法最優(yōu)解對應(yīng)的工位圖

圖5 兩階段體系模型

3.2 IE技術(shù)再平衡改善

由圖4可知，第1、3、4、10工位的加工時間比較長，處于忙碌狀態(tài)，是整個流程的瓶頸環(huán)節(jié)，也是造成后續(xù)工位高空閑率的因素。因為工作站負荷不均衡，限制了裝配線的整體產(chǎn)出效率，對其余工位的生產(chǎn)能力產(chǎn)生了瓶頸效應(yīng)，因此，利用工業(yè)工程(Industrial Engineering,簡稱IE)技術(shù)[15]對第1、3、4、10工位的工序進行重點再改善。

以第10工位中的6號工序為例進行雙手作業(yè)分析，對多余及無效的動作進行改善，其改善前的雙手作業(yè)分析結(jié)果，如圖6所示。

通過對H裝配線不合理現(xiàn)象的分析，利用“6W1H”提問技術(shù)和“ECRS”原則對6號工序進行雙手作業(yè)改善，其中提問技術(shù)從生產(chǎn)作業(yè)的七個方面(作業(yè)要完成什么(what)、在何地做(where)、何時做(when)、何人做(who)、為誰做(for whom)、作業(yè)方法(how)和為何這樣做(why))有序的探尋問題的根源，能夠快速準確地對生產(chǎn)作業(yè)現(xiàn)存的問題作出定位，并發(fā)現(xiàn)問題產(chǎn)生的原因。再通過“ECRS”原則對提問技術(shù)找到的作業(yè)問題進行取消(Eliminate)、合并(Combine)、重排(Rearrange)、簡化(Simplify)5個環(huán)節(jié)的調(diào)整，使得6號工序時間由20s 降低到14 s，其結(jié)果如圖7所示。

依據(jù)6號工序的改善思路對第10工位的其余工序及第1、3、4工位進行改善，其結(jié)果如表3所示。

圖6 改善前主板焊接雙手作業(yè)分析

圖7 改善后主板焊接雙手作業(yè)

工位編號作業(yè)時間/s改善前改善后工位111096工位311092工位411598工位10120100

經(jīng)過對瓶頸工序進行改善，瓶頸節(jié)拍CT由原來的120 s變?yōu)?00 s，平滑指數(shù)H由22.36變?yōu)?8.65，平衡率E*由73.33%變?yōu)?8.00%，符合“一件流”的生產(chǎn)模式要求。

3.3 驗證兩階段法求解程度

為了證實兩階段法的求解效果是非最優(yōu)解一猜想，提出直接利用改進遺傳算法對H產(chǎn)品裝配線平衡問題尋優(yōu)求解。在工作站數(shù)K=10時，瓶頸節(jié)拍CT=90 s，平滑指數(shù)H=3.33，平衡率E*=97.78%，其最優(yōu)解對應(yīng)的工位圖，如圖8所示。將兩階段法和改進遺傳算法求解結(jié)果對比，結(jié)果表明：兩階段法得到的結(jié)果是非最滿意解，但是一個有效可行解；改進遺傳算法尋優(yōu)效果較好，但未能從作業(yè)操作改善的角度提升生產(chǎn)線效率。

圖8 改進遺傳算法最優(yōu)解對應(yīng)的工位圖

4 結(jié)論

本文通過構(gòu)建以裝配線平衡損失率、裝配節(jié)拍和站間平滑指數(shù)為最小優(yōu)化目標的第Ⅱ類裝配線平衡模型，通過實例驗證了GA算法和改進GA算法的準確性。根據(jù)實際問題的特點，利用GA算法優(yōu)化H產(chǎn)品裝配線，其最優(yōu)解未能符合“一件流”的生產(chǎn)模式要求，提出了IE技術(shù)與GA算法相結(jié)合的再平衡改善策略，使得裝配線效率從73.33%提升到了88%，且將GA-IE兩階段法和改進GA算法的求解結(jié)果作對比，結(jié)果表明：GA-IE兩階段法求解效果符合生產(chǎn)活動要求，但獲得的是可行解，非最優(yōu)解。兩階段法可以為生產(chǎn)管理人員在裝配線規(guī)劃方面提供方法支持。