陳 帥，晁永生，江 韓

(新疆大學機械工程學院，烏魯木齊 830047)

0 引言

裝配線平衡研究主要被分為兩大類：一種是給定生產線節(jié)拍，以最小工作站數(shù)目為優(yōu)化目標的第一類裝配線平衡問題[1]；另一種是給定裝配線工作站數(shù)，以最小生產節(jié)拍為優(yōu)化目標的第二類裝配線平衡問題[2]。第一類裝配線平衡問題只產生在設計一條新的裝配線時，而每當現(xiàn)有的裝配線做出調整需要重新達到平衡時，第二類裝配線平衡問題就會隨之產生[3]，而且隨著企業(yè)裝配環(huán)境的復雜化，往往需要對第二類裝配線平衡問題的多個目標進行優(yōu)化。

在實際裝配生產中、每個任務完成裝配所需的零部件存儲在對應工位的零部件放置區(qū)，由于不同任務所需的零部件尺寸范圍跨度大，造成不同工位的占地面積具有很大差異，不便于物流運輸與人員行走，導致物流運輸效率低下增加不必要的時間成本，因此應考慮任務所需的占地面積，合理分配任務到工位上使得每個工位的占地面積相對均勻。同時在重新規(guī)劃裝配線時，某些工位會增加新的任務因此工人需要學習如何裝配新的任務，而不同的任務，裝配難度是不同的，因此對應所需要花費的學習成本也不同，所以當工位增加新的任務時會帶來學習成本的增加，為了降低企業(yè)重新調整裝配線的總成本，在優(yōu)化其他目標的同時應該盡可能最小化學習成本。因此面臨特定的裝配環(huán)境時需要考慮對多個目標同時進行優(yōu)化以保證求解結果滿足實際的生產需求。

蟻獅算法[4](Ant Lion Algorithm,ALA)是一種新型智能群算法，具有尋優(yōu)效率高，全局搜索尋優(yōu)能力強等優(yōu)點，目前已在多個領域[5-7]內得到了應用，并且取得了不錯的效果，本文在單目標蟻獅算法的基礎上提出一種多目標蟻獅算法(Multi-objective Ant Lion Algorithm,MOALA)，運用于第二類多目標裝配線平衡問題的求解。通過對實例算例求解并與改進多目標粒子群算法對比分析，驗證該算法的有效性和優(yōu)越性。

1 第二類多目標裝配線平衡問題的數(shù)學模型

1.1 問題描述

為了簡化問題,只考慮任務分配過程中所需的零部件占地面積不同，合理分配任務到工位上使得各工位的占地面積相對均衡，同時最小化工位的生產節(jié)拍以提高生產效率，并且盡可能降低調整后的裝配分配方案帶來的學習成本。

某企業(yè)實例裝配作業(yè)任務的任務信息和調整前后的裝配方案如表1所示，給定的工位數(shù)目為3。調整前后裝配方案的節(jié)拍分別為17，15，每個工位所需占地面積分別為[48.2,46.7,12.8]，[37.2,27.3,43.2]，可知調整后的裝配方案較調整前在節(jié)拍和占地面積均衡性上都要好，但是由于工位2和工位3增加了新的任務，所以也帶來了學習成本，新增加的任務為任務6與任務3,4，所以學習成本的累積和是17。

表1 任務信息與調整前后的裝配方案

本文以最小化生產節(jié)拍、學習成本，占地面積均衡指標為目標建立第二類多目標裝配線平衡問題的優(yōu)化模型，假設：①每個任務都有穩(wěn)定的任務時間且學習成本和所需的占地面積都是固定的；②必須將所有的任務都分配到工位中；③工位個數(shù)是確定的；④任務的分配不能違反優(yōu)先關系約束。

1.2 數(shù)學模型

