電子液壓制動控制單元的混流裝配線平衡優化研究*

蔡啟明,李偉偉

(南京航空航天大學 經濟與管理學院,江蘇 南京 211106)

0 引 言

國內某汽車零部件制造商加大對零部件的研發與投入,新開設了汽車電子液壓制動控制單元的混流裝配線。

電子液壓制動系統是一種比機械制動更為高級的汽車安全技術,能夠大大縮短制動距離。而電子液壓制動控制單元是電子液壓制動控制系統的核心元器件,對電子液壓制動系統發出指令,直接影響汽車的制動性能。

混流裝配線要能夠滿足多品種、小批量的需求,是一種能將多種具有相似工業流程的產品進行混合生產的裝配線。但是,企業運用混流裝配線時涉及到混流裝配線的平衡問題,例如:工作站的數目過多,占用過大的面積,造成空間的浪費;各個工作站的裝配時間分布差距過大會導致生產瓶頸的出現,工人負荷不均,生產停滯;分配工人在不同的工作站,不同的分配方式帶來的成本也不一樣;裝配線的生產節拍,影響到企業能否完成企業的生產目標,等等。

目前,有很多學者關注混流裝配線的研究。姚午厚[1]研究了混流裝配線的多種優化算法對混流裝配線進行了平衡的排序,開發了智能家居行業混流裝配線平衡與排序系統。揣博君[2]以生產節拍、平滑指數和操作工人成本為多目標函數,用改進的遺傳算法來進行求解。宋春雷[3]以最小化完工時間、零部件消耗速率均衡化和相鄰產品相似度最大化為目標,建立了多目標投產排序模型,應用遺傳算法和Pareto排序思想對模型進行了求解。張志文[4，5]建立了以MODAPTS為基礎的標準工時系統,并結合線平衡理論建立了流水線平衡模型,再利用遺傳算法求解出了最優化方案。戴韜[6]對混流汽車液壓電子制動控制單元工藝過程進行了數學建模,采用優化遺傳算法進行了求解。蘇平等人[7]提出了一種綜合運用遺傳算法和仿真分析的混合裝配線平衡問題的求解方法。胡羅克等人[8]應用工業工程方法和仿真技術,對實際企業的裝配線做了系統科學的平衡分析和改善。BUKCHIN Y等人[9]通過對工人安排方案進行編碼,用遺傳變異尋求最小化工人空閑時間,提高了生產線的效率。LI Z等人[10]為了解決雙面混合裝配線的平衡問題,采用了多種啟發式算法綜合比較,證明了改進的迭代貪婪算法具有有效性。RASHID M[11]利用多目標離散粒子群優化算法來對整個混流裝配線平衡和排序的問題進行了建模和優化。SAHU A等人[12]提出了一種新的遺傳算法,提高了求解最小工作站數、瓶頸時間等參數的效率。AKPINAR S,SUNGUR B,DELICE Y等人[13-15]對混流裝配線的工人分配進行了優化。

但是上述學者關注的是混流裝配線的研究,還很少有人對汽車電子液壓制動控制單元的混流裝配線進行研究。

筆者通過建立以工作站數最小、裝配節拍最小以及各工作站裝配時間的均方差最小的多目標數學模型,利用改進的自適應遺傳算法加快收斂速度,得到滿意解,降低設備與庫存成本,減少各工作站裝配時間的波動,平衡生產線。

1 混流裝配線平衡理論和研究問題

1.1 基本概念

此處所涉及到的幾個關鍵的混流裝配線鍵術語,詳細基本概念可以參見參考文獻中的前4條文獻。

(1)工序優先關系圖。表示產品裝配過程中各個作業元素的先后關系。

A、B兩種產品的作業元素優先圖如圖1所示。

圖1 A、B產品的作業元素優先圖

(2)優先關系矩陣。將產品的作業元素優先圖用矩陣來表示。

上圖中A、B產品的優先關系矩陣如圖2所示。

圖2 A、B產品的優先關系矩陣

(3)綜合作業優先關系圖。A、B兩種產品的綜合作業優先關系圖如圖3所示。

圖3 A、B兩種產品的綜合作業優先關系圖

1.2 電子液壓制動控制單元的混流裝配線

通過對某汽車零部件公司的電子液壓制動控制單元的混流裝配線進行研究發現,該公司主要裝配3種不同型號的控制單元,包括零件的壓裝、電子控制-液壓控制-馬達合裝、綜合測試3大部分。其中,零件的壓裝是指利用壓力機對組件進行壓裝;電子控制-液壓控制-馬達合裝是指利用螺絲、壓力機將液壓控制單元、電子控制單元和電機三者連接;綜合測試部分包括對傳感器、油泵、制動器、電機等關鍵零件進行測試。

