改進蟻群算法對混合ASP和ALB問題研究

楊 卓，金雪峰

（武漢船用電力推進裝置研究所，武漢 430064）

改進蟻群算法對混合ASP和ALB問題研究

楊 卓，金雪峰

（武漢船用電力推進裝置研究所，武漢 430064）

本文利用蟻群算法對混合裝配序列規(guī)劃和裝配生產(chǎn)線平衡問題進行優(yōu)化求解。通過裝配聯(lián)絡圖來獲得表示裝配線上作業(yè)任務先后順序約束的裝配作業(yè)任務優(yōu)先關系圖。針對混合問題的新的優(yōu)化目標和約束條件，建立了一個混合優(yōu)化問題數(shù)學模型，并利用自適應改進后的蟻群算法對數(shù)學問題進行求解。

蟻群算法 ASP ALB

0 引言

裝配序列規(guī)劃（ASP）是對裝配過程中組裝零部件先后順序進行研究，裝配生產(chǎn)線平衡（ALB）是對裝配過程中各個站的工序的先后順序進行優(yōu)化，它們是裝配最優(yōu)化問題中的兩個重要的 NP組合優(yōu)化問題。過去的研究者們対這兩個問題都有大量的研究，然后極少有研究者們綜合地考慮這兩個方面，事實上不同的裝配序列會對生產(chǎn)線上的作業(yè)工序有極大的影響，單一研究ASP和ALB可能無法得到最優(yōu)的裝配方案。

ASP問題的所有優(yōu)化目標，都是將整個裝配體的裝配視為一個連貫、無間斷的過程，但是一旦當裝配體放在裝配生產(chǎn)線上去，就會被分配到各個不同的工作站上進行組裝，因此原先的裝配系列的優(yōu)化結果很有可能因為外部條件改變不適用了，從而導致這樣一個可能：裝配序列優(yōu)化所得到一個較好的裝配序列方案，放在裝配線上卻出現(xiàn)了一個糟糕的作業(yè)分配結果，使各個工作站之間的作業(yè)時間極度不均衡，反而降低了生產(chǎn)效率。本文使用改進蟻群算法對混合的ASP和ALB問題進行研究，規(guī)避單一研究的弊端，尋找裝配體最優(yōu)的裝配方法。

1 混合問題優(yōu)化目標

ASP問題的有三個的優(yōu)化目標，即裝配工具變換次數(shù)，裝配方向變換次數(shù)和裝配穩(wěn)定性的問題，如果能盡可能地減少總工具變換次數(shù)或總方向變化次數(shù)，則可以有效減少總的裝配時間。實際在生產(chǎn)線上生產(chǎn)時，零件是在工作站和工作站之間傳遞的，由于各個裝配作業(yè)耗費的時間有長有短，如果某個工作站上裝配時間過長，則它后面的工作站會陷入停滯狀態(tài)。混合 ASP和 ALB問題需要調整裝配序列并將它們合理分配到不同的工作站上，盡可能保證各個工作站的時間一致，從而減少停滯和等待時間。綜合考慮裝配序列的排序和工作站的分配，能得到最經(jīng)濟省時的裝配方案。

2 構建裝配聯(lián)絡圖

研究裝配序列時首先要保證裝配方案是可行的，裝配的可行性可以使用干涉矩陣進行判斷，矩陣中的每個元素表示的是對應的零部件在裝配時，其在±x，±y，±z方向上是否與其他零件有干涉關系。干涉矩陣F可以表示如下：

為了將裝配零件序列的序列排序轉化為裝配作業(yè)的序列排序問題，需要使用鄰接矩陣來表示零件間的連接關系，并用零件間的連接關系表示可能存在的所有裝配作業(yè)?？梢员硎境扇缦碌?n階方程：

其中

