原丕業(yè), 劉佳楠, 劉 暢, 張 萌

(青島理工大學(xué) 管理工程學(xué)院,山東 青島 266520)

0 引言

隨著市場(chǎng)對(duì)產(chǎn)品準(zhǔn)時(shí)化、多樣化需求的增加，JIT制造逐漸受到企業(yè)的重視?；炝餮b配線可混合、連續(xù)裝配結(jié)構(gòu)、工藝相似的不同產(chǎn)品，是一種柔性生產(chǎn)系統(tǒng)，能夠幫助企業(yè)有效應(yīng)對(duì)市場(chǎng)環(huán)境的快速變化，但是在實(shí)際應(yīng)用中往往因工序分配不合理，使得工作站閑置和超載時(shí)間較多，降低了裝配線整體效率。因此，必須對(duì)混流裝配線進(jìn)行平衡，消除等待和浪費(fèi)。

目前，關(guān)于該問題的研究主要集中于算法的設(shè)計(jì)和模型的改進(jìn)。查靚等[1]構(gòu)建了直線型和U型裝配線第一類平衡問題的整數(shù)規(guī)劃模型；徐發(fā)平等[2]運(yùn)用改進(jìn)分支定界法求解了生產(chǎn)節(jié)拍固定，最小化工位數(shù)的裝配線平衡問題；唐秋華等[3]以工作站數(shù)最小為目標(biāo)，考慮生產(chǎn)中的學(xué)習(xí)效應(yīng)和加強(qiáng)約束，建立非線性平衡模型；張則強(qiáng)等[4]通過研究產(chǎn)品作業(yè)時(shí)間的隨機(jī)性，優(yōu)化了混裝線的工作站數(shù)；焦玉玲等[5]綜合考慮作業(yè)元素的時(shí)間和位置階位值，將平衡率最大作為目標(biāo)建立不同布置下的優(yōu)化模型。

以工作站數(shù)最小或裝配線平衡率最高為主的單目標(biāo)模型可以較快求解平衡問題，但對(duì)實(shí)際生產(chǎn)中的制約因素考慮較少。為了滿足復(fù)雜多變的市場(chǎng)需求，企業(yè)在對(duì)裝配線布局時(shí)，常進(jìn)行多目標(biāo)決策。Betul等[6]研究了平衡對(duì)生產(chǎn)效率、工作站間負(fù)荷均衡以及線平滑率的影響；Masoud等[7]將工位負(fù)載和裝配線效率作為混合U型裝配線平衡效果的評(píng)判指標(biāo)；扈靜等[8]引入平衡損耗系數(shù)和平滑指數(shù)研究混流裝配線平衡問題；韓煜東等[9]以混裝線實(shí)際節(jié)拍最小化和合理確定作業(yè)人數(shù)為目標(biāo)來降低加工成本；李愛平等[10]通過測(cè)度作業(yè)元素的裝配關(guān)系復(fù)雜性，優(yōu)化了裝配線節(jié)拍和平滑系數(shù)。綜上，混裝線多目標(biāo)平衡問題的目標(biāo)設(shè)定大多以平衡結(jié)果為依據(jù)，對(duì)因混合產(chǎn)品工序時(shí)間差異所導(dǎo)致的工作站負(fù)荷均衡性考慮較少，同時(shí)忽略了目標(biāo)間數(shù)量級(jí)差異對(duì)聯(lián)合目標(biāo)最優(yōu)性的影響。

基于上述分析，盡管關(guān)于混流裝配線平衡問題的研究較豐富，但平衡過程中依然有很多問題還沒有解決，理論與實(shí)踐存在差距。本文將以目前應(yīng)用更為廣泛的U型混流裝配線為研究對(duì)象，在最小化工作站數(shù)的基礎(chǔ)上均衡工作站間負(fù)荷和工作站內(nèi)不同產(chǎn)品的作業(yè)負(fù)荷，并將不同產(chǎn)品工序操作時(shí)間的加權(quán)和作為該工序?qū)嶋H作業(yè)時(shí)間，建立多目標(biāo)優(yōu)化模型，來減少裝配生產(chǎn)中的浪費(fèi)。