筆者繪制出3種制動控制單元的綜合作業優先關系圖,如圖4所示。

圖4 3種制動控制單元的綜合作業優先關系圖

已知A、B、C 3種產品的需求量D1、D2、D3分別為400、100、100,所以各產品的需求比例q1、q2、q3分別為2/3、1/6、1/6;測得每個產品各工序的時間,并求得在綜合作業優先關系圖(即在混流裝配線)中,裝配這3種產品時各個工序的時間,如表1所示。

表1 各工序的時間

2 裝配線平衡數學模型的建立

傳統的混流裝配線平衡主要包括3類:

(1)給定生產節拍,求解最小的工作站數;

(2)給定工作站數目,使得生產節拍最小;

(3)給定生產節拍和工作站數,使得各工作站負荷均衡。

汽車電子液壓制動控制單元的混流裝配線平衡問題在傳統問題的基礎上進一步拓展,筆者綜合考慮生產節拍、工作站數和工作站間負荷均衡3個指標,對混流裝配線進行統籌優化。

以下是具體的數學模型。

2.1 數學符號假設

TT—總有效生產時間;

D—所有產品的總需求量;

P—產品的種類;

Dp—第p種產品的需求量;

CTtheory—理論生產節拍,CTtheory=TT/D;

CTreal—實際生產節拍;

m—第m個作業元素,M—作業元素的總和;

qp—第p種產品的比例,qp=Dp/D;

w—第w個工作站,Wreal—實際工作站總數,Wtheory—理論工作站數;

tpm—第p種產品第m個工序所花費的標準時間;

2.2 目標函數

為了使得企業獲得更多的利潤,對混流裝配線平衡的研究已經不僅僅局限于單目標、雙目標甚至多目標以提升多方面效益,例如:工人成本費用最少、生產節拍最小、工作站數目最少、各個工作站的負荷差異最小、傳送帶停止時間最少、總切換時間最少,等等。此處主要根據企業的實際需求,設定了3個目標函數:工作站的數目最少、生產節拍最小、各工作站的負荷均衡。

(1)工作站的數目最少

各工作站的數目最少為混流裝配線平衡研究中的第一類問題,即在知道理論生產節拍時,確定最小的工作站的數目,來減少裝配所需的空間、工人成本,等等。根據企業當前的有效生產時間和在有效時間內需裝配的產品數量,來確定理論生產節拍,再根據綜合作業優先圖,得到總時間與理論的生產節拍的比值,得到理論上最少工作站的數目,即:

(1)

在進行作業元素分配時,會發現Wtheory太小,工作站的數目不能容納所有的作業元素,這時再逐個增加工作站的數量得到實際工作站數目Wreal,即:

Wreal=Wtheory+k

(2)

式中:k—新增的工作站數目。

(2)生產節拍最小

求生產節拍最小是混流裝配線平衡研究中的第二類問題,就是使得各工作站總時間的最大值最小化,它決定了能否在規定的時間內生產出足夠的產品數量來滿足客戶的需求。

所以,實際的生產節拍最小化為:

(3)

(3)裝配線平滑指數L最小

裝配線平滑指數L用以衡量各工作地之間的作業負荷分布是否均勻,它是混流裝配線中的第3類問題。裝配線平滑指數L越小,表明各個工作站之間的加工時間越接近,作業元素的分配越合理。

裝配線平滑指數L為:

(4)

2.3 約束條件

(1)每一個作業元素只能分配給一個工作站,即:

(5)

(2)每個工作站生產的時間不能超過CTtheory,即:

(6)

(3)必須要滿足各個作業元素之間存在著產品工藝上的先后順序,即:

(7)

式中:pre(m)—在工作元素m的緊前工序集合。

(4)各個決策變量必須為0或1,即:

xiw,xmw∈{0,1} ?i,m,w

(8)

2.4 目標函數權重的確定

因此,這是一個多目標的優化問題,絕大多數情況下,多個目標函數不能同時取得最優解。對于決策者而言,當目標函數達到一定的范圍即可認為是最優解。這里采用加權法來賦予3個目標函數不同的加權,使得多目標優化問題轉化為單目標的優化問題,而加權由決策者的偏好決定。

這里采用層次分析法(AHP)的判斷矩陣來確定各目標的權重,判斷矩陣由3個目標重要性程度的比值組成。判斷矩陣的元素一般用數字1～9來確定,代表不同的重要性程度。工作站的數目影響了混流裝配線的占地面積、工人成本、空閑時間,等等。

