改進蟻群算法在生產(chǎn)線加工方案選擇中的應(yīng)用

孔志學 姜 恒 張珠峰

改進蟻群算法在生產(chǎn)線加工方案選擇中的應(yīng)用

孔志學 姜 恒 張珠峰

（上海航天精密機械研究所，上海 201600）

針對多品種小批量數(shù)控加工生產(chǎn)線，不同工件、多種工藝路線在同一條生產(chǎn)線上進行混合生產(chǎn)時生產(chǎn)線節(jié)拍低、設(shè)備利用率低的問題，提出了一種迭代漸進式蟻群算法對生產(chǎn)線最優(yōu)加工方案進行選擇。基于時序優(yōu)先原則，按工藝路線串行、設(shè)備資源使用時間連續(xù)的準則，建立生產(chǎn)線時間模型及生產(chǎn)線綜合評價指標；改進算法流程，限定初代算法規(guī)模，快速遍歷所有產(chǎn)品加工路線，再逐步擴大算法規(guī)模，根據(jù)歷代最優(yōu)解不同工藝路線分布情況，對螞蟻路徑距離值進行更新，采用至今最優(yōu)螞蟻信息素疊加擴散策略，促使搜索進程加速向最優(yōu)解收斂；采用低閾值偽隨機算法，提高算法全局搜索能力，避免算法后期陷入局部最優(yōu)解。在VS2015軟件平臺上進行算法仿真對比，結(jié)果表明，該算法在避免局別最優(yōu)和算法收斂速度方面具有明顯優(yōu)勢。

生產(chǎn)線時間模型；迭代漸進式蟻群算法；時間線排序；工藝路線

1 引言

近年來，隨著航天事業(yè)的快速發(fā)展，航天典型結(jié)構(gòu)件數(shù)控加工生產(chǎn)線不斷投入生產(chǎn)應(yīng)用，而航天產(chǎn)品依然以多品種中小批量生產(chǎn)為主，用于生產(chǎn)單一產(chǎn)品的加工生產(chǎn)線運行效率低、設(shè)備利用率低、投資成本高，已成為制約生產(chǎn)線相關(guān)技術(shù)在航天企業(yè)推廣應(yīng)用的瓶頸之一。

為提高流水車間的生產(chǎn)效率和設(shè)備利用率，Liu Yencheng等[1]提出一種流水車間作業(yè)模型，將工件不同類型，設(shè)計分支定界算法，優(yōu)化降低車間生產(chǎn)周期；段建國等[2]提出了一種基于時間向量的多工序加工系統(tǒng)工藝路線重組建模與優(yōu)化方法，提高了工藝規(guī)劃的柔性和動態(tài)適應(yīng)性。Liu Jiyin等[3]建立了混合整數(shù)線性規(guī)劃模型，以解決工藝重入和并行工作站的周期性調(diào)度問題；孔繼利等[4]提出了一種平順移動模式下考慮加工時間與調(diào)整時間可分離的多目標流水車間批量調(diào)度方法，基于禁忌搜索算法求解最優(yōu)調(diào)度方案，并實現(xiàn)為批量工件的加工和加工制造設(shè)備調(diào)整指定精確的生產(chǎn)作業(yè)計劃。