1 U型混流裝配線平衡問題描述

混流裝配線平衡問題就是研究在裝配作業(yè)順序、市場(chǎng)需求量、混合產(chǎn)品裝配比等既定條件下，將一系列工序分配到一定數(shù)量的工作站中，同時(shí)確保各工作站實(shí)際作業(yè)時(shí)間不超過給定節(jié)拍且工作站閑置時(shí)間最小，以消除瓶頸，提高生產(chǎn)效率。與傳統(tǒng)直線布置不同，U型裝配線上工作站間距離較近，可按照前后兩個(gè)方向同時(shí)進(jìn)行工序分配，工序交叉、組合的空間更大，有效減少了工作站閑置時(shí)間。因此當(dāng)需求發(fā)生變化時(shí)，能夠迅速調(diào)整以適應(yīng)生產(chǎn)，如圖1顯示了一種U型裝配線的工序分配方案。

圖1 U型裝配線工序分配示意圖

建模過程涉及到的符號(hào)和變量解釋如下：

i：工序序號(hào)，i=1,2,3,…,n，n為工序總數(shù)；

j、k：工作站序號(hào)，j、k=1,2,3,…,m，m為所需工作站數(shù)；

αq：品種q的裝配比例，且αq=dq/d；

tiq：品種q在工序i的裝配時(shí)間；

xij：0-1變量，xij=1表示按照作業(yè)序列從前往后將工序i分配到工作站j；

yij：0-1變量，yij=1表示按照作業(yè)序列從后往前將工序i分配到工作站j；

I(k)：分配到工作站k上的工序集合；

E：工序全集，E={1,2,3,…,n}；

P：n階矩陣，表示工序間的綜合作業(yè)優(yōu)先關(guān)系，滿足pst=P(s,t)∈(0,1)。當(dāng)pst=1時(shí)，說明工序s是t的緊前工序；

aj：工作站j的狀態(tài)變量，aj∈(0,1)，當(dāng)aj=1時(shí)，說明工作站j分配了工序。

為了使研究的問題更加明晰，進(jìn)行如下假設(shè)：(1)作業(yè)優(yōu)先關(guān)系約束對(duì)所有產(chǎn)品一致；(2)不同產(chǎn)品的同一工序應(yīng)分配到相同工作站；(3)工序是不可再細(xì)分的最小作業(yè)單元。

2 多目標(biāo)優(yōu)化模型建立

2.1 目標(biāo)識(shí)別

混流裝配線平衡的最終目標(biāo)是使生產(chǎn)保持一種均衡、連續(xù)的流動(dòng)狀態(tài)，各工作站作業(yè)同步進(jìn)行，減少工作站的閑置和超載時(shí)間，提高資源利用率。因此，保證各工作站間平均負(fù)荷的均衡性十分重要，以最小化工作站間平均單件產(chǎn)品作業(yè)時(shí)間值的均方差來衡量該目標(biāo)，如公式(1)所示。

(1)

此外，在裝配線平均負(fù)荷均衡的前提下，由于不同產(chǎn)品作業(yè)時(shí)間的差異，工作站的瞬時(shí)負(fù)荷也可能會(huì)超過設(shè)計(jì)節(jié)拍，造成生產(chǎn)不穩(wěn)定，因此對(duì)裝配線進(jìn)行平衡時(shí)還應(yīng)保證工作站內(nèi)不同產(chǎn)品的作業(yè)負(fù)荷差異最小，對(duì)該目標(biāo)定量化表示如下：

(2)

最后，工作站的數(shù)量影響著系統(tǒng)初期的建造成本，所以必須將工作站數(shù)維持在合理水平。

