單車型單邊裝配線平衡調(diào)度模型研究

李 明,唐秋華,席忠民,夏緒輝,鄧明星

(1.武漢科技大學(xué)理學(xué)院,湖北武漢,430065;2.武漢科技大學(xué)機(jī)械自動(dòng)化學(xué)院,湖北武漢,430081; 3.神龍汽車有限公司技術(shù)中心,湖北武漢,430051;4.武漢科技大學(xué)汽車與交通工程學(xué)院,湖北武漢,430081)

單車型單邊裝配線平衡調(diào)度模型研究

李 明1,唐秋華2,席忠民3,夏緒輝2,鄧明星4

(1.武漢科技大學(xué)理學(xué)院,湖北武漢,430065;2.武漢科技大學(xué)機(jī)械自動(dòng)化學(xué)院,湖北武漢,430081; 3.神龍汽車有限公司技術(shù)中心,湖北武漢,430051;4.武漢科技大學(xué)汽車與交通工程學(xué)院,湖北武漢,430081)

平衡汽車裝配線能夠提高企業(yè)生產(chǎn)效率、穩(wěn)定產(chǎn)品質(zhì)量、降低生產(chǎn)延遲。根據(jù)單車型單邊裝配工藝要求,分別以工位間實(shí)際操作時(shí)間差最小和最大工位持續(xù)時(shí)間最小為目標(biāo),利用0-1變量,建立了混合整數(shù)規(guī)劃裝配線調(diào)度模型,利用此模型可求得平衡率很高的調(diào)度方案。實(shí)驗(yàn)證明該模型所得方案是可信的,將其用在裝配線設(shè)計(jì)階段具有可行性。

混合整數(shù)規(guī)劃;0-1變量;裝配線平衡

汽車產(chǎn)品結(jié)構(gòu)復(fù)雜,生產(chǎn)批量一般較大,為保證裝配質(zhì)量、提高勞動(dòng)生產(chǎn)率,生產(chǎn)廠家會(huì)根據(jù)產(chǎn)品的結(jié)構(gòu)特點(diǎn),從裝配工藝角度將其分解成為可單獨(dú)組織裝配的單元,合理地安排人員、設(shè)備和工作地點(diǎn),組織并行、流水作業(yè)。汽車裝配涉及上千項(xiàng)操作,而操作間優(yōu)先關(guān)系非常繁雜,如何合理完成操作向各工位的分配,決策各操作的開始時(shí)間,使得裝配線上各工位負(fù)荷盡可能達(dá)到平衡,在裝配線的設(shè)計(jì)階段和生產(chǎn)管理過程中,都是一個(gè)不可回避的問題。

裝配線平衡可以提高企業(yè)生產(chǎn)效率,穩(wěn)定產(chǎn)品質(zhì)量,降低生產(chǎn)延遲。該工程問題是典型的NP難問題[1],其數(shù)學(xué)本質(zhì)是決策一系列操作向各工位分配的混合整數(shù)規(guī)劃問題。汽車裝配操作多,導(dǎo)致離散變量數(shù)目繁多,潛在的組合爆炸可能性可能導(dǎo)致實(shí)際問題不可求解。

20世紀(jì)50年代,Salveson首次提出并建立了單品種裝配線平衡問題的數(shù)學(xué)模型,此后相關(guān)的方法被不斷提出并應(yīng)用于求解單邊裝配線平衡問題。Talbot等[2]采用啟發(fā)式算法求解裝配線平衡問題;Scholl等[3]提出了一種新的啟發(fā)式算法,得到了簡(jiǎn)單單車型裝配線平衡問題的精確解; Lapierre等[4]利用禁忌搜索算法對(duì)裝配線平衡問題進(jìn)行求解;Baybars[5]對(duì)簡(jiǎn)單的裝配線平衡問題給出了精確的求解算法;Klein等[6]利用分支定界法求解簡(jiǎn)單裝配線平衡問題。國(guó)內(nèi)對(duì)此問題的研究相對(duì)較少,張則強(qiáng)等[7]和毛凌翔等[8]分別利用蟻群算法對(duì)裝配線平衡問題進(jìn)行了有效的求解。