生產(chǎn)線是考慮物流資源條件下有限加工設(shè)備流水線式制造的生產(chǎn)系統(tǒng)，具有柔性制造、并行制造的特點，對生產(chǎn)節(jié)拍、設(shè)備利用率要求苛刻。謝堯等[5]提出了面向零件加工的并聯(lián)柔性生產(chǎn)線排產(chǎn)與調(diào)度系統(tǒng)，采用粒子群算法解決了生產(chǎn)線指定機床加工、緊急插單、超期時間最短等需求的算法優(yōu)化問題；毛永年[6]等提出具有并行制造特征的自動化混流生產(chǎn)線調(diào)度（MILP）模型，優(yōu)化了制造系統(tǒng)的生產(chǎn)效率；而劉偉等[7]則構(gòu)造了加工工藝順序模型，并運用蟻群算法對工藝路線進行了優(yōu)化；常智勇等[8]提出一種自適應(yīng)蟻群算法，將生產(chǎn)資源對產(chǎn)品工藝路線的選擇考慮在內(nèi)，以制造資源更換率最小為目標，實現(xiàn)了制造條件約束下的產(chǎn)品最優(yōu)工藝路線選擇；鄧可等[9]提出基于蟻群算法的半導體生產(chǎn)線調(diào)度模型（ASWFSM），引入專家系統(tǒng)作為推理機，在小規(guī)模生產(chǎn)線調(diào)度問題上具有良好的效果和穩(wěn)定性；楊煜俊等[10]提出的混合蟻群算法，在解決機器人多任務(wù)作業(yè)調(diào)度問題上，具有較高的可靠性和魯棒性。可見，生產(chǎn)車間、生產(chǎn)線的排產(chǎn)與調(diào)度優(yōu)化是一個重要的研究課題，蟻群算法及其改進算法在該研究領(lǐng)域取得了較好的效果。

本文針對不同工件、多種工藝路線在同一條生產(chǎn)線混合生產(chǎn)時的工藝路線尋優(yōu)問題，提出迭代漸進式蟻群算法，在建立生產(chǎn)線時間模型與生產(chǎn)線綜合評價指標的基礎(chǔ)上，通過改進蟻群算法，在迭代過程中更新路徑距離值，并引入至今最優(yōu)螞蟻信息素疊加擴散策略、低閾值偽隨機算法，提升了蟻群算法的性能。

2 生產(chǎn)線時間模型構(gòu)建

以多品種中小批量生產(chǎn)線為研究對象，針對不同工件、不同工藝路線在生產(chǎn)線上進行混合生產(chǎn)，基于時序優(yōu)先原則，按工藝路線串行、設(shè)備資源使用時間連續(xù)的準則，建立生產(chǎn)線時間模型。

2.1 工藝路線模型構(gòu)建

面向生產(chǎn)線的工藝路線是對產(chǎn)品毛坯在生產(chǎn)線上加工制造成為零件的過程的描述，而工藝路線是工序的集合，因此，可將工序相關(guān)的加工信息定義為產(chǎn)品的工序MP（manufacturing process），使用七元組表示：

其中，id為工序編碼，name為工序名稱，M為生產(chǎn)線使用機床的集合，Tool為不同設(shè)備資源使用刀具的集｛Tool1,Tool2,...,Tool｝合、F為不同設(shè)備資源使用工裝的集合｛F1,2,...,F｝、W為不同設(shè)備資源使用方法的集合｛1,2,...,W｝、P表示不同狀態(tài)下的零件。由零件各工序所組成的集合即為該零件的工藝路線PR（Process Route），表示如下：

2.2 約束條件

本文構(gòu)建的時間模型和算法具有以下約束條件：

a. 生產(chǎn)線中的設(shè)備資源在生產(chǎn)線運行過程中不發(fā)生故障；

b. 生產(chǎn)線中的數(shù)控機床在同一時間只能加工一個工件的某一道工序，且每個工件每道工序只能指定一臺數(shù)控機床，若該工序有可替代機床，則按新工藝路線進行配置；

c. 每道工序包括上料、加工、下料等三個環(huán)節(jié)，若有測量機，則按數(shù)控機床加工處理；

d. 每道工序完成的標志是下料完成；

e. 后道工序必須在前道工序完成后，才能被加工；

f. 生產(chǎn)線中的設(shè)備資源同一時刻只能執(zhí)行一項生產(chǎn)任務(wù)；

g. 同一設(shè)備資源不同任務(wù)，按任務(wù)時序優(yōu)先的原則進行順序排列，時間重疊的低優(yōu)先級任務(wù)向后順延。

2.3 生產(chǎn)線時間模型設(shè)計

無故障條件下的生產(chǎn)線連續(xù)運行是各個設(shè)備不同任務(wù)的組合，將生產(chǎn)線的各類任務(wù)抽象為時間片段，則生產(chǎn)線時間模型是對各個任務(wù)執(zhí)行時間片段及時間片段間時序關(guān)系的描述。如圖1所示，可知，根據(jù)上述工藝路線模型，針對不同產(chǎn)品，可設(shè)置多種工藝路線，但對生產(chǎn)線系統(tǒng)而言，不同工藝路線、不同工序可使用的設(shè)備資源是一定的，各個設(shè)備上下料所使用的機器人或其他物流設(shè)備及其備料或存料的輔助裝置是一定的。