實際生產節拍的大小決定了單位時間里生產的產品數量以及產品能否按時交付給客戶,其重要性不言而喻,明顯重要于各個工作站之間的負荷分配是否均衡。

因此,筆者構造多目標的判斷矩陣如表2所示。

表2 目標函數的判斷矩陣

根據判斷矩陣求解,可得到3個目標的權重分別為0.57、0.33和0.1。此時,多目標優化就轉化成了單目標優化,即:

minf=0.57Wreal+0.33CTreal+0.1L

(9)

(10)

3 自適應遺傳算法求解

該類數學模型屬于NP-hard問題,一般利用啟發式算法求解。遺傳算法就是一種啟發式算法,根據適者生存的原則,利用適應度函數來對方案進行評價,從而擇優汰劣;各個方案之間再進行交叉、變異生成更好的方案,再次進行擇優劣汰,如此迭代一定的次數得到最優方案[16]。

遺傳算法流程圖如圖5所示。

圖5 遺傳算法流程圖

3.1 編碼方式

自適應遺傳算法的第一步就是確定編碼的方式,合理的編碼方式便于計算適應度,簡化交叉和變異操作,提升算法的執行效率。編碼方式分為二進制編碼、整數編碼、實數編碼等。不同于標準遺傳算法的編碼方式,筆者采用基于綜合作業優先圖的整數編碼,各個位置上的基因排列必須遵循作業元素的先后順序,并且每個工序只能出現一次,染色體的長度與工序的個數相等。

根據綜合作業關系優先矩陣來得到一條染色體的基因序列,其編碼過程分為兩步:

(1)創建s=Judge(PA)函數,用于生成可以分配的工序s,s是函數返回值,并且這些s滿足當前綜合作業關系優先矩陣條件。假設PA為綜合作業關系優先矩陣,y代表工序的個數,i代表工序的編號。具體操作過程如下:

Step1:i=1,判斷PA第i列是否全部為0,如果是則將工序i放入s中去,否則執行Step2;

Step2:i=i+1,重復Step1,直到i=y結束,將此時的s作為函數的返回值;

(2)創建c=P_chrom(PA)函數,用于生成當前PA條件下的一條染色體c,染色體c是函數返回值。y代表工序的個數,j代表s的長度,i代表工序的編號。具體操作過程如下:

Step1:i=1,利用Judge(PA)函數得到s;

Step2:從s中隨機抽取一個工序t放入染色體c中;

Step3:使得PA中的t列為inf,t行為0;

Step4:i=i+1,重復Step1、Step2、Step3,直到i=y結束,將此時的c作為函數的返回值。

下面將圖2中A產品的優先關系矩陣作為PA,舉例說明編碼操作:

Step1:i=1,利用Judge(PA)函數得到s={1,5};

Step2:從s中隨機抽取一個工序5放入染色體c中;

Step3:使得PA中第5列為inf,第5行為0。此時,PA作業優先關系矩陣如圖6所示。

圖6 PA作業優先關系矩陣

Step4:i=2,利用Judge(PA)函數得到s={1};

Step5:從s中隨機抽取工序1放入c中;

Step6:使得PA中第1列為inf,第1行為0。此時,PA作業優先關系矩陣如圖7所示。

圖7 PA作業優先關系矩陣

Step7:重復以上步驟直到安排完所有工序。

最終,可以隨機得到A產品的一條染色體如圖8所示。

圖8 A產品的一條隨機染色體

3.2 種群初始化

種群初始化就是確定隨機產生的染色體數目。種群數目過大會導致算法收斂過早,并且造成算法運行時間變長,效率降低。種群數目過小可能使得算法“早熟”,導致適應度陷入局部最優解。因此,要合理確定種群的數目。筆者設置初始種群pop的大小n為80,具體初始化種群的算法如下所示:

Step1:i=1,利用c=P_chrom(PA)函數生成一條染色體作為pop的第i行;

Step2:i=i+1,當i到達種群的大小n時,算法結束。

3.3 計算適應度與譯碼

在自適應遺傳算法中,可以根據適應度f′來判斷染色體的優劣和靠近最優解的程度。因為此處選擇了輪盤賭選擇法,適應度大的染色體,遺傳到下一代的概率大;反之,概率則小。適應度值就像是數學模型中的目標函數,適應度越大的染色體越接近最優解。而在式(9)中,目標函數的最優解是一個最小值,因此需要對目標函數進行轉化。該文以f′=50-0.57Wreal+0.33CTreal+0.1L作為適應度函數。

