孟榮華，李世紅，羅 強，饒運清+

(1.三峽大學(xué) 水電機械設(shè)備設(shè)計與維護(hù)湖北省重點實驗室，湖北 宜昌 443002； 2.華中科技大學(xué) 數(shù)字制造裝備與技術(shù)國家重點實驗室，湖北 武漢 430074； 3.貴州交通職業(yè)技術(shù)學(xué)院，貴州 貴陽 550008)

0 引言

隨著我國大中型機械設(shè)備制造的發(fā)展，企業(yè)對金屬結(jié)構(gòu)件的需求越來越大，金屬板材結(jié)構(gòu)件生產(chǎn)周期相對較長，需要消耗大量的金屬板材，金屬零件的供應(yīng)是否及時對后續(xù)結(jié)構(gòu)件的生產(chǎn)影響很大。在切割下料車間，隨著企業(yè)的發(fā)展，切割機器數(shù)量逐年增加，且很有可能會使用不同類型的機器?，F(xiàn)階段企業(yè)所使用的數(shù)控切割設(shè)備主要有火焰、等離子和激光切割機3類，相互獨立的多臺不同類型的設(shè)備可以同時啟動，互不影響。對大量的金屬板材進(jìn)行切割會消耗大量的資源，制造成本高，在切割工序中為金屬板材選用合適的機器以及安排合理的生產(chǎn)順序能夠以最小的投入降低總生產(chǎn)成本。

根據(jù)Graham等[1]提出的分類方法，切割下料車間的調(diào)度問題屬于并行機生產(chǎn)調(diào)度問題，而且金屬板材的切割時間取決于所分配的機器，同時多臺機器互不影響，因此更具體地說，該問題屬于不相關(guān)并行機調(diào)度問題(Unrelated Parallel Machine Scheduling Problem, UPMSP)。對并行機調(diào)度這個NP-hard問題[2]的研究，在調(diào)度模型和求解算法兩個方面不斷的深入，取得了許多成果[3]。Mokotoff[3]對以最小化最大完工時間(根據(jù)α|β|γ表示法[1]，表示為Cmax)為目標(biāo)的同型并行機調(diào)度問題進(jìn)行了詳細(xì)的綜述。Kaabi等[4]從算法的復(fù)雜性、機器環(huán)境和優(yōu)化目標(biāo)等角度綜述了考慮可用性約束的并行機調(diào)度問題研究進(jìn)展。

在復(fù)雜環(huán)境下的并行機調(diào)度問題，與實際調(diào)度較吻合，得到學(xué)術(shù)界的廣泛關(guān)注。Centeno[5]考慮釋放時間(release time)和工件可使用的機器集合(machine eligibility restrictions)，以Cmax為目標(biāo)函數(shù)建立數(shù)學(xué)模型，設(shè)計了一種新的啟發(fā)式算法求解。Rabadi等[6]同樣以Cmax為目標(biāo)，研究了包含準(zhǔn)備時間的不相關(guān)并行機調(diào)度問題。Hashemian等[7]考慮機器的可用性約束，利用新的枚舉算法求解以Cmax為目標(biāo)的并行機調(diào)度問題。Hamzadayi等[8]針對序列相關(guān)準(zhǔn)備時間的相同并行機調(diào)度問題，同樣以Cmax為目標(biāo)建立混合整數(shù)線性規(guī)劃模型，用模擬退火和遺傳算法(Genetic Algorithm，GA)求解。針對模糊環(huán)境(加工時間、釋放時間和準(zhǔn)備時間都是模糊的)下的不相關(guān)并行機調(diào)度問題，Liao等[9]提出一種混合蟻群算法。羅家祥等[10]研究了含釋放時間的相同和不相關(guān)兩類并行機調(diào)度問題，提出一種基于變深度環(huán)交換鄰域結(jié)構(gòu)的迭代局部搜索(Iterated Local Search, ILS)算法，并與Scatter Search搜索方法結(jié)合加強了ILS逃出局部最優(yōu)的能力。王凌等[11]針對不相關(guān)并行機混合流水線調(diào)度問題設(shè)計了一種基于排列的編碼和解碼方法，并提出一種人工蜂群算法求解。