圖1 產(chǎn)品工藝路線與生產(chǎn)線資源對應(yīng)關(guān)系圖

本文針對生產(chǎn)線系統(tǒng)，基于VC++分別設(shè)計了相應(yīng)的單向鏈表對象用以描述產(chǎn)品工藝路線的時間模型、加工設(shè)備的時間模型、物流系統(tǒng)的時間模型。

b. 產(chǎn)品工藝路線時間對象

定義工序為物流系統(tǒng)上料load、機床加工machining、物流系統(tǒng)下料unload等時間片段的組合對象，則工藝路線可描述為組成工藝路線的所有工序單向鏈表對象的集合。

2.4 基于時間模型的生產(chǎn)線綜合評價指標

流水車間調(diào)度問題的決策目標一般為時間資源[11]，本文考慮采用生產(chǎn)線生產(chǎn)節(jié)拍以及設(shè)備利用率作為生產(chǎn)線綜合評價指標對工藝路線及其時序進行優(yōu)選，并對應(yīng)設(shè)置權(quán)重系數(shù)，目標函數(shù)如下：

其中，為生產(chǎn)線設(shè)備加工任務(wù)總數(shù)量，為生產(chǎn)線加工產(chǎn)品總數(shù)量，為單一產(chǎn)品的工序數(shù)量，target為生產(chǎn)線評價的生產(chǎn)節(jié)拍目標值，target為機床設(shè)備利用率目標值，為權(quán)重系數(shù)。

3 經(jīng)典蟻群算法

經(jīng)典蟻群算法是一種模擬螞蟻群覓食過程尋求最短路徑的群體智能算法[12]，蟻群隨機選擇路徑，并在每條路徑上留下信息素，信息素隨時間不斷揮發(fā)，使蟻群能夠按信息素濃度高的路徑選擇最短路徑。本文將生產(chǎn)線加工產(chǎn)品數(shù)量與TSP問題中的城市數(shù)量對應(yīng)，路徑的選擇與工藝路線的選擇對應(yīng)，路徑最大距離與生產(chǎn)線綜合評價指標相對應(yīng)，基于經(jīng)典蟻群算法對生產(chǎn)線工藝路線進行了優(yōu)選。

3.1 概率函數(shù)

蟻群在選擇工藝路線時，其轉(zhuǎn)移概率根據(jù)信息素濃度與啟發(fā)式函數(shù)確定[13]，本文采用輪盤賭法保證算法的搜索能力，狀態(tài)轉(zhuǎn)移概率由式（2）～式（4）確定：

3.2 生產(chǎn)線時間線排序

基于上述約束條件，分別建立生產(chǎn)線加工時間模型、機床時間模型、機器人時間模型，并按以下步驟排序，如圖2所示。

圖2 經(jīng)典蟻群算法流程圖

S1：首先在工藝路線選取后，按集合順序查詢工序?qū)ο?，并根?jù)工序設(shè)置的機床組合所需機器人上料時間片段和該機床加工時間片段。

S2：判斷該機床所需的上料時刻是否屬于該機床當前時間線中的允許上料時間段內(nèi)，若與已存在的機床任務(wù)沖突，則順延至最先的允許上料時刻。

S3：將S1的組合時間片段插入該機床時間模型鏈表對象中。

S4：判斷機床所需的機器人上料時間片段是否在機器人空閑時段，若不在空閑時段，則順延該機床上料開始時刻至機器人最先的空閑時刻，并返回S1。

S5：判斷該時間片段是否與已存在的機器人上下料任務(wù)有沖突，若有沖突，則先定位沖突任務(wù)的時間片段所在生產(chǎn)線時間模型的位置，再按生產(chǎn)線時間模型，順延沖突任務(wù)及其后續(xù)任務(wù)的時間片段。

S6：將機器人上料時間片段插入機器人時間模型、生產(chǎn)線時間模型中。