(3)

2.2 聯(lián)合目標(biāo)函數(shù)的建立

由于各目標(biāo)函數(shù)分別代表著問題在不同維度的最優(yōu)化，目標(biāo)之間存在量綱差異，因此，本文提出了一種目標(biāo)函數(shù)標(biāo)準(zhǔn)化方式——目標(biāo)法，用來解決聯(lián)合目標(biāo)中的多目標(biāo)兼容性問題。目標(biāo)法的中心思想是以各單目標(biāo)最優(yōu)值的倒數(shù)作為標(biāo)準(zhǔn)化系數(shù)，將不同維度的目標(biāo)函數(shù)值轉(zhuǎn)換為相同維度的百分比誤差值，實(shí)現(xiàn)多目標(biāo)聯(lián)立。

另外，不同目標(biāo)對(duì)平衡總目標(biāo)的貢獻(xiàn)度不同，可以通過目標(biāo)權(quán)重的大小來反映，采用層次分析法得到f1、f2、f3的權(quán)重系數(shù)分別為0.45、0.23、0.32。

綜上，定義聯(lián)合目標(biāo)函數(shù)為:

J=min(0.45×v1f1+0.23×v2f2+0.32×v3f3)

(4)

其中，v1、v2、v3分別為目標(biāo)f1，f2，f3的標(biāo)準(zhǔn)化系數(shù)。

2.3 模型的約束條件

U型混裝線平衡模型的約束條件主要有：

(1)工序分配約束。即所有工序均被分配，且每個(gè)工序只能分配給一個(gè)工作站；

(5)

(2)工作站分配約束。即每個(gè)工作站至少分配一項(xiàng)工序任務(wù)；

(6)

(3)優(yōu)先關(guān)系約束。對(duì)于任意工序來說，只有它的所有直接緊前工序或所有直接緊后工序都已經(jīng)分配完畢，該工序才能進(jìn)行分配；

(7)

(4)節(jié)拍約束。各工作站實(shí)際作業(yè)時(shí)間不超過給定節(jié)拍；

(8)

(5)最大分配原則約束。在保證節(jié)拍約束的前提下，將盡可能多的工序分配到該工作站內(nèi)；

(9)

(6)保證相鄰工作站的任務(wù)集沒有交叉，且所有工作站任務(wù)集的并集等于工序全集E。

I(j)={xij+yij=1|i,j=1,2,…,n|},

(10)

3 自適應(yīng)遺傳算法設(shè)計(jì)

為了使自適應(yīng)遺傳算法(AGA)能更好地求解混流裝配線平衡問題，對(duì)其編碼和運(yùn)算迭代機(jī)制做如下改進(jìn)。

3.1 染色體的編碼與解碼

本文采用作業(yè)序號(hào)編碼的方式。按照各工序分配至工作站的先后順序，將作業(yè)序號(hào)排成一列，分別對(duì)應(yīng)染色體的各個(gè)基因位，得到的基因序列就是一條編碼后的染色體。解碼就是將染色體各基因位對(duì)應(yīng)的工序按照約束條件依次分配到相應(yīng)工作站中。圖2為一條染色體基因編碼與解碼的示例。

圖2 染色體編碼與解碼

3.2 初始種群的產(chǎn)生

為保證解的質(zhì)量和多樣性，加快算法收斂速度，在生成初始種群時(shí)借鑒小生境思想。首先按照規(guī)則生成十個(gè)指定規(guī)模的原始種群，然后對(duì)每個(gè)原始種群中的個(gè)體按照適應(yīng)度值大小進(jìn)行排序，最后分別選擇各種群適應(yīng)度值排在前10%的個(gè)體，組成一個(gè)新的種群，實(shí)現(xiàn)種群初始化。

原始種群可通過如下步驟產(chǎn)生：