現(xiàn)在假設一個裝配體有1-9共九個零件，使用T1-T4共四種工具進行裝配。使用鄰接矩陣表示各個零件間的連接關系，然后將有連接關系的零件用有向線段連接起來，例如1→2表示的就是將2號零件裝到1號零件上。經(jīng)過干涉矩陣檢驗后，將不可能實現(xiàn)的連接關系去掉，將所用可能的裝配序列保留下來制作成一個有向圖，即是裝配序列聯(lián)絡圖。裝配序列聯(lián)絡圖中的每個點代表一個零件，每條有向邊代表的是一個裝配作業(yè)，不同的裝配作業(yè)使用不同的工具。一個典型的裝配體的裝配序列聯(lián)絡圖如圖1所示:

裝配序列聯(lián)絡圖中包含了零件的裝配順序優(yōu)先關系，同時也包含了零件與零件間裝配過程的順序關系。通過裝配序列聯(lián)絡圖，我們就可以將零件裝配序列問題轉化為作業(yè)序列問題。裝配聯(lián)絡圖完成之后，接下來建立數(shù)學模型并使用蟻群算法來搜索最優(yōu)的裝配作業(yè)分配到各個工作站上的方案。

3 混合問題建模

假設作業(yè)任務總數(shù)為 n，完成第i個作業(yè)任務的時間為it，工作站總數(shù)為m，第 j個工作站上工具變換次數(shù)為工作站的節(jié)拍為 c，那么我們的優(yōu)化目標就是最小化工作站的數(shù)量，所以優(yōu)化問題的目標是:

1）使裝配線平衡率盡可能的大，裝配線平衡率是反應裝配線上各個工作站之間時間的均衡程度，是考核裝配效率和裝配成本的重要指標，各個工作站工時相差的越大，則平衡率越低。即

其中，LE為裝配線的平衡率，錯誤！未找到引用源。是第k個工作站上的所有裝配作業(yè)任務本身的裝配時間，m是工作站的數(shù)量。

2）使裝配線的平滑性指數(shù)盡可能的低，裝配線平滑性指數(shù)反應的是各個工作站上作業(yè)時間分布的離散情況，這個值越大，則各個工作站之間的作業(yè)時間相差越大，那么停滯等待和超載負荷的時間也就越長。即

其中，SI為裝配線的平衡性指數(shù)。

在完成優(yōu)化目標的基礎上，還要滿足的一定約束條件則是：

1）所有作業(yè)任務都應該被分配到工作站中，不能有遺漏，即

其中，錯誤！未找到引用源。為分配的第k個工作站的作業(yè)任務的集合，E為裝配線上任務的集合，錯誤！未找到引用源。，n為作業(yè)任務的數(shù)量。

2）每個作業(yè)任務只能分配到一個工作站上，不同的工作站上不會有相同的裝配作業(yè)任務，即

3）裝配作業(yè)任務的分配需要滿足之前的裝配作業(yè)優(yōu)先關系圖，若一個裝配作業(yè)任務的緊前任務被安在某個工作站中，那么該作業(yè)任務肯定只能分配到這個工作站或其后的工作站中，即

其中，錯誤！未找到引用源。，W為裝配作業(yè)任務優(yōu)先關系矩陣。

4）每個工作站上的裝配作業(yè)總時間不能超過工作站的生產(chǎn)節(jié)拍時間，即

其中，c為裝配線的節(jié)拍，錯誤！未找到引用源。

為第k個工作站上的總裝配時間。

4 使用蟻群算法尋找最優(yōu)解

蟻群算法中，螞蟻將裝配作業(yè)任務分配到每一個工作站的過程，其實是可以想象為一群螞蟻沿著裝配任務優(yōu)先圖爬行的過程，每只螞蟻圖中每個節(jié)點上，選擇下一條路徑的概率，是依據(jù)當前可選路徑上在信息素的殘留余量和啟發(fā)式信息，并且受到裝配任務先后順序關系和生產(chǎn)任務節(jié)拍時間的約束與限制，當螞蟻在沿著裝配作業(yè)任務優(yōu)先圖上完成一次爬行，并經(jīng)過所有的節(jié)點，則是代表所有任務都被分配到了工作站中，從而求得了一個可行解。本文所使用的蟻群算法的求解流程如圖4-1所示。這種解法可以有效的保證可行解的獲得，其中，每只螞蟻都是按照以下規(guī)則進行搜索：

