陳丹丹 曹慕昆

(1.華為技術(shù)有限公司,廣東 深圳 250012;2.廈門大學 管理學院,福建 廈門 361005)

0 引言

在經(jīng)濟全球化和客戶需求多樣化的時代,制造企業(yè)面臨著日趨激烈的市場競爭。具體表現(xiàn)在:產(chǎn)品更新?lián)Q代速度加快,迫使企業(yè)不斷加大研發(fā)投入;市場快速變化,帶來更多的不確定性和不可預(yù)測性;傳統(tǒng)的大批量生產(chǎn)方式日漸衰落,無法滿足客戶豐富多樣的個性化需求;全球資源短缺,造成原材料價格不斷上漲。這些挑戰(zhàn)驅(qū)使企業(yè)從生產(chǎn)方式的源頭著手變革,逐漸由傳統(tǒng)的大批量生產(chǎn)轉(zhuǎn)變成JIT(Just In Time)生產(chǎn)[1-2]。為了快速響應(yīng)市場需求,縮短產(chǎn)品交貨周期,提高產(chǎn)品質(zhì)量和降低生產(chǎn)成本,企業(yè)必須重視其生產(chǎn)制造環(huán)節(jié)的優(yōu)化問題。

裝配線是制造型企業(yè)的核心生產(chǎn)環(huán)節(jié),又稱流水線,由一系列通過傳送帶或移動帶相互連接的工作站組成。為了組裝單個產(chǎn)品,每個工作站在給定的時間內(nèi)重復(fù)執(zhí)行一組特定的操作[3]。裝配線主要分為直線型裝配線和U型裝配線兩種[4]。相較于直線型裝配線,U型裝配線為工作站分配任務(wù)提供了更多的選擇,操作員不僅可以處理緊鄰任務(wù),還可以處理U型線兩側(cè)的任務(wù),近年來成為JIT生產(chǎn)系統(tǒng)的重要組成部分。

U型裝配線平衡問題(U-Shaped Assembly Line Balancing Problem,UALBP)是指在U型裝配線上,給定一組有限的任務(wù),每個任務(wù)具有固定的操作時間,將任務(wù)分配給有序的工作站,使任務(wù)滿足指定的優(yōu)先關(guān)系,并實現(xiàn)某些性能的最優(yōu)化[5-6]。UALBP主要分為兩類:type-1問題,給定裝配線節(jié)拍時間,最小化工作站數(shù)量,目標是在滿足一定生產(chǎn)率的同時利用盡可能少的工作站,當啟動新裝配線時就發(fā)生type-1問題;type-2問題,給定裝配線工作站數(shù)量,最小化節(jié)拍時間,目的是最大化具有固定工作站數(shù)量的現(xiàn)有裝配線的生產(chǎn)率水平,當使用現(xiàn)有裝配線重新設(shè)計裝配工藝時就存在type-2問題。與type-1問題相比,type-2問題更為常見,因為隨著市場需求變化,產(chǎn)品產(chǎn)量、種類也頻繁變動,企業(yè)需要根據(jù)現(xiàn)有的人員和設(shè)備進行裝配線調(diào)整,使生產(chǎn)能力適應(yīng)市場環(huán)境變化,提高生產(chǎn)柔性。

在競爭激烈的市場環(huán)境下,企業(yè)只有縮短產(chǎn)品生產(chǎn)時間,快速響應(yīng)客戶需求,才能贏得市場份額。使用U型裝配線能夠幫助企業(yè)提高生產(chǎn)效率,同時降低生產(chǎn)成本,是企業(yè)提高市場競爭力的一項重要舉措。然而,UALBP type-2問題對企業(yè)合理安排生產(chǎn)是一個難題,如果解決不好,會帶來工位負荷不均衡,裝配線堵塞,以及U型裝配線優(yōu)點不能充分利用等問題,從而嚴重影響裝配線產(chǎn)量的提高。因此,解決該問題對企業(yè)提高生產(chǎn)效率、降低生產(chǎn)成本,有著重要的意義。針對目前學術(shù)界缺乏UALBP type-2問題研究的現(xiàn)狀,本文以最小化節(jié)拍時間和工作站工作負荷絕對偏差為目標函數(shù)構(gòu)建數(shù)學模型,使用改進的遺傳算法作為求解方法,并利用Matlab實現(xiàn)算法,求出最優(yōu)工作站工序分配方案。本文的研究希望為此類問題提供一個完整的解決方案,為需要解決U型裝配線平衡type-2問題的企業(yè)人員提供可借鑒的思路和方法。

