基于層次聚類的機加工線平衡優(yōu)化*

□ 李愛平 □ 傅 翔 □ 劉雪梅

同濟大學(xué)機械與能源工程學(xué)院 上海 201804

1　研究背景

生產(chǎn)制造企業(yè)為滿足客戶對于交貨期的需求，期望以最短的時間加工出高質(zhì)量的零件。因此，節(jié)拍與平衡率成為衡量生產(chǎn)線優(yōu)劣的主要技術(shù)指標(biāo)。線平衡問題自1955年由Salveson［1］第一次提出以來，一直都是熱點問題，業(yè)內(nèi)諸多專家學(xué)者及工程技術(shù)人員都對其進(jìn)行了研究。但由于線平衡問題的復(fù)雜性，即使最簡單的問題也都屬于非確定多項式難題［2］，且大規(guī)模線平衡問題尤其復(fù)雜，因此仍需尋求較為便捷的方法解決該問題。

文獻(xiàn)［3］針對柔性加工線平衡問題，提出了工位配置、操作分配與排序的方法，這一方法考慮了多種約束條件，通過設(shè)計多目標(biāo)算法獲得了較優(yōu)解。文獻(xiàn)［4］通過應(yīng)用基于貪婪隨機自適應(yīng)搜索算法的啟發(fā)式算法來優(yōu)化可重構(gòu)機加工線多目標(biāo)平衡問題，取得了不錯的成果，但這一方法只適用于加工操作數(shù)較少的情況。文獻(xiàn)［5-6］針對機加工線平衡問題，提出了混合整數(shù)規(guī)劃的數(shù)學(xué)模型及基于貪婪隨機自適應(yīng)搜索算法的啟發(fā)式算法，處理大規(guī)模生產(chǎn)線的平衡問題，但存在算法復(fù)雜、收斂較慢、效率較低等問題。文獻(xiàn)［7］等在COMSOAL技術(shù)和回溯方法論的基礎(chǔ)上，提出了一種啟發(fā)式算法，考慮特征之間的加工優(yōu)先級和兼容性約束關(guān)系，針對機加工線中各裝夾下的加工元聚類排序問題，在減少主軸頭和工作站數(shù)量的同時，獲得了比較理想的節(jié)拍和平衡率，這一方法在求解大規(guī)模機加工線平衡問題時表現(xiàn)出較優(yōu)的特性。文獻(xiàn)［8］以減少設(shè)備數(shù)量為目標(biāo)，將加工操作進(jìn)行分模塊處理，并將其按一定的約束條件合理分配至各個機床，同時研究了幾種較優(yōu)算法對不同特征操作數(shù)量的優(yōu)化結(jié)果，從而得出在一定范圍內(nèi)適宜采用的算法。

可見，盡管國內(nèi)外諸多學(xué)者都對線平衡問題進(jìn)行了大量研究，也取得了較為豐碩的成果，但在求解大規(guī)模機加工線平衡問題時，仍存在算法復(fù)雜、求解效率較低等問題。筆者在總結(jié)之前研究的基礎(chǔ)上，提出一種基于層次聚類處理的加工元聚類方法，將加工元分為不同組單元，并應(yīng)用改進(jìn)的遺傳算法進(jìn)行優(yōu)化求解。

2　問題描述

生產(chǎn)復(fù)雜零件時，由于待加工操作較多，一次裝夾難以完成全部加工，因此需要分多個工位依次加工，每個工位配備相應(yīng)數(shù)量的機床，并使各工位以一個統(tǒng)一的節(jié)拍串行工作。柔性機加工生產(chǎn)線平衡指將需要加工的操作按一定的約束關(guān)系，以特定的方式分配至各工位，進(jìn)而達(dá)到節(jié)拍最短、輔助時間最短、平衡率最高等優(yōu)化目標(biāo)。

2.1　加工元模型

通常，零件都由攜帶加工信息的特征所組成，若一個零件由m個特征組成，則由這m個特征組成零件的加工特征集F可表示為：

式中：fi為零件的第i個特征元。

由于每個特征元對應(yīng)一種或多種加工方法鏈，而每種加工方法鏈又由多個元素組成，因此筆者將這樣的元素稱為加工元，則零件的加工序列可以表示為：

式中:Oi為第i個加工元；n為加工元總數(shù)。

為完整表示加工元的屬性，筆者引入五維向量Oi=｛WID，WTool，WFix，WTAD，WTime｝，WID為加工操作編號，WTool為所采用的刀具，WFix為所采用的夾具，WTAD為該加工操作所在工位刀具可進(jìn)刀的方向，WTime為加工時間。

