基于蟻群算法的沖壓車間模具協同調度優化研究

張麗萍，朱振威，周雄輝

(上海交通大學模具CAD國家工程研究中心，上海 200030)

0 引言

隨著市場競爭的加劇，制造企業的生產模式更多地轉向多品種、小批量生產以滿足用戶個性化需求，其中就包括汽車覆蓋件沖壓生產車間。一個型號的汽車包含“四門兩蓋”等眾多覆蓋件，一個覆蓋件又要使用多副模具，經過拉延、沖孔、切邊、整形等多道工序成型。因此，在沖壓生產時，需要由兩臺行車在模庫和生產線之間頻繁地調度模具，以保證快速切換生產不同種類的零件，由此產生模具協同調度優化問題。該問題又包括模具在模庫中的存放位置問題，和兩臺行車協同調度模具順序問題。目前，針對此沖壓車間模具協同調度優化問題的研究較少，尚未找到相關參考文獻，但在特定方面與其具有相似性的問題仍具有參考意義，如對于多行車協同調度問題。梁承姬等[1]研究了行車作業模式對雙軌道吊作業效率的影響，提出了行車接力運輸模式和混合運輸模式，并基于遺傳算法進行了求解驗證。苗亮亮等[2]提出“同抓同放”行車調運方案，并利用k-means算法優化行車作業距離。YANG等[3]考慮了煉鋼連續鑄造過程中起重機間的非碰撞約束，采用分段運輸策略以消除碰撞沖突。對于物體存放位置問題，倪敏敏等[4]提出了分區域動態平衡策劃方案，以提高集裝箱堆場空間利用率。GHAREHGOZLI等[5]為減少集裝箱重定位操作，基于隨機動態規劃模型，采用決策樹啟發式方法進行求解。ZHANG等[6]引入了需求相關模式概念，對存放位置分配問題中待放置物體間的相關性進行了研究與分析。

港口集裝箱調度問題與模具協同調度優化問題具有相似性。前者關注集裝箱在陸側和海側間的多行車調度安排。因此，這兩個問題均需要考慮被運輸物體的存放位置和多行車協同調度作業順序。后者同樣屬于NP難問題，需要采用啟發式方法來獲得最優解或近優解[7]，如遺傳算法[8]、蟻群算法[9]、粒子群算法[10]、模擬退火算法[11]等。兩個問題又有若干不同點。首先，模具完成零件加工任務后需要被運回模庫，而集裝箱運輸只涉及集裝箱的單次運輸；第二，生產同一零件但不同工藝過程的模具之間存在工藝順序和工位的關聯約束，需要接連運往生產線或運回模庫，但是港口集裝箱之間彼此獨立。因此，模具協同調度優化問題更加復雜。

結合模具協同調度優化問題特點，本文首先提出模具在模庫中的分組存放策略和聚集存放策略，并給出3種具有常見沖壓生產工位數量的模具具體放置方式。隨后提出行車協同調度蟻群算法，以求解模具調度最短耗時，并對比分析了兩種模具存放方式的優劣。

1 問題描述

常見沖壓車間整體布局如圖1所示，主要包括模庫、生產線(加工區域)、模具臨時放置區和兩臺行車。生產線通常擁有3～5個加工工位，需要連續加工以最大化生產效率。因此，生產線沖壓生產時，首先由兩臺行車在模具臨時放置區Ⅱ快速卸下并入庫已完成生產的零件模具，并從模庫中吊裝出和配置好生產下一零件的模具至模具臨時放置區Ⅰ；再由機械手臂快速推出加工區當前使用模具至模具臨時放置區Ⅱ，并將已準備好的模具推入加工區域。如此循環，這樣生產線一完成沖壓生產當前零件，就可以迅速生產下一種零件。可以看出，模具在模庫中的存放方式和兩臺行車協同調度模具的順序是影響模具調度耗時的關鍵。

圖1 常見沖壓生產車間布局

1.1 模庫結構