1 文獻綜述

UALBP屬于NP-hard組合優(yōu)化難題[7],目前的求解方法主要有精確算法(如線性規(guī)劃法、枚舉法、最短路徑法、動態(tài)規(guī)劃法等)和元啟發(fā)式算法(如遺傳算法,模擬退火算法,禁忌搜索,蟻群算法,粒子群算法等)。Miltenburg和Wijngaard最早開始研究簡單UALBP,提出了任務(wù)時間確定的動態(tài)規(guī)劃方法,并將其用于解決任務(wù)數(shù)量為11個的問題;文中也提出了一種位置權(quán)重法(RPWT)用于解決大規(guī)模任務(wù)問題,但任務(wù)數(shù)不超過111個[8]。隨后,Urban提出了一種整數(shù)線性規(guī)劃方法,旨在最小化站點數(shù)量,其所開發(fā)的精確解決方法也是較早進行簡單UALBP研究的典型代表之一[9]。國內(nèi)學者宋華明和韓玉啟提出一種基于遺傳算法的平衡優(yōu)化方法,以求解裝配線效率最大化問題[10]。Sabuncuoglu等使用改進蟻群算法求解簡單UALBP中的最小化工作站數(shù)量問題[11]。同樣針對工作站數(shù)量最小化問題,Li等提出一種混合整數(shù)線性規(guī)劃模型,并用面向工作站的改進蟻群優(yōu)化算法求解[12]。Celik等定義了隨機任務(wù)時間的U型裝配線再平衡問題,考慮了包括任務(wù)轉(zhuǎn)置成本、工作站開/關(guān)成本以及工作站操作成本在內(nèi)的裝配線再平衡總成本,以最小化總成本為目標構(gòu)建模型,并使用蟻群算法進行求解[13]。Oksuz等認為在U型裝配線中,工人的表現(xiàn)非常重要,工人的技能差異導(dǎo)致實際完成時間與假定的標準時間不同;因此,在模型中將工人的技能通過工人完成每個任務(wù)的性能系數(shù)反映到UALBP 中[14]。

目前解決type-2問題主要使用多目標優(yōu)化方法。Bortolini等以最小化裝配線節(jié)拍時間和人機工程學風險為目標,所構(gòu)建的模型不僅定義了工作站最優(yōu)任務(wù)分配,還定義了每個組件的最佳存儲位置[15]。Saif等考慮了由于不確定事件導(dǎo)致任務(wù)時間超過節(jié)拍的情況,模型以最小化節(jié)拍時間和工作站工作負荷平滑指數(shù)為目標函數(shù),并提出一種基于帕累托最優(yōu)的人工蜂群算法予以求解[16]。李英德和魯建廈以節(jié)拍最小化和負荷均衡為目標,提出了改進的蟻群算法,該算法在作業(yè)和工作站之間釋放信息素,利用局部更新和只對最優(yōu)路徑進行更新的全局更新策略進行信息素積累,同時構(gòu)造了包括最大、概率和隨機三種方式的混合搜索機制[17]。李明等提出一種改進的規(guī)則組合算法,規(guī)則包括操作選擇規(guī)則、操作分配規(guī)則、工位時間定界壓縮規(guī)則和變步長搜索規(guī)則[18]。

