基于有向網(wǎng)絡(luò)的雙U型裝配線平衡實驗與分析

焦玉玲,徐良成,王占中,張 鵬

(吉林大學(xué) 交通學(xué)院,長春130022)

0 引 言

流水化裝配線是進(jìn)行大規(guī)模生產(chǎn)制造的高效生產(chǎn)方式。在社會需求逐漸變?yōu)槎嗥贩N、小批量的客戶定制化和產(chǎn)品多樣化的情況下,生產(chǎn)制造企業(yè)需要提高裝配線機(jī)動性、柔性。裝配線平衡問題(Assembly line balancing problem,ALB問題)[1]就是對整個生產(chǎn)裝配線進(jìn)行研究,提高裝配線平衡率。流水裝配線組織設(shè)計是在滿足節(jié)拍和作業(yè)之間先后順序關(guān)系的前提下,組合并分配作業(yè),使各工作站工時盡可能相等,目的是減少裝配線的閑置時間,提高工人和設(shè)備的利用率。裝配線平衡(ALB)問題的研究主要分為兩種情況:一種是給定裝配線節(jié)拍,最小化裝配線上的工作站數(shù);另一種是給定裝配線的工作站數(shù),最小化裝配線的節(jié)拍[2]。

1955年Salveson[3]提出了線性規(guī)劃求解模型,對于裝配線平衡問題采用解析法來描述,給出了求解裝配線平衡問題最優(yōu)解的求解過程。Jackson[4]在1956年提出求解裝配線平衡問題的枚舉法,利用枚舉法搜索在給定生產(chǎn)節(jié)拍的條件下工作站的最小數(shù)目,以此獲得最優(yōu)解。Uˇgur等[5]對于求解混合生產(chǎn)線平衡問題通過構(gòu)造并行線路,采用0-1整數(shù)規(guī)劃模型,算法主要通過引入新的參數(shù)來減少目標(biāo)函數(shù)中的決策變量和約束條件中約束的數(shù)目。Miltenburg等[6]介紹了傳統(tǒng)的直線型裝配線和U型裝配線并將兩種裝配線進(jìn)行比較,指出U型裝配線的優(yōu)點。Yegul等[7]介紹了一種混合的U型雙邊裝配線,并提出了多通道隨機(jī)分配算法,解決了小型的雙邊裝配線平衡問題,求出分配任務(wù)的順序和裝配線所需的最小工作站數(shù)目。Mura等[8]使用遺傳算法解決多約束條件下裝配線平衡過程中最小化工作站總數(shù)問題,最后用案例說明了算法的可行性。Kucukkoc等[9]介紹了一種新型的平行U型裝配線,使用啟發(fā)式算法求解最小工作站數(shù),但對于大型裝配線平衡問題,求解較為費時。本文引入有向網(wǎng)絡(luò)法來解決大型計算的計算效率。

為了研究產(chǎn)品的流水裝配線組織設(shè)計和裝配線平衡問題,在對四驅(qū)車車模進(jìn)行產(chǎn)品結(jié)構(gòu)、裝配工藝流程分析的基礎(chǔ)上,在實驗室流水裝配線上模擬5個工作站分配裝配工序測得流水作業(yè)節(jié)拍,據(jù)此節(jié)拍建立數(shù)學(xué)模型,應(yīng)用有向網(wǎng)絡(luò)圖求解最小化U型裝配線上的工作站數(shù),并設(shè)計了雙U型裝配線。

1 數(shù)學(xué)建模

1.1 問題描述

本文研究兩條平行的U型裝配線,見圖1,用L1、L2分別表示兩條U型裝配線,將U型裝配線工作區(qū)域在平面上分成了4行(z＝1,2,3,4)和不同的列(q＝1,2,…,Q;Q為裝配線隊列的總數(shù)),工作站用表示。企業(yè)可以根據(jù)產(chǎn)品結(jié)構(gòu)和實際生產(chǎn)情況進(jìn)行不同的工作站劃分。兩條相鄰的裝配線之間的工作站稱為多線工作站(例如:等),位于多線工作站的操作員可以在兩條線上完成作業(yè);位于裝配線內(nèi)部(圖中顯示為L2)的工作站叫做交叉工作站(例如:等),位于這些工作站的操作員可以在此區(qū)域內(nèi)執(zhí)行作業(yè);同樣,也有常規(guī)工作站(例如:等),在該工作站中操作員只可以在一個特定裝配線和區(qū)域執(zhí)行工作。

