一種改進(jìn)的蟻群算法在工藝規(guī)劃與車間調(diào)度集成優(yōu)化中的應(yīng)用

王進(jìn)峰， 范孝良， 宗鵬程， 萬書亭

（華北電力大學(xué)能源動力與機(jī)械工程學(xué)院，河北 保定 071003）

工藝規(guī)劃與車間調(diào)度（integrated process planning and scheduling，IPPS）是制造過程中的兩個重要子系統(tǒng)。在傳統(tǒng)制造模式下，工藝規(guī)劃和車間調(diào)度往往是獨(dú)立運(yùn)行，互不干涉，科研工作者也往往將二者割裂研究。但是，車間生產(chǎn)的實(shí)際情況表明，工藝規(guī)劃是車間調(diào)度的基礎(chǔ)，將車間調(diào)度和工藝規(guī)劃集成研究更符合生產(chǎn)的實(shí)際情況。IPPS集成研究是通過綜合考慮工藝規(guī)劃和車間調(diào)度來優(yōu)化生產(chǎn)過程，將各個加工訂單分解為可調(diào)整的工藝路線，并以此作為車間生產(chǎn)調(diào)度的輸入，按照生產(chǎn)資源和生產(chǎn)系統(tǒng)的現(xiàn)狀選擇合適的加工工序和工藝路線，安排各加工工序在相應(yīng)的機(jī)床加工，最終獲得滿足生產(chǎn)實(shí)際情況的工藝和調(diào)度方案。Chryssolouris等[1]在80年代中期第一次提出了工藝規(guī)劃與車間調(diào)度集成的構(gòu)想，此后科研工作者嘗試使用各種方法求解 IPPS問題。Morad和Zalzala[2]第一次提出采用基于遺傳算法(genetic algorithm，GA)解決工藝規(guī)劃和調(diào)度集成問題。Kumar等[3]第一次試圖應(yīng)用蟻群算法解決工藝規(guī)劃和調(diào)度集成問題。Kim等[4]采用一種共生進(jìn)化算法提高了算法的搜索效率，并且在論文中設(shè)計了較為復(fù)雜的 IPPS標(biāo)準(zhǔn)算例。董朝陽和孫樹棟[5]采用免疫遺傳算法求解工藝設(shè)計與調(diào)度集成問題。Leung等[6]提出了基于AND/OR圖的工藝規(guī)劃和調(diào)度集成模型，以最小完工時間為優(yōu)化目標(biāo)，求解工藝規(guī)劃和調(diào)度問題的方法。Wong等[7]在文獻(xiàn)[6]的基礎(chǔ)上，改進(jìn)了蟻群算法，通過兩個階段的蟻群算法求解工藝規(guī)劃和調(diào)度問題，即：工序選擇和工序排序兩個階段。到目前為止，國內(nèi)外的學(xué)者在解決 IPPS問題時，主要存在兩方面問題：①IPPS問題的表達(dá)方案缺少柔性，往往不能反應(yīng)現(xiàn)場的真實(shí)情況；②大部分解決方法屬于單目標(biāo)優(yōu)化，以最大完工時間Cmax作為目標(biāo)，忽視了其他更加貼合生產(chǎn)的實(shí)際需求，譬如交貨期等。為了解決上述問題，本文改進(jìn)了 IPPS問題的表達(dá)方案，為工序離散圖中的工序節(jié)點(diǎn)增加了可選機(jī)床及其加工時間。針對蟻群算法容易出現(xiàn)的收斂過慢和局部收斂問題，采用信息素動態(tài)更新策略，并將多目標(biāo)優(yōu)化策略應(yīng)用于求解過程。

1 基于AND/OR圖的工藝規(guī)劃與車間調(diào)度集成問題

工藝規(guī)劃和調(diào)度集成問題的描述如下：

