張麗萍，朱振威，周雄輝

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

0 引言

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

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

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

1 問題描述

常見沖壓車間整體布局如圖1所示，主要包括模庫、生產(chǎn)線(加工區(qū)域)、模具臨時(shí)放置區(qū)和兩臺(tái)行車。生產(chǎn)線通常擁有3～5個(gè)加工工位，需要連續(xù)加工以最大化生產(chǎn)效率。因此，生產(chǎn)線沖壓生產(chǎn)時(shí)，首先由兩臺(tái)行車在模具臨時(shí)放置區(qū)Ⅱ快速卸下并入庫已完成生產(chǎn)的零件模具，并從模庫中吊裝出和配置好生產(chǎn)下一零件的模具至模具臨時(shí)放置區(qū)Ⅰ；再由機(jī)械手臂快速推出加工區(qū)當(dāng)前使用模具至模具臨時(shí)放置區(qū)Ⅱ，并將已準(zhǔn)備好的模具推入加工區(qū)域。如此循環(huán)，這樣生產(chǎn)線一完成沖壓生產(chǎn)當(dāng)前零件，就可以迅速生產(chǎn)下一種零件?？梢钥闯?，模具在模庫中的存放方式和兩臺(tái)行車協(xié)同調(diào)度模具的順序是影響模具調(diào)度耗時(shí)的關(guān)鍵。

圖1 常見沖壓生產(chǎn)車間布局

1.1 模庫結(jié)構(gòu)

R1R2R3R4R5R6R7R8C1D31D41D42C2C3C4C5

1.2 調(diào)度約束條件

模具協(xié)同調(diào)度優(yōu)化問題屬于多約束單目標(biāo)優(yōu)化問題。優(yōu)化目標(biāo)為最短模具調(diào)度總耗時(shí)。結(jié)合實(shí)際問題，約束條件如下。

1) 行車距離約束： 兩臺(tái)行車在協(xié)同調(diào)度模具時(shí)，基于安全考慮，需要滿足一定的距離約束。當(dāng)兩臺(tái)行車位于模庫時(shí)，應(yīng)至少間隔兩行模庫距離；當(dāng)兩臺(tái)行車位于生產(chǎn)線時(shí)，應(yīng)至少間隔一個(gè)工位距離。

2) 模具位置約束： 當(dāng)模具被運(yùn)輸至生產(chǎn)線時(shí)，需要放置在對應(yīng)工序的工位位置。同時(shí)，模具放置在模庫中時(shí)，也應(yīng)遵循優(yōu)化存放位置要求。

3) 模具關(guān)聯(lián)運(yùn)輸約束： 零件沖壓生產(chǎn)需要經(jīng)過多道工序，相應(yīng)地需要有多副模具。因此，生產(chǎn)同一零件的多副模具應(yīng)該接連運(yùn)輸至生產(chǎn)線以完成該零件沖壓生產(chǎn)。

4) 模具優(yōu)先運(yùn)輸約束： 當(dāng)模具運(yùn)往生產(chǎn)線時(shí)，位于同一模架的上層模具應(yīng)先于下層模具運(yùn)輸；相反地，當(dāng)模具運(yùn)回模庫時(shí)，位于同一模架的下層模具應(yīng)先于上層模具運(yùn)輸。

2 模具存放策略

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

2.1 分組存放策略

分組存放的核心規(guī)則如下。

1) 分組規(guī)則： 生產(chǎn)同一零件的多副模具按照行車在生產(chǎn)線的距離約束要求兩兩結(jié)合成組，使得兩臺(tái)行車在生產(chǎn)線可同時(shí)吊裝每組模具，比如將第3工位對應(yīng)的模具(3號(hào)模具)與第1工位對應(yīng)的模具(1號(hào)模具)分成一個(gè)小組。

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

3) 最優(yōu)規(guī)則： 應(yīng)使得盡可能多的組能同時(shí)被兩臺(tái)行車運(yùn)輸。同時(shí)，生產(chǎn)同一零件的模具在滿足分組存放的前提下，應(yīng)盡量放置在同一個(gè)模架上，以減少模具騰挪次數(shù)。

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

2.1.1 三工位模具存放

對于三工位沖壓生產(chǎn)線，將3號(hào)模具與1號(hào)模具形成一個(gè)小組，在模庫內(nèi)分組放置在同一層。2號(hào)模具放置在第二層。

2.1.2 四工位模具存放

對于四工位沖壓生產(chǎn)線，將1號(hào)模具與3號(hào)模具、2號(hào)模具與4號(hào)模具分別形成兩個(gè)小組，在模庫內(nèi)分組放置。

2.1.3 五工位模具存放

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

2.2 聚集存放策略