綜合來看,現(xiàn)有研究很少將UALBP和type-2問題聯(lián)系起來。典型的例子是鄭巧仙和何國良提出雙階段蟻群算法用于求解UALBP的type-2問題[19],但是存在收斂速度慢,運算時間開銷大,易陷入局部最優(yōu)等問題。大量研究表明遺傳算法(GA)在求解各類裝配線平衡問題中使用頻率最高,效果更好[20]。原因在于GA具有良好的普遍適用性,可以與其他算法相結(jié)合,能夠較好地解決復(fù)雜問題。例如Leu等最先展示如何使用GA求解簡單裝配線平衡問題,證實了GA的解決方案比傳統(tǒng)的啟發(fā)式解決方案有顯著改進[21];隨后Mamun等使用GA求解裝配線平衡type-1問題[22];Hwang和Katayama針對混合裝配線多目標平衡和排序問題,使用改進GA求解[23];韓煜東和董雙飛等運用自然數(shù)序列編碼策略和拓撲排序理論對GA進行改進并同樣求解混合裝配線多目標優(yōu)化問題[24];Hwang等提出一種基于優(yōu)先級的GA求解UALBP[25],Hamzadayi和Yildiz將模擬退火法與GA的適應(yīng)度相結(jié)合形成有效的適應(yīng)度函數(shù),用于計算混合UALBP的type-1問題[26]。但是,目前尚且缺乏使用GA求解type-2型UALBP的研究。另外,使用GA不是簡單的算法套用,而是需要根據(jù)問題特點進行算法設(shè)計,尤其是編碼解碼方式的重新設(shè)計。

綜上,本文針對UALBP type-2問題,運用GA作為求解方法,提出一種新的編碼解碼方式,使之能夠滿足所構(gòu)建模型的求解要求,并快速求得最優(yōu)解。算法通過兩個算例進行有效性驗證,并通過一個企業(yè)案例檢驗應(yīng)用效果。

2 數(shù)學模型構(gòu)建

裝配線平衡問題定義為:給定裝配產(chǎn)品的組合優(yōu)先關(guān)系圖,以一個有向無回路圖G=(T,P,t)表示;其中,T表示工序節(jié)點的集合,T={Ti|i=1,2,…,n};P表示節(jié)點之間連接的弧線的集合,即作業(yè)的優(yōu)先關(guān)系集合,P={(i,j)|Tj必須在Ti做完之后才能開始};t表示工序的操作完成時間,t={ti|i=1,2,…,n};所要解決的問題是確定一個節(jié)點集的劃分S={Sk|k=1,2,…,m},使得在給定工作站數(shù)量的情況下,裝配線效率最大和工作站工作負荷絕對偏差最小。裝配線平衡數(shù)學模型構(gòu)建需先設(shè)定基本假設(shè)、參數(shù)變量、目標函數(shù)和約束條件。分述如下:

2.1 模型基本假設(shè)

UALBP模型需滿足以下幾點假設(shè),(1)U型裝配線只組裝一種產(chǎn)品;(2)產(chǎn)品工序優(yōu)先關(guān)系已知;(3)工序操作完成時間是確定的,并且與指定的工作站無關(guān);(4)不允許并行任務(wù)和并行工作站;(5)不允許在制品庫存;(6)異步操作,忽略工人行走所花費的時間。

2.2 參數(shù)設(shè)定

記N為產(chǎn)品組裝工序總數(shù),i表示工序編號(i=1,2,…,N);K為裝配線工作站總數(shù)量,j表示工作站編號(j=1,2,…,K);Cm為理論最小節(jié)拍;ti為工序i的操作完成時間;P表示工序優(yōu)先關(guān)系約束集,P(x,y)表示工序x優(yōu)先于工序y操作;決策變量C為裝配線最小節(jié)拍,Sj為分配到工作站j的工序集;xij和yij為

2.3 約束條件與目標函數(shù)

本文研究的是UALBP type-2問題,即已知裝配線工作站數(shù)量,求最小節(jié)拍時間。由于裝配線效率與工作站數(shù)量、節(jié)拍時間相關(guān),因此可以選擇裝配線效率(LE)作為目標函數(shù)。在已知工作站數(shù)量的情況下,求使裝配線效率最大的最小節(jié)拍數(shù),因此模型的第一個目標函數(shù)可以寫為:

將任務(wù)分配給工作站時,通常使用的是單程決策規(guī)則。工序按順序列出,然后嘗試將它們分配給工作站。如果工序操作完成時間超過工作站剩余時間(節(jié)拍減去已分配工序占用時間),則考慮下一個工序。如果無法為工作站分配其他工序,則打開下一個工作站。這種分配方式的主要缺點是,工序大部分都分配給前面工作站,那么后面分配的工作站空閑時間可能會變得很大,故存在改進余地。因此本文的另一個目標是工作站工作負荷絕對偏差(ADW)最小化。當工作站工作負荷與生產(chǎn)節(jié)拍差距越小時,裝配線組裝速度越平穩(wěn),工時浪費越少,裝配線效率越高。因此,模型的第二個目標函數(shù)是:

模型約束條件為:

(1)分配約束,每個工序都必須被分配且只能分配到一個工作站。

(2)工位分配約束,每個工作站至少有一道工序。

(3)節(jié)拍約束,各個工作站工序總操作時間均不超過裝配線節(jié)拍。

(4)優(yōu)先關(guān)系約束,公式6和7表示工序既可以從前向后分配,也可以從后向前分配也可以前后兩個方向同時進行分配。

3 求解U型裝配線平衡問題的改進遺傳算法

將遺傳算法應(yīng)用于裝配線平衡問題求解,關(guān)鍵在于如何將求解問題與染色體建立聯(lián)系,即如何對染色體進行編碼解碼。編碼策略對遺傳算子,尤其是交叉和變異算子的設(shè)計有很大影響,進而影響產(chǎn)生解的可行性和多樣性。因此在使用GA求解裝配線平衡問題時,需建立一套編碼解碼規(guī)則。本文提出一種基于優(yōu)先級的編碼解碼方法,以及對應(yīng)的基于位置的映射交叉算子,使遺傳算法能夠滿足本文UALBP type-2問題的求解要求。

3.1 編碼與解碼

UALBP type-2問題求解過程可以分為兩個部分,工作站工序分配和工作站內(nèi)工序操作排序。以下以Jackson[27]的11個任務(wù)例子說明基于優(yōu)先級的編碼解碼方法。假設(shè)需要將N個工序分配給J個工作站,圖1給出了裝配線產(chǎn)品工序優(yōu)先關(guān)系圖?；趦?yōu)先級的編碼解碼方法分為兩個階段。

圖1 裝配線產(chǎn)品工序優(yōu)先關(guān)系圖Figure 1 Assembly line product process precedence relation

第一個階段是編碼的過程。首先,如圖2生成初始染色體,輸入對應(yīng)于工序編號的優(yōu)先級編號,確保每個工序具有不同的優(yōu)先級。然后,隨機交換兩個節(jié)點的優(yōu)先級以生成初始染色體。染色體的每個位置稱為基因,每個基因使用優(yōu)先關(guān)系圖中節(jié)點的優(yōu)先級,得到基于優(yōu)先級的染色體。

第二個階段是產(chǎn)生任務(wù)序列,也就是解碼的過程。解碼方法有三條分配規(guī)則:(1)打開一個新的工作站時,選擇候選節(jié)點中優(yōu)先級最大的那個節(jié)點,作為第一個分配的節(jié)點;(2)選擇哪一個節(jié)點作為下一個分配節(jié)點的依據(jù)是,候選節(jié)點中哪一個節(jié)點與已分配節(jié)點的操作完成時間之和最接近節(jié)拍時間;(3)當可選的節(jié)點中有兩個或兩個以上操作完成時間相同,則隨機選擇其中一個作為下一個分配的節(jié)點。

以圖2生成的初始染色體為例進行工序分配,假設(shè)節(jié)拍C=10,工作站數(shù)量為5,分配過程如下。

圖2 初始染色體生成過程Figure 2 O riginal chromosome generation process

步驟1:打開第一個工作站,工作站空閑時間等于節(jié)拍=10。

步驟2:根據(jù)工序優(yōu)先關(guān)系圖1,從圖的起始點開始分配;由于U型裝配線工序可以從前向后分配,也可以從后向前分配,也可以兩個方向同時進行分配,因此,節(jié)點1和11都可以作為起始分配點;選擇節(jié)點1和11,比較二者的優(yōu)先級;節(jié)點1的優(yōu)先級為7,節(jié)點11的優(yōu)先級為3,節(jié)點1的優(yōu)先級高于節(jié)點11,將節(jié)點1分配至第一個工作站,更新工作站空閑時間為=4;