步驟1輸入綜合作業(yè)關(guān)系矩陣P、節(jié)拍C、工序總數(shù)n、種群容量popsize。初始化個(gè)體計(jì)數(shù)器size=1、基因計(jì)數(shù)器l=1、工作站計(jì)數(shù)器m=1，工作站空閑時(shí)間idle_time=C。

步驟2生成一條可行的染色體:

(1)對(duì)矩陣P同時(shí)按照行列進(jìn)行搜索，將沒有緊前作業(yè)和沒有緊后作業(yè)的工序放入待分配工序集合N中；

(2)隨機(jī)選擇N中的工序i，若i的作業(yè)時(shí)間≤idle_time，則將i放入工作站m，并計(jì)算當(dāng)前工作站m的空閑時(shí)間idle_time=idle_time-工序i的作業(yè)時(shí)間，轉(zhuǎn)到(3)；否則，增加新工作站，令m=m+1，并重置工作站空閑時(shí)間idle_time=C，返回(2)；

(3)更新關(guān)系矩陣P。當(dāng)工序i沒有緊前作業(yè)時(shí)，令P中第i行所有非0元素等于0，P(i,i)=1；當(dāng)工序i沒有緊后作業(yè)時(shí)，令P中第i列所有非0元素等于0，P(i,i)=1；

(4)令l=l+1，判斷l(xiāng)≥n是否成立。若滿足條件，則表示所有工序均已分配到相應(yīng)工作站，得到一條可行的染色體，執(zhí)行步驟3；否則，返回步驟2。

步驟3對(duì)生成的染色體進(jìn)行編碼。

步驟4更新個(gè)體計(jì)數(shù)器size=size+1，判斷size≥popsize是否成立，若是，則退出程序，輸出所有個(gè)體即為原始種群；否則，返回步驟1，繼續(xù)生成新的染色體。

3.3 適應(yīng)度函數(shù)

3.4 自適應(yīng)交叉和變異概率設(shè)計(jì)

在遺傳算法運(yùn)行初期，種群個(gè)體的適應(yīng)度差異較大，算法易陷入早熟，此時(shí)交叉和變異概率應(yīng)該取較大值，以擴(kuò)大搜索空間，產(chǎn)生更多新個(gè)體；在迭代后期，算法逐漸收斂，種群個(gè)體的適應(yīng)度普遍較高，這時(shí)應(yīng)該減小交叉、變異概率，防止破壞優(yōu)良基因，加快算法收斂到最優(yōu)解。綜上，給出本文自適應(yīng)交叉概率pc和變異概率pm的調(diào)整公式：

式中，pcl表示種群進(jìn)化到第l代時(shí)，染色體的交叉概率；pml表示第l代個(gè)體的變異概率。mpcl與mpml為中間變量，pcmax為交叉概率的上限值，pmmax為變異概率的上限值，mpcl=pcmax×2-ΔZ/Zmax,mpml=pmmax×e-ΔZ/Zmax。Zmax表示當(dāng)前種群個(gè)體的最大適應(yīng)度值，Zavg表示當(dāng)前種群個(gè)體的平均適應(yīng)度值，ΔZ=Zmax-Zavg。

3.5 遺傳算子

3.5.1 選擇

為了防止遺傳退化，保留優(yōu)秀基因，選擇操作采用輪盤賭與精英保留策略相結(jié)合的方法，具體操作過程為：

(1)保留父代種群中適應(yīng)度值較大的前20%精英個(gè)體；(2)利用輪盤賭方法從父代種群中選擇個(gè)體組成子代新種群；(3)將子代種群中適應(yīng)度較小的20%個(gè)體用保留的父代精英個(gè)體替換。

3.5.2 交叉

優(yōu)良基因的交叉組合在一定程度上更容易產(chǎn)生優(yōu)秀個(gè)體，按照交叉概率隨機(jī)確定待交叉?zhèn)€體，兩兩配對(duì)，交換部分基因。以兩條各包含7個(gè)基因的染色體為例，說明交叉操作過程。