當已知一個種群時,并不能比較染色體之間的優劣。因為種群的染色體中包含的信息只有基因的排列順序(即工序的順序),比較種群的優劣需要最小工作站數Wreal、實際生產節拍CTreal和裝配線平滑指數L的信息。譯碼的操作就是根據一條染色體排列的順序求得Wreal、CTreal、L。

3.4 選擇

選擇算子是為了保留優質染色體,淘汰劣質染色體。該文選擇了輪盤賭法選擇法作為選擇算子,它模擬博彩游戲的輪盤賭,一個輪盤被劃分為n個扇形(n為種群的大小),而每個扇形的面積與它所表示的染色體的適應度成正比;為了選擇種群中的個體,設想有一個指針指向輪盤,轉動輪盤,當輪盤停止后,指針所指向的染色體被選擇。因為一個染色體的適應度越大表示該染色體的扇形面積越大,所以它被選擇的可能性也就越大。

具體操作如下:

Step1:計算種群各個染色體的適應度fi;

Step4:在[0,1]區間產生一個隨機數r;

Step5:若r

Step6:重復Step4和Step5共n次。

3.5 交叉

顯然,一定數量種群的染色體,一般很難得到最優解。那么,在種群數量固定的情況下,要得到或者是接近最優解,就要使染色體的基因相互交叉,就是使種群多樣化的一種算子。此處的交叉操作不同于一般遺傳算法中染色體的交叉,隨意地交叉會破壞優秀染色體中符合綜合作業優先關系的基因。因此,筆者采用了兩點交叉的方式。

為了更方便理解,下面用一個例子來說明本文交叉算子的思想,假設父代1和父代2的基因排列順序均滿足某個作業裝配工序的優先順序,如圖9所示。

圖9 兩點交叉算子的示意圖

Step1:當rand

pc的表達式為：

(11)

式中：pcmax—最大交叉概率;pcmin—最小交叉概率;i—當前迭代次數;m—總迭代次數。

Step2:逐個找到變量temp中的成員在Chrom2(即父代2)中的位置,存入變量index中(index的含義是Chrom1交叉的染色體在Chrom2中的索引),即index={1,7,2,3};

Step3:將index從小到大進行排序,得到新的index={1,2,3,7}(新的index即為temp在Chrom2中的排列順序,有Chrom2(index)={3,5,6,4},即為圖9中箭頭所指父代2的基因);

Step4:在Chrom1中Cpoint1到Cpoint2基因位置存入Chrom2(index)={3,5,6,4},生成子代1。

Step5:在Chrom2中的索引位置即index={1,2,3,7},分別存入temp={3,4,5,6}。生成子代2。

新生成的子代1和子代2不僅豐富了種群的多樣性,增加了搜索的范圍,還符合綜合優先關系圖的優先順序。對于更加復雜染色體的交叉算子,原理與這個例子一致。

3.6 變異

為了豐富種群的多樣性,增加搜索范圍,此處引入變異算子。變異就是使得染色體中的某個基因發生變化,然而平凡的變化會破壞基因應符合的順序,產生不可行解。為了消除不可行解,筆者采用了考慮綜合作業優先關系矩陣的單點變異。

為了方便更好地理解變異算法,下面舉例說明,已知某混流裝配線的綜合作業優先關系圖和綜合作業優先關系矩陣如圖10、圖11所示。

圖10 綜合作業優先關系圖

圖11 綜合作業優先關系矩陣

假設已知一條滿足該裝配順序的染色體c={1,2,3,4,5,6},變異思想主要是隨機產生一個變異點mpoint;前面的基因序列保持不變,將mpoint處基因及后面的基因序列重新排列。

解決這個例子算法的步驟如下:

Step1:當rand

圖12 單點變異示意圖

pm的表達式為：

(12)

式中：pmmax—最大變異概率;pmmin—最小變異概率;i—當前迭代次數;m—總迭代次數。

Step2:當基因1、2保持不變,求出此時的綜合作業優先矩陣PA如圖13所示。

圖13 變異后的綜合作業優先關系矩陣

Step3:用3.1中的Judge(PA)函數得到s={3,4};

Step4:隨機選擇一個基因,這里假設選擇基因4放入染色體3號位中;

Step5:再保持基因1、2、5不變,求出此時的綜合作業優先矩陣PA;

Step6:重復上述步驟,最終得到一條變異后的染色體如圖14所示。

圖14 變異后的染色體

新生成的染色體再次豐富了種群的多樣性,也增加了算法的搜索范圍,防止算法陷入局部最優解。對于該文更加復雜染色體的變異算子原理與此例一致。

4 自適應遺傳算法運行結果分析

4.1 參數設置

第一次試驗將種群大小設定為n=80,迭代次數m={100,200,300,400},最大交叉概率為0.9,最小交叉概率為0.5,最大變異概率為0.01,最小變異概率為0.005,目標在8 h生產A、B、C 3種產品共600件。