除了最小化最大完工時間目標(biāo)函數(shù)外，還有總拖期最小化。Kim等[12]對準(zhǔn)備時間根據(jù)排序變動的不相關(guān)并行機調(diào)度問題進(jìn)行研究，用模擬退火算法進(jìn)行求解總拖期最小化的問題。Shim等[13]則對同型并行機進(jìn)行研究，以總拖期最短為目標(biāo)函數(shù)應(yīng)用分支界定算法求解。González等[14]研究了準(zhǔn)備時間根據(jù)排序變動的單一機器調(diào)度問題，該問題以加權(quán)拖期為目標(biāo)函數(shù)，提出一種分散搜索算法。Rajkanth等[15]研究了考慮釋放時間的不相關(guān)并行機調(diào)度問題，以總得提前期和拖期最小化為目標(biāo)構(gòu)建混合整數(shù)線性規(guī)劃模型，并采用一種改進(jìn)的遺傳算法求解。李鵬等[16]針對不確定制造環(huán)境中配件數(shù)量約束條件發(fā)生變化后的并行機動態(tài)調(diào)度問題，提出一種基于操作屬性模式的并行機動態(tài)調(diào)度算法優(yōu)化總拖期時間性能指標(biāo)。

以最小化最大完工時間和總拖期最小化為目標(biāo)函數(shù)的調(diào)度問題模型，其目的是為了提高生產(chǎn)效率，增加企業(yè)的響應(yīng)柔性，提高企業(yè)對市場的響應(yīng)速度。然而，在大中型機械設(shè)備和大型鋼結(jié)構(gòu)件的生產(chǎn)制造中，產(chǎn)品復(fù)雜且制造成本高，生產(chǎn)人員更加注重總生產(chǎn)成本的控制。本文從降低總生產(chǎn)成本出發(fā)，分析金屬板材切割下料工序的成本構(gòu)成，以切割工序需要的總成本為目標(biāo)函數(shù)，建立該不相關(guān)并行機調(diào)度優(yōu)化問題的數(shù)學(xué)模型。針對該優(yōu)化問題，提出一種十進(jìn)制灰狼優(yōu)化(Decimal Grey Wolf Optimization, DGWO)算法進(jìn)行求解。

1 問題描述與模型構(gòu)建

1.1 問題描述

金屬板材切割下料車間的調(diào)度問題屬于不相關(guān)并行機調(diào)度問題。具體地，此問題研究的是將n張板材分配到滿足加工約束的g種型號共m臺的數(shù)控切割機上加工，并對分配到同一臺機器上的板材進(jìn)行排序。在整個切割工序中，本文主要考慮了加工成本、庫存成本和延期成本。在加工成本中，又由4個部分構(gòu)成：設(shè)備啟動成本，切割成本，空行程成本和穿孔成本。如表1所示。

表1 切割工序成本構(gòu)成

一張板材的整個切割過程分為準(zhǔn)備、加工和收料3個時間段。準(zhǔn)備時間是在上一張板材收料完成后將待切割板材放到切割設(shè)備上，設(shè)備啟動之前需要的時間，與板材有關(guān)，收料時間也只與板材有關(guān)，而加工時間則與板材和所選擇的切割設(shè)備有關(guān)。加工時間是設(shè)備的啟動準(zhǔn)備時間、切割時間、穿孔時間和空行程時間四者相加。

1.2 模型假設(shè)

考慮到實際問題的特點和問題可處理性，對問題做如下合理假定：

(1)每張板材只有切割這一個工序，可以在滿足尺寸工藝約束的任何一臺機器上加工；

(2)每臺機器在同一時間只能加工一張板材；

(3)板材切割過程不中斷；

(4)任何一張板材只能使用一臺機器切割；

(5)板材上的零件收料完成表示已交貨，開始下一張板材。

1.3 符號定義

m為切割機總數(shù);

n為板材總數(shù);

i=1,…,n為第i張板材;

j=1,…,m為第j臺機器;

hj×lj×wj為切割機最大切割尺寸;

hi×li×wi為板材i的尺寸;

Di為板材i的交貨期;

Cj為設(shè)備j的單位時間啟動成本;

Ti,j為板材i在機器j上的單個穿孔時間;

Si,j為板材i在機器j上開始切割時間;

Ei,j為板材i在機器j上完成切割時間;

Ni為板材i的穿孔數(shù)量;

Vi,j為板材i在機器j上的切割速度;

Bi,j為板材i在機器j上時設(shè)備啟動時間;

MFi為第i張板材可用機器集合;

