基于智能水滴算法的汽車沖壓車間調度方法研究

胡曉宇　路曉鵬　陳文莉　白文濤

摘 要：汽車沖壓制造作為整車生產中的重要一環，提高其生產效率降低其制造成本是各大汽車廠商不斷在追求的目標。而隨著沖壓車間生產規模不斷擴大與其工序日漸繁雜，使得實現其高效、低成本的排產調度變得越來越困難。因此，本文以最大完工時間作為優化目標，提出了一種運用智能水滴算法來完成汽車沖壓車間調度的方法。通過對沖壓車間調度問題進行分析，在考慮各沖壓工序流轉時間、沖壓設備換模時間與沖壓加工時間的基礎上設定了其目標函數，并構建各工序間的時間矩陣來對其進行有效約束。再根據智能水滴算法的迭代求解特性，將沖壓工序與算法因子進行了融合，通過仿擬水滴的流動路徑來獲得沖壓工序的排序方案，并借助智能水滴算法的全局搜索能力來獲取最優的沖壓車間調度方案，對解決該問題提供一種新的方法思路。

關鍵詞：沖壓車間 生產調度 智能水滴算法

1 引言

汽車產業作為全球制造業經濟的重要組成部分，在全球化背景下，各大車企都在不斷提升其有效競爭力，這也使得汽車制造業一直都是前沿生產技術與管理技術的重要實踐地。而沖壓作為汽車制造過程中的重要環節，其生產效率、生產質量會直接對后續的焊裝、涂裝及總裝等生產過程造成影響。因此如何有效的提升沖壓車間的使用效率、降低生產制造成本、提高沖壓件的質量成為了汽車制造企業不得不面對的問題[1]。

傳統的汽車沖壓車間調度多采用基于人工經驗規則的方法進行排產，容易出現費時長、效率低、易出錯等問題。而伴隨著智能優化算法的不斷發展與運用，越來越多的學者對沖壓車間調度問題進行了相關研究。李浩[2]在對沖壓車間的生產模式與特點進行分析的基礎上，提出運用遺傳算法來解決沖壓車間調度問題。李崢峰等人[3]在考慮了沖壓生產線具備加工特性的前提下構建數學模型，并將遺傳算法與啟發式規則進行結合來進行問題求解。周春生等人[4]則在考慮沖壓生產過程中的節能的基礎上構建沖壓調度優化模型，并利用改進后的遺傳算法來尋求最優方案。田志鵬[5]基于沖壓車間具備柔性特性的前提下，以生產周期與生產成本作為優化目標來構建調度模型，并提出運用混合人工蜂群算法來進行求解。張麗萍等人[6]在對沖壓車間中的模具存放策略進行分析的基礎上，提出采用蟻群算法來尋求最佳的調度方案。

智能水滴算法（Intelligent Water Drops，IWD）是一種較為新穎的基于仿生學思想的優化算法，其通過模擬河流中的水滴的流動過程及特性來尋求有效路徑，進而獲得最優解，具有全局尋優能力強和快速收斂等優點。該算法目前已在車輛路徑規劃問題、裝配序列規劃問題、旅行商問題等典型的NP-hard優化問題上得到應用[7]。

在上述研究的基礎上，本文針對汽車沖壓車間生產調度問題，提出一種基于智能水滴算法的調度方法，借助其全局搜索能力強、搜索速度快、容易實現的特點對沖壓車間調度進優化。

2 汽車沖壓車間調度問題的定義及模型描述

沖壓車間通常會有多條沖壓作業線，能夠完成多種類型的沖壓加工件的沖壓工序。不同的沖壓加工件在加工過程根據其成型要求的差異，可能會在多臺沖壓機上完成不同的工序，同時也可以通過對沖壓設備更換模具來適應不同加工需求。

一般情況下，單個沖壓件在一臺設備上的加工時間約需8至20秒，但是對一臺沖壓設備更換沖壓模具則需要數十分鐘，在高效率運轉背景下，巨大的時間差距使得模具更換時間不得不考慮。除此以外，對于有多道工序的沖壓件來說，還需要在沖壓設備之間進行流轉，其耗費的運輸時間也需要考慮在調度問題中。