本文針對(duì)汽車裝配線平衡問題,考慮各項(xiàng)操作的優(yōu)先關(guān)系和工藝要求,以裝配平衡為目標(biāo)建立單車型單邊裝配線平衡調(diào)度模型,以期為生產(chǎn)線任務(wù)分配的設(shè)計(jì)提供技術(shù)支持。

1 單車型單邊裝配線平衡問題

按所裝配車型類型劃分,國(guó)內(nèi)汽車裝配生產(chǎn)線主要有單車型流水生產(chǎn)線、多車型交替生產(chǎn)線和多車型混流生產(chǎn)線;按工位布局劃分,又存在單邊和雙邊之分。由于雙邊裝配的思想與單邊裝配基本一致,本文以單車型單邊裝配線為研究對(duì)象,建立其裝配線平衡的數(shù)學(xué)模型。

按照單車型單邊組織裝配生產(chǎn),一般要求實(shí)現(xiàn)以下特征:專業(yè)程度高,操作數(shù)量多。裝配線上的總操作數(shù)量很大,但每個(gè)工位的工人只從事一個(gè)或幾個(gè)固定操作,以便熟練操作。裝配生產(chǎn)具有明顯的周期性。完成操作分配后所得操作時(shí)間最長(zhǎng)工位的作業(yè)時(shí)間,稱為節(jié)拍。為保證生產(chǎn)的連續(xù)性,要求:①各工位的操作總時(shí)間等于或略小于節(jié)拍,以防止工位上的任務(wù)堆積以及設(shè)備或人員的無效等待;②裝配線具有異步性和并發(fā)性,各工位的狀態(tài)只在離散時(shí)間點(diǎn)上發(fā)生躍變,保證生產(chǎn)過程的平衡性和并行性;③工藝路線服從操作邏輯規(guī)則,被加工對(duì)象在工位間作單向運(yùn)動(dòng)。生產(chǎn)線的布置可以是直線式、U型或X型等方式。

在汽車裝配生產(chǎn)線上,工人在其工位時(shí)間內(nèi)需要完成多項(xiàng)操作,每項(xiàng)操作的操作時(shí)間相對(duì)穩(wěn)定,建模時(shí)將其視為常數(shù)。同時(shí),為了衡量裝配線的平衡程度,引入平衡率 p作為評(píng)價(jià)指標(biāo),定義為

式中:J為工位的總數(shù);Tj表示工位 j(j=1,…, J)的總操作時(shí)間;CT為裝配線的節(jié)拍。

一般地,如果裝配線的平衡率為50%～60%時(shí),表明生產(chǎn)線缺乏管理,生產(chǎn)隨意;當(dāng)裝配線的平衡率為60%～70%時(shí),表明生產(chǎn)過程管理比較關(guān)注平衡問題;當(dāng)裝配線平衡率為70%～85%時(shí),證明生產(chǎn)線的管理十分科學(xué);當(dāng)裝配線的平衡率大于85%時(shí),則認(rèn)為該生產(chǎn)線的平衡問題得到了很好的解決。

2 單車型單邊裝配線平衡調(diào)度模型

2.1 模型I

在單車型單邊裝配線上,假設(shè)給定操作總數(shù)為 I,其序號(hào)記為 i,k,i′(i,k,i′=1,2,…,I);假設(shè)裝配線總共有J個(gè)工位,其序號(hào)記為 j,j′(j,j′= 1,2,…,J);操作 i的實(shí)際操作時(shí)間記為ti。為了表征操作間的優(yōu)先關(guān)系,引入直接優(yōu)先集 P= {(i,k)},對(duì)于任意(i,k)∈P,表示操作 i直接優(yōu)先于操作k。

定義實(shí)數(shù)變量 Startij,表示在工位 j上操作i的開始時(shí)刻,如果任務(wù)i不在工位j上,則相應(yīng)變量為0。為了確定操作i是否在工位j上,引入0-1決策變量 xij,定義 xij=1表示操作 i在工位 j上,否則 xij=0;為了確定兩個(gè)操作 i和k的先后關(guān)系,引入0-1決策變量Orderik,定義Orderik=1表示操作i優(yōu)先于操作k,否則Orderik=0。在決策前,根據(jù)裝配線的邏輯順序和幾何要求,部分操作間的優(yōu)先關(guān)系(包括直接優(yōu)先關(guān)系和間接優(yōu)先關(guān)系)已經(jīng)確定,所以對(duì)這部分操作相應(yīng)的決策變量可以直接賦值,以提高計(jì)算效率。