xi,j為板材i在機器j上切割時，1；其他，0。

1.4 調(diào)度模型

本文研究的不相關(guān)并行機調(diào)度問題是指為每張板材合理分配使用的機器，安排每臺機器上板材的加工順序，確定板材的開始切割時間和完工時間，使得整個切割工序的總成本C盡可能最小。

(1)

s.t.

(2)

(3)

Ei,j

(4)

(5)

(6)

MFi∈M,MFi≠?;

(7)

hi≤hj∪li≤lj∪wi≤wj,xij=1。

(8)

其中：式(1)為調(diào)度的優(yōu)化目標(biāo)；式(2)是分配約束，表示每張板材只能分配給一臺機器進(jìn)行切割；式(3)為板材i在機器j上的設(shè)備啟動成本；式(4)時間約束，表示板材在當(dāng)前機器切割未完成時，下一張板材不能開始進(jìn)行切割；式(5)和式(6)表示第i張板材的切割完成時間和下一張板材的開始切割時間；式(7)表示板材進(jìn)行切割加工的可用機器集合；式(8)表示尺寸約束，待切割板材i的尺寸要滿足機器可切割的尺寸要求，否則不能進(jìn)行切割。

本文研究的不相關(guān)并行機調(diào)度問題與流水車間和作業(yè)車間調(diào)度不同，主要特點是每張板材可以在滿足工藝要求的多臺設(shè)備上加工，同時本文不僅以企業(yè)最關(guān)心的制造成本作為目標(biāo)函數(shù)，還在模型中也考慮了完工時間，將時間轉(zhuǎn)化為庫存成本和延期成本，求解最優(yōu)的調(diào)度方案。

求解所研究的不相關(guān)并行機調(diào)度問題，關(guān)鍵點與難點在于確定每張板材分配到哪臺機器以及開始切割的時間，即每臺切割設(shè)備上切割哪些板材以及所切割板材的次序。當(dāng)確定了板材的加工機器和次序，加工成本、庫存成本和延期成本就可以通過相應(yīng)的關(guān)系式計算出來。由于該問題是NP-hard問題[2]，當(dāng)板材數(shù)量較多時，用相應(yīng)的算法較難求得最優(yōu)解，本文提出一種全局搜索能力較好的元啟發(fā)式算法DGWO算法來求解。

2 求解算法

不相關(guān)并行機調(diào)度問題是NP-hard問題[2]，針對此類組合優(yōu)化問題，由于元啟發(fā)式算法具有較好的全局搜索能力，因此得到了較廣泛的研究和應(yīng)用?；依撬惴ㄒ驗槠淞己玫膹V度開拓和深度開采能力，引起了國內(nèi)外學(xué)者的廣泛關(guān)注，并已被應(yīng)用到求解各種復(fù)雜問題中。Mirjalili等[17]提出灰狼算法，并用于求解高維多峰連續(xù)函數(shù)優(yōu)化問題。吳虎勝等[18]將其應(yīng)用于求解旅行商問題。Emary等[19]將二進(jìn)制灰狼算法應(yīng)用于機器學(xué)習(xí)的特征選取中，提高了分類的準(zhǔn)確性和降低選取特征的數(shù)量；Komaki[20]等對兩階段裝配流水車間的調(diào)度問題用灰狼算法進(jìn)行求解。

本文提出算法參數(shù)少且易編碼實現(xiàn)的DGWO算法，該算法將狼群中的狼依據(jù)不同職責(zé)分工劃分為頭狼、猛狼、探狼，然后根據(jù)灰狼的捕獵行為和獵物的分配方式，抽象出探狼游走、猛狼圍獵這兩種智能行為以及“勝者為王”的頭狼誕生規(guī)則。

由于所研究的問題為離散組合優(yōu)化問題，應(yīng)用二進(jìn)制編碼方式的灰狼算法求解較困難，本文根據(jù)問題特點采用十進(jìn)制編碼方式，即將每張板材用一個十進(jìn)制整數(shù)表示，構(gòu)成一個十進(jìn)制序列(xi1,xi2,xi3,…,xij,…,xin)表示，即DGWO算法中每一匹狼的位置。其中i=1,2,…,M；xip≠xiq，p≠q；xip，xiq，p，q，j=1,2,…,n。M表示狼群大小，n表示板材數(shù)量。當(dāng)采用該編碼方式時，求解的難點在于如何處理模型中的工藝約束、機器分配和板材次序問題。在程序中，每個編碼位除了用一個變量表示板材外，還有一個變量用來存儲該板材所分配的機器，而板材在同一機器中的切割順序通過十進(jìn)制序列從左到右的先后次序來表示。