對于每一個加工元，都有以下約束：① 一個加工元屬于且僅屬于一個特征元；②一個加工元屬于且僅屬于一個加工階段；③一個加工元屬于且僅屬于一個工位；④一個加工元有且僅使用一把刀具；⑤ 一個加工元屬于且僅屬于一個裝夾。

2.2　約束模型

2.2.1 工藝約束

加工元分配時需要遵循一定的工藝約束準(zhǔn)則，這樣才能保證零件的加工質(zhì)量，取得良好的經(jīng)濟效益。根據(jù)加工元之間的強弱關(guān)系，可分為強制性約束與經(jīng)濟性約束兩大類。

強制性約束指加工零件時必須嚴(yán)格執(zhí)行的約束，如先面后孔、先粗后精、先基準(zhǔn)后其它、先主后次等。經(jīng)濟性約束指在加工過程中只對加工經(jīng)濟產(chǎn)生影響的約束，加工元違反經(jīng)濟性約束不會對零件加工質(zhì)量產(chǎn)生影響。

2.2.2 裝夾約束

零件加工時需要利用夾具對其進(jìn)行定位夾緊，以便刀具準(zhǔn)確定位加工。由于夾具的遮擋，使一些特征不能被刀具加工，因而產(chǎn)生了裝夾約束。

2.2.3 工位約束

為取得良好的平衡效果，將加工元分配至各工位時，需滿足工位時間約束：

式中：T0為理論節(jié)拍，由企業(yè)生產(chǎn)綱領(lǐng)決定；TP（k）為 k工位限制分配時間；M（k）為k工位配備的機床數(shù)。

總機床數(shù)M為各個工位機床數(shù)之和：

2.2.4 其它約束

此外，還有一些其它約束，如包含約束與不包含約束。包含約束要求某些加工元必須在一次裝夾下完成加工，不包含約束要求某些加工元不能在同一裝夾下加工，需分工位加工。

2.3　優(yōu)化目標(biāo)

節(jié)拍及平衡率作為評價企業(yè)生產(chǎn)效率的主要技術(shù)指標(biāo)，其重要性不言而喻。筆者以節(jié)拍和平衡率為主要優(yōu)化目標(biāo)，尋求整線節(jié)拍CT最小化、平衡率Bp最大化：

式中：Ti為工位i的節(jié)拍；Tsum為加工零件所需的總時間。

3　層次聚類處理

聚類分析是指在無引導(dǎo)的條件下，應(yīng)用數(shù)學(xué)方法研究和處理所給對象的分類及各類之間的親疏程度。筆者應(yīng)用層次聚類方法對樣本集合進(jìn)行合并，直到滿足終止條件，完成聚類處理。

3.1　零件聚類模型

對于零件加工元集合 P=｛O1，O2，...，Oi，...，On｝，聚類的目的是將加工元按照約束關(guān)系及某種屬性關(guān)系分為 K 類，C=｛C1，C2，...，CK｝（K≤n）， 這 K 類需滿足：①Ci≠i=1，2，...，K；②Ci=｛C1，C2，...，CK｝；③ Ci∩Cj=，i，j=1，2，...，K 且 i≠j。

為確定待聚類加工元間的相近關(guān)系，需度量加工元間的相似程度或非相似程度，再用適當(dāng)方法進(jìn)行聚類分組，建立分類譜系圖。聚類分析方法通常使用相似因數(shù)（向量夾角余弦）和歐氏距離因數(shù)等作為分類統(tǒng)計量。

3.1.1 相似因數(shù)

設(shè)輸入數(shù)據(jù)空間Rm中n個樣品定量觀測數(shù)Xα=（xα1，xα2，...，xαm）T，α=1，2，...，n，定義相似因數(shù)衡量樣品之間的相似程度：

式中：Sαβ為相似因數(shù)，即 α、β 兩個樣品向量 Φ（Xα）和Φ（Xβ）之間的夾角余弦，并且具有對稱性，Sαβ=Sβα，Sαβ∈［-1,1］。

3.1.2 歐式距離因數(shù)

式中：Dαβ為 α、β 兩樣品向量 Φ（Xα）和 Φ（Xβ）之間的歐式距離二次方，Dαβ同樣具有對稱性，Dαβ=Dβα。

3.2　加工操作之間相似度的計算