m 臺機(jī)床｛W1,W2,…Wm｝完成 n個零件{J1,J2,…Jn}的加工。每個零件 Ji包含 p道工序{Oi1,Oi2,…Oip}，可形成由p道工序按照一定規(guī)則構(gòu)成的q道可選工藝路線{Li1,Li2,…Liq}，集成問題的優(yōu)化目標(biāo)是確定n個零件的工序，并根據(jù)工廠的實(shí)際情況，進(jìn)行車間作業(yè)調(diào)度。IPPS問題描述，還需要引入以下條件：

（1）完成工序 Oij的機(jī)床 Wk可選，某道工序指定機(jī)床的加工時間tijk已知，其中｛Oij∈O,Wk∈W,i = 1,2,…,n,j = 1,2,…,p ,k = 1,2,…,m｝；

（2）某個時刻每臺機(jī)床Wk只能處理一個作業(yè)Ji,同一作業(yè)Ji的兩道工序不能同時加工，且工序Oij一經(jīng)開始就不能中斷；

（3）機(jī)器調(diào)整時間和零件運(yùn)輸時間忽略不記；

（4）不考慮機(jī)床故障等突發(fā)性因素。

為了便于應(yīng)用蟻群算法解決 IPPS問題，將IPPS問題表示為AND/OR圖，AND/OR圖是一個由3種元素構(gòu)成的離散圖，即節(jié)點(diǎn)集、有向弧/無向弧集、AND/OR關(guān)系。節(jié)點(diǎn)集代表所有零件工藝路線包含的所有工序 Oij。有向弧表示同一零件加工工序間的優(yōu)先級關(guān)系。無向弧表示螞蟻在不同零件工序間可能存在的訪問關(guān)系。有向弧和無向弧表示螞蟻從一個節(jié)點(diǎn)到另一個節(jié)點(diǎn)可能走的路徑。節(jié)點(diǎn)、有向弧、無向弧構(gòu)成所有零件的可行工藝路線。圖1為兩個零件的離散工序圖，節(jié)點(diǎn)O12代表零件1的第2道工序。工序O12可由兩條臺機(jī)床加工W4，W6，其加工時間分別為9 s，8 s。圖1中零件2的節(jié)點(diǎn)工序O21包含7條無向弧，分別指向零件1的7道工序。同理，零件1和零件2的每個節(jié)點(diǎn)工序都包含若干指向其他節(jié)點(diǎn)的無向弧。為了使圖1不過分凌亂，圖中只表示了工序O21的無向弧，而忽略了零件1和零件2的其他節(jié)點(diǎn)工序的無向弧。

同一零件的不同工序之間除了優(yōu)先級關(guān)系外，還有AND、OR關(guān)系。AND關(guān)系指的是工序間的串行關(guān)系，而OR關(guān)系指的是工序間的并行關(guān)系。圖 1中“AND-1”關(guān)系表示的是工序O15、O16允許出現(xiàn)兩種排列，即 O15-＞O16和O16-＞O15，圖1中“OR-2”關(guān)系表示工序O22之后，可以是工序O23，也可以是工序O26和O27。因此，圖1所示AND/OR圖中表示的零件1和零件2的工藝路線如表1所示。

2 應(yīng)用蟻群算法解決IPPS問題

本文針對IPPS問題的復(fù)雜性，在文獻(xiàn)[7]的基礎(chǔ)上，改進(jìn)了 IPPS問題的表達(dá)方案，應(yīng)用了多目標(biāo)優(yōu)化策略改善 IPPS問題的求解質(zhì)量，為了避免收斂過慢和局部收斂問題，采用信息素動態(tài)更新策略。

2.1 工序選擇階段

該階段 AND/OR圖中的節(jié)點(diǎn)是信息素的攜帶者。蟻群中的所有螞蟻置于開始節(jié)點(diǎn)，螞蟻按照一定的選擇概率選擇下一節(jié)點(diǎn)，該選擇概率取決于兩方面，即下一節(jié)點(diǎn)的能見度ηuv和螞蟻遺留在節(jié)點(diǎn)的信息素τuv，因此，螞蟻r選擇下一節(jié)點(diǎn)的概率可表示為：節(jié)點(diǎn)u到節(jié)點(diǎn)v遺留在節(jié)點(diǎn)v的信息素，β為能見度的權(quán)重系數(shù)，α為信息素的權(quán)重系數(shù)。aces[r]為螞蟻r在節(jié)點(diǎn)u的下一節(jié)點(diǎn)訪問列表。