圖1 平行U型裝配線系統(tǒng)示意圖Fig.1 Schematic diagram of parallel U-shaped assembly line system

對于裝配線平衡問題本文進(jìn)行第一種情況研究,即給定裝配線節(jié)拍,最小化裝配線上的工作站數(shù)目。設(shè)定生產(chǎn)節(jié)拍用r表示,作業(yè)元素集合用F＝{1,2,…,k}表示,F k表示第k個作業(yè)元素,作業(yè)元素時間用T表示,工作站用S表示,S＝{1,2…,N},S i表示第i個工作站所包含的作業(yè)元素集合。

1.2 數(shù)學(xué)模型

在確定了生產(chǎn)節(jié)拍和作業(yè)元素時間之后,裝配線平衡就是在滿足約束條件的前提下,使工作站數(shù)目達(dá)到最小,并使閑置時間最小,裝配線的平衡率達(dá)到最高。故裝配線組織必須滿足以下約束條件:

(1)同一個作業(yè)不能同時分配給兩個工作站,即不可能出現(xiàn)S1＝{1,2,3},S2＝{1,4,5}。

(2)所有作業(yè)都必須分配到工作站,即所有工作站作業(yè)元素集合的并集等于F。

(3)每個工作站內(nèi)作業(yè)元素時間之和必須小于或等于生產(chǎn)節(jié)拍。

(4)所有作業(yè)元素必須按照作業(yè)元素優(yōu)先關(guān)系圖來分配到工作站。

建立裝配線平衡問題數(shù)學(xué)模型如下。

目標(biāo)函數(shù):

約束條件:

式中:N為工作站數(shù)目;r為生產(chǎn)節(jié)拍;k為第k個作業(yè)元素;T1(F k)、T2(F k)分別為分配給裝配線L1、L2的作業(yè)元素F k的作業(yè)時間。

2 模型求解

2.1 有向加權(quán)網(wǎng)絡(luò)求優(yōu)先關(guān)系權(quán)值

裝配線中每個作業(yè)的分配都與作業(yè)元素緊前關(guān)系及后續(xù)作業(yè)數(shù)量有關(guān)。對于作業(yè)元素之間的優(yōu)先關(guān)系,根據(jù)有向圖理論,用優(yōu)先關(guān)系矩陣來表示作業(yè)之間的緊前關(guān)系。故引入一個K維(K為作業(yè)元素個數(shù))矩陣P(i,j),表示各作業(yè)元素間的緊前關(guān)系,其矩陣元素可定義如下:

根據(jù)優(yōu)先關(guān)系圖建立P矩陣,根據(jù)作業(yè)時間表建立T列陣,P與T相乘求得T(F k),再求優(yōu)先關(guān)系權(quán)重值,步驟如下:

(1)計算每一個作業(yè)元素k的時間位置權(quán)重F tk。

式中:W k為作業(yè)元素k的后續(xù)作業(yè)元素集合;NT lk為作業(yè)元素k的作業(yè)時間與全部后續(xù)作業(yè)元素時間之和,l為第l條U型裝配線,l＝1或2;T(F k)為第k個作業(yè)元素的時間;T(F kp)為第k個作業(yè)元素的后續(xù)作業(yè)時間。

在裝配線上,根據(jù)NT lk值按升序排列所有的作業(yè)元素,對于NT lk值最小的作業(yè)元素賦予時間位置權(quán)重F tk＝1,對于NT lk值次小的作業(yè)元素賦予時間位置權(quán)重F tk＝2,如果作業(yè)元素NT lk值相同,則被賦予相同的時間位置權(quán)重F tk。依次類推,直到所有作業(yè)元素都被賦予F tk。

(2)計算每一個作業(yè)元素k的后續(xù)作業(yè)量權(quán)重F hk。

式中:N H lk為作業(yè)元素的后續(xù)作業(yè)元素個數(shù)。

在裝配線上,根據(jù)NH lk值按升序排列所有的作業(yè)元素,對于N H lk值最小的作業(yè)元素賦予后續(xù)作業(yè)量權(quán)重F hk＝1,對于NH lk值次小的作業(yè)元素賦予后續(xù)作業(yè)量權(quán)重F hk＝2,如果作業(yè)元素N H lk值相同的,則被賦予相同的后續(xù)作業(yè)量權(quán)重F hk。依次類推,直到所有作業(yè)元素都被賦予F hk。