假設(shè)待交叉的兩個(gè)父代個(gè)體為R1、R2，交叉后產(chǎn)生的子代個(gè)體為S1、S2。對(duì)于R1來說，隨機(jī)產(chǎn)生兩個(gè)交叉點(diǎn)c1和c2，只保留區(qū)間[c1,c2]的基因完整遺傳給子代S1。然后刪除R2中含有的與片段[c1,c2]相同的基因，將剩余基因順序不變的補(bǔ)充到S1缺失的基因位上，得到新個(gè)體S1，上述過程如圖3所示，S2的生成過程同S1。

圖3 交叉操作過程示意圖

由于交叉操作具有隨機(jī)性，交叉后子代個(gè)體的某些基因可能會(huì)違反綜合作業(yè)優(yōu)先關(guān)系，因此還需要對(duì)新生成的染色體進(jìn)行基因沖突檢測(cè)，調(diào)整違反優(yōu)先關(guān)系的基因位置，保證染色體的可行性。

3.5.3 變異

變異操作可以使遺傳過程迅速跳出局部最優(yōu)，防止算法陷入早熟。

(1)隨機(jī)確定變異個(gè)體的變異點(diǎn)a1，在矩陣P中遍歷a1位置上工序i的所有直接前序和后序作業(yè)，并確定它們?cè)谠撟儺惾旧w中的位置；

(2)令i的所有緊前工序中排在末位的工序基因位置為b1，所有緊后工序排在首位的工序基因位置為b2；

(3)將a1處的基因隨機(jī)插入到區(qū)間[b1,b2]的任意位置，生成新個(gè)體。

3.6 算法終止

每迭代一次，更新算法運(yùn)行次數(shù)generation=generation+1，當(dāng)達(dá)到最大迭代次數(shù)max_gen時(shí)，終止程序，輸出當(dāng)前結(jié)果作為最優(yōu)解。

3.7 算法性能測(cè)試

選擇混流裝配線經(jīng)典問題對(duì)自適應(yīng)遺傳算法的性能進(jìn)行驗(yàn)證。表1給出了標(biāo)準(zhǔn)遺傳算法和自適應(yīng)遺傳算法求解不同節(jié)拍的12個(gè)測(cè)試問題的解，其中mmin表示最優(yōu)工作站數(shù)。從表中可以看出，當(dāng)作業(yè)元素的個(gè)數(shù)較小時(shí)，標(biāo)準(zhǔn)GA和AGA都可以取得最優(yōu)解，隨著問題規(guī)模的擴(kuò)大，AGA逐漸表現(xiàn)出優(yōu)勢(shì)，所得平衡方案的平滑指數(shù)和聯(lián)合目標(biāo)函數(shù)值均比GA求解結(jié)果要小，說明了自適應(yīng)遺傳算法在求解混流裝配線平衡問題時(shí)是有效的。

表1 測(cè)試問題的解

4 算例研究

混流裝配線上生產(chǎn)A、B、C三種產(chǎn)品，計(jì)劃期內(nèi)的需求量為DA=400、DB=200、DC=300，則在每個(gè)最小生產(chǎn)循環(huán)內(nèi)，各產(chǎn)品將按照4:2:3的比例組織生產(chǎn)，即αA=4/9、αB=2/9、αC=1/3。所有產(chǎn)品的工序操作時(shí)間及綜合作業(yè)優(yōu)先關(guān)系的數(shù)據(jù)來自于文獻(xiàn)14，見表2所示。

表2 產(chǎn)品的綜合作業(yè)關(guān)系和作業(yè)元素時(shí)間

