簡(jiǎn)單直線和U型裝配線平衡中的改進(jìn)階位法

焦玉玲， 邢小翠， 朱春鳳， 徐良成， 鄒連慧

(1.吉林大學(xué) 交通學(xué)院，吉林 長(zhǎng)春 130021；2.吉林建筑大學(xué) 土木工程學(xué)院，吉林 長(zhǎng)春 130021)

生產(chǎn)線平衡是對(duì)生產(chǎn)線的全部工序進(jìn)行負(fù)荷分析，通過調(diào)整工序間的負(fù)荷分配使各工序達(dá)到能力平衡的技術(shù)與方法，消除各種等待浪費(fèi)，提高生產(chǎn)線的整體效率.裝配線平衡是裝配線工作站作業(yè)分配均衡性技術(shù)，是一種典型的NP-hard問題[1]，隨著生產(chǎn)加工作業(yè)元素?cái)?shù)量的增加，平衡問題的復(fù)雜度呈幾何級(jí)數(shù)增加[2]，求解過程復(fù)雜且困難.隨著客戶需求逐漸變?yōu)槎嗥贩N，小批量的客戶定制化和產(chǎn)品多樣化，生產(chǎn)制造企業(yè)需要提高裝配線機(jī)動(dòng)性、柔性，引起裝配線上作業(yè)元素與產(chǎn)品種類的增加，裝配線平衡問題的解決方案數(shù)量急劇增加.相對(duì)于客戶需求的變化，傳統(tǒng)的直線型裝配線缺乏柔性，任務(wù)分配重新調(diào)整困難，U型裝配線的布局克服了這個(gè)缺點(diǎn).

U型裝配線上的工作站相距較近，不僅簡(jiǎn)化了物料的運(yùn)輸，而且柔性較高，在外部需求發(fā)生變化時(shí)，通過增加或減少操作人員的數(shù)量實(shí)現(xiàn)裝配線節(jié)拍調(diào)整達(dá)到新的平衡，分配作業(yè)元素時(shí)，選擇的范圍更大，分配效果一般比直線型裝配線好[3].

裝配線平衡算法是學(xué)術(shù)界和實(shí)踐界關(guān)注的熱點(diǎn)問題.1955年Salveson[4]第一次提出用解析法求解裝配線平衡問題，并用一個(gè)簡(jiǎn)單的實(shí)際案例求解裝配線平衡的過程.隨著對(duì)裝配線問題研究的深入以及現(xiàn)代智能算法的發(fā)展，裝配線平衡問題得到有效解決，Lapierre等[5]利用禁忌搜索算法，在當(dāng)工作站的時(shí)間超過生產(chǎn)節(jié)拍時(shí)，調(diào)整可行解空間和目標(biāo)函數(shù)求解范圍，通過結(jié)合實(shí)際工業(yè)的數(shù)據(jù)驗(yàn)證了算法的有效性.Ozcan、Kellegoz和Toklu[6]對(duì)作業(yè)元素時(shí)間隨機(jī)的混流裝配線平衡與排序問題，采用遺傳算法求解，結(jié)合具體的U型裝配線實(shí)例對(duì)于算法的有效性和作業(yè)時(shí)間的隨機(jī)性進(jìn)行了研究.Jonn-alagedda[7]對(duì)于給定工作站數(shù)，最小化生產(chǎn)節(jié)拍的U型裝配線平衡問題，采用遺傳算法求解.求解裝配線平衡問題的人工智能算法[8-10]，如遺傳算法、禁忌搜索法和粒子群算法等，其編碼方式復(fù)雜，計(jì)算空間復(fù)雜度較高，可能會(huì)出現(xiàn)局部收斂情況.

基于特定搜索規(guī)則的啟發(fā)式算法，其計(jì)算簡(jiǎn)單，計(jì)算效率高.Kucukkoc和Zhang[11]運(yùn)用階位法規(guī)則解決裝配線平衡問題，本文選用基于改進(jìn)階位法規(guī)則的啟發(fā)式算法求解裝配線平衡問題，即確定節(jié)拍下求工作站數(shù)盡可能少的裝配線平衡，并結(jié)合越野車實(shí)驗(yàn)算例，求解并驗(yàn)證算法有效，比較了直線型、單U型和雙U型裝配線平衡效果.

1 改進(jìn)階位法

1.1 階位法簡(jiǎn)介