筆者采用相似度s表示兩加工元之間的相近關(guān)系。與一般的聚類方法不同，裝夾規(guī)劃的加工單元之間存在各種約束關(guān)系，因此此處采用一種啟發(fā)式方法進(jìn)行聚類處理。

在聚類處理中，相似度越大表示加工元之間相似程度越高，越適合在同一裝夾下加工。定義相似度s由兩部分組成，即 s=（s1，s2），其中 s1為待聚類的加工元必須滿足制造資源加工能力約束，s2為加工元間的位置公差，兩者進(jìn)一步表征了加工元之間的親疏關(guān)系。

3.2.1相似度s1

規(guī)定相似度 s1由四部分組成， 即 s1=（s11，s12，s13，s14）。

s11為兩加工元所使用的機床設(shè)備相似度，若Oi與Oj都能在同一機床設(shè)備上加工，則s11=1，否則s11=0。

筆者使用的是臥式四軸加工中心，其生產(chǎn)能力范圍見表1。

表1　臥式四軸加工中心生產(chǎn)能力范圍

s12為兩加工元間的加工刀具相似度，當(dāng)加工元Oi與Oj使用相同型號規(guī)格的刀具時，s12=1，否則s12=0。

s13為兩加工元間的加工方位面相似度，當(dāng)加工元Oi與Oj具有相同的可加工方向時，s13=1，否則s13=0。

s14對應(yīng)于工藝約束中強制性約束的定位與基準(zhǔn)約束，表示加工元間的定位基準(zhǔn)關(guān)系相似度。規(guī)定當(dāng)加工元Oi與Oj具有相同的定位加工基準(zhǔn)時，s14=1，否則s14=0。

3.2.2 相似度s2

相似度 s2由兩部分組成，即 s2=（s21，s22）。

s21為兩加工元間的形位公差關(guān)系，當(dāng)加工元Oi與Oj間具有形位公差時，s21=1，否則s21=0。

s22為切削力大小，主要針對精度高、需要分階段加工的特征操作。當(dāng)零件加工精度要求高或剛度差時，對零件的某些特征需分階段進(jìn)行，粗加工與精加工的參數(shù)設(shè)置不同，切削力大小相差較大，此時若將不同加工階段的加工元聚合到一起，容易引起零件切削變形量增大。規(guī)定當(dāng)加工元Oi與Oj屬于同一個加工階段時，s22=1；當(dāng)加工元Oi與Oj分別屬于精加工與粗加工時，s22=0；當(dāng)加工元Oi與Oj分別屬于半精加工與粗加工或半精加工與精加工時，s22=0.7。

3.2.3 相似度s

從2.2節(jié)可知，約束分為強制性約束和經(jīng)濟性約束，在進(jìn)行加工元間的相似度s計算時，s1是針對強制性約束設(shè)定的，s2是針對經(jīng)濟性約束設(shè)定的。對于相似度s，可以采用加權(quán)處理，計算式為：

考慮到強制性約束對于聚類的重要性，設(shè)定α1=10，α2=1。

3.2.4 加工操作相異度矩陣

由式（9）相似度計算公式，分別計算兩兩加工元間的相似度值，并將其存入下三角矩陣，得到相異度矩陣SN×N：

3.3　基于不同閾值的操作聚類

通過相異度矩陣計算出兩兩加工元間的相似度，將其聚合后組成加工元段。聚類的粒度粗細(xì)需控制適當(dāng)，若粒度過細(xì)，則聚類后的加工元種類仍然較多，不能起到降低問題規(guī)模的目的；若粒度過粗，則問題的某些性質(zhì)被模糊，聚類后加工元種類的多樣性降低，影響算法求解的解空間?？梢?，聚類分析的閾值設(shè)置顯得尤為重要［9］。

筆者采用基于凝聚的層次聚類法，將操作段數(shù)目控制在某個合適區(qū)間內(nèi)。

（1）按公式計算零件所有加工元間的相似度s（Oi，Oj）。

（2）根據(jù)相似度s生成加工元間的相異度矩陣SN×N。

（3）設(shè)定閾值σ，根據(jù)相異度矩陣，將矩陣內(nèi)的元素按數(shù)值從小到大進(jìn)行排列 σ1＜σ2＜σ3＜...＜σn。 分別設(shè)定閾值 σ=σ1，σ2，．．．，σn，針對不同閾值得到不同層次的聚類結(jié)果，其中r為操作段的編號，σn為該操作段的閾值。

（4）依據(jù)啟發(fā)式方法進(jìn)行加工操作分組。