(3)計算每一個作業(yè)元素k的優(yōu)先關(guān)系權(quán)重值R pk。

2.2 啟發(fā)式算法分配作業(yè)元素

計算出作業(yè)元素的優(yōu)先關(guān)系權(quán)重值R pk后,列出未分配的作業(yè),從第一個工作站開始分配,由當(dāng)前的工作站決定兩條裝配線上可利用的作業(yè)元素,生成可利用的作業(yè)列表。

檢查分配作業(yè)的原則是:作業(yè)未被分配;作業(yè)沒有緊前(緊后)作業(yè),或者它的所有的前任作業(yè)(后任作業(yè))都被分配,并且作業(yè)是按照優(yōu)先關(guān)系圖表的前后關(guān)系所分配的;當(dāng)前工作站的剩余容量(時間)足夠執(zhí)行該作業(yè)。

每當(dāng)一個作業(yè)被分配時,作業(yè)列表就會更新一次,選擇另一個新的作業(yè)并且分配給當(dāng)前工作站,一直持續(xù)到當(dāng)前工作站沒有容量(時間)來完成作業(yè)。當(dāng)從優(yōu)先關(guān)系圖前部分配作業(yè)元素時,選擇優(yōu)先關(guān)系權(quán)重最大的作業(yè)元素,當(dāng)從優(yōu)先關(guān)系圖后部分配作業(yè)元素時,選擇優(yōu)先關(guān)系權(quán)重最小的作業(yè)元素,同時必須兼顧作業(yè)元素時間,使當(dāng)前工作站的閑置時間盡可能小,滿足目標(biāo)函數(shù)。

2.3 裝配線的性能分析

裝配線平衡問題的效果采用時間損失系數(shù)ε、平衡率BP和平滑系數(shù)SI評價[9]。平衡率衡量整個裝配過程中裝配線平衡和對時間利用效率的指數(shù)。時間損失系數(shù)衡量裝配線對時間的有效利用程度。時間平滑系數(shù)衡量裝配線負(fù)荷的均勻程度。因此,建立裝配線平衡的效果評價數(shù)學(xué)模型為:

式中:Tei為每i個工作站被分配作業(yè)元素的作業(yè)時間總和;Temax為工作站中作業(yè)時間總和的最大值。如果最大值等于節(jié)拍,Temax取節(jié)拍,系統(tǒng)達(dá)到最優(yōu);如果小于節(jié)拍,則還可以繼續(xù)優(yōu)化。

3 算 例

選擇兩個結(jié)構(gòu)工藝相似的四驅(qū)車車模(以下簡稱車模1、車模2)進(jìn)行實驗,先產(chǎn)品結(jié)構(gòu)分析,再裝配工藝流程設(shè)計,分別在實驗室流水裝配線L1和L2上進(jìn)行裝配實驗,測得生產(chǎn)節(jié)拍r＝10 s。裝配作業(yè)元素工作內(nèi)容及時間見表1。車模1、車模2的作業(yè)總時間分別為44 s和41 s。

表1 作業(yè)元素工作內(nèi)容及時間表Table 1 Information and time table of job elements

根據(jù)工作內(nèi)容及工藝流程確定了作業(yè)元素及緊前關(guān)系,作業(yè)元素流程圖見圖2。

3.1 直線型裝配線

根據(jù)有向網(wǎng)絡(luò)理論求出作業(yè)元素的優(yōu)先關(guān)系權(quán)重,計算結(jié)果見表2。

圖2 作業(yè)元素優(yōu)先關(guān)系圖Fig.2 Priority relation graph of job elements

表2 作業(yè)元素優(yōu)先關(guān)系權(quán)重表Table 2 Priority relation weight table of job elements

在實驗室兩條平行直線型裝配線上對車模1和車模2進(jìn)行裝配及組織設(shè)計。車模1和車模2所需的最低工作站數(shù)均為5。根據(jù)啟發(fā)式算法分配作業(yè)元素,其裝配線工作站布置及作業(yè)元素分配見表3。

直線型裝配線設(shè)計平面簡圖見圖3。根據(jù)裝配線的平衡效果評價模型,綜合考慮兩條直線型裝配線的平衡率BP＝85%,總的閑置時間為15 s。