S7：將機床加工時間片段插入機床時間模型、生產(chǎn)線時間模型中，并獲取該機床所需的機器人下料時間片段。

S8：判斷該機器人下料時間片段是否與已存在的機器人上下料任務(wù)有沖突，若有沖突，則先定位沖突任務(wù)的時間片段所在生產(chǎn)線時間模型的位置，再按生產(chǎn)線時間模型，順延沖突任務(wù)及其后續(xù)任務(wù)的時間片段。

S9：將機器人下料時間片段插入機器人時間模型、生產(chǎn)線時間模型中。

S10：判斷工藝路線是否已結(jié)束，若未結(jié)束，返回S1直至結(jié)束。

S11：根據(jù)生產(chǎn)線時間模型、機床時間模型的鏈表對象計算生產(chǎn)線綜合評價指標。

3.3 信息素更新

按信息素規(guī)則要求，在螞蟻釋放信息素的同時，對路徑上的信息素按比例揮發(fā)，并按式（5）～式（7）更新。

4 迭代漸進式改進蟻群算法

結(jié)合數(shù)控加工生產(chǎn)線批量生產(chǎn)的特點以及生產(chǎn)組織經(jīng)驗，多品種中小批量混線生產(chǎn)時，某一產(chǎn)品上線生產(chǎn)一般采用單一工藝路線生產(chǎn)線效率較高，提出了一種迭代漸進式改進蟻群算法。

4.1 不同批量條件下的最優(yōu)方案對比

首先基于經(jīng)典蟻群算法對不同批量條件下生產(chǎn)線最優(yōu)加工方案進行優(yōu)選與對比，軟件仿真試驗條件及結(jié)果如表1所示。

表1 不同批量下的產(chǎn)品工藝路線執(zhí)行情況表

如圖3所示，不同批量條件下，產(chǎn)品在生產(chǎn)線加工的最優(yōu)加工方案中，工藝路線的分布具有明顯規(guī)律。其一，在單一批量條件下，A產(chǎn)品一般以工藝路線1、工藝路線2為主，B產(chǎn)品一般以工藝路線1為主；其二，在不同批量間，產(chǎn)品工藝路線的分布區(qū)間占比具有一致性，且批量越大，越明顯。

圖3 不同批量條件下各工藝路線分布情況圖

4.2 算法流程改進

本文提出的迭代漸進式改進蟻群算法流程如圖4所示。

圖4 迭代漸進式改進蟻群算法流程圖

S1：根據(jù)上線加工的產(chǎn)品種類及其適用的生產(chǎn)線工藝路線數(shù)量，確定每代產(chǎn)品的加工數(shù)量，按式（8）～式（10）更新。

式中，為上線產(chǎn)品總數(shù)量，為上線產(chǎn)品種類數(shù)，M為第中產(chǎn)品工藝路線數(shù)，為所有產(chǎn)品工藝路線的總數(shù)，n為第代時產(chǎn)品加工數(shù)量，C為第代蟻群迭代的次數(shù)，為蟻群算法的總迭代次數(shù)。

S2：按輪盤賭法進行工藝路線選擇，并依次對工序路線中的工序進行時間排序，計算生產(chǎn)線綜合評價指標，更新環(huán)境信息素，更新產(chǎn)品禁忌表。

S3：迭代完成生產(chǎn)線最優(yōu)工藝路線選擇。

S4：按式（11）更新距離矩陣。

式中，X為第個工藝路線在最優(yōu)工藝路線中被選擇的次數(shù)。

S5：若所有產(chǎn)品已完成加工，則結(jié)束，否則，返回S1。

4.3 算法參數(shù)優(yōu)化

經(jīng)典蟻群算法存在易陷入局部最優(yōu)、收斂速度慢的問題，蟻群系統(tǒng)ACS、精英策略蟻群算法ASelite[14]、最大最小蟻群算法MMAS[15]等均在不同應(yīng)用案例中可對算法性能在一定程度上進行改進，參考前期的研究成果，引入精英螞蟻策略和偽隨機比例規(guī)則對信息素更新和輪盤賭法優(yōu)化。

