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

孔志學(xué) 姜 恒 張珠峰

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

孔志學(xué) 姜 恒 張珠峰

（上海航天精密機(jī)械研究所，上海 201600）

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

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

1 引言

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

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

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

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

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

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

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

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

其中，id為工序編碼，name為工序名稱，M為生產(chǎn)線使用機(jī)床的集合，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)建的時(shí)間模型和算法具有以下約束條件：

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

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

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

d. 每道工序完成的標(biāo)志是下料完成；

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

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

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

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

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

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

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

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

定義工序?yàn)槲锪飨到y(tǒng)上料load、機(jī)床加工machining、物流系統(tǒng)下料unload等時(shí)間片段的組合對(duì)象，則工藝路線可描述為組成工藝路線的所有工序單向鏈表對(duì)象的集合。

2.4 基于時(shí)間模型的生產(chǎn)線綜合評(píng)價(jià)指標(biāo)

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

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

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

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

3.1 概率函數(shù)

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

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

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

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

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

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

S3：將S1的組合時(shí)間片段插入該機(jī)床時(shí)間模型鏈表對(duì)象中。

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

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

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

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

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

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

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

S11：根據(jù)生產(chǎn)線時(shí)間模型、機(jī)床時(shí)間模型的鏈表對(duì)象計(jì)算生產(chǎn)線綜合評(píng)價(jià)指標(biāo)。

3.3 信息素更新

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

4 迭代漸進(jìn)式改進(jìn)蟻群算法

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

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

首先基于經(jīng)典蟻群算法對(duì)不同批量條件下生產(chǎn)線最優(yōu)加工方案進(jìn)行優(yōu)選與對(duì)比，軟件仿真試驗(yàn)條件及結(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 算法流程改進(jìn)

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

圖4 迭代漸進(jìn)式改進(jìn)蟻群算法流程圖

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為第代時(shí)產(chǎn)品加工數(shù)量，C為第代蟻群迭代的次數(shù)，為蟻群算法的總迭代次數(shù)。

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

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

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

式中，X為第個(gè)工藝路線在最優(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)用案例中可對(duì)算法性能在一定程度上進(jìn)行改進(jìn)，參考前期的研究成果，引入精英螞蟻策略和偽隨機(jī)比例規(guī)則對(duì)信息素更新和輪盤賭法優(yōu)化。

改進(jìn)式（5），按式（12）、式（13）更新。

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

5 結(jié)果與分析

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

5.1 應(yīng)用對(duì)象

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

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

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

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

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

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

5.3 仿真對(duì)比

五種算法仿真對(duì)比試驗(yàn)中，至今最優(yōu)解及其進(jìn)化迭代次數(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 五種算法對(duì)比試驗(yàn)數(shù)據(jù)統(tǒng)計(jì)表

五種算法的歷代最優(yōu)解收斂趨勢(shì)圖如圖6所示?？梢姡疚奶岢龅乃惴ㄔ诔跗谑諗克俣壬吓c其他四種算法相近；在中期保持了一定的發(fā)散性，在后期，仍然具有一定的全局檢索能力。

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

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

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

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

6 結(jié)束語(yǔ)

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

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

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

c. 采用低閾值偽隨機(jī)算法，提高算法后期的全局搜索能力，避免提前陷入局部最優(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 段建國(guó)，王彥森，謝楠. 基于時(shí)間向量的多工序加工系統(tǒng)工藝路線重組建模與優(yōu)化[J]. 計(jì)算機(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 孔繼利，苑春薈，楊福興，等. 平順移動(dòng)模式下考慮加工時(shí)間與調(diào)整時(shí)間可分離的多目標(biāo)流水車間批量調(diào)度[J]. 系統(tǒng)工程理論與實(shí)踐，2017，37(11)：2882～2896

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

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

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

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

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

10 楊煜俊，陳業(yè). 求解柔性機(jī)器人車間調(diào)度問題的混合蟻群算法[J]. 計(jì)算機(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]. 計(jì)算機(jī)工程與應(yīng)用，2009，45(11)：26～29

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

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

15 楊延慶，李鵬飛，何博. 求解TSP問題的改進(jìn)最大最小蟻群算法[J]. 西安工程大學(xué)學(xué)報(bào)，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

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

2021-07-09