圖1 兩個零件的工序離散圖

表1 零件1和零件2的工藝路線

下一節(jié)點(diǎn)的能見度主要取決于該節(jié)點(diǎn)工序在相應(yīng)機(jī)床的加工時間。通常情況下，節(jié)點(diǎn)工序加工時間越短，螞蟻選擇該節(jié)點(diǎn)的概率越大。因此，節(jié)點(diǎn)v的能見度如式(2)所示。

式(2)中tijk為工序Oij在機(jī)床Wk的加工時間，E為能見度影響系數(shù)，為正值，其取值大小取決于tijk，從式(2)可看出，節(jié)點(diǎn)v的能見度與tijk成反比，tijk越小，螞蟻選擇該節(jié)點(diǎn)的概率越高。

螞蟻在每次尋優(yōu)過程中，在其訪問節(jié)點(diǎn)中都會堆積信息素，該信息素隨著時間歷程會逐漸消退。最終堆積在各個節(jié)點(diǎn)的信息素將引導(dǎo)螞蟻選擇相應(yīng)的節(jié)點(diǎn)，當(dāng)螞蟻初始迭代前，各節(jié)點(diǎn)設(shè)定信息素初值0τ。各個節(jié)點(diǎn)采用動態(tài)的信息素更新

式(1)中u為源節(jié)點(diǎn)，v為目標(biāo)節(jié)點(diǎn)，ηuv為從源節(jié)點(diǎn)u到目標(biāo)節(jié)點(diǎn)v的能見度，τuv為螞蟻r從策略，該策略主要包括全局更新和局部更新兩種策略。

2.1.1 全局更新

對于螞蟻 r，每完成一次從開始節(jié)點(diǎn)到結(jié)束節(jié)點(diǎn)的迭代，則更新途徑路徑中每個節(jié)點(diǎn)的信息素。各個節(jié)點(diǎn)信息素τuv如式(3)所示：

式(3)中τuv（new）為螞蟻r迭代后堆積在節(jié)點(diǎn)v上的信息素，ρglobal為信息素?fù)]發(fā)系數(shù)，ρglobal=ρ0，τuv（old）為螞蟻r迭代前節(jié)點(diǎn)v上的信息素，Δτr為螞蟻r本次迭代結(jié)束后，節(jié)點(diǎn)v的信息素增量。其中，該增量大小與螞蟻r完成本次迭代后的時間歷程有關(guān)。因此，節(jié)點(diǎn)v的信息素增量Δτr如式(4)所示：

式(4)中Qglobal為信息素增量系數(shù)，Qglobal=Q0。Ck為螞蟻r完成本次迭代后的時間歷程，其取值可由式(5)計算：

式(5)中Xijk：調(diào)整系數(shù)，其值為：

2.1.2 局部更新

局部更新策略主要為了解決兩種情況，即收斂過慢和局部收斂。

（1）局部更新策略一。為了加速蟻群算法的收斂，對于表現(xiàn)較好的節(jié)點(diǎn)可加速其信息素的堆積。因此，對于單次迭代表現(xiàn)最好的螞蟻所選擇的節(jié)點(diǎn)再次執(zhí)行信息素更新操作。即：當(dāng)某次迭代中，蟻群中所有的螞蟻完成遍歷后，選擇 Cr最小的訪問路徑的各個節(jié)點(diǎn)，再次執(zhí)行信息素的更新操作，其更新公式如式(3)～(6)所示，這種方法能夠加速信息素在較優(yōu)路徑上的堆積，從而提高了算法的搜索效率。