階位法[12](ranked positional weight technique)是1961年由Helgeson和Birnie提出的.階位法是求出作業(yè)元素的時(shí)間及其后續(xù)作業(yè)元素時(shí)間之和稱為時(shí)間階位(也稱為時(shí)間權(quán)值)，根據(jù)求得時(shí)間權(quán)值大小分配作業(yè)，并沒有考慮作業(yè)元素的后續(xù)作業(yè)量個(gè)數(shù).

改進(jìn)階位法(modified ranked positional weight technique,MRP)綜合考慮作業(yè)元素時(shí)間階位和作業(yè)元素后續(xù)作業(yè)量階位，得到作業(yè)元素的綜合階位，再根據(jù)綜合階位的大小排序賦值，得到作業(yè)元素的綜合階位值.每個(gè)作業(yè)元素的時(shí)間階位是其本身的作業(yè)時(shí)間與后續(xù)所有作業(yè)元素時(shí)間之和，作業(yè)元素的作業(yè)量階位是該作業(yè)元素及后續(xù)的作業(yè)元素個(gè)數(shù)之和.

改進(jìn)階位法是綜合考慮時(shí)間權(quán)重和后續(xù)作業(yè)量權(quán)重來獲得綜合階位值.作業(yè)元素后續(xù)作業(yè)量的多少影響著流水線上的作業(yè)均衡.

1.2 作業(yè)元素優(yōu)先關(guān)系

在作業(yè)元素優(yōu)先關(guān)系圖中，元素之間的關(guān)系由優(yōu)先關(guān)系集合Pset和優(yōu)先關(guān)系矩陣P來表示.如果作業(yè)元素i在作業(yè)元素j之前完成，稱作業(yè)元素i是作業(yè)元素j的先行作業(yè)，作業(yè)元素j是作業(yè)元素i的后繼作業(yè).可以用一個(gè)有序數(shù)對(duì)(i，j)表示，有先后關(guān)系的所有作業(yè)元素都用有序數(shù)對(duì)表示，構(gòu)成優(yōu)先關(guān)系集合Pset.

對(duì)于有序數(shù)對(duì)(i，j)，當(dāng)作業(yè)元素i、j直接相鄰時(shí)，稱作業(yè)元素i是j的緊前作業(yè)，作業(yè)元素j是i的直接后繼作業(yè)；當(dāng)作業(yè)元素i、j不相鄰時(shí)，稱作業(yè)元素i是j的間接先行作業(yè)，作業(yè)元素j是i的間接后繼作業(yè).作業(yè)元素的優(yōu)先關(guān)系具有傳遞性，即如果作業(yè)元素i、j滿足有序數(shù)對(duì)(i，j)，作業(yè)元素j、q滿足有序數(shù)對(duì)(j，q)，則作業(yè)元素i、q滿足有序數(shù)對(duì)(i，q).

作業(yè)元素之間的優(yōu)先關(guān)系也可以用優(yōu)先關(guān)系矩陣來表示.對(duì)于優(yōu)先關(guān)系圖中有n個(gè)作業(yè)元素，該優(yōu)先關(guān)系矩陣為n×n方陣P.其中優(yōu)先關(guān)系矩陣P中的元素Pij(i=1,2,…,n;j=1,2,…,n)的取值取決于作業(yè)元素i和j的優(yōu)先關(guān)系，即

1.3 確定作業(yè)元素的綜合階位值

依據(jù)有向圖理論[13]和優(yōu)先關(guān)系矩陣P求解綜合階位值[14]，求解步驟如下：

(1) 計(jì)算作業(yè)元素i的作業(yè)量階位Rhi

Hi=count{Fi}

式中：Hi表示作業(yè)元素的后續(xù)作業(yè)元素個(gè)數(shù);Fi為作業(yè)元素i的后續(xù)作業(yè)元素集合.

根據(jù)Hi值按升序排列所有的作業(yè)元素，對(duì)于Hi值最小的作業(yè)元素賦予后續(xù)作業(yè)量階位Rhi=1，對(duì)于Hi值次小的作業(yè)元素賦予后續(xù)作業(yè)量階位Rhi=2，如果作業(yè)元素Hi值相同的，則被賦予相同的后續(xù)作業(yè)量階位Rhi.此類推，直到所有作業(yè)元素都被賦予一個(gè)特定Rhi.

(2) 計(jì)算作業(yè)元素i的時(shí)間階位Rti

式中：Ti表示作業(yè)元素i的作業(yè)時(shí)間與全部后繼作業(yè)元素時(shí)間之和,q為Fi集合里的作業(yè)元素.