已知該混流裝配線的設(shè)計(jì)節(jié)拍為32s，共39個(gè)工序，按照本文所述多目標(biāo)優(yōu)化方法進(jìn)行工序平衡。運(yùn)用MATLAB語言編寫算法程序，設(shè)置自適應(yīng)遺傳算法的參數(shù)為：最大交叉概率pcmax=0.9，最大變異概率pmmax=0.1，種群規(guī)模popsize=30，最大迭代次數(shù)max_gen=100。以三種產(chǎn)品的加權(quán)平均作業(yè)時(shí)間作為該工序操作時(shí)間，得到問題的最優(yōu)解如表3所示，混流裝配線上需設(shè)置6個(gè)工作站，線平衡率為95.01%，平滑指數(shù)為5.93，各工作站間作業(yè)負(fù)荷較均衡，說明應(yīng)用本文的多目標(biāo)平衡優(yōu)化方法能夠得到相對(duì)最優(yōu)的工序分配方案。

表3 優(yōu)化結(jié)果對(duì)比分析

與文獻(xiàn)14的最優(yōu)解進(jìn)行對(duì)比，雖然本文優(yōu)化結(jié)果的平滑指數(shù)較優(yōu)，但線平衡率卻比文獻(xiàn)14低2.82%。分析原因如下：表4、表5分別列出了在表3所示的兩種最優(yōu)工序布置下，三種產(chǎn)品在各工作站內(nèi)的實(shí)際作業(yè)負(fù)荷。可以看出，在本文的最優(yōu)解下，各產(chǎn)品的平衡率較高，而文獻(xiàn)14中三種產(chǎn)品在各工作站間的負(fù)荷差異較大，尤其當(dāng)工作站1加工產(chǎn)品C以及工作站4加工產(chǎn)品A時(shí)，工作站瞬時(shí)負(fù)荷分別達(dá)到36.5s和35s，這使得裝配線實(shí)際節(jié)拍大于設(shè)計(jì)節(jié)拍32s，造成生產(chǎn)不穩(wěn)定。另外，表6中文獻(xiàn)14最優(yōu)解對(duì)應(yīng)的目標(biāo)函數(shù)值f2較大，f3較小，也說明文獻(xiàn)14的方法僅考慮了工作站間作業(yè)時(shí)間的一致性，而忽略了因不同產(chǎn)品作業(yè)時(shí)間差異所導(dǎo)致的工作站瞬時(shí)負(fù)荷不均衡問題。因此，在混流裝配線平衡過程中應(yīng)綜合考慮工作站間負(fù)荷平衡以及工作站內(nèi)不同產(chǎn)品之間的作業(yè)負(fù)荷平衡，以最大限度的發(fā)掘裝配線效率。

表4 文獻(xiàn)14中三種產(chǎn)品在不同工作站的作業(yè)情況

表5 本文多目標(biāo)優(yōu)化方法下三種產(chǎn)品在不同工作站的作業(yè)情況

表6 各目標(biāo)函數(shù)值對(duì)比

5 結(jié)論

針對(duì)U型混流裝配線平衡問題的特點(diǎn)，本文兼顧工作站平均負(fù)荷與瞬時(shí)負(fù)荷均衡問題，建立了以工作站數(shù)最小、工作站間平均單件產(chǎn)品以及工作站內(nèi)不同產(chǎn)品負(fù)荷均衡為目標(biāo)的優(yōu)化模型，同時(shí)應(yīng)用目標(biāo)法對(duì)各目標(biāo)函數(shù)進(jìn)行標(biāo)準(zhǔn)化處理，算例驗(yàn)證的結(jié)果表明多目標(biāo)優(yōu)化方法能夠有效的解決混裝線平衡問題。采用自適應(yīng)遺傳算法作為模型的求解方法，進(jìn)行標(biāo)桿案例研究，說明改進(jìn)AGA在求解大規(guī)模混流裝配線平衡問題時(shí)具有明顯優(yōu)勢(shì)。本文的研究成果能夠?yàn)槠髽I(yè)提供借鑒和參考，具有一定的理論與實(shí)踐意義。