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

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

0 引 言

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

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

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

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

1.1 問題描述

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

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

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

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

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

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

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

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

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

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

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

約束條件:

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

2 模型求解

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.3 裝配線的性能分析

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

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

3 算 例

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

表1 作業(yè)元素工作內(nèi)容及時(shí)間表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)重,計(jì)算結(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

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

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

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

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

3.2 雙U型裝配線

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

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

表4 分配步驟Table 4 Assignment steps

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

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

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

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

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

4 結(jié) 論

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

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

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

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

[2]宋華明,韓玉啟.基于遺傳算法的U型生產(chǎn)線平衡[J].系統(tǒng)工程報(bào),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.