按Ti值升序排列所有作業(yè)元素，對(duì)于Ti值最小的作業(yè)元素賦予時(shí)間位置階位Rti=1，對(duì)于Ti值次小的作業(yè)元素賦予時(shí)間位置階位Rti=2，如果作業(yè)元素Ti值相同，則被賦予相同的時(shí)間階位Rti.依此類推，直到所有作業(yè)元素都被賦予一個(gè)特定的Rti值.

(3) 計(jì)算作業(yè)元素i的綜合階位值Ri

Ri=Rhi×Rti

2 建立裝配線平衡數(shù)學(xué)模型

2.1 參數(shù)定義

定義的常量和決策變量見表1.

表1 參數(shù)定義Tab.1 Parameters definition

2.2 U型裝配線平衡問題數(shù)學(xué)模型

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

式中:E為裝配線平衡率.

約束條件：

(1)

(2)

(3)

(4)

(5)

Wk+1≤Wk,k=1,2,…,m0-1

(6)

(7)

(8)

裝配線平衡率最大化為目標(biāo)函數(shù).約束條件(1)表示對(duì)于某一個(gè)作業(yè)元素i只能采用一種方式來分配，即按照從前到后的順序或者按照從后往前的順序，且只能被分配到一個(gè)工作站中；約束條件(2)表示第k個(gè)工作站中的總作業(yè)時(shí)間之和不超過生產(chǎn)節(jié)拍C；約束條件(3)表示如果作業(yè)元素j按照從前向后的順序分配，那么作業(yè)元素j的緊前作業(yè)元素都要按照從前向后的順序分配；約束條件(4)表示如果作業(yè)元素j按照從后向前的順序分配，那么作業(yè)元素j的緊前作業(yè)元素都要按照從后向前的順序分配；約束條件(5)表示如果某個(gè)工作站中有作業(yè)元素，那么這個(gè)工作站就要開啟.

當(dāng)約束條件(1)～(2)中的yik取值為0時(shí)，數(shù)學(xué)模型為直線型裝配線平衡問題，約束條件(1)表示每個(gè)作業(yè)元素必須分配到唯一的工作站；約束條件(2)表示工作站k中的總作業(yè)時(shí)間之和不超過生產(chǎn)節(jié)拍C；約束條件(6)保證直線型裝配線上順序排列的m0個(gè)工作站中，如果第(k+1)個(gè)工作站開啟，那么前面的第k個(gè)工作站必須開啟；約束條件(7)表示如果第k個(gè)工作站中有作業(yè)元素，那么第k個(gè)工作站必須開啟；約束條件(8)表示作業(yè)元素之間的優(yōu)先關(guān)系約束.

3 改進(jìn)階位法求解模型

改進(jìn)階位法求解模型是依據(jù)作業(yè)元素的綜合階位值對(duì)U型裝配線平衡.

3.1 基于改進(jìn)階位法分配作業(yè)

根據(jù)作業(yè)元素i的綜合階位值Ri，從第一個(gè)工作站開始分配，裝配線上可分配的作業(yè)元素由當(dāng)前設(shè)置的工作站形式?jīng)Q定，工作站形式有常規(guī)工作站和交叉工作站.

檢查分配作業(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í)間來執(zhí)行其他作業(yè)元素，同時(shí)保證工作站的總時(shí)間要小于等于節(jié)拍.當(dāng)從優(yōu)先關(guān)系圖起點(diǎn)開始分配作業(yè)元素時(shí)，選擇綜合階位值最大的作業(yè)元素分配到工作站，當(dāng)從優(yōu)先關(guān)系圖后部開始分配作業(yè)元素時(shí)，選擇綜合階位值最小的作業(yè)元素分配到工作站，同時(shí)必須兼顧工作站被分配的作業(yè)元素時(shí)間總和小于等于節(jié)拍，或者使當(dāng)前工作站的閑置時(shí)間盡可能小，滿足目標(biāo)函數(shù).

U型裝配線和直線型裝配線的作業(yè)元素分配方式不同.對(duì)于U型裝配線，將作業(yè)元素分配到工作站時(shí)，既可以按照裝配線的加工方向從前到后分配或者從后到前分配，同時(shí)也可以兩個(gè)方向上同時(shí)進(jìn)行，這樣U型裝配線平衡問題的求解難度增大，但是U型和雙U型裝配線平衡效率有所提高.而在直線型裝配線上，分配作業(yè)元素到工作站時(shí)按照單方向進(jìn)行，降低了作業(yè)元素之間的組合搭配的交叉性，會(huì)導(dǎo)致直線型裝配線生產(chǎn)效率降低.雙U型裝配線可以同時(shí)裝配2件同類型的產(chǎn)品.