因此，為盡可能的使得沖壓整體生產時間最短、設備的利用效率最高，本文基于最大完工時間考慮，對沖壓件的加工順序和所用設備進行有效排序。

2.1 沖壓車間調度問題模型描述

可將沖壓車間調度問題描述為：沖壓車間內的各型沖壓設備M數量為m臺，待進行沖壓加工的工件J數量為n個，每個沖壓件各自的加工工序O是已知確定的，且其先后順序固定無法改變，不同的沖壓工序能分配到合適的設備上完成。同時，每臺設備一次只執行一步工序，同一時間內無法同時執行多道工序。

本文在考慮加工時間、設備切換時的運輸時間、設備更換模具的換模時間的基礎上，設定的優化目標則是令完成所有沖壓件的各道工序所花費的總時間最短。

為與算法進行結合，對該問題模型進行編碼定義如下：

① 待加工沖壓件集合，其中n為所需加工的沖壓件的總數；

② 沖壓設備集合，其中m為可用沖壓設備的總數；

③ 沖壓件Jk所需的加工工序集合，其中，x為沖壓件Ji所需的加工工序總數，，而Okl則表示沖壓件Jk的第l步工序，且第l+1步工序必須在第l步工序前進行；

④ 沖壓件Jk從第l步工序Okl到第l+1步工序Ok（l+1）所需要的加工時間為Tpkl，k（l+1）；

⑤ 沖壓件Jk從第l步工序Okl到第l+1步工序Ok（l+1）所需要的運輸時間設定為Tskl，k（l+1）；

⑥ 沖壓件Jk從第l步工序Okl到第l+1步工序Ok（l+1）所需要的換模時間設定為Tckl，k（l+1）；

⑦ 完成所有待加工沖壓件所需的時間為T，則

上式中，Tp為完成所有工序所需的加工時間，Ts為完成所有工序所需的運輸時間，Tc為完成所有工序所需的換模時間。

因為該模型的優化目標是使得完成所有工序的時間T最短，即目標函數為

如表1所示，為表征沖壓單元的特征編碼方式示例。

由于每個加工沖壓件的工序數是固定的，且加工的沖壓件數量也是已知的，故而沖壓任務的總工序數是固定不變的，因此可以將該問題歸化為求解的所有沖壓工序的排序問題。

2.2 沖壓工序時間矩陣的構建

設定在沖壓過程中兩工序Oi與Oj間所需耗費的時間為Ti，j，其為前一步工序Oi所需的加工時間Tpi、兩工序間所需的換模時間Tci，j以及運輸時間Tsi，j之和，即

在考慮沖壓加工時間、換模時間、運輸時間基礎上，定義沖壓工序時間矩陣C為

上式中，U為所有沖壓件加工所需的工序數總和，通過構建時間矩陣C可以清楚獲得各個工序之間的耗時關系。同時，為保障各工序符合加工順序要求，令沖壓件Jk第l步工序Okl到第l-1工序Ok（l-1）所需要的時間為+∞。

3 面向汽車沖壓車間調度問題的智能水滴算法

經過建模歸化，可將汽車沖壓車間調度問題視作典型的組合優化問題，因此可將其與智能水滴算法迭代求解過程進行結合，從而來尋獲最優的沖壓調度方案。在符合沖壓件的工序先后順序要求的前提下，結合各沖壓件在沖壓過程中所需的加工時間、換模時間與運輸時間，以最大完工時間作為優化目標對各個沖壓工序進行有效排序。

通過將各沖壓工序與智能水滴算法中的流動節點進行結合，從而構成水滴的流動路徑，同時設定每次迭代的水滴數量NIWD與沖壓件數量n相等，令各水滴分別從各沖壓件的首道工序開始流動，在遵循工序順序約束與考慮所需耗時的前提下自由選擇合適的流動節點，直至流動到最后一個節點，而各水滴的流動路徑即形成了各沖壓件的生產加工序列。

以表2所示的沖壓任務為例，某批沖壓任務共有2個沖壓件，每個沖壓件的成型加工又各需3道工序，其各沖壓工序的時間矩陣為C1。