R1R2R3R4R5R6R7R8C1D31D41D42C2C3C4C5

1.2 調度約束條件

模具協同調度優化問題屬于多約束單目標優化問題。優化目標為最短模具調度總耗時。結合實際問題，約束條件如下。

1) 行車距離約束： 兩臺行車在協同調度模具時，基于安全考慮，需要滿足一定的距離約束。當兩臺行車位于模庫時，應至少間隔兩行模庫距離；當兩臺行車位于生產線時，應至少間隔一個工位距離。

2) 模具位置約束： 當模具被運輸至生產線時，需要放置在對應工序的工位位置。同時，模具放置在模庫中時，也應遵循優化存放位置要求。

3) 模具關聯運輸約束： 零件沖壓生產需要經過多道工序，相應地需要有多副模具。因此，生產同一零件的多副模具應該接連運輸至生產線以完成該零件沖壓生產。

4) 模具優先運輸約束： 當模具運往生產線時，位于同一模架的上層模具應先于下層模具運輸；相反地，當模具運回模庫時，位于同一模架的下層模具應先于上層模具運輸。

2 模具存放策略

受到調度約束條件限制，模具在模庫中的存放位置對于模具調度總耗時有重要影響。通過分析可以發現： 模具調度耗時除正常吊裝和卸載耗時外，還包括兩臺行車為保證安全距離而相互等待的耗時，以及模具騰挪耗時。針對這兩種時間消耗，提出了模具在模庫中的分組存放和聚集存放策略。分組存放主要關注行車碰撞沖突，以減少行車相互等待的耗時；聚集存放以減少模具騰挪耗時。

2.1 分組存放策略

分組存放的核心規則如下。

1) 分組規則： 生產同一零件的多副模具按照行車在生產線的距離約束要求兩兩結合成組，使得兩臺行車在生產線可同時吊裝每組模具，比如將第3工位對應的模具(3號模具)與第1工位對應的模具(1號模具)分成一個小組。

2) 存放規則： 為滿足行車在模庫內的距離約束要求，整個模庫在Rp位置處劃分為前后兩部分(朝向生產線方向為前)，其中，p=max{3，r/3}；3表示兩臺行車在模庫內的最短距離(以模架行數為單位)。劃分在同一組內的兩副模具，按照在生產線放置的前后關系分別放置在模庫前后側，且兩副模具沿調度方向距離為p。這樣可使得兩臺行車能同時從模庫中調度這兩副模具至生產線。

3) 最優規則： 應使得盡可能多的組能同時被兩臺行車運輸。同時，生產同一零件的模具在滿足分組存放的前提下，應盡量放置在同一個模架上，以減少模具騰挪次數。

下面將以三工位模具、四工位模具和五工位模具為例，分別闡述其具體分組存放方法。

2.1.1 三工位模具存放

對于三工位沖壓生產線，將3號模具與1號模具形成一個小組，在模庫內分組放置在同一層。2號模具放置在第二層。

2.1.2 四工位模具存放

對于四工位沖壓生產線，將1號模具與3號模具、2號模具與4號模具分別形成兩個小組，在模庫內分組放置。

2.1.3 五工位模具存放

對于五工位沖壓生產線，1號～4號模具仍按照四工位模具存放方式放置。對于5號模具，可以錯落放置在模庫前后部分使得第三層空位均勻分布，為其他模具分組放置提供可能。

2.2 聚集存放策略

分組存放策略通過讓兩臺行車盡可能同時作業來縮短模具調度耗時，但會增加模具騰挪操作。因此，本文又提出聚集存放策略，以減少模具騰挪操作。聚集存放的核心規則如下。

1) 聚集規則： 生產同一種零件的多副模具應盡可能放置在同一個模架上。

2) 最優規則： 在滿足聚集規則的同時，應盡量按照分組原則使兩臺行車能夠同時工作。

下面將以三、四和五工位模具為例，分別闡述其具體聚集存放方法。

2.2.1 三工位模具存放