分組存放策略通過讓兩臺(tái)行車盡可能同時(shí)作業(yè)來縮短模具調(diào)度耗時(shí)，但會(huì)增加模具騰挪操作。因此，本文又提出聚集存放策略，以減少模具騰挪操作。聚集存放的核心規(guī)則如下。

1) 聚集規(guī)則： 生產(chǎn)同一種零件的多副模具應(yīng)盡可能放置在同一個(gè)模架上。

2) 最優(yōu)規(guī)則： 在滿足聚集規(guī)則的同時(shí)，應(yīng)盡量按照分組原則使兩臺(tái)行車能夠同時(shí)工作。

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

2.2.1 三工位模具存放

對于三工位沖壓生產(chǎn)線，將1號(hào)～3號(hào)模具聚集存放。同時(shí)，3號(hào)模具和1號(hào)模具應(yīng)緊鄰放置，使得前后行車在生產(chǎn)線可同時(shí)吊裝3號(hào)模具和1號(hào)模具。

2.2.2 四工位模具存放

對于四工位沖壓生產(chǎn)線，可將2號(hào)～4號(hào)模具在模庫前側(cè)聚集存放，1號(hào)模具則單獨(dú)放置在模庫后側(cè)。這兩個(gè)模架沿行車調(diào)度方向應(yīng)至少間隔3行。同時(shí)，應(yīng)將2號(hào)模具放置在第一層，4號(hào)模具放置在第二層，3號(hào)模具放置在第三層，使得前后行車在模庫中或生產(chǎn)線上能同時(shí)吊裝3號(hào)模具與1號(hào)模具，及4號(hào)模具和2號(hào)模具。

2.2.3 五工位模具存放

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

3 行車協(xié)同調(diào)度問題求解

基于行車協(xié)同調(diào)度問題的特點(diǎn)，本文采用蟻群算法對問題求解。蟻群算法適于求解大規(guī)模問題，常被用來求解各種組合優(yōu)化問題，如旅行商問題[12]、作業(yè)車間調(diào)度問題[13]、網(wǎng)絡(luò)路由問題[14]等。

將行車完成一次模具調(diào)度任務(wù)的過程作為一個(gè)節(jié)點(diǎn)，類比于螞蟻行走過程中所經(jīng)過的各個(gè)路徑節(jié)點(diǎn)。由于存在兩臺(tái)行車，將兩臺(tái)行車的模具調(diào)度任務(wù)節(jié)點(diǎn)交叉排列，形成一個(gè)完整的調(diào)度序列。

3.1 蟻群算法關(guān)鍵步驟

3.1.1 獲取可選調(diào)度模具

當(dāng)前模具的調(diào)度狀態(tài)可分為3種： 第一種是準(zhǔn)備調(diào)度狀態(tài)，即兩臺(tái)行車剛開始準(zhǔn)備調(diào)度某一零件的模具可選的調(diào)度模具集合為剩余待沖壓零件所有相關(guān)模具所處模架的最上層模具；第二種是正在調(diào)往生產(chǎn)線狀態(tài)，即下一個(gè)沖壓零件類型已經(jīng)確定，兩臺(tái)行車已完成與該零件相關(guān)的模具的部分調(diào)度任務(wù)，當(dāng)前可選的調(diào)度模具集合為與該零件相關(guān)的剩余未調(diào)度模具所處模架的最上層模具；第三種是調(diào)回模庫狀態(tài)，即兩臺(tái)行車正在將已完成沖壓生產(chǎn)任務(wù)的模具調(diào)回模庫，當(dāng)前可選的調(diào)度模具集合為生產(chǎn)線剩余待調(diào)回模具。

3.1.2 計(jì)算轉(zhuǎn)移概率

轉(zhuǎn)移概率是行車選擇某模具作為其下次調(diào)度目標(biāo)的概率值。顯然，兩臺(tái)行車同時(shí)作業(yè)時(shí)間越長，則調(diào)度時(shí)間利用率越高，調(diào)度總耗時(shí)也會(huì)更短。因此，以在迭代中積累的模具調(diào)度節(jié)點(diǎn)子序列為啟發(fā)式信息，選擇模具的信息素濃度值

(1)

其中，accessDies表示當(dāng)前可選調(diào)度模具集合；sseqk(m)表示從模具k開始，連續(xù)m個(gè)模具構(gòu)成的模具調(diào)度子序列，該子序列相鄰節(jié)點(diǎn)之間均存在兩臺(tái)行車共同作業(yè)時(shí)間段；pri(sseqk(m))表示這個(gè)子序列的優(yōu)先概率，其計(jì)算公式為：

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

(2)

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

3.1.3 信息素更新