（5）進(jìn)行單元組內(nèi)排序。

按這一聚類方法，可對發(fā)動機缸體零件各個方位面上的加工元進(jìn)行聚類處理，以減小問題規(guī)模。

4　遺傳算法

遺傳算法是一種通過模擬自然界物種進(jìn)化過程，尋求全局最優(yōu)的隨機搜索算法，具有較強的魯棒性和通用優(yōu)化能力，廣泛用于求解各類復(fù)雜問題。筆者對傳統(tǒng)遺傳算法進(jìn)行優(yōu)化改進(jìn)，將其應(yīng)用于求解線平衡優(yōu)化問題。

4.1　編碼

為簡化算法運算，筆者對每一個加工元進(jìn)行編號，采用加工元序列號編碼方式，將加工元排列為一個向量，作為一個染色體。

4.2　解碼

解碼過程即產(chǎn)生解方案的過程，筆者按照各工位裝夾約束及時間約束，將加工元序列編號分配至各工位，產(chǎn)生最終解方案。

4.3　選擇

選擇算子采用輪盤賭選擇方式，有助于將適應(yīng)度值較大的個體保存下來。

4.4　交叉變異

遺傳算法的交叉變異概率是影響算法性能的關(guān)鍵，直接影響算法的收斂性。筆者通過引入自適應(yīng)策略對交叉變異算子進(jìn)行優(yōu)化改進(jìn)，以避免算法早熟現(xiàn)象的產(chǎn)生。交叉概率Pc和變異概率Pm按如下公式進(jìn)行自適應(yīng)調(diào)整：

式中：Pcmax、Pcmin為交叉概率的上下限；Pmmax、Pmmin為變異概率的上下限；fmax為種群的最大適應(yīng)度；favg為種群適應(yīng)度平均值；f′為參與交叉的兩個個體中較大的適應(yīng)度；f為參與變異的兩個個體中較大的適應(yīng)度。

4.5　初始種群

隨機生成yPop個個體組成初始種群。每一個個體按加工元之間的強制性約束和經(jīng)濟性約束分配至各工位，這樣不僅滿足各種約束關(guān)系，而且具有較高的初始平衡率。

5　算例

5.1　實例描述

筆者以某企業(yè)發(fā)動機缸體柔性生產(chǎn)線為例，進(jìn)行線平衡優(yōu)化。該企業(yè)現(xiàn)有臥式四軸加工中心9臺，夾具由專業(yè)夾具廠商合作生產(chǎn)。

▲圖1 缸體三維模型及加工特征

圖1為發(fā)動機缸體三維模型及其加工特征。表2為缸體頂面加工元信息。根據(jù)前文所述，已將同一類型操作聚為一類，如表2中4個缸套孔合并為一個加工單元。經(jīng)初步統(tǒng)計，該缸體零件共有69個加工特征、149個加工元。在此基礎(chǔ)上，再進(jìn)行層次聚類處理。限于篇幅，筆者以缸體頂面為例進(jìn)行聚類分組。

5.2　層次聚類處理

5.2.1 計算各加工元相似度

由表2可知，加工元O1與O2均可使用臥式四軸加工中心加工，s11=1；刀具相同，s12=1；進(jìn)刀方向一致，s13=1；定位基準(zhǔn)相同，s14=1；由于兩者不存在公差關(guān)系，s21=0；頂面粗精銑分屬于粗加工與精加工，s22=0。加工元O1與O2的相似度可根據(jù)式（9）計算得到：

同理，可得其它加工元間的相似度：

表2　缸體頂面加工元信息

5.2.2 頂面相異度矩陣

將上述所求相似度值輸入相異度矩陣S19×19：

5.2.3 閾值

遍歷相異度矩陣，可得其相似度值處于0～41區(qū)間范圍內(nèi)，按從小到大排列為 0＜30＜30.7＜31＜32＜41。 依次按照相似度值設(shè)定相應(yīng)的閾值，得到最優(yōu)加工單元組為：=｛O1，O8，O10，O11｝，=｛O2，O5，O6，O7｝，=｛O3，O4｝，=｛O9，O12，O13，O14｝，=｛O15，O16｝，=｛O17，O18，O19｝。

5.3　算法求解

5.3.1 參數(shù)設(shè)置

筆者設(shè)置如下：yPop=30，Pcmax=0.6，Pcmin=0.1，Pmmax=0.07，Pmmin=0.01，迭代次數(shù) Gmax=300。

5.3.2 遺傳算法對比