對于三工位沖壓生產線，將1號～3號模具聚集存放。同時，3號模具和1號模具應緊鄰放置，使得前后行車在生產線可同時吊裝3號模具和1號模具。

2.2.2 四工位模具存放

對于四工位沖壓生產線，可將2號～4號模具在模庫前側聚集存放，1號模具則單獨放置在模庫后側。這兩個模架沿行車調度方向應至少間隔3行。同時，應將2號模具放置在第一層，4號模具放置在第二層，3號模具放置在第三層，使得前后行車在模庫中或生產線上能同時吊裝3號模具與1號模具，及4號模具和2號模具。

2.2.3 五工位模具存放

對于五工位沖壓生產線，將3號～5號模具在模庫前側聚集存放，1號和2號模具在模庫后側聚集存放，且兩模架之間沿調度方向至少間隔p行。同時，1號～4號模具仍可分組存放在第一、二層，5號模具則放置在第三層。

3 行車協同調度問題求解

基于行車協同調度問題的特點，本文采用蟻群算法對問題求解。蟻群算法適于求解大規模問題，常被用來求解各種組合優化問題，如旅行商問題[12]、作業車間調度問題[13]、網絡路由問題[14]等。

將行車完成一次模具調度任務的過程作為一個節點，類比于螞蟻行走過程中所經過的各個路徑節點。由于存在兩臺行車，將兩臺行車的模具調度任務節點交叉排列，形成一個完整的調度序列。

3.1 蟻群算法關鍵步驟

3.1.1 獲取可選調度模具

當前模具的調度狀態可分為3種： 第一種是準備調度狀態，即兩臺行車剛開始準備調度某一零件的模具可選的調度模具集合為剩余待沖壓零件所有相關模具所處模架的最上層模具；第二種是正在調往生產線狀態，即下一個沖壓零件類型已經確定，兩臺行車已完成與該零件相關的模具的部分調度任務，當前可選的調度模具集合為與該零件相關的剩余未調度模具所處模架的最上層模具；第三種是調回模庫狀態，即兩臺行車正在將已完成沖壓生產任務的模具調回模庫，當前可選的調度模具集合為生產線剩余待調回模具。

3.1.2 計算轉移概率

轉移概率是行車選擇某模具作為其下次調度目標的概率值。顯然，兩臺行車同時作業時間越長，則調度時間利用率越高，調度總耗時也會更短。因此，以在迭代中積累的模具調度節點子序列為啟發式信息，選擇模具的信息素濃度值

(1)

其中，accessDies表示當前可選調度模具集合；sseqk(m)表示從模具k開始，連續m個模具構成的模具調度子序列，該子序列相鄰節點之間均存在兩臺行車共同作業時間段；pri(sseqk(m))表示這個子序列的優先概率，其計算公式為：

pri(sseqk(m))=Tc o/Ttotal

(2)

其中，Tc o和Ttotal分別為調度過程中，前后行車共同作業時間與總耗時，它們的比值越大，即前后行車共同作業時間越長，則在當前迭代中繼續按照此子序列順序調度模具的概率值也就越大。若當前無保留的節點子序列或所有當前節點子序列不可用，則蟻群做隨機選擇。初始時，n只螞蟻被隨機放置在可選調度模具集合中。

3.1.3 信息素更新

在每一次迭代中，會產生新的子序列。對于兩個交叉的子序列，即兩個子序列包含至少一個相同模具，則保留優先值大的而淘汰優先值小的，使得若干模具之間盡可能組成最優模具調度順序。重新計算該子序列對應的模具調度軌跡上的信息素濃度值。

3.1.4 模具調度時間計算

根據生產實際經驗，模具調度時間計算基于以下兩個假設：

1) 層位置相關運輸時間假設，模具裝載時長和卸載時長只與起始位置和目標位置所處層數有關。

2) 兩步運輸時間假設，行車平行移動時間已被考慮進裝載時間和卸載時間，一臺行車完成某模具的運輸時間可認為是裝載時間和卸載時間之和。