1）開啟一個新的工作站，定制節(jié)拍時間c； 2）在未分配的作業(yè)任務集合中，依據(jù)裝配作業(yè)任務優(yōu)先關系圖，構建初始可分配任務集；3）若可分配作業(yè)任務集為非空集合，則從可分配任務集中，依據(jù)搜索算法的規(guī)則，挑選出一項新的作業(yè)任務分配至目前正在進行裝配的工作站，并計算當前工作站上的裝配作業(yè)任務總時間

若錯誤！未找到引用源。，且未分配任務不為空，則更新可分配任務集，同時進行局部信息素更新，重復步驟 2）和 3）。若錯誤！未找到引用源。，則轉至步驟5）。若未分配任務為空集，則轉至步驟 6）；5）中止任務到當前工作站上的分配，開啟一個新的工作站作為當前工作站，重復步驟2）3）4）；6）所有任務已經(jīng)分配完，終止算法。輸出可行解的結果，并依據(jù)優(yōu)化目標函數(shù)進行評價和信息素更新。

5實驗驗證

對Tseng和Chen的論文［1］中的裝配實例進行求解，使用MATLAB編寫算法，求得解裝配線平衡率LE值越大，裝配線平衡性指數(shù)SI越小，則求得的解越佳。

從對比圖上可以看出節(jié)拍時間為28分鐘，目標函數(shù)值最大，結果較好。現(xiàn)在取節(jié)拍時間為28分鐘，求取最優(yōu)裝配方案，收斂曲線如圖4所示。

在Tseng和Chen的論文［1］中，他們使用混合遺傳算法求得的最優(yōu)方案與本文結果略有不同的，原論文中的裝配最優(yōu)方案的裝配線平衡率LE=89.6%，總裝配時間為 75.4分鐘。雖然原論文中的裝配線平衡性的目標函數(shù)與本文不同，不妨用本文的裝配線平衡性的計算方式來計算這一方案中各個工作站間作業(yè)時間的平滑性，得SI=4.06。將兩個裝配方案的參數(shù)進行比較，如表1所示。

6 結論

使用改進后的蟻群算法對混合問題進行求解，證明了使用本文中提出的數(shù)學模型處理裝配體在生產(chǎn)線上的裝配問題是可行的，同時用實例驗證，所得到的計算收斂速度較快，計算結果與原文中的結果相比較更好，驗證了本文中提出的混合問題的數(shù)學模型和處理方法的有效性與實用性。

參考論文:

［1]H. E. Tseng. Hybrid evolutionary multi-objective algorithms for integrating assembly sequence planning and assembly line balancing［J］. International Journal of Production Research， November 1， 2008， 46（21）: 5951-5977.

［2]H. E. Tseng， C. E. Tang. A sequential consideration for assembly sequence planning and assembly line balancing using the connector concept［J］. International Journal of Production Research， January 1， 2006， 44（1）: 97-116.

［3]趙姍姍，李宗斌. 一種新的裝配序列規(guī)劃方法研究［N］. 西安交通大學學報， 2007， 41（5）: 580-584.

［4]于建明，蔡建國. 裝配建模及裝配順序分層規(guī)劃方法研究［J］. 機械科學與技術， 2000， 19（4）: 671-673.

［5]ZhouPing Yin. A connector based hierarchical approach to assembly sequence planning for mechanical assemblies［J］. Computer-Aided Design，2003， 35（1）: 37-56.

Research on Hybrid Assembly Sequence Planning and Assembly Line Balancing Question with Ant Colony Algorithm

Yang Zhuo， Jin Xuefeng
（Wuhan Institute of Marine Electric Propulsion， Wuhan 430064， China）

In this paper， the ant colony algorithm is used to solve the hybrid assembly sequence planning and assembly line balancing question through the assembly liaison graph to obtain the assembly task priority graph. In view of new optimization objectives and constraint conditions of the hybrid question， the mathematical model of a hybrid optimization question is established and the ant colony algorithm is improved to solve mathematical question.

colony algorithm； assembly sequence planning； assembly line balancing

O29

A

1003-4862（2016）07-0073-04

2016-03-15

楊卓（1988-），男，碩士。研究方向：仿真模型。