采用隨機的方式初始化狼群，即隨機生成一個十進(jìn)制序列，然后在每張板材的可用機器集合中隨機選擇一臺機器。將頭三匹狼(按照成本從小到大排序)選為頭狼α、β、γ，剩余的狼視為探狼，進(jìn)行游走搜索“獵物”?；依怯巫咚阉鳙C物，抽象為在解空間中搜索尋求最優(yōu)解，而求解該問題最優(yōu)解的核心與難點在于確定板材的切割機器和次序，因此根據(jù)問題特點，針對十進(jìn)制編碼方式，本文對灰狼算法的游走行為進(jìn)行改進(jìn)，提出一種適合求解所研究調(diào)度問題的游走運動算子，其包含移位和重新分配機器兩種操作。移位就是將人工狼i的位置Xi=(xi1,xi2,xi3,…,xij,…,xin)中隨機選定含有stepa個編碼位的片段插入到隨機選定的位置，之后對該片段重新隨機分配機器。stepa是游走步長，stepa=Nw1，w1為游走步長因子，*表示向上取整。移位的工件其對應(yīng)的機器編碼則隨機重新生成。每執(zhí)行一次算子就計算其嗅到的獵物氣味濃度，狼“嗅到”的獵物氣味濃度抽象為目標(biāo)函數(shù)值Y=f(X)，即解碼計算總成本。探狼i在游走次數(shù)h達(dá)到上限hmax時，取嗅到的氣味濃度最大的一次為此次游走的結(jié)果。

頭狼嚎叫召喚猛狼，指揮他們向其所在的位置Xlead靠近，進(jìn)行圍獵。在連續(xù)組合優(yōu)化問題中，兩匹狼的距離根據(jù)數(shù)值的大小來衡量，但在離散組合優(yōu)化問題中，這種方式并不適用，因此本文用定義一的方式來衡量。向獵物靠近就是對猛狼的位置Xi進(jìn)行某種變換，本文提出一種奔襲運動算子。

定義1狼之間的距離。兩個狼p和q在相同編碼位上數(shù)值不相等的個數(shù)D，

p,q∈{1,2,…,M},p≠q。

(9)

D越小說明兩個人工狼之間的距離越近。

DGWO算法的具體步驟如下：

步驟1算法初始化。設(shè)定狼群的規(guī)模為M，設(shè)置算法最大迭代次數(shù)為kmax，最大游走次數(shù)hmax，兩個步長因子w1、w2，初始化狼群。

步驟2根據(jù)“勝者為王”的頭狼產(chǎn)生規(guī)則，嗅到獵物氣味濃度最大的頭三匹狼(即成本最小)為頭狼α、β、γ，剩余的狼為探狼，進(jìn)行游走，直到h>hmax。

步驟3三匹頭狼召喚，猛狼隨機選擇一匹奔向的頭狼，此時的頭狼視為獵物。猛狼對獵物發(fā)起圍攻行為，即根據(jù)奔襲運動算子猛狼進(jìn)行位置的變換，根據(jù)圍攻前后Y值大小，進(jìn)行貪婪決策。

步驟4按照頭狼角逐規(guī)則對三匹頭狼進(jìn)行更新。

步驟5判斷算法是否達(dá)到了終止條件，是則輸出求解問題的最優(yōu)解——頭狼α的位置編碼Xp和其感受到的獵物氣味濃度Ylead，否則轉(zhuǎn)步驟2。

3 實驗分析

為驗證灰狼算法應(yīng)用在不相關(guān)并行機調(diào)度問題上的有效性，本文根據(jù)Liaw[21]等和Kim[22]等介紹的標(biāo)準(zhǔn)算例生成方式以及金屬結(jié)構(gòu)件車間調(diào)研情況，生成算例數(shù)據(jù)。因為很多企業(yè)在購買切割機器時，每次購買的切割類型不同，可以切割的板材類型也不同，所以本文算例假設(shè)有有4種類型的切割機器各1臺，具體的機器信息如表2所示。

表2 切割設(shè)備信息