3.2 裝配線平衡效果評(píng)價(jià)

裝配線平衡的效果采用平衡率E和平滑系數(shù)S[15]評(píng)價(jià).平衡率衡量整個(gè)裝配過程中裝配線平衡和對(duì)時(shí)間利用效率的指數(shù).平滑系數(shù)衡量裝配線負(fù)荷的均勻程度.平衡率越高說明裝配線對(duì)于時(shí)間的利用程度越好，平滑系數(shù)越低說明裝配線各工作站負(fù)荷越均勻，整個(gè)裝配線效率和裝配產(chǎn)品的穩(wěn)定性越高.因此，裝配線平衡率提取目標(biāo)函數(shù)結(jié)果，平滑系數(shù)，計(jì)算如下：

式中：T(k)表示第k個(gè)工作站中作業(yè)時(shí)間總和，maxT(k)表示最大的工作站時(shí)間.

4 算例1

Bomman問題[16]的作業(yè)元素優(yōu)先關(guān)系圖，如圖1，圖中圓圈里的數(shù)字表示該作業(yè)元素的序號(hào)，作業(yè)元素圓圈上方數(shù)字表示該作業(yè)元素的作業(yè)時(shí)間.作業(yè)元素的總時(shí)間為75，裝配線的生產(chǎn)節(jié)拍設(shè)定C=26，確定最小工作站數(shù).

圖1 Bomman問題的優(yōu)先關(guān)系Fig.1 Precedence relationship of Bomman problem

4.1 綜合階位值

Bomman問題的作業(yè)元素的優(yōu)先關(guān)系集合為：Pset={(1,2)，(2,3)，(2,4)，(3,5)，(4,6)，(5,7)，(6,8)，(7,8)}.優(yōu)先關(guān)系集合Pset中有8對(duì)直接的優(yōu)先關(guān)系，不含有間接的優(yōu)先關(guān)系，其間接優(yōu)先關(guān)系可以根據(jù)作業(yè)元素之間優(yōu)先關(guān)系的傳遞性得到.優(yōu)先關(guān)系矩陣P的三元組表示：A=[(1,2,1),(2,3,1),(2,4,1),(3,5,1),(4,6,1),(5,7,1),(6,8,1),(7,8,1)].

由優(yōu)先關(guān)系矩陣和作業(yè)元素時(shí)間計(jì)算作業(yè)元素綜合階位值，得到Bomman問題作業(yè)元素的綜合階位值矩陣Ri=[48,35,24,12,15,6,4,1].

4.2 改進(jìn)階位法求解結(jié)果及評(píng)價(jià)

改進(jìn)階位法(MRP)依據(jù)作業(yè)元素的綜合階位值對(duì)裝配線平衡問題數(shù)學(xué)模型求解，將作業(yè)元素分配到直線型裝配線和U型裝配線，實(shí)現(xiàn)裝配線平衡的優(yōu)化.并將結(jié)果與分支定界法(Branch and Bound,簡(jiǎn)稱BB)的結(jié)果進(jìn)行對(duì)比，見表2.

表2 分配結(jié)果Tab.2 Allocation results

從表2可見，簡(jiǎn)單直線型裝配線布置4個(gè)工作站，線平衡率為72.12%，,平滑系數(shù)19.87和17.06.U型裝配線布置3個(gè)工作站，節(jié)約了一個(gè)工作站，線平衡率為96.15%，且平滑系數(shù)為2.24和3.00，U型裝配線的平衡率比直線型的平衡率高出24%，且裝配線平滑系數(shù)降低了79.8%，流水線上的作業(yè)均衡效果好.基于改進(jìn)階位法規(guī)則的啟發(fā)式算法的平滑系數(shù)優(yōu)于分枝定界法的結(jié)果，說明U型裝配線的平衡效果好于簡(jiǎn)單直線型，且各工作站負(fù)荷均勻.

5 實(shí)驗(yàn)算例2