則設定單次迭代的水滴數量為2，從S點開始將2個水滴分別分配到首道工序節點O11、O21上開始流動，在構建其各沖壓工序的時間矩陣C1可以判斷出各工序間的所需耗費時長，并將其賦值在各節點路徑上。水滴在流動過程中會盡可能選擇耗時更少的節點路徑，且不會回流，這樣就能有效保證在尋求最優完工時間的同時，也符合工序順序約束的要求。最后，所有水滴流動至結束點E，獲取各沖壓件的加工序列。如圖1所示，為各沖壓水滴的流動路徑選擇過程。

基于智能水滴算法的沖壓車間調度問題的求解過程如圖2所示，具體實施步驟如下：

第1步：對沖壓任務中各沖壓件的工序進行編碼，并為各工序從沖壓設備集合M隨機選取可用設備；

第2步：在考慮加工時間、換模時間與運輸時間的基礎上，分析各沖壓工序之間所需耗費時間Ti，j，并構建沖壓工序時間矩陣C；

第3步：設定好各工序之間的優先約束關系；

第4步：初始化智能水滴算法的靜態與動態參數，設定水滴種群的數量NIWD等于沖壓件數量n，并為各水滴的初始流動速度與初始攜帶的泥土量賦值；

第5步：構建沖壓工序水滴集合Vc（IWD），初始為空矩陣；

第6步：在沖壓工序時間矩陣及優先順序關系的約束下，以目標函數F為優化目標，令各水滴選擇合適的流動節點進行向下流動；

第7步：將各水滴所流經的工序節點信息按順序填入至集合Vc（IWD），進行實時更新，生成沖壓工序序列；

第8步：待各水滴流經所有工序節點后，獲得當前迭代所生成的較優沖壓工序排列方案；

第9步：更新當前迭代較優解水滴流動路徑中泥土量；

第10步：不斷更新每次迭代所獲的較優解的集合；

第11步：當達到所設定的最大迭代次數則停止搜索，否則回到第4步重復執行；

第12步：待所有水滴完成迭代求解后，從較優解集中輸出最優解，即完工時間最短的沖壓工序調度方案。

4 結語

針對以最大完工時間為優化目標的汽車沖壓車間調度問題，本文在考慮沖壓工序的沖壓時間、各工序之間轉運時間與換模時間的基礎上描述了該問題的數學模型，并通過構建沖壓工序的時間矩陣可以達成優化目標并保障各沖壓工序之間的順序約束關系。

同時，在將汽車沖壓車間調度問題歸化為作業車間調度問題的基礎上，結合智能水滴算法的迭代求解特性，將沖壓工序方案與智能水滴的流動路徑進行結合，借助智能水滴優秀的全局搜索與快速求解能力能有效尋獲沖壓工序的排列方案。該調度方法為后續研究提供了一種思路，還需進一步與現場應用環境相結合，考慮更多現實因素，從而增強其可行性與實踐性。

注：柳州鐵道職業技術學院校級立項項目（2022-KJB06）資助。

參考文獻：

[1]馬煥雯.汽車制造沖壓車間生產計劃與生產調度的研究[D].武漢理工大學，2013.

[2]李浩.基于遺傳算法的沖壓車間調度算法研究與系統實現[D].華中科技大學，2009.

[3]李崢峰，喻道遠，楊曙年，等.基于工序約束并行機模型的沖壓線調度[J].計算機集成制造系統，2009，15（12）：7.

[4]周春生，劉志峰，黃海鴻，等.基于遺傳算法的沖壓車間節能調度優化研究[J].制造業自動化，2018，40（5）：7.

[5]田志鵬.面向汽車混流生產的沖壓車間調度和裝配線排序方法研究與應用[D].華中科技大學，2016.

[6]張麗萍，朱振威，周雄輝.基于蟻群算法的沖壓車間模具協同調度優化研究[J].模具技術，2021，40（03）：1-8.

[7]Niu S H，Ong S K，Nee A Y C. An improved Intelligent Water Drops algorithm for achieving optimal job-shop scheduling solutions[J]. International Journal of Production Research，2012，50（15）：4192-4205.