改進式（5），按式（12）、式（13）更新。

對輪盤賭法改進，采用偽隨機比例規(guī)則，狀態(tài)轉(zhuǎn)移概率按式（14）更新。

5 結(jié)果與分析

本文使用VS2015平臺，將迭代漸進式蟻群算法與經(jīng)典蟻群算法AS、蟻群系統(tǒng)算法ACS、精英蟻群算法ASelite、最大最小蟻群算法MMAS進行軟件仿真與對比分析。

5.1 應(yīng)用對象

如圖5所示，艙體生產(chǎn)線包括2臺車銑復合加工中心、3臺臥式五軸加工中心、1臺桁架機器人、1臺地軌機器人，兩種典型產(chǎn)品：舵機艙、電子艙，適用于生產(chǎn)線的產(chǎn)品工藝路線分別為3種、2種，每組批各8件。

圖5 艙體生產(chǎn)線組成圖

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

兩種產(chǎn)品各工藝路線條件下實際工序時間及機器人上下料時間條件如表2所示。

表2 產(chǎn)品工藝信息表 s

生產(chǎn)線綜合評價指標優(yōu)化計算時，生產(chǎn)節(jié)拍、設(shè)備利用率目標值分別為target=3h/件，target=60％，權(quán)重系數(shù)=0.7。

5.3 仿真對比

五種算法仿真對比試驗中，至今最優(yōu)解及其進化迭代次數(shù)如表3所示?？梢?，本文提出的算法在尋優(yōu)能力優(yōu)于AS、ACS、ASelite、MMAS算法；在最優(yōu)解選取上，明顯優(yōu)于AS算法最優(yōu)解的值，與ACS、MMAS算法最優(yōu)解的值接近，與ASelite算法最優(yōu)解的值基本一致。

表3 五種算法對比試驗數(shù)據(jù)統(tǒng)計表

五種算法的歷代最優(yōu)解收斂趨勢圖如圖6所示?？梢?，本文提出的算法在初期收斂速度上與其他四種算法相近；在中期保持了一定的發(fā)散性，在后期，仍然具有一定的全局檢索能力。

圖6 歷代最優(yōu)解收斂趨勢圖

五種算法仿真對比試驗中，IPACS、ASelite算法最終獲得的生產(chǎn)線最優(yōu)加工方案一致性較好，如圖7所示，為本文提出算法最優(yōu)解條件下，生產(chǎn)線選擇五種路線的時序及五臺機床的上料、加工、下料的時間片段分布圖，可見，該算法對兩種產(chǎn)品五種工藝路線的加工時序進行了合理排序，使五臺機床加工任務(wù)的時間片段較為連續(xù)，生產(chǎn)線總體生產(chǎn)節(jié)拍最小，機床設(shè)備平均利用率最高。

圖7 生產(chǎn)線最優(yōu)加工方案時序圖

因此，本文提出的迭代漸進式蟻群算法在收斂能力上與主流改進蟻群算法相當，在尋優(yōu)能力、避免陷入局部最優(yōu)解等方面具有優(yōu)勢。

6 結(jié)束語

針對數(shù)控加工生產(chǎn)線加工方案優(yōu)選問題，提出了一種迭代漸進式蟻群算法，改進后的算法在收斂速度、尋優(yōu)能力具有明顯優(yōu)勢。本文算法具有以下特點：

a. 改進算法流程，在小規(guī)模算法條件下，獲取工藝路線分布情況，并迭代更新路徑距離，提高算法中后期選擇較優(yōu)工藝路線的概率，提高收斂速度。

b. 引入至今最優(yōu)螞蟻信息素疊加擴散策略，提高算法向全局最優(yōu)解收斂的能力。

c. 采用低閾值偽隨機算法，提高算法后期的全局搜索能力，避免提前陷入局部最優(yōu)。

1 Liu Yencheng, Fang Kueitang, Lin B M T. A branch-and-bound algorithm for make span minimization in differentiation flow shops[J]. Engineering Optimization, 2013, 45(12): 1397～1408

2 段建國，王彥森，謝楠. 基于時間向量的多工序加工系統(tǒng)工藝路線重組建模與優(yōu)化[J]. 計算機集成制造系統(tǒng)，2020，26(7)：1814～1823

