王進峰， 范孝良， 宗鵬程， 萬書亭

（華北電力大學能源動力與機械工程學院，河北 保定 071003）

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

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

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

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

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

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

（3）機器調整時間和零件運輸時間忽略不記；

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

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

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

2 應用蟻群算法解決IPPS問題

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

2.1 工序選擇階段

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

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

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

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

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

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

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

2.1.1 全局更新

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

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

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

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

2.1.2 局部更新

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

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

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

式(7)中

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

式(8)中

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

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

2.2 工序排序階段

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

最大負荷機床負荷Lmax可表示為：

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

機床最大負荷差值Bmax可表示為：

式(12)中Lmin是最小負荷機床負荷。

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

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

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

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

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

3 算例仿真

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

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

在圖2所示的AND/OR圖中，應用上述第二階段蟻群算法，進行路徑尋優(yōu)。設定初始參數(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)路徑

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

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

表2 對比測試結果

4 結 束 語

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

[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] 董朝陽,孫樹棟. 基于免疫遺傳算法的工藝設計與調度集成[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.