在每一次迭代中，會(huì)產(chǎn)生新的子序列。對于兩個(gè)交叉的子序列，即兩個(gè)子序列包含至少一個(gè)相同模具，則保留優(yōu)先值大的而淘汰優(yōu)先值小的，使得若干模具之間盡可能組成最優(yōu)模具調(diào)度順序。重新計(jì)算該子序列對應(yīng)的模具調(diào)度軌跡上的信息素濃度值。

3.1.4 模具調(diào)度時(shí)間計(jì)算

根據(jù)生產(chǎn)實(shí)際經(jīng)驗(yàn)，模具調(diào)度時(shí)間計(jì)算基于以下兩個(gè)假設(shè)：

1) 層位置相關(guān)運(yùn)輸時(shí)間假設(shè)，模具裝載時(shí)長和卸載時(shí)長只與起始位置和目標(biāo)位置所處層數(shù)有關(guān)。

2) 兩步運(yùn)輸時(shí)間假設(shè)，行車平行移動(dòng)時(shí)間已被考慮進(jìn)裝載時(shí)間和卸載時(shí)間，一臺(tái)行車完成某模具的運(yùn)輸時(shí)間可認(rèn)為是裝載時(shí)間和卸載時(shí)間之和。

以前行車為例，計(jì)算過程如圖3所示。其中，C1表示前行車，C2表示后行車，tC1是前行車開始裝載時(shí)間、開始卸載時(shí)間和結(jié)束運(yùn)輸時(shí)間的統(tǒng)一表示。

圖3 調(diào)度時(shí)間計(jì)算流程

3.2 蟻群算法計(jì)算過程

行車協(xié)同調(diào)度優(yōu)化問題的蟻群算法實(shí)現(xiàn)流程如圖4所示。

4 實(shí)例分析

4.1 行車協(xié)同調(diào)度蟻群算法實(shí)例

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

圖4 行車協(xié)同調(diào)度蟻群算法流程

表1 裝載和卸載時(shí)長

為進(jìn)一步驗(yàn)證蟻群算法優(yōu)異性，本文將蟻群算法與基于規(guī)則的啟發(fā)式優(yōu)化算法進(jìn)行對比。仍考慮到兩臺(tái)行車同時(shí)作業(yè)可有效利用時(shí)間的啟發(fā)式思想，可采用如下規(guī)則進(jìn)行優(yōu)化求解：

最少行車位置沖突。即前行車應(yīng)優(yōu)先選擇位于模庫前側(cè)的模具或者緩沖區(qū)位置，而后行車的選擇正好相反。

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

圖5 四工位模具存放實(shí)例

表2 四工位模具聚集存放調(diào)度實(shí)例

表3 不同規(guī)模測試案例輸入

表4 蟻群算法求解結(jié)果

表5 基于規(guī)則的優(yōu)化算法求解結(jié)果

4.2 模具存放策略對比

以圖2的8行5列模庫結(jié)構(gòu)為例，對模具分組存放和聚集存放方式下的單個(gè)零件模具調(diào)度時(shí)長求解，并對比分析，結(jié)果如表6所示。其中，調(diào)度時(shí)長包括將生產(chǎn)同一零件的不同工位模具運(yùn)往生產(chǎn)線和運(yùn)回模庫的總時(shí)長；模庫容量為模庫最多能夠提供生產(chǎn)的零件種類。同時(shí)，本文以四工位沖壓生產(chǎn)線為例，在不同零件沖壓生產(chǎn)任務(wù)規(guī)模下，以隨機(jī)生成的200個(gè)生產(chǎn)任務(wù)作為連續(xù)輸入，使用蟻群算法進(jìn)行求解。對模具分組存放和聚集存放方式下的模具調(diào)度結(jié)果比較100次后，獲得的比較結(jié)果如圖6所示?？梢钥闯觯谡w上，相較于分組存放策略，模具聚集存放能夠更大概率獲得更短調(diào)度耗時(shí)，說明模具騰挪次數(shù)是影響模具調(diào)度耗時(shí)的關(guān)鍵。但是模具聚集存放會(huì)導(dǎo)致模庫空間利用率有所下降。所以沖壓企業(yè)應(yīng)該根據(jù)實(shí)際需求選擇相應(yīng)的模具存放策略。

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

圖6 兩種存放策略100次比較結(jié)果

5 結(jié)論

圍繞沖壓車間模具協(xié)同調(diào)度優(yōu)化問題進(jìn)行了討論，解決了模具在模庫中的存放位置問題和兩臺(tái)行車協(xié)同調(diào)度模具順序問題。主要結(jié)論如下。

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

2) 以模具調(diào)度耗時(shí)最短為目標(biāo)，采用蟻群算法求解行車協(xié)同調(diào)度問題，并與基于規(guī)則的優(yōu)化算法進(jìn)行對比，證明了蟻群算法的有效性與優(yōu)勢。

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