在流水生產(chǎn)實(shí)驗(yàn)中，對(duì)于工序多、流程復(fù)雜裝配線平衡問題研究和分析，提高其平衡效果乃至提高流水生產(chǎn)效率，提出運(yùn)用改進(jìn)階位法求解單U和雙U型裝配流水線.如圖2所示，選取裝配實(shí)驗(yàn)的車模(局部)，進(jìn)行結(jié)構(gòu)分析和工序時(shí)間測(cè)定，得到裝配流程圖，如圖3所示，作業(yè)元素15個(gè)，總時(shí)間是208 s，設(shè)定4個(gè)工作站，最小化節(jié)拍，以時(shí)間階位和改進(jìn)階位法分別進(jìn)行直線、單U型和雙U型裝配線平衡.

圖2 車模(局部)結(jié)構(gòu)Fig.2 Vehicle model (partial) structure

圖3 車模裝配流程Fig.3 Vehicle model assembly flow

5.1 車模裝配線平衡結(jié)果布局

按照算例1計(jì)算過程，對(duì)算例2采用時(shí)間階位法和改進(jìn)階位法兩種方法分別平衡裝配線，平衡結(jié)果繪制成裝配線布局圖，如圖4～圖6.

圖4 直線型裝配線平面布局Fig.4 Simple line assembly line layout

圖5 單U型裝配線平面布局Fig.5 Single U-shaped assembly line layout

5.2 比較平衡效果指標(biāo)

計(jì)算車模的時(shí)間階位法、改進(jìn)階位法分配方案的節(jié)拍、平衡率和平滑系數(shù)等指標(biāo)，見表3.

從表3結(jié)果可見，車模簡(jiǎn)單直線型裝配線平衡的時(shí)間階位法、改進(jìn)階位法和遺傳算法求解結(jié)果雖然差別不大，節(jié)拍、平衡率和平滑系數(shù)都相等，但U型裝配線節(jié)拍減小了，單U型的平衡效果最好，比較雙U型時(shí)間階位和改進(jìn)階位的求解結(jié)果，改進(jìn)階位法的平滑系數(shù)好，驗(yàn)證了改進(jìn)階位法求解雙U型裝配線平衡問題的優(yōu)越性.

圖6 雙U型裝配線平面布局Fig.6 Double U-shaped assembly line layout表3 車模平衡效果指標(biāo)比較Tab.3 Car model balance effect index comparison

線型算法平衡效果指標(biāo)C/sE/%S直線型時(shí)間階位5791.2212.73遺傳算法5791.2312.73單U型改進(jìn)階位5594.554.899雙U型時(shí)間階位5594.569.798改進(jìn)階位5594.569.487

6 結(jié)論

結(jié)合算例，已知作業(yè)元素時(shí)間和作業(yè)元素優(yōu)先關(guān)系圖，建立了裝配線平衡的數(shù)學(xué)模型，計(jì)算作業(yè)元素綜合階位值，應(yīng)用改進(jìn)階位法對(duì)數(shù)學(xué)模型求解，得到直線型和U型(單U和雙U型)裝配線平衡結(jié)果，比較裝配線的平衡效果，得出以下結(jié)論：

(1) 依據(jù)作業(yè)元素時(shí)間和優(yōu)先關(guān)系計(jì)算各作業(yè)元素的綜合階位值，提出了改進(jìn)階位法，求解了裝配線平衡問題，結(jié)果合理有效，為企業(yè)裝配線平衡與優(yōu)化提供有效的新方法.

(2) 改進(jìn)階位法求解的U型裝配線平衡效果優(yōu)于分枝定界法的結(jié)果，與直線型裝配線比較，平衡率提高了24%，平滑系數(shù)降低了79.8%，提高了裝配線效率和設(shè)備使用效率，使裝配線負(fù)荷程度更為均勻，為流水裝配線方案設(shè)計(jì)提供了有效方法.

(3) 結(jié)合實(shí)驗(yàn)室實(shí)際車模(局部)實(shí)驗(yàn)，對(duì)流水線實(shí)驗(yàn)設(shè)計(jì)雙U型裝配實(shí)驗(yàn)方案，改進(jìn)階位的結(jié)果與時(shí)間階位法進(jìn)行對(duì)比，改進(jìn)階位法的平滑系數(shù)降低了.對(duì)于小型結(jié)構(gòu)的流水線平衡問題，改進(jìn)階位法優(yōu)勢(shì)并不明顯，但在計(jì)算零件多結(jié)構(gòu)復(fù)雜的大型產(chǎn)品的裝配線平衡問題時(shí)，改進(jìn)階位法平衡效果明顯且易于操作.