基于規(guī)則組合的Job Shop多目標(biāo)柔性調(diào)度方法

王?，? 蔣增強(qiáng), 葛茂根

(合肥工業(yè)大學(xué)機(jī)械與汽車工程學(xué)院,安徽合肥 230009)

0 引 言

隨著現(xiàn)代制造業(yè)的發(fā)展,小批量、多品種、具有不同完工時間和產(chǎn)品要求的柔性制造逐漸取代了大批量、單品種的流水線產(chǎn)品制造,與此相適應(yīng)的柔性車間的調(diào)度問題隨之成為機(jī)械制造業(yè)研究的熱點問題。

目前常用的柔性調(diào)度方法主要集中在各種優(yōu)化算法上,如微粒群算法、遺傳算法、免疫算法、模擬退火算法及神經(jīng)網(wǎng)絡(luò)算法等[1-5],但是在實際應(yīng)用中隨著生產(chǎn)系統(tǒng)規(guī)模的擴(kuò)大,這些優(yōu)化算法普遍存在著運算量較大、速度較慢、不容易求取全局較優(yōu)解的問題,難以適應(yīng)現(xiàn)場調(diào)度的實時性需求。本文通過建立一種基于規(guī)則組合的多目標(biāo)柔性調(diào)度方法,利用規(guī)則調(diào)度的簡單、快速的特點,解決Job Shop制造環(huán)境下多目標(biāo)柔性調(diào)度的快速求解問題。

1 問題描述

關(guān)于柔性調(diào)度問題可以描述為:設(shè)有m類待加工工件和n臺機(jī)器,pi表示工件i包含的工序數(shù);表示工件i的第j道工序在機(jī)器k上加工表示工序開始加工時間;表示工序的加工時間。

每個工件包含一道或多道工序并且每道工序可以在多臺性能不同的機(jī)器上加工,每道工序的加工時間、成本隨機(jī)器性能的不同而變化。調(diào)度目標(biāo)是對所有工序在不同機(jī)器上的加工順序進(jìn)行排列,使總優(yōu)化目標(biāo)達(dá)到最優(yōu),并且加工過程還要滿足以下假設(shè)和約束條件:

(1)工件加工工藝事先已經(jīng)確定。

(2)加工過程中,任一道已開始加工的工序不允許中途中斷。

(3)在零時刻所有的工件都可以被加工。

(4)同一時刻,同一臺機(jī)器只能加工一道工序。

(5)同一類工件的工序之間有先后約束,上一工序 j-1完成后才能開始下一工序 j,即:tsijk-ti(j-1)k-tsi(j-1)k≥0。

綜合考慮工件的時間指標(biāo)、成本指標(biāo)以及質(zhì)量指標(biāo),設(shè)定目標(biāo)函數(shù)為min{f(T,C,Q)},其中T、C、Q分別表示時間、成本和質(zhì)量指標(biāo)。

1.1 T的計算方法

T作為時間指標(biāo),主要包含最大完工時間指標(biāo)T(1)和加權(quán)延期和時間指標(biāo)T(2)兩部分,T=T(1)+T(2)。

每類工件的時間指標(biāo) Ti主要由時間變量(t(i),tijk,tei)組成。t(i)為工件 i的交貨期,tijk為工件i的j道工序在機(jī)器k上的加工時間,tei為工件i的完工時間。

最大完工時間指標(biāo)T(1)的計算公式為T(1)=max{tei},總延期時間指標(biāo)T(2)的計算公式為:

式中l(wèi)i為第i類工件的超期懲罰權(quán)重系數(shù),該系數(shù)和訂購工件的客戶級別密切相關(guān)。

其中

1.2 C的計算方法

成本指標(biāo)C主要包含加工成本指標(biāo)C(1)和延誤成本指標(biāo)C(2),即C=C(1)+C(2)。若設(shè)備k的單位成本為ck,則工件i的j道工序的加工成本cijk=ck×tijk,因此,所有工件的加工總成本C(1)=;延誤總成本為式中 αi為工件提前單位時間損失成本;βi為工件延期單位時間損失成本;αi、βi的大小視實時工況而定。

1.3 Q的計算方法

2 規(guī)則調(diào)度方法研究

2.1 調(diào)度規(guī)則描述

