基于層次聚類的機加工線平衡優化*

□ 李愛平 □ 傅 翔 □ 劉雪梅

同濟大學機械與能源工程學院 上海 201804

1　研究背景

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

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

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

2　問題描述

生產復雜零件時，由于待加工操作較多，一次裝夾難以完成全部加工，因此需要分多個工位依次加工，每個工位配備相應數量的機床，并使各工位以一個統一的節拍串行工作。柔性機加工生產線平衡指將需要加工的操作按一定的約束關系，以特定的方式分配至各工位，進而達到節拍最短、輔助時間最短、平衡率最高等優化目標。

2.1　加工元模型

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

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

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

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

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

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

2.2　約束模型

2.2.1 工藝約束

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

強制性約束指加工零件時必須嚴格執行的約束，如先面后孔、先粗后精、先基準后其它、先主后次等。經濟性約束指在加工過程中只對加工經濟產生影響的約束，加工元違反經濟性約束不會對零件加工質量產生影響。

2.2.2 裝夾約束

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

2.2.3 工位約束

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

式中：T0為理論節拍，由企業生產綱領決定；TP（k）為 k工位限制分配時間；M（k）為k工位配備的機床數。

總機床數M為各個工位機床數之和：

2.2.4 其它約束

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

2.3　優化目標

節拍及平衡率作為評價企業生產效率的主要技術指標，其重要性不言而喻。筆者以節拍和平衡率為主要優化目標，尋求整線節拍CT最小化、平衡率Bp最大化：

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

3　層次聚類處理

聚類分析是指在無引導的條件下，應用數學方法研究和處理所給對象的分類及各類之間的親疏程度。筆者應用層次聚類方法對樣本集合進行合并，直到滿足終止條件，完成聚類處理。

3.1　零件聚類模型

對于零件加工元集合 P=｛O1，O2，...，Oi，...，On｝，聚類的目的是將加工元按照約束關系及某種屬性關系分為 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。

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

3.1.1 相似因數

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

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

3.1.2 歐式距離因數

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

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

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

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

3.2.1相似度s1

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

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

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

表1　臥式四軸加工中心生產能力范圍

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

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

s14對應于工藝約束中強制性約束的定位與基準約束，表示加工元間的定位基準關系相似度。規定當加工元Oi與Oj具有相同的定位加工基準時，s14=1，否則s14=0。

3.2.2 相似度s2

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

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

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

3.2.3 相似度s

從2.2節可知，約束分為強制性約束和經濟性約束，在進行加工元間的相似度s計算時，s1是針對強制性約束設定的，s2是針對經濟性約束設定的。對于相似度s，可以采用加權處理，計算式為：

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

3.2.4 加工操作相異度矩陣

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

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

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

筆者采用基于凝聚的層次聚類法，將操作段數目控制在某個合適區間內。

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

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

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

（4）依據啟發式方法進行加工操作分組。

（5）進行單元組內排序。

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

4　遺傳算法

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

4.1　編碼

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

4.2　解碼

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

4.3　選擇

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

4.4　交叉變異

遺傳算法的交叉變異概率是影響算法性能的關鍵，直接影響算法的收斂性。筆者通過引入自適應策略對交叉變異算子進行優化改進，以避免算法早熟現象的產生。交叉概率Pc和變異概率Pm按如下公式進行自適應調整：

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

4.5　初始種群

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

5　算例

5.1　實例描述

筆者以某企業發動機缸體柔性生產線為例，進行線平衡優化。該企業現有臥式四軸加工中心9臺，夾具由專業夾具廠商合作生產。

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

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

5.2　層次聚類處理

5.2.1 計算各加工元相似度

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

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

表2　缸體頂面加工元信息

5.2.2 頂面相異度矩陣

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

5.2.3 閾值

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

5.3　算法求解

5.3.1 參數設置

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

5.3.2 遺傳算法對比

分別應用改進后的遺傳算法與傳統遺傳算法對這一問題進行求解，如圖2所示。對比圖2發現，改進后的算法收斂速度更快，效率更高，優化目標更佳，只需90次迭代便能找到最優解，而傳統遺傳算法要經過164迭代才能找到最優解。

▲圖2 遺傳算法對比

5.3.3 結果分析

算法運行50次后，得到最優解方案，見表3。該方案中，生產節拍為539.44 s，平衡率高達98.78%，工位數為6，其構型方案如圖3所示。筆者算法所得方案與企業自身規劃方案對比見表4，可以發現筆者的算法方案節拍縮短33.68 s，平衡率提高7.88個百分點。

表3　最優解方案

表4　方案對比

▲圖3 最優構型方案

綜上所述，應用層次聚類方法對加工元聚類分組，有效減少了加工元的種類數量，降低了問題求解的規模與難度?；诮徊孀儺愃阕幼赃m應的改進遺傳算法在求解線平衡問題中優勢明顯，不僅收斂速度更快，所求目標值更佳，而且可以有效降低生產節拍，提升線平衡率，對于提高企業市場競爭力具有較大幫助。

6　結語

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

［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］.計算機工程與應用，2006，42（5）：29-31.