步驟3:當節(jié)點1分配完后,緊后工序2、3、4、5就可以分配,加入候選節(jié)點集S候={2,3,4,5,11},比較哪個節(jié)點的操作時間最接近;節(jié)點2的操作時間為2小于空閑時間備選,節(jié)點3和節(jié)點4的操作時間超過工作站1的空閑時間,故排除;節(jié)點11的操作時間正好等于工作站1的空閑時間,因此選擇節(jié)點11作為第二個分配的節(jié)點,將其分配到工作站1,更新工作站1的空閑時間為0。

步驟4:打開第二個工作站,工作站空閑時間等于節(jié)拍=10;當節(jié)點11分配后,根據(jù)優(yōu)先關(guān)系圖,其緊后工序9和10也可以分配,將其加入候選集S候={2,3,4,5,9,10};比較節(jié)點的優(yōu)先級,分別為 2、10、4、5、6、1,節(jié)點 3 的優(yōu)先級最高,將節(jié)點3分配至第二個工作站,更新工作站空閑時間為5,更新候選集S候={2,4,5,9,10};工序7需要工序3、4、5均分配完成后才能分配,因此還不能加入候選集。

步驟5:比較候選集S候={2,4,5,9,10}中哪個節(jié)點的操作時間最接近;節(jié)點9和10操作時間均為5,此時隨機選擇其中之一,例如選擇節(jié)點9,將其分配至第二個工作站,更新工作站空閑時間為0,候選集更新為S候={2,4,5,7,10}。

步驟6:以此類推將每個節(jié)點都分配至工作站,每個工作站都至少有一道工序,最終得到的分配方案為S1={1,11},S2={3,9},S3={4,7},S4={2,5,10},S5={6,8},總空閑時間為4。

若要根據(jù)上述解碼方法向工作站分配工序,在type-1問題中,節(jié)拍是已知的,所以在向工作站分配工序時可以以節(jié)拍約束作為分配規(guī)則;在type-2問題中,盡管節(jié)拍是未知的,依然要滿足工作站總操作時間小于節(jié)拍的約束條件。在此,本文假設(shè)一個固定節(jié)拍,然后以一定的增量進行試算,直到找到最優(yōu)值,具體處理過程如下:

步驟1:初始化節(jié)拍時間,Cm為對應(yīng)工作站數(shù)量下的最小節(jié)拍,令C*=Cm+10。

步驟2:以C*為節(jié)拍約束,按照解碼方法將N個作業(yè)元素分配到K個工作站,得到每個工作站的總操作時間分別為T(S1),T(S2),T(S3),…,T(Sj),j=1,2,…,K;如果每個工作站的總操作時間T(Sj)≤C*,且所有工序均分配完畢,那么以最大工作站總操作時間max{T(Sj)}(1≤j≤K)作為該工序分配方案下的最小節(jié)拍C,算法停止;若存在工序未分配,則執(zhí)行下一步。

步驟3:令C*=Cm+20,重新分配工序至工作站,若新方案每個工作站總操作時間T(Sj)≤C*,且所有工序均分配完畢,那么以新方案的最大工作站總操作時間max{T(Sj)}(1≤j≤K)作為該工序分配方案下的最小節(jié)拍C,算法停止;否則令C*=Cm+30,再次分配工序,以此類推,節(jié)拍每次增加10個單位,直到所有工序完全分配完畢,算法停止。

3.2 適應(yīng)度函數(shù)

遺傳算法依據(jù)適應(yīng)度值大小對個體進行優(yōu)勝劣汰,因而適應(yīng)度函數(shù)指導(dǎo)著種群的進化方向。適應(yīng)度函數(shù)本質(zhì)上是問題的目標函數(shù)。本文的目標函數(shù)為最大化裝配線效率和最小化工作站工作負荷絕對偏差,對應(yīng)的適應(yīng)度函數(shù)為:

本文同時考慮了裝配線效率(E)和工作站工作負荷絕對偏差(V)兩個問題。裝配線效率(E)是最大化問題,值域在[0,1]之間;工作站工作負荷絕對偏差(V)是最小化問題,值域為大于等于0的整數(shù)。兩個函數(shù)求解目標不一致,值域分布也相差較大,由此得到的適應(yīng)度值可能不能體現(xiàn)個體的性能,因而將f2(V)改寫成1+f2(V)的倒數(shù),這樣二者都是最大化問題,且值域也都在[0,1]之間,消除了由于量綱不同帶來的影響。因此模型的適應(yīng)度函數(shù)寫為:

3.3 選擇、交叉與變異操作算子

3.3.1 選擇

本文以聯(lián)賽選擇作為選擇策略。基本思想是從當前群體中隨機選擇一定數(shù)量的個體,將其中適應(yīng)度值最大的保留到下一代,反復(fù)執(zhí)行該過程,直到下一代個體數(shù)量達到設(shè)定的種群規(guī)模。本文取聯(lián)賽規(guī)模為2,每次取出2個父代個體比較后再放回。

3.3.2 交叉

由于本文采用的是基于優(yōu)先級的編碼解碼方式,染色體上基因的數(shù)字表示的是任務(wù)節(jié)點在任務(wù)序列中的優(yōu)先級。只要保證所有基因座上的數(shù)字都不相同,具體數(shù)字為何值并不影響操作,優(yōu)先級數(shù)字只是用于確定候選節(jié)點中哪一節(jié)點優(yōu)先分配。因此,在設(shè)置交叉算子時,無需考慮新生成的個體是否滿足任務(wù)優(yōu)先關(guān)系,本文在這里提出一種基于位置的映射交叉,依然以Jackson[27]的例子為例,交叉過程如下。

步驟1:從交配池中隨機選取兩條染色體作為父代1和父代2,隨機生成一個[0,1]隨機數(shù);當隨機數(shù)小于交叉概率時,進行交叉操作,否則不進行交叉操作;確定需要交叉操作后,根據(jù)位串長度L,對每條染色體隨機生成兩個交叉點I1和I2(I1,I2∈[1,L-1],I1≠I2),將兩個父代染色體分為三部分,如圖3所示。

圖3 染色體交叉片段示意圖Figure 3 Chromosome crossover segments

步驟2:確定基于位置的映射關(guān)系,父代1中隨機產(chǎn)生的兩個交叉點確定了染色體的交叉片段;首先找到交叉片段中基因座上的數(shù)字在父代2中的先后順序,然后根據(jù)數(shù)字在父代2中的先后順序重新排列父代1的交叉片段,即可得到新的基因片段;父代2交叉片段上基因座的數(shù)字則根據(jù)其在父代1中的排列順序重新排序,如圖4所示。

圖4 基于位置映射的算子操作示意圖Figure 4 Location-based mapping crossover operator

步驟3:將映射后的交叉片段與原本的父代染色體拼接形成新的下一代。

圖5 子代染色體Figure 5 Offspring chromosome

3.3.3 變異

本文使用互換變異算子,對每一條染色體產(chǎn)生一個[0,1]隨機數(shù),當隨機數(shù)小于變異概率時,進行變異操作,否則不進行變異操作。確定需要變異操作后,在染色體上隨機選擇兩個不同的基因,將其位置對換,即可產(chǎn)生新的染色體,操作如圖6所示

圖6 變異算子操作示意圖Figure 6 M utation operator

3.4 算法改進有效性驗證

為了檢驗本文改進遺傳算法的有效性和準確性,從文獻資料中選擇經(jīng)典算例Heskia-28和Kilbridge-45作為實驗算例,利用本文提出的遺傳算法對其進行求解,并將結(jié)果與目前使用遺傳算法求得較好結(jié)果的Jonnalagedda等[28]的最優(yōu)計算結(jié)果進行對比。Heskia-28算例有28個作業(yè)元素,作業(yè)總完成時間為1024秒,Kilbridge-45算例包含45個作業(yè)元素,作業(yè)總完成時間為552秒。

算例均在CPU為Inter(R)Core(TM)i5-8250U@1.60 GHz,內(nèi)存為8 G的筆記本上運行,算法使用Matlab R2016b編程實現(xiàn)。算法參數(shù)設(shè)置為:n=100,Pc=0.8,Pm=0.08,最大迭代次數(shù)為500次,如果在100次連續(xù)迭代中,所得解的性能提高不超過1%,算法停止。對Heskia-28和Kilbridge-45算例各求解5次,將本文的計算結(jié)果與Jonnalagedda等文獻同樣使用遺傳算法求解的結(jié)果對比,如表1。