規(guī)則調(diào)度方法是指在系統(tǒng)運行時,根據(jù)一定的規(guī)則和策略決定下一步操作的方法。其優(yōu)點是不必進(jìn)行大量的計算,避開了“組合爆炸問題”,只要選擇了合適的規(guī)則便可產(chǎn)生相應(yīng)的調(diào)度策略,方便易行。同時規(guī)則調(diào)度方法的計算速度非?？?可以及時、快速地實現(xiàn)基于實時工況條件下的多目標(biāo)柔性調(diào)度[7]。

目前確定的調(diào)度規(guī)則已經(jīng)超過100多種,其中運用較為廣泛的主要有 FCFS、SPT、LPT、EDD、SCR、MWKR、LWKR 及MOPNR等規(guī)則。本文根據(jù)柔性調(diào)度的特點,結(jié)合多目標(biāo)調(diào)度的需求,選擇如下的調(diào)度規(guī)則,并針對柔性調(diào)度的特點進(jìn)行了相應(yīng)的改進(jìn),具體描述如下:

(1)SPT規(guī)則:優(yōu)先選擇加工時間最短的任務(wù)。

(2)EDD規(guī)則:優(yōu)先選擇完工期限最早的任務(wù),盡可能保證交貨期。

(3)SCR規(guī)則:優(yōu)先選擇關(guān)鍵比最小的任務(wù),關(guān)鍵比的公式為:。式中DD是工件的交貨期(t(i)),CD是當(dāng)前時間,T是工件的剩余工序加工時間,(j′為 i工件的當(dāng)前工序)。

(4)MWKR規(guī)則:優(yōu)先選擇余下加工時間最長的任務(wù),加工時間的計算公式為

(5)MOPNR規(guī)則:優(yōu)先選擇余下工序數(shù)最多的任務(wù),工序數(shù)的計算公式為pi-j′。

(6)SPC規(guī)則:優(yōu)先選擇加工成本最小的工序任務(wù),工序加工成本的計算公式為ck×tijk。

(7)HPQ規(guī)則:優(yōu)先選擇工序能力指數(shù)最高的任務(wù)。

(8)RONDOM規(guī)則:隨機(jī)挑選任務(wù)。

2.2 雙層規(guī)則組合的調(diào)度方法

根據(jù)調(diào)度目標(biāo)函數(shù)中選取的優(yōu)化性能指標(biāo),考慮到滿足加工時間、加工成本和加工質(zhì)量的要求,在分析各種調(diào)度規(guī)則特點的基礎(chǔ)上,選取以下規(guī)則,采用雙層規(guī)則組合的方式構(gòu)建調(diào)度方案集。4種第 1 層規(guī)則(EDD、SCR、MWKR、MOPNR)和4種第2層規(guī)則(SPT、SPC、HPQ 、RONDOM)共組成16組方案。

調(diào)度流程示意如圖1所示。

圖1 雙層規(guī)則組合調(diào)度流程示意圖

調(diào)度開始時,將調(diào)度任務(wù)集中當(dāng)前時刻所有可以開始加工的工序任務(wù),調(diào)入待加工任務(wù)集,根據(jù)組合規(guī)則中的第1層調(diào)度規(guī)則對這些工序任務(wù)進(jìn)行排序。當(dāng)同一優(yōu)先級的待加工工序任務(wù)數(shù)大于1時,將此優(yōu)先級別的工序任務(wù)合并為一個集合(視為一個新的虛擬工序任務(wù)類型),進(jìn)入第2層規(guī)則調(diào)度。

根據(jù)待加工任務(wù)的排序結(jié)果,由高到低依次選取各個待加工任務(wù),根據(jù)組合規(guī)則中的第2層調(diào)度規(guī)則進(jìn)行工序方案的選定,即為當(dāng)前可加工工序任務(wù)選擇機(jī)器設(shè)備的過程。若最優(yōu)級工序任務(wù)所需設(shè)備處在加工狀態(tài)時,則選次優(yōu)級工序任務(wù),以此類推。若同一優(yōu)先級工序任務(wù)所需的設(shè)備均處在加工狀態(tài)的話,則將該優(yōu)先級工件歸入下一輪調(diào)度的待加工任務(wù)集。若同一優(yōu)先級的工序方案數(shù)量大于1且工序所需設(shè)備均空閑時,則隨機(jī)選擇設(shè)備。