決策變量 xij和實(shí)數(shù)變量 Startij之間存在內(nèi)在的聯(lián)系,即如果 xij=1,則在工位 j上操作i的開始時(shí)刻Startij應(yīng)滿足 Startij≥0,否則 xij=0,此關(guān)系可用下式描述:

式中:Tmax為常量,表示一個(gè)較大的時(shí)間,可取作所有操作的操作時(shí)間之和。

在裝配生產(chǎn)線上,操作i必須被執(zhí)行并且只能在一個(gè)工位上進(jìn)行,即應(yīng)滿足

在裝配過程中,對(duì)于存在直接優(yōu)先關(guān)系的某兩項(xiàng)操作i和k,顯然不論它們是否在同一個(gè)工位中,都應(yīng)滿足

汽車裝配線是流水作業(yè),即對(duì)同一個(gè)工位上的兩項(xiàng)不同操作i和k,其關(guān)系必須是串行的,此串行關(guān)系可利用下面兩個(gè)不等式進(jìn)行控制

對(duì)相鄰的兩個(gè)工位,一般要求前一個(gè)工位結(jié)束后才能進(jìn)行下一個(gè)工位,但如果空間上允許,這兩個(gè)工位之間允許有一定的重疊時(shí)間,為此引入常量 Toverlap表示相鄰兩個(gè)工位重疊時(shí)間的上界,則前一個(gè)工位的結(jié)束時(shí)間與后一個(gè)工位的開始時(shí)間之間應(yīng)滿足下面不等式:

考慮到操作的不可分割性,在各個(gè)工位,工人裝配汽車零件時(shí)允許有閑置時(shí)間,但此閑置時(shí)間應(yīng)盡可能小,為此引入常量 Tid le表示各工位閑置時(shí)間的上界,顯然各工位的實(shí)際操作時(shí)間和持續(xù)時(shí)間應(yīng)滿足下面不等式:

考慮到目標(biāo)函數(shù)為非線性函數(shù),引入下面不等式將其線性化:

式(2)～式(10)即為單車型單邊裝配線平衡問題的調(diào)度模型,記為模型Ⅰ。

2.2 模型Ⅱ

在模型Ⅰ中,約束條件(8)的目的在于使得各工位的閑置時(shí)間盡可能地小,即不超過 Tid le,目標(biāo)函數(shù)式(9)、式(10)的目的在于使得各工位的平衡度盡可能地高,這兩個(gè)目的也可以由下式一并完成

式(2)～式(7)與式(11)稱為單車型單邊裝配線平衡問題的調(diào)度模型Ⅱ。

2.3 模型Ⅰ與模型Ⅱ的尋優(yōu)思想比較

模型Ⅰ和Ⅱ都以提高裝配線平衡為目標(biāo),但其尋優(yōu)思想略有不同。如圖1(a)所示,模型Ⅰ通過最小化最長(zhǎng)和最短實(shí)際工位操作時(shí)間差異,使得各工位的實(shí)際操作時(shí)間盡可能相等;而模型Ⅱ則通過最小化最大工位持續(xù)操作時(shí)間,使得各工位的操作時(shí)間達(dá)到平衡,如圖1(b)所示。此外模型Ⅰ考慮的是實(shí)際操作時(shí)間長(zhǎng)度,可以保證工位內(nèi)部無閑置時(shí)間,而模型Ⅱ則最小化工位持續(xù)時(shí)間,其中包含閑置時(shí)間。

圖1 模型Ⅰ和模型Ⅱ的尋優(yōu)思想差異示意圖Fig.1 Optim ization difference between modelⅠand modelⅡ

3 算例

假設(shè)某汽車裝配線需要在3個(gè)工位上完成16項(xiàng)操作,各項(xiàng)操作的實(shí)際操作時(shí)間和操作之間的優(yōu)先關(guān)系如見圖2所示。