（2）局部更新策略二。局部收斂指的是當(dāng)連續(xù)幾代蟻群搜索的最優(yōu)路徑完全相同，并且該解明顯不是最優(yōu)解時，則蟻群算法陷入了局部收斂。導(dǎo)致產(chǎn)生局部收斂現(xiàn)象的直接原因是信息素的非正?？焖俣逊e。為了判斷是否存在局部收斂，設(shè)置局部收斂判斷指標(biāo)StdRpt。當(dāng)蟻群算法執(zhí)行過程中，連續(xù)NumRpt代蟻群輸出相同的最優(yōu)節(jié)點(diǎn)列表時，則系統(tǒng)判斷存在局部收斂，系統(tǒng)啟動信息素局部更新策略。局部更新策略主要包括調(diào)整信息素的揮發(fā)速度和減弱局部較優(yōu)路徑的信息素量。因此，式(3)變更為：

式(7)中

信息素增量Δrτ如式(9)所示：

式(8)中

Cr取值同式(5)和式(6)。

當(dāng)蟻群中的螞蟻經(jīng)過多次迭代后，AND/OR圖中相應(yīng)的訪問節(jié)點(diǎn)則堆積了一定的信息素，最終在AND/OR圖中形成一條相對固定的路徑，該路徑包含了每一個零件的某一道可行工藝路線的所有節(jié)點(diǎn)，該節(jié)點(diǎn)列表即為工序選擇階段的輸出，也是第二階段工序排序階段的輸入。

2.2 工序排序階段

本階段對第一階段形成的節(jié)點(diǎn)列表進(jìn)行工序排序，蟻群置于開始節(jié)點(diǎn)，算法執(zhí)行，完成從開始節(jié)點(diǎn)到結(jié)束節(jié)點(diǎn)的遍歷。本階段節(jié)點(diǎn)間的有向弧和無向弧成為信息素的攜帶者。螞蟻選擇節(jié)點(diǎn)及弧段時的選擇機(jī)制同第一階段，但是由于本階段最終要形成合理的調(diào)度方案，因此，其評價指標(biāo)不同于第一階段。通常情況下，調(diào)度方案的評價指標(biāo)根據(jù)優(yōu)化目標(biāo)不同而不同。本文將最大完工時間Cmax最小化、最大負(fù)荷機(jī)床負(fù)荷Lmax最小化和車間機(jī)床最大負(fù)荷差值最小化Bmax作為優(yōu)化目標(biāo)。

最大負(fù)荷機(jī)床負(fù)荷Lmax可表示為：

其中：Xijk如式(6)所示。

機(jī)床最大負(fù)荷差值Bmax可表示為：

式(12)中Lmin是最小負(fù)荷機(jī)床負(fù)荷。

最大完工時間Cmax可表示為：

式(13)中Ci是零件Ji的完工時間。

為了簡化優(yōu)化過程，根據(jù)上述3個優(yōu)化目標(biāo)的重要程度，分別為之設(shè)置不同的權(quán)重系數(shù)，則多目標(biāo)優(yōu)化問題轉(zhuǎn)變?yōu)閱文繕?biāo)的優(yōu)化問題。式(4)和式(9)中的Cr可以表示為：

式(14)中，Cmax(r)、Lmax(r)、Bmax(r)表示螞蟻r完成某次迭代后的最大完工時間，最大負(fù)荷機(jī)床的負(fù)荷，車間機(jī)床最大負(fù)荷差值。λC、λL、λB分別表示Cmax(r)、Lmax(r)、Bmax(r)的權(quán)重。

本階段各弧段的信息素更新也需要全局更新和局部更新相結(jié)合的信息素動態(tài)更新策略。

3 算例仿真

以圖1所示的IPPS問題為例，驗(yàn)證算法的有效性。設(shè)定初始參數(shù)如下：K=8，MaxRpt =5，τ0=1.0，ρ0=0.65，E=20，Q0=100，α=2.0，β=1.0。經(jīng)過上述算法后，形成了輸出節(jié)點(diǎn)列表，原AND/OR圖則轉(zhuǎn)變?yōu)閳D2所示的AND/OR圖。

圖2 工序選擇后的AND/OR圖

