單車型單邊裝配線平衡調度模型研究

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

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

單車型單邊裝配線平衡調度模型研究

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

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

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

混合整數規劃;0-1變量;裝配線平衡

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

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

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

本文針對汽車裝配線平衡問題,考慮各項操作的優先關系和工藝要求,以裝配平衡為目標建立單車型單邊裝配線平衡調度模型,以期為生產線任務分配的設計提供技術支持。

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

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

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

在汽車裝配生產線上,工人在其工位時間內需要完成多項操作,每項操作的操作時間相對穩定,建模時將其視為常數。同時,為了衡量裝配線的平衡程度,引入平衡率 p作為評價指標,定義為

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

一般地,如果裝配線的平衡率為50%～60%時,表明生產線缺乏管理,生產隨意;當裝配線的平衡率為60%～70%時,表明生產過程管理比較關注平衡問題;當裝配線平衡率為70%～85%時,證明生產線的管理十分科學;當裝配線的平衡率大于85%時,則認為該生產線的平衡問題得到了很好的解決。

2 單車型單邊裝配線平衡調度模型

2.1 模型I

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

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

決策變量 xij和實數變量 Startij之間存在內在的聯系,即如果 xij=1,則在工位 j上操作i的開始時刻Startij應滿足 Startij≥0,否則 xij=0,此關系可用下式描述:

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

在裝配生產線上,操作i必須被執行并且只能在一個工位上進行,即應滿足

在裝配過程中,對于存在直接優先關系的某兩項操作i和k,顯然不論它們是否在同一個工位中,都應滿足

汽車裝配線是流水作業,即對同一個工位上的兩項不同操作i和k,其關系必須是串行的,此串行關系可利用下面兩個不等式進行控制

對相鄰的兩個工位,一般要求前一個工位結束后才能進行下一個工位,但如果空間上允許,這兩個工位之間允許有一定的重疊時間,為此引入常量 Toverlap表示相鄰兩個工位重疊時間的上界,則前一個工位的結束時間與后一個工位的開始時間之間應滿足下面不等式:

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

考慮到目標函數為非線性函數,引入下面不等式將其線性化:

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

2.2 模型Ⅱ

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

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

2.3 模型Ⅰ與模型Ⅱ的尋優思想比較

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

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

3 算例

假設某汽車裝配線需要在3個工位上完成16項操作,各項操作的實際操作時間和操作之間的優先關系如見圖2所示。

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

圖2 單車型單邊裝配線操作優先關系圖Fig.2 Dom inance relationship of the one-side assembly line

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

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

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

圖4 模型Ⅱ所得裝配線調度方案甘特圖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] 張則強,程文明,鐘斌,等.求解裝配線平衡問題的一種改進蟻群算法[J].計算機集成制造系統,2007, 13(8):1 632-1 637.

[8] 毛凌翔,鄭永前.蟻群算法求解裝配線平衡第一類問題[J].計算機系統應用,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

[責任編輯 鄭淑芳]

2010-06-17

國家自然科學基金資助項目(50875190/E051005).

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