基于智能水滴算法的汽車沖壓車間調(diào)度方法研究

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

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

關(guān)鍵詞：沖壓車間 生產(chǎn)調(diào)度 智能水滴算法

1 引言

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

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

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

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

2 汽車沖壓車間調(diào)度問題的定義及模型描述

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

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

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

2.1 沖壓車間調(diào)度問題模型描述

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

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

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

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

② 沖壓設(shè)備集合，其中m為可用沖壓設(shè)備的總數(shù)；

③ 沖壓件Jk所需的加工工序集合，其中，x為沖壓件Ji所需的加工工序總數(shù)，，而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）所需要的運輸時間設(shè)定為Tskl，k（l+1）；

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

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

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

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

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

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

2.2 沖壓工序時間矩陣的構(gòu)建

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

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

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

3 面向汽車沖壓車間調(diào)度問題的智能水滴算法

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

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

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

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

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

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

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

第3步：設(shè)定好各工序之間的優(yōu)先約束關(guān)系；

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

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

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

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

第8步：待各水滴流經(jīng)所有工序節(jié)點后，獲得當前迭代所生成的較優(yōu)沖壓工序排列方案；

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

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

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

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

4 結(jié)語

針對以最大完工時間為優(yōu)化目標的汽車沖壓車間調(diào)度問題，本文在考慮沖壓工序的沖壓時間、各工序之間轉(zhuǎn)運時間與換模時間的基礎(chǔ)上描述了該問題的數(shù)學模型，并通過構(gòu)建沖壓工序的時間矩陣可以達成優(yōu)化目標并保障各沖壓工序之間的順序約束關(guān)系。

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

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

參考文獻：

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

[2]李浩.基于遺傳算法的沖壓車間調(diào)度算法研究與系統(tǒng)實現(xiàn)[D].華中科技大學，2009.

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

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

[5]田志鵬.面向汽車混流生產(chǎn)的沖壓車間調(diào)度和裝配線排序方法研究與應(yīng)用[D].華中科技大學，2016.

[6]張麗萍，朱振威，周雄輝.基于蟻群算法的沖壓車間模具協(xié)同調(diào)度優(yōu)化研究[J].模具技術(shù)，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.