2.3 基于離差最大化原理的權(quán)重計算方法

2.3.1 離差最大化原理

假設(shè)屬性權(quán)重向量為 ω=(ω1,ω2,…ωn),ωj≥0,j∈M,并滿足單位化約束條件,則各方案的綜合屬性值可定義為:

多屬性決策,一般是對這些方案綜合屬性值的排序比較,若所有方案在屬性uj的屬性值差異越小,則說明該屬性對方案決策與排序所起的作用越小,反之,則說明其對方案決策將起重要作用[6]。

因此,從對方案進(jìn)行排序的角度考慮,方案屬性值偏差越大的屬性應(yīng)該賦予越大的權(quán)重。

根據(jù)上述分析,向量 ω的選擇應(yīng)使所有屬性對所有方案的總離差最大。因此,屬性uj的權(quán)重計算公式為:

2.3.2 權(quán)重計算方法

根據(jù)離差最大化原理,在調(diào)度方案的一組有效解中,若某一個性能指標(biāo)在各個調(diào)度方案中的變化范圍很小,表明現(xiàn)有的資源條件滿足這個性能指標(biāo)的能力相對穩(wěn)定。那么調(diào)度方案的選擇對該性能指標(biāo)的影響較小,則該性能指標(biāo)不應(yīng)該成為判斷調(diào)度方案優(yōu)劣的主要指標(biāo),所以就不應(yīng)該賦予其重要的權(quán)重。

依據(jù)此原理分析計算規(guī)則調(diào)度的結(jié)果,可以得到一組權(quán)重系數(shù) ω(1),將該權(quán)重系數(shù)與專家系統(tǒng)給出的權(quán)重系數(shù) ω(2)結(jié)合,取兩者加權(quán)值之和作為衡量優(yōu)化性能指標(biāo)在目標(biāo)函數(shù)中重要程度的量化標(biāo)準(zhǔn)。

ω既反映了生產(chǎn)系統(tǒng)的實際需求,又兼顧了現(xiàn)場生產(chǎn)資源狀況滿足系統(tǒng)需求的能力,可以較好地適應(yīng)Job Shop生產(chǎn)車間柔性生產(chǎn)環(huán)境復(fù)雜多變的特點。

3 仿真結(jié)果與分析

為了驗證基于規(guī)則組合的Job Shop多目標(biāo)柔性調(diào)度方法的實用性和有效性,對Job Shop車間一個5類工件、5臺機(jī)器的柔性調(diào)度問題進(jìn)行研究,主要數(shù)據(jù)見表1所列。

其中,5類工件的交貨期分別為[20 h 24 h 18 h 25 h 28 h]。運用本文的調(diào)度方法,運行時間為2 s,結(jié)果見表2所列。

表1 工序的加工時間、加工費用和相關(guān)數(shù)據(jù)

表2 規(guī)則組合調(diào)度結(jié)果

表2中,T(2)為加權(quán)延期和;T(1)為最大完工時間;C(1)為加工成本;C(2)為延誤成本;Q為加工質(zhì)量。

根據(jù)組合規(guī)則調(diào)度結(jié)果,結(jié)合專家系統(tǒng)給出的權(quán)重組合系數(shù),運用離差最大化方法進(jìn)行調(diào)度方案排序,分析結(jié)果如下:

考慮工件的加權(quán)延期和和延誤成本和,規(guī)則組合調(diào)度結(jié)果得到的性能指標(biāo)[T(1)T(2)QC(1)+C(2)]權(quán)重組合 ω(1)=[0.6664 0.0544 0.1735 0.1057],此時,專家系統(tǒng)給出的權(quán)重組合 ω(2)=[0.5 0.1 0.1 0.3]。實時工況要求在時間指標(biāo)上主要強(qiáng)調(diào)工件的加權(quán)延期和最小,而非通常所要求的最大完工時間越短越好,因此,工件的加權(quán)延期和指標(biāo)成為調(diào)度方案優(yōu)劣性判斷的重要依據(jù)。此外,在滿足工件交貨期要求的情況下,包含延誤成本在內(nèi)的成本指標(biāo)成為評判調(diào)度方案優(yōu)劣的另一個重要指標(biāo)。