3 Liu Jiyin, Jiang Yun, Zhou Zhili. Cyclic scheduling of a single hoist in extended electroplating lines: a comprehensive integer programming solution[J]. IIE Transactions, 2002, 34(10): 905～914

4 孔繼利，苑春薈，楊福興，等. 平順移動模式下考慮加工時間與調(diào)整時間可分離的多目標流水車間批量調(diào)度[J]. 系統(tǒng)工程理論與實踐，2017，37(11)：2882～2896

5 謝堯. 面向零件加工的并聯(lián)柔性生產(chǎn)線排產(chǎn)與調(diào)度系統(tǒng)研發(fā)[D]. 武漢：華中科技大學，2018

6 毛永年，唐秋華，張利平，等. 具有并行制造特征的自動化混流生產(chǎn)線調(diào)度模型[J]. 計算機集成制造系統(tǒng)，2019，25(7)：1717～1728

7 劉偉，王太勇，周明，等. 基于蟻群算法的工藝路線生成及優(yōu)化[J]. 計算機集成制造系統(tǒng)，2010，16(7)：1378～1382

8 常智勇，楊建新，趙杰，等. 基于自適應(yīng)蟻群算法的工藝路線優(yōu)化[J]. 機械工程學報，2012，48(9)：163～169

9 鄧可，林杰，張鵬. 基于蟻群算法的半導體生產(chǎn)線調(diào)度方法研究[J]. 計算機工程與應(yīng)用，2009，45(12)：198～201

10 楊煜俊，陳業(yè). 求解柔性機器人車間調(diào)度問題的混合蟻群算法[J]. 計算機工程與應(yīng)用，2018，54(13)：160～167

11 Yenisey M M, Yagmahan B. Multi-objective permutation flow shop scheduling problem: Literature review, classification and current trends[J]. Omega, 2014, 45(2): 119～135

12 王鳳，林杰. 設(shè)備組合加工的生產(chǎn)調(diào)度問題研究[J]. 計算機工程與應(yīng)用，2009，45(11)：26～29

13 劉中強，游曉明，劉升. 一種啟發(fā)式動態(tài)信息素更新策略的蟻群算法[J]. 計算機工程與應(yīng)用，2018，54(20)：20～27

14 汪貴慶，袁杰，沈慶宏. 基于精英蟻群算法的交通最優(yōu)路徑研究[J]. 南京大學學報（自然科學版），2019，55(5)：709～717

15 楊延慶，李鵬飛，何博. 求解TSP問題的改進最大最小蟻群算法[J]. 西安工程大學學報，2010，24(6)：818～821

Application of Improved Ant Colony Optimization in Production Line Processing Planning

Kong Zhixue Jiang Heng Zhang Zhufeng

(Shanghai Spaceflight Precision Machinery Institute, Shanghai 201600)

In order to solve the problems of low production cycle and low equipment utilization when different workpieces with multiple process routes are processed on the multi-variety and small batch CNC machining production line, an iterative progressive ant colony algorithm is proposed to select the optimal processing plan of the production line. Based on the principle of time sequence priority, the process route serialization and equipment resource usage time continuous criteria, establish production line time model and production line comprehensive evaluation index; improve the algorithm process, first, limit the scale of the first generation algorithm, quickly traverse all product processing routes, and then gradually expand the algorithm scale. According to the distribution of different process routes of the best solutions in the past generations, update the ant path distance value, adopting the best ant pheromone superposition diffusion strategy so far, to promote the search process to accelerate the convergence to the optimal solution; using a low-threshold pseudo-random algorithm to improve the algorithm’s global search ability and avoid the algorithm from falling into the local optimal solution in the later stage. On the VS2015 software platform, the algorithm simulation comparison is conducted. The results show that the algorithm has great improvement in avoiding local optimization and accelerating convergence speed.

production line time model；iterative progressive ant colony system；timeline sort；process route

TP274

A

孔志學（1989），碩士，機械工程專業(yè)；研究方向：數(shù)字化生產(chǎn)線技術(shù)。

2021-07-09