以前行車為例，計算過程如圖3所示。其中，C1表示前行車，C2表示后行車，tC1是前行車開始裝載時間、開始卸載時間和結束運輸時間的統一表示。

圖3 調度時間計算流程

3.2 蟻群算法計算過程

行車協同調度優化問題的蟻群算法實現流程如圖4所示。

4 實例分析

4.1 行車協同調度蟻群算法實例

依據實際生產經驗，行車裝載和卸載時長如表1所示。以零件生產任務O={2，12，19}為例(圖5)，基于圖5(b)所示四工位模具聚集放置示例，蟻群算法求解的模具調度過程如表2所示，該例證明了蟻群算法對解決行車協同調度問題的有效性。

圖4 行車協同調度蟻群算法流程

表1 裝載和卸載時長

為進一步驗證蟻群算法優異性，本文將蟻群算法與基于規則的啟發式優化算法進行對比。仍考慮到兩臺行車同時作業可有效利用時間的啟發式思想，可采用如下規則進行優化求解：

最少行車位置沖突。即前行車應優先選擇位于模庫前側的模具或者緩沖區位置，而后行車的選擇正好相反。

以圖5(a)四工位模具分組存放為例，表3為不同規模的零件沖壓生產任務輸入，重復求解100次后，蟻群算法求解結果和基于規則的啟發式算法求解結果如表4和表5所示，其中，Min和Max表示最短、最長調度耗時；Avg表示平均調度耗時；SD表示標準偏差；Time表示平均求解時長。對比結果表明，本文所提出的蟻群算法在同等輸入條件下，能夠獲得更短耗時調度方案。基于規則的優化算法僅在每一步做出了相對優異的選擇，但是蟻群算法能夠積累先前調度經驗，在整體上進行綜合考慮。

圖5 四工位模具存放實例

表2 四工位模具聚集存放調度實例

表3 不同規模測試案例輸入

表4 蟻群算法求解結果

表5 基于規則的優化算法求解結果

4.2 模具存放策略對比

以圖2的8行5列模庫結構為例，對模具分組存放和聚集存放方式下的單個零件模具調度時長求解，并對比分析，結果如表6所示。其中，調度時長包括將生產同一零件的不同工位模具運往生產線和運回模庫的總時長；模庫容量為模庫最多能夠提供生產的零件種類。同時，本文以四工位沖壓生產線為例，在不同零件沖壓生產任務規模下，以隨機生成的200個生產任務作為連續輸入，使用蟻群算法進行求解。對模具分組存放和聚集存放方式下的模具調度結果比較100次后，獲得的比較結果如圖6所示。可以看出，在整體上，相較于分組存放策略，模具聚集存放能夠更大概率獲得更短調度耗時，說明模具騰挪次數是影響模具調度耗時的關鍵。但是模具聚集存放會導致模庫空間利用率有所下降。所以沖壓企業應該根據實際需求選擇相應的模具存放策略。

表6 模具分組和聚集存放對比

圖6 兩種存放策略100次比較結果

5 結論

圍繞沖壓車間模具協同調度優化問題進行了討論，解決了模具在模庫中的存放位置問題和兩臺行車協同調度模具順序問題。主要結論如下。

1) 提出了模具在模庫中的分組存放策略和聚集存放策略。分組存放策略可提高兩臺行車作業效率，但會增加模具騰挪操作；而聚集存放策略可減少模具騰挪操作時間。

2) 以模具調度耗時最短為目標，采用蟻群算法求解行車協同調度問題，并與基于規則的優化算法進行對比，證明了蟻群算法的有效性與優勢。

3) 對3種不同工位數量的不同模具存放方式進行對比分析，利用蟻群算法求解模具調度時長，證明模具騰挪次數對行車調度耗時影響更大。為盡量減少調度耗時，應采用模具聚集存放策略，但是模具聚集存放會降低模庫空間利用率。沖壓車間生產規劃人員應該根據實際需求進行合理選擇。