表1 本文改進遺傳算法與文獻[28]遺傳算法求解結(jié)果比較Table 1 Result com parison between our im proved GA and the GA in literature [28]

表1中第二列K表示給定的工作站數(shù)量;第三列C表示理想節(jié)拍時間,由工序總完成時間除以給定的工作站數(shù)量得到;第四列c表示文獻[28]求得的最優(yōu)解;第五列p表示文獻[28]求得的最優(yōu)節(jié)拍與理想節(jié)拍的偏差;第六列cˉ表示使用本文所提出的遺傳算法求解5次得到的節(jié)拍均值;第七列c表示5次結(jié)果中的最優(yōu)值;第八列p表示本文遺傳算法求得的最優(yōu)解與理想節(jié)拍的偏差;第九列ˉt表示5次計算的平均計算時間,計算時間由Matlab自動計時得到。

為證實本文遺傳算法的有效性,需與文獻[28]在計算規(guī)模、計算結(jié)果和計算效率三個方面進行比較。首先,二者共同求解上述的兩個算例,計算規(guī)模相同;其次是計算結(jié)果,對比第四列文獻[28]的最優(yōu)節(jié)拍和第七列本文的最優(yōu)節(jié)拍,在8個節(jié)拍時間中,本文的最優(yōu)解均比文獻[28]小,說明本文的遺傳算法求解結(jié)果優(yōu)于文獻[28]。再將本文的最優(yōu)節(jié)拍與第三列理想節(jié)拍相比,可以發(fā)現(xiàn)二者極為相近,偏差最大僅為2秒,一般而言,裝配線平衡節(jié)拍較難達到理想值,但是本文的遺傳算法卻能6次求得理想值,4次節(jié)拍時間僅偏差1秒,由此表明本文的遺傳算法求解結(jié)果優(yōu)于現(xiàn)有文獻[28]。最后是計算效率,本文算法在3～5分鐘內(nèi)便能計算完畢,而文獻[28]沒有說明計算時間,無法進行對比,但本文算法計算時間較短,在可接受范圍內(nèi)。

圖7展示了Kilbridge-45算例在第4次計算時迭代次數(shù)與目標函數(shù)的關(guān)系。從圖中可以看出,目標函數(shù)隨著迭代次數(shù)的增加而增大,最終收斂到一個最優(yōu)解。大部分情況下,算法在10代以內(nèi)就能找到最優(yōu)解。而當工作站數(shù)量為5、7時,算法早期收斂過快,陷入了早熟狀態(tài),但早熟最多持續(xù)80多代就跳出來了,繼而收斂到全局最優(yōu)解。由此表明本文所提出的遺傳算法不僅收斂速度快,而且能夠避免陷入局部最優(yōu),在進入早熟狀態(tài)時也可以較快跳出。綜合計算結(jié)果和收斂情況,可以得出結(jié)論,本文所提出的遺傳算法在求解U型裝配線平衡問題上是有效的。

圖7 K ilbridge-45算例計算收斂情況Figure 7 Convergence situation when calculating case K ilbridge-45

4 案例驗證

除了算例驗證之外,本文提出的模型和算法也被用于S公司實際的A1裝配線改造工作中。S公司是全球能效管理和自動化領(lǐng)域?qū)＜襍E公司設(shè)立在廈門的一個子公司,主要從事輸配電領(lǐng)域真空器和中壓斷路器生產(chǎn)制造的電氣企業(yè),成立于2005年,年產(chǎn)值近5億人民幣,產(chǎn)品銷往全國各地,部分出口到國外。S公司目前產(chǎn)量最大的兩條生產(chǎn)線是U型裝配線。為了提高產(chǎn)量,解決產(chǎn)能不足的問題,S公司計劃改進產(chǎn)量最大的A1總裝裝配線。改進中發(fā)現(xiàn),A1工位負荷不均衡和裝配線堵塞情況嚴重,這是裝配線不平衡的體現(xiàn),阻礙了產(chǎn)量的提高。故本文的研究問題屬于典型的UALBP type-2問題。