表3 作業(yè)元素分配信息及時間表Table 3 Information and time table of job elements

圖3 直線型裝配線工作站布置圖Fig.3 Workstation layout diagram of straight line-shaped assembly line

3.2 雙U型裝配線

對現(xiàn)有實驗室裝配線進(jìn)行改進(jìn),采用兩條U型裝配線平行布置。根據(jù)表2中優(yōu)先關(guān)系權(quán)重對裝配線分配作業(yè)元素。具體分配步驟見表4。從表4中可見,當(dāng)前工作站的剩余時間是在每一個作業(yè)元素分配到當(dāng)前工作站后確定。在每個作業(yè)元素分配后,算法從更新后的任務(wù)列表中繼續(xù)挑選和分配下一個作業(yè)元素,持續(xù)進(jìn)行到當(dāng)前工作站沒有足夠的剩余時間完成任何一個作業(yè)。繼續(xù)將任務(wù)分配到下一設(shè)定工作站,所有作業(yè)元素全部分配到兩條裝配線上。

裝配線工作站分配結(jié)果見圖4,分成了9個工作站,裝配線的平衡率BP＝94.4%,閑置時間為5 s。

表4 分配步驟Table 4 Assignment steps

圖4 平行的U型裝配線工作站布置圖Fig.4 Workstation layout diagram of parallel U-shaped assembly line

3.3 直線型和U型裝配線平衡效果比較

根據(jù)計算結(jié)果,將直線型和U型兩種類型的裝配線平衡效果進(jìn)行比較,結(jié)果見表5。

從表5可以看出,與直線型相比較,U型裝配線工站數(shù)減少1個,裝配線的平衡率提高了11.1%,時間損失系數(shù)降低了62.6%,時間平滑系數(shù)降低了64.4%。

表5 兩種裝配線平衡效果比較表Table 5 Comparison table of balance effect of two kinds of assembly lines

4 結(jié) 論

(1)通過實驗獲得數(shù)據(jù),對裝配線平衡建立數(shù)學(xué)模型,應(yīng)用有向網(wǎng)絡(luò)理論求解,計算結(jié)果正確有效。

(2)裝配線平衡方法有效,引入有向網(wǎng)絡(luò)實現(xiàn)網(wǎng)絡(luò)圖的程序計算,為大型網(wǎng)絡(luò)計算提供了一種新途徑,為企業(yè)裝配線平衡與優(yōu)化提供快速計算方法。

(3)雙U型裝配線設(shè)計有效,與直線型實驗室算例比較,平衡率提高了11.1%,并節(jié)省了1個工作站。不僅節(jié)約成本,而且提高了實驗室車模的裝配效率,加快車模零部件流通,提高了實驗室的實驗設(shè)備的使用效率,為提高流水裝配線平衡提供了有效的新方法。

[1]陳榮秋,馬士華.生產(chǎn)運作管理[M].2版.北京:高等教育出版社,2009:17-115.

[2]宋華明,韓玉啟.基于遺傳算法的U型生產(chǎn)線平衡[J].系統(tǒng)工程報,2002,17(5):424-429.Song Hua-ming,Han Yu-qi.Balance of U-shaped production line based on genetic algorithm[J].Systems Engineering,2002,17(5):424-429.

[3]Salveson M E.The assembly line balancing problem[J].Journal of Industrial Engineering,1955,6(3):18-25.

[4]Jackson J R.A computing procedure for a line balancing problem[J].Management Science,1956,2(3):261-271.

[5]Uˇgur?zcan,Hadi G?k?en,Bilal Toklu.Balancing parallel two-sided assembly lines[J].International Journal of Production Research,2010,48(16):4767-4784.

[6]Miltenburg G J,Wijingaard J.The U-line line balancing problem[J].Management Science,1994,40(10):1378-1388.

[7]Yegul M F,Agpak K,Yavuz M,et al.A new algorithm for U-shaped two-sided assembly line balancing[J].Transactions-Canadian Society for Mechanical Engineering,2010,34(2):225-241.

[8]Mura M D,Dini G.Worker skills and equipment optimization in assembly line balancing by a genetic approach[J].Procedia Cirp,2016,44:102-107.

[9]Kucukkoc I,Zhang D Z.Balancing of parallel U-shaped assembly lines[J].Computers&Operations Research,2015,64(C):233-244.