分別應(yīng)用改進(jìn)后的遺傳算法與傳統(tǒng)遺傳算法對這一問題進(jìn)行求解，如圖2所示。對比圖2發(fā)現(xiàn)，改進(jìn)后的算法收斂速度更快，效率更高，優(yōu)化目標(biāo)更佳，只需90次迭代便能找到最優(yōu)解，而傳統(tǒng)遺傳算法要經(jīng)過164迭代才能找到最優(yōu)解。

▲圖2 遺傳算法對比

5.3.3 結(jié)果分析

算法運行50次后，得到最優(yōu)解方案，見表3。該方案中，生產(chǎn)節(jié)拍為539.44 s，平衡率高達(dá)98.78%，工位數(shù)為6，其構(gòu)型方案如圖3所示。筆者算法所得方案與企業(yè)自身規(guī)劃方案對比見表4，可以發(fā)現(xiàn)筆者的算法方案節(jié)拍縮短33.68 s，平衡率提高7.88個百分點。

表3　最優(yōu)解方案

表4　方案對比

▲圖3 最優(yōu)構(gòu)型方案

綜上所述，應(yīng)用層次聚類方法對加工元聚類分組，有效減少了加工元的種類數(shù)量，降低了問題求解的規(guī)模與難度。基于交叉變異算子自適應(yīng)的改進(jìn)遺傳算法在求解線平衡問題中優(yōu)勢明顯，不僅收斂速度更快，所求目標(biāo)值更佳，而且可以有效降低生產(chǎn)節(jié)拍，提升線平衡率，對于提高企業(yè)市場競爭力具有較大幫助。

6　結(jié)語

筆者針對現(xiàn)有方法在求解大規(guī)模機加工線平衡問題時存在算法復(fù)雜、效率較低等問題，提出了一種針對發(fā)動機缸體類零件加工特征的層次聚類方法。首先對零件特征進(jìn)行轉(zhuǎn)化，以加工元為最小單位，構(gòu)建加工元先后約束、工藝約束、裝夾約束及工位約束；然后以節(jié)拍、平衡率為優(yōu)化目標(biāo)，建立了基于層次聚類的線平衡問題求解模型；接著對交叉變異算子采用自適應(yīng)策略，改進(jìn)了傳統(tǒng)遺傳算法，從而加快了算法運行效率，有效避免算法陷入早熟，提升了解搜索空間；最后以某企業(yè)發(fā)動機缸體生產(chǎn)線為例，將分組后的加工單元組分配至各工位，達(dá)到了較好的平衡效果，對于指導(dǎo)企業(yè)生產(chǎn)具有重要的實際意義。

［1］ SALVESON M E.The Assembly Line Balancing Problem［C］.Proceedings of the Second Symposium in Linear Programming，Washington D C，1955.

［2］ TANG Q H，LI Z X，ZHANG L P，et al.Effective Hybrid Teaching-learning-based Optimization Algorithm for Balancing Two-sided Assembly Lines with Multiple Constraints［J］.Chinese Journal of Mechanical Engineering， 2015， 28（5）：1067-1079.

［3］ 劉雪梅，孟飛飛，李愛平，等.基于多色集合理論和遺傳算法的加工中心工步排序研究［J］.中國機械工程，2013，24（18）：2437-2442.

［4］ DELORME X， MALYUTIN S， DOLGUI A.A Multiobjective Approach for Design of Reconfigurable Transfer Lines［J］.IFAC-PapersOnLine， 2016， 49（12）：509-514.

［5］ ESSAFI M，DELORME X，DOLGUI A.A GRASP Heuristic for Sequence-Dependent Transfer Line Balancing Problem［J］.IFAC Proceedings Volumes， 2009， 42（4）：762-767.

［6］ ESSAFI M， DELORME X， DOLGUI A， et al.A MIP Approach for Balancing TransferLine with Complex Industrial Constraints［J］.Computers&Industrial Engineering， 2010， 58（3）：393-400.

［7］ FINEL B， DOLGUI A，VERNADAT F.A Random Search and Backtracking Procedure for Transfer Line Balancing［J］.International Journal of Computer Integrated Manufacturing，2008， 21（4）：376-387.

［8］ GUSCHINSKAYA O， DOLGUI A.Comparison of Exact and Heuristic Methods for a Transfer Line Balancing Problem［J］.International Journal of Production Economics， 2009， 120（2）：276-286.

［9］ 王倫文.聚類的粒度分析［J］.計算機工程與應(yīng)用，2006，42（5）：29-31.