將圖2中的數(shù)據(jù)分別代入模型Ⅰ和模型Ⅱ,利用GAM S軟件求解,結(jié)果如表1所示。繪制裝配線平衡調(diào)度方案甘特圖如圖3和圖4所示。

圖2 單車型單邊裝配線操作優(yōu)先關(guān)系圖Fig.2 Dom inance relationship of the one-side assembly line

由表1中可見,兩個(gè)模型求解所得裝配線調(diào)度方案的平衡率都很高,表明模型所得單車型單邊裝配線調(diào)度可以達(dá)到很好的平衡。此外,模型Ⅰ能夠控制工位內(nèi)部的閑置時(shí)間(本例中為0),而模型Ⅱ則只能使得此閑置時(shí)間盡可能小(本例工位2中閑置時(shí)間為1),算例所得結(jié)論與前面模型的理論分析相一致,表明模型及其求解方法是有效的。

表1 模型Ⅰ和模型Ⅱ的求解結(jié)果Table 1 Solutions of modelⅠand modelⅡ

圖3 模型Ⅰ所得裝配線調(diào)度方案甘特圖Fig.3 Gantt chart of the assembly line from model I

圖4 模型Ⅱ所得裝配線調(diào)度方案甘特圖Fig.4 Gantt chart of the assembly line from modelⅡ

[1] Bartholdi J J.Balancing two-sided assembly lines:A case study[J].International Journal of Production Research,1993,31:2 447-2 461.

[2] Talbot F B,Patterson J H,Gehrlein W V.A comparative evaluation of heuristic line balancing tech-niques[J].Management Science,1986,32:430-454.

[3] Scholl A,Becker C.State-of-the-art exact and heuristic solution p rocedures for simp le assembly line balancing[J].European Journal of Operational Research,2006,168(3):666-693.

[4] Lapierre SD,Ruiz A,So riano P.Balancing assembly lines w ith tabu search[J].European Journal of Operational Research,2006,168(3):826-837.

[5] Baybars I.A survey of exact algo rithm s fo r the simp le assembly line balancing p roblem[J].Management Science,1986,32:240-253.

[6] Klein R,Scholl A.Maximizing the p roduction rate in simple assembly line balancing—a branch and bound p rocedure[J].European Journal of Operational Research,1996,91(2):367-385.

[7] 張則強(qiáng),程文明,鐘斌,等.求解裝配線平衡問題的一種改進(jìn)蟻群算法[J].計(jì)算機(jī)集成制造系統(tǒng),2007, 13(8):1 632-1 637.

[8] 毛凌翔,鄭永前.蟻群算法求解裝配線平衡第一類問題[J].計(jì)算機(jī)系統(tǒng)應(yīng)用,2009,19(1):140-143.

Balancing of single-model one-sided assembly line models

L i M ing1,Tang Qiuhua2,X i Zhongm in3,Xia Xuhui2,Deng M ingxing4
(1.College of Science,Wuhan University of Science and Technology,Wuhan 430065,China; 2.College of Machinery and Automation,Wuhan University of Science and Technology,Wuhan 430081,China; 3.Technical Center,Dongfeng Peugot Citroen Automobile Company L td.,Wuhan 430051,China; 4.College of Automobile and Traffic Engineering,W uhan University of Science and Technology,Wuhan 430081,China)

Balanced automobile assem bly line can raise p roduction efficiency,stabilize p roduct quality, and reduce p roduction delay.M ixed integer p rogramming assembly line scheduling model is established w ith binary variable according to the assembling specificationsof single-model one-sided line to minimize the difference between each station time and the duration time of the maximum station respectively,and two high balance rate scheduling p rogram s are obtained acco rding to the model.The experimental results show that the scheme is p romising and feasible w hen emp loyed in assembly line design.

mixed integer p rogramming;binary variable;assembly line balancing

TH181

A

1674-3644(2010)06-0620-04

[責(zé)任編輯 鄭淑芳]

2010-06-17

國(guó)家自然科學(xué)基金資助項(xiàng)目(50875190/E051005).

李 明(1976-),男,武漢科技大學(xué)講師.E-mail:lmzqx@163.com