變量及其含義定義如下：n為任務數(shù)；m為工位數(shù)；I為任務矩陣，I=(1,2,…,n)為行向量，由所有任務序號構成；t(i)為任務i的操作時間，Cost(i)為任務i的學習成本，Area(i)為任務i所需要的占地面積，i為I內任務；Pdn×n為優(yōu)先關系矩陣，如果任務i1是i2的優(yōu)先任務，Pd(i2,i1)=1，否則為0；J為工位矩陣，J=(1,2,…,m)由所有I中的元素構成；j為J內元素；ST(j)為工位j的裝配時間；Sq(j)表示工位j所分配到的任務集合。

CT為裝配線節(jié)拍：

CT=max{ST(1),ST(2),…,ST(m)}

(1)

CtTheory為裝配線節(jié)拍的理論值：

(2)

WArea(j)為工位j的占地面積：

WArea(j)=∑(Area(Sq(j)))

(3)

其中，MArea為所有工位當中最大的占地面積：

MArea=max(WArea(1),…,WArea(m))

(4)

(5)

決策變量：

xij，0-1變量，當任務i被分配到第j個工位時，xij=1，否則xij=0。

目標函數(shù)：

Z={Z1,Z2,Z3}

(6)

Z1=minCT

(7)

(8)

(9)

約束條件：

(10)

ST(j)≤CT

(11)

(12)

模型說明：式(6)表示同時優(yōu)化3個目標值；其中優(yōu)化目標Z1如式(7)所示最小化工位的生產節(jié)拍；優(yōu)化目標Z2如式(8)所示，最小化由每個工位新增加的操作任務帶來的學習成本；優(yōu)化目標Z3如式(9)所示最小化工位占地面積均衡指標使得空間面積得到合理化的應用。式(10)表示每個任務只能與一個工作站相匹配，不能進行重復分配；式(11)表示生產節(jié)拍約束，每個工位的操作時間都應小于或等于生產節(jié)拍；式(12)表示優(yōu)先關系約束。其中式(10)～式(12)對應的3種約束被稱為裝配線平衡的基本約束。

2 求解第二類多目標裝配線平衡問題的蟻獅

算法

求解第二類多目標裝配線平衡優(yōu)化問題，難點在于確保最優(yōu)解集的均勻性和多樣性，本文在單目標蟻獅算法的基礎上提出一種多目標蟻獅算法用于求解該問題，通過引入解碼和基于牛頓二分法的解碼裝配任務分配規(guī)則，使得每個個體均滿足裝配線平衡的基本約束；引入Pareto支配規(guī)則，確保得到的精英蟻獅群為最優(yōu)解集，為了保證最優(yōu)解集的均勻性和多樣性，去除單目標蟻獅算法中的蟻獅捕食規(guī)則而是將螞蟻和蟻獅種群合并成新種群并且引入基于非支配排序和擁擠度的精英保留策略更新蟻獅種群的位置。多目標蟻獅算法的流程如圖1所示。

圖1 多目標蟻獅算法流程圖

2.1 解碼和基于牛頓二分法的解碼裝配任務分配

假設個體的位置為向量PosList，輸出的任務序列矩陣為TaskList，對于PosList的解碼采用文獻[8]中基于位置優(yōu)先權重的解碼方法，通過結合位置向量和優(yōu)先關系矩陣將個體的位置解碼為對應的任務序列矩陣。為求解任務序列矩陣TaskList的最優(yōu)分配節(jié)拍，利用牛頓二分法的思想不斷將節(jié)拍搜索區(qū)間一分為二從而快速將任務分配到工位上，得出最優(yōu)分配節(jié)拍CT和任務分配集合Sq，解碼裝配任務分配流程如圖2所示。

圖2 解碼裝配任務分配流程圖

2.2 Pareto支配規(guī)則和精英保留策略