根據(jù)先期實地考察調(diào)研,獲得S公司A1裝配線所生產(chǎn)產(chǎn)品的工序優(yōu)先關(guān)系圖,如圖8所示。產(chǎn)品需經(jīng)過29道工序,圖中圓圈代表產(chǎn)品生產(chǎn)工序,圓圈旁邊的數(shù)字代表工序所需時長。據(jù)此工序圖,S公司原有的A1裝配線布局如圖9所示。

圖8 A1裝配線產(chǎn)品組合優(yōu)先關(guān)系圖Figure 8 Product combination precedence relation of the assembly line A1

圖9 A1裝配線優(yōu)化前裝配線配置情況Figure 9 Assembly line configuration situation before optim ization

根據(jù)本文提出的模型優(yōu)化此UALBP type-2問題,得到A1裝配線的工作站數(shù)為10時,最優(yōu)生產(chǎn)節(jié)拍數(shù)達到最小值193,此時裝配線效率達到98.7%。根據(jù)此最優(yōu)方案,可繪制出優(yōu)化后的裝配線工作站分配和工人分工情況,如圖10所示。將其與優(yōu)化前的裝配線相比,雖然優(yōu)化后的方案比優(yōu)化前增加了2個工人,但效率卻大大提高了。優(yōu)化前裝配線節(jié)拍時間為304秒,效率為78.33%,工人數(shù)為8人;優(yōu)化后裝配線節(jié)拍時間為193秒,裝配線效率為98.70%,工人數(shù)為10人,節(jié)拍時間降低111秒,效率提高26%。另外,A1裝配線每天可多生產(chǎn)53臺產(chǎn)品機構(gòu),產(chǎn)量提高了58.89%。

圖10 優(yōu)化后裝配線配置情況Figure 10 Assembly line configuration situation after optim ization

為了更方便查看優(yōu)化后裝配線布局以及各工作站具體分工,將圖10轉(zhuǎn)化成裝配線布局圖。裝配線布局圖如圖11所示,裝配線總長16.5m,一邊長7m,一邊長8m,即每個工位各長1m,U型彎道設(shè)置為1.5 m。部分工人按照地面指示標線在U型兩側(cè)走動完成一個工作站的零件裝配,工人行走路線之間不會出現(xiàn)交叉,且行走路線長度較短,減少了工時占用。工人在裝配線兩側(cè)來回走動工作,充分發(fā)揮了U型裝配線的優(yōu)點。由此可見,優(yōu)化后裝配線明顯優(yōu)于優(yōu)化前的裝配線,能夠解決S公司U型裝配線增產(chǎn)的問題。

圖11 優(yōu)化后裝配線布局圖Figure 11 Assembly line layout after optim ization

5 結(jié)論與展望

本文構(gòu)建了U型裝配線平衡type-2問題模型,通過平衡工作站工作負荷絕對偏差以平衡裝配線,并在已知工作站數(shù)量的情況下,求解使裝配線效率最大化的最小節(jié)拍,最終得到一條效率高,負荷均衡且運行順暢的U型裝配線。此外,在本文所提出的改進遺傳算法中,基于優(yōu)先級的編碼方法,能在遵循工序優(yōu)先級關(guān)系的前提下,實現(xiàn)基因的多樣性,避免無效基因的產(chǎn)生,減輕計算量,相對應(yīng)的解碼方式也能夠快速地將工序分配到工作站,且使工作站總完成時間盡可能接近節(jié)拍時間,最大限度地減少空閑時間,二者均可促使遺傳算法更高效地完成計算。

兩個經(jīng)典算例的求解結(jié)果表明,本文所提改進遺傳算法能夠在較短時間內(nèi)求得最優(yōu)解,結(jié)果精確度高于一般遺傳算法,且算法能夠避免陷入局部最優(yōu),具有較好的性能。在后續(xù)的研究中,可以將本文的算法推廣應(yīng)用于求解混合U型裝配線、雙邊裝配線以及考慮各種約束條件的各類裝配線的平衡問題。