一共生成5組算例進(jìn)行測試，板材數(shù)量分別為20，40，60，80，100。每個算例中有關(guān)板材的數(shù)據(jù)按表3和表4中列出的方式在一定范圍內(nèi)隨機生成，板材類型從表3中隨機選擇，庫存成本為定值。交貨期則根據(jù)生成公式Rand[P(1-τ-ρ/2)，P(1-τ+ρ/2)]隨機生成。其中本文設(shè)置τ=0.2，ρ=0.4，交貨期不是非常緊急，而且各零件的交貨期分散度也不是非常集中。

(10)

表3 板材類型

表4 算例數(shù)據(jù)生成

GWO算法是一種智能優(yōu)化算法，為評價本文提出的DGWO算法的實用性和有效性，本文選用了遺傳算法以及和聲算法(Harmony Search Algorithm，HSA)兩種常用的智能算法進(jìn)行對比。在求解許多離散問題過程中，文獻(xiàn)[8]研究的遺傳算法表現(xiàn)出良好的求解性能，被廣泛用于求解各種優(yōu)化問題。和聲算法[23]也被應(yīng)用于求解調(diào)度優(yōu)化問題，本文應(yīng)用基本的HSA算法，其參數(shù)設(shè)置見文獻(xiàn)[23]。3種算法求解結(jié)果如表5所示。求解算法設(shè)置相同的迭代次數(shù)和種群數(shù)量，每組算例獨立運行20次，選用最優(yōu)值、平均值、方差作為對比指標(biāo)。由表5中可以看出，在板材數(shù)量為20時，DGWO算法在最優(yōu)值和平均值上劣于GA，但是從方差上來看，求解結(jié)果的穩(wěn)定性比GA好。當(dāng)板材數(shù)量大于20時，從所比較的3個重要指標(biāo)來看，DGWO算法都優(yōu)于GA與HSA。如圖3所示為3種求解算法所求的最優(yōu)制造成本柱形圖，如圖4所示為三者算法最優(yōu)值差值的趨勢圖，從兩圖中可以明顯看出，隨著板材數(shù)量的增加，差值越來越大，可見DGWO算法能夠較好地求解大規(guī)模并行機調(diào)度問題。

表5 算法求解結(jié)果對比

如圖5所示為在板材數(shù)量為100時，迭代2 000次，DGWO，GA和HSA三種算法的進(jìn)化迭代圖，圖5中黑色虛線表示三者的趨勢線。從圖中可以很明顯地看出，DGWO算法收斂速度快，可以比GA和HSA更快地尋取到最優(yōu)解。當(dāng)?shù)?00到400次時，已經(jīng)取得較優(yōu)的解，且多次運行的效果也比較穩(wěn)定。

由實驗結(jié)果可以看出，本文提出的DGWO算法能夠有效求解所研究的問題。分析認(rèn)為，主要原因是：DGWO算法根據(jù)所研究問題的特點以及求解難點而設(shè)計；采用與其他算法不一樣的進(jìn)化策略，即狼群中的狼在三匹頭狼中，隨機選擇一匹靠近，這就保證整個狼群向最優(yōu)解方向靠近的同時避免陷入局部解；整個的算法結(jié)構(gòu)簡潔，進(jìn)化速度快。

4 結(jié)束語

本文對大中型機械設(shè)備和大型鋼結(jié)構(gòu)件生產(chǎn)制造過程中，金屬板材切割下料車間的制造成本較高問題進(jìn)行了研究分析。研究發(fā)現(xiàn)，良好的調(diào)度可以有效地降低成本。該車間的生產(chǎn)調(diào)度問題屬于不相關(guān)并行機調(diào)度問題，本文以成本為目標(biāo)函數(shù)，在分析制造成本構(gòu)成的基礎(chǔ)上，建立該問題的調(diào)度模型，并提出一種十進(jìn)制灰狼算法對該問題進(jìn)行求解。算例測試結(jié)果表明，所提算法能夠有效地求解該問題，且收斂速度快，計算結(jié)果優(yōu)于GA和HSA，特別是在計算規(guī)模較大的調(diào)度問題時比GA和HSA算法更優(yōu)。由于DGWO算法在求解不相關(guān)并行機調(diào)度問題上的良好表現(xiàn)，下一步的研究工作將擴展該算法在調(diào)度問題上的應(yīng)用范圍，同時對算法的參數(shù)作進(jìn)一步的研究。