在多目標優(yōu)化問題中，往往存在多個目標之間構成相互沖突的關系，通常不可能找到一個最優(yōu)解使得每個目標函數(shù)都達到最優(yōu)，因此解的優(yōu)劣性采用文獻[9]中的Pareto支配規(guī)則來衡量,對于無法執(zhí)行任務分配的個體直接設置為最劣個體，由Pareto支配規(guī)則選擇蟻獅種群中的最優(yōu)解集為精英蟻獅群。采用文獻[10]中基于非支配排序和擁擠度的精英保留策略選擇出新的蟻獅群，種群數(shù)量均為P的螞蟻種群Pt和蟻獅種群Qt合并成種群數(shù)量為2P的Rt，先對Rt中的個體非支配排序分層，分層完畢之后，對每一層的個體計算擁擠度，最后根據(jù)每個個體的優(yōu)劣程度從種群Rt中選出前P個個體形成新的蟻獅種群。

3 實例驗證

為驗證算法的性能，以某企業(yè)的實際問題為例優(yōu)化求解，給定工位數(shù)目m=3，任務信息如表1所示。并與改進的多目標粒子群算法[11](Multi-objective Improved Particle Swarm Algorithm,MIPSA)對比分析，使用以下指標對算法進行綜合衡量：

(1)非劣解數(shù)目：表示算法搜索Pareto最優(yōu)解的能力。

(2)世代距離[12]：表示所求的Pareto最優(yōu)解距真實Pareto最優(yōu)解的運近程度。

(3)間隔[13]：表示所求的Pareto最優(yōu)解中各個解的均布程度。

(4)運行時間：表示算法運行一次所需的時間。

由于問題的可行解空間規(guī)模巨大，難以得到真實的最優(yōu)解集，因此取各算法求出的最優(yōu)解集作為所求問題的真實最優(yōu)解集。經過算法的靈敏性實驗，設置算法相關參數(shù)：種群數(shù)目P=300，最大迭代次數(shù)tmax=300；初始搜索步長dt=10，節(jié)拍搜索精度CTaccuracy=0.01。為消除隨機因素的影響，各算法取100次的平均結果對4個指標對比說明。

由表2可知多目蟻獅算法在4個指標上均比改進多目標粒子群算法更優(yōu)，表明在單目標蟻獅算法中去除蟻獅捕食規(guī)則的基礎上加入Pareto支配規(guī)則與基于非支配排序和擁擠度的精英保留策略之后，多目標蟻獅算法不僅在搜索Pareto最優(yōu)解的能力上相比于改進多目標粒子群算法更強而且所求得的最優(yōu)解集不僅更靠近于真實的最優(yōu)解集而且在均布程度上也比其他兩種算法更優(yōu)，在運行時間上由于多目標蟻獅算法的迭代更新機制比改進多目標粒子群算法的復雜度更低，所以用更短的時間即可求出更優(yōu)的Pareto解集。

表2 4種指標比較

在表3中列出了100次求解結果中兩種算法求解出的各目標函數(shù)最小值，并且列出了多目標蟻獅算法中3個目標函數(shù)最小值的求解方案進行說明，可知多目標蟻獅算法搜索出的3個目標函數(shù)最小值均比改進多目標粒子群算法搜索出的值都要小，再次表明多目標蟻獅算法搜索出的最優(yōu)解集更接近于真實的最優(yōu)解集。結合表2和表3可知多目標蟻獅算法能在更短時間內為企業(yè)提供更多且更優(yōu)的裝配方案。

表3 求解結果

4 結論

通過對實際問題的求解，并與改進多目標粒子群算法對比分析，表明多目標蟻獅算法在搜索Pareto最優(yōu)解的能力上相比于改進多目標粒子群算法更強；所求得的最優(yōu)解集不僅更靠近于真實的最優(yōu)解集而且在均布程度上也比改進多目標粒子群算法更優(yōu)，在運行時間上也更短。從而說明了多目標蟻獅算法在求解第二類多目標裝配線平衡優(yōu)化問題的適用性和優(yōu)越性。