在圖2所示的AND/OR圖中，應(yīng)用上述第二階段蟻群算法，進(jìn)行路徑尋優(yōu)。設(shè)定初始參數(shù)如下：K=8，MaxRpt=5，τ0=1.0，ρ0=0.65，E=10，Q0=100，α=2.0，β=1.0，λC= 0.3、λL= 0.2、λB= 0.5。獲得的最優(yōu)路徑，如圖3所示。

圖3 最優(yōu)路徑

為了進(jìn)一步驗(yàn)證算法的有效性，以韓國學(xué)者Kim在2003年提出的標(biāo)準(zhǔn)算例進(jìn)行測試。該標(biāo)準(zhǔn)算例由18種零件組成，每種零件由8～22道工序組成，由18種零件組成了24個測試問題，具體的標(biāo)準(zhǔn)算例數(shù)據(jù)見參考文獻(xiàn)[8]。對比 Kim[8]的SEA算法[4]和本文提出的改進(jìn)ACO算法的最大完工時間Cmax，結(jié)果如表2所示。

從表2的數(shù)據(jù)，可以發(fā)現(xiàn)大部分測試算例的Cmax都有改進(jìn)，算例10的Cmax改進(jìn)程度達(dá)到了24%，算例13、15、19、21的改進(jìn)程度也超過了10%。但是對于個別算例，譬如，算例18的Cmax不僅沒有改進(jìn)反而有所降低，反復(fù)測試該算例，發(fā)現(xiàn)，本算法在解決此算例問題時，反復(fù)的陷入局部收斂或者接近局部收斂，需要對局部更新策略重新設(shè)計。

表2 對比測試結(jié)果

4 結(jié) 束 語

本文改進(jìn)了標(biāo)準(zhǔn)蟻群算法求解 IPPS問題的策略。通過節(jié)點(diǎn)集、有向弧/無向弧集、AND/OR關(guān)系，優(yōu)化了 IPPS問題的求解模型，采用局部更新策略一，加速信息素的堆積，提高了算法的搜索速度；采用局部更新策略二，避免了算法的局部收斂。在工序排序階段，應(yīng)用多目標(biāo)優(yōu)化策略，提高算法的求解質(zhì)量。針對具體實(shí)例進(jìn)行了仿真試驗(yàn)，給出了各個參數(shù)的最優(yōu)取值和最終的仿真結(jié)果。

[1] Chryssolouris G,Chan S,Cobb W. Decision making on the factory floor: an integrated approach to process planning and scheduling [J]. Robotics and Computer-Integrated Manufacturing,1984,1(3～4):315-319.

[2] Morad N,Zalzala A. Genetic algorithms in integrated process planning and scheduling [J]. Journal of Intelligent Manufacturing,1999,10(2): 169-179.

[3] Kumar R,Tiwari M K,Shankar R. Scheduling of flexible manufacturing systems: an ant colony optimization approach [J]. Proceedings of the Institution of Mechanical Engineers,Part B: Journal of Engineering Manufacture,2003,217(10): 1443-1453.

[4] Kim Y K,Park K,Ko J. A symbiotic evolutionary algorithm for the integration of process planning and job shop scheduling [J]. Computers & Operations Research,2003,30(8),1151-1171.

[5] 董朝陽,孫樹棟. 基于免疫遺傳算法的工藝設(shè)計與調(diào)度集成[J]. 計算機(jī)集成制造系統(tǒng),2006,12(11):1807-1813.

[6] Leung C W,Wong T N,Mak K L,Fung R Y K.Integrated process planning and scheduling by an agent-based ant colony optimization [J]. Computers and Industrial Engineering,2010,59(1):166-180.

[7] Wong T N,Zhang Sicheng,Wang Gong,Zhang luping.Integrated process planning and scheduling-multiagent system with two-stage ant colony optimization algorithm [J]. International Journal of Production Research,2012,50(21): 6188-6201.

[8] Kim Y K. 2003[EB/OL]. [2013-06] http://syslab.chonnam. ac.kr/links/data-pp&s.doc.