本文取2組權(quán)重平均值得到 ω=[0.5832 0.0772 0.1367 0.2028],根據(jù)ω計算得到調(diào)度方案排序為6-5-10-3-2-1-11-9-8-15-7-14-13-16-4-12,排序表明當(dāng)前工況條件下方案6、5、10較優(yōu)。其中加工成本最低的方案12的甘特圖如圖2所示,最大完工時間最短的調(diào)度方案7的甘特圖如圖3所示。

圖2 時間甘特圖

圖3 時間甘特圖

此外,為了驗證組合規(guī)則調(diào)度的通用性,根據(jù)上述仿真分析的結(jié)果,運用本文的調(diào)度規(guī)則組合方案對參考文獻(xiàn)[8]中的實例數(shù)據(jù)進(jìn)行驗證,其中,調(diào)度方案6的甘特圖如圖4所示。

圖4 時間甘特圖

運用離差最大化的方法對方案進(jìn)行排序,結(jié)果見表3所列。

通過結(jié)果比較,本文的調(diào)度方案2和方案6的適應(yīng)度值均優(yōu)于參考文獻(xiàn)的調(diào)度結(jié)果。雖然成本比參考文獻(xiàn)的方案增加了不到2%,但是最大完工時間提前了6 h,縮減了約12%,而且調(diào)度求解所用的時間僅為2 s。因此,無論在調(diào)度求解時間上還是調(diào)度優(yōu)化結(jié)果上,基于規(guī)則組合的多目標(biāo)柔性調(diào)度方法都具有很好的適用性。

表3 不同調(diào)度方法的結(jié)果比較

4 結(jié) 論

(1)利用調(diào)度規(guī)則針對性強(qiáng)、實現(xiàn)速度快的特點,在對多種調(diào)度規(guī)則進(jìn)行改進(jìn)的基礎(chǔ)上,建立一種滿足Job Shop車間多目標(biāo)柔性調(diào)度需求的雙層規(guī)則組合調(diào)度方法。

(2)運用離差最大化的原理,結(jié)合生產(chǎn)系統(tǒng)實際需求確定各優(yōu)化性能指標(biāo)的權(quán)重,實現(xiàn)Job Shop多目標(biāo)柔性調(diào)度方案的快速選取。

(3)通過仿真實例驗證,該方法在實際生產(chǎn)過程中依據(jù)實時工況,快速提供滿足系統(tǒng)需求的較優(yōu)調(diào)度方案方面具有很好的適用性。

[1] 劉明周,張明偉,蔣增強(qiáng),等.基于混合粒子群算法的多目標(biāo)柔性Job-Shop調(diào)度方法[J].農(nóng)業(yè)機(jī)械學(xué)報,2008,39(5):122-127.

[2] 鞠全勇,朱劍英.多目標(biāo)批量生產(chǎn)柔性作業(yè)車間優(yōu)化調(diào)度[J].機(jī)械工程學(xué)報,2007,43(8):148-154.

[3] 余建軍,孫樹棟,劉易勇.基于免疫算法的多目標(biāo)柔性Job Shop調(diào)度研究[J].系統(tǒng)工程學(xué),2007,22(5):214-222.

[4] 袁 坤,朱劍英.一種求解多目標(biāo)柔性 Job Shop調(diào)度的改進(jìn)遺傳算法[J].中國機(jī)械工程,2007,18(2):651-656.

[5] 翁妙鳳,李曉敏.基于模擬退火多種群并行進(jìn)化規(guī)劃的柔性調(diào)度方法[J].華東船舶工業(yè)學(xué)院學(xué)報,2002,16(2):27-31.

[6] 徐澤水.不確定多屬性決策方法及應(yīng)用[M].北京:清華大學(xué)出版社,2004:22-26.

[7] 王艷紅,尹朝萬,張 宇.基于多代理和規(guī)則調(diào)度的敏捷調(diào)度系統(tǒng)研究[J].計算機(jī)集成制造系統(tǒng),2000,6(4):45-49.

[8] 柳 穎,馬 劍.基于多目標(biāo)決策的車間作業(yè)調(diào)度算法研究[J].中國制造業(yè)信息化,2007,36(21):14-18.