MATLAB的執行結果,不同的迭代次數與適應度函數值的關系,如圖15所示。

圖15 不同的迭代次數與適應度函數值的關系

圖15是種群為80時,不同的迭代次數與適應度函數值的關系。

MATLAB的執行結果,即不同的迭代次數對適應度函數值的影響,如圖16所示。

圖16將圖15中的4條曲線放入一張圖中,從而更好地觀察適應度函數收斂的重合程度。結果發現,當迭代次數達到60左右時,適應度函數值收斂,再增加迭代的次數,適應度函數值無明顯的變化。因此,綜合考慮到算法的效率和局部最優解的情況,筆者將迭代的次數設定為100。

第二次試驗將種群大小設定為n={80,160,240,320},迭代次數m=100,最大交叉概率為0.9,最小交叉概率為0.5,最大變異概率為0.01,最小變異概率為0.005,目標在8 h生產A、B、C 3種產品共600件。

執行的結果,即不同種群下適應度函數值和迭代次數的關系,如圖17所示。

圖17 不同種群下適應度函數值和迭代次數的關系

當種群為80時,適應度函數值在100次迭代過程中可以完全收斂,而增加種群的數目到160、240、320,與種群為80時的收斂值幾乎一致;并且沒有搜索到更優解,只是略微增加了適應度函數的收斂速度?？紤]到算法的效率和局部最優解,將種群的大小設置為80。

4.2 運行結果分析與對比

在具體固定了種群的大小和迭代的次數后,就可以進行多次試驗來求得最優解。

筆者進行了30次試驗,選取4次在MATLAB中的實驗結果,適應度函數值和迭代次數的關系曲線如圖18所示。

圖18 適應度函數值和迭代次數的關系曲線

從圖18可以看出,雖然初始種群的適應度函數值不一樣,但在迭代的過程中不斷地選擇、交叉、變異后,適應度函數值都收斂于31與31.5之間的某個數。

筆者進行了30次試驗,選取4次在MATLAB中的實驗結果,目標函數值和迭代次數的關系圖如圖19所示。

圖19 目標函數值和迭代次數的關系圖

在圖19中可以發現與圖14之間存在著聯系,因為在3.3節中設計適應度函數值時,將目標函數值進行了轉化,即f′=50-f,所以適應度函數和目標函數關于y=25對稱?？梢园l現在迭代過程中,目標函數值收斂于18.5和19之間的某個數。

利用MATLAB中繪制傳統遺傳算法得到的工序分配方式,如圖20所示。

圖20 優化前各工序在8個工作站的分配柱狀圖

自適應遺傳算法在30組實驗中求得優化后的工序分配方式,如圖21所示。

圖21 優化后各工序在7個工作站的分配柱狀圖

最優解顯示最小工作站數Wreal為7,實際生產節拍CTreal為44.33,裝配線平滑指數為2.47,目標函數值f為18.87,適應度函數值f′為31.13,在規定有效工作時間內可以生產出649件產品,超出目標產量49件。

分別用傳統遺傳算法與自適應遺傳算法來解決混流裝配線平衡問題,得到優化前后的參數對比如表3所示。

表3 優化前后混流裝配線的參數對比

由表3可知:

(1)減少了1個工作站,降低了工人與設備的費用;

(2)平滑指數降低了59.36%,使得各個工作站之間的裝配時間波動更小,裝配作業的負荷更加均衡;

(3)實際生產節拍增加了2.66秒/件,使產量減少42件;

(4)在完成目標產量600件的基礎上還降低了庫存量46.15%,降低了庫存成本。

5 結束語

針對汽車電子液壓制動控制單元的混流裝配線平衡問題,筆者建立了裝配線的多目標數學模型,利用MATLAB編寫了改進后的自適應遺傳算法,并對此進行了求解,通過調整參數設置得到了其最優解,最后將其與傳統的遺傳算法進行了對比分析。

研究結果表明:

(1)利用自適應遺傳算法對汽車電子液壓制動控制單元的混流裝配線平衡進行優化,其效果優于傳統遺傳算法;

(2)優化后,減少了1個工作站,平滑指數降低了59.36%,生產節拍增加了2.66秒/件,完成目標產量并降低庫存,大大降低了混流裝配線工人與設備的成本,提升了混流裝配線的平衡率。

在后續的研究過程中,筆者將利用NSGA-II算法來解決多目標決策的問題,使得各個目標函數都盡可能能找到最優的解集,并將其應用于汽車電子液壓制動控制單元的混流裝配線平衡。