基于蟻群算法的虛擬企業生產任務調度優化研究

趙 強,周 敏

(武漢科技大學機械自動化學院,湖北武漢,430081)

虛擬企業(VE)是指分布在不同地區的多個常規企業利用信息和網絡技術而快速響應市場需求與變化所組建的動態聯盟,也是組織、人力、技術和信息等資源在完善網絡組織結構基礎上的有效集成[1-2]。當某企業面臨資源缺乏或能力限制而導致無法獨立完成某項生產任務時,就可以以盟主企業身份通過構建VE來完成該任務。一般來說,盟主企業首先將生產任務分解、歸并為若干個子任務,然后采取招標或選擇代理(V E-broker)等方式選擇適宜的合作企業承擔相應的子任務,通過合作企業共同努力最終完成整個生產任務。生產任務調度關系到VE運作的成敗,已成為VE研究的一項重要內容。Wu[3]等提出了任務分解、歸并的具體方法,該方法為VE生產任務調度奠定了基礎;高陽等[4]建立了基于多智能體的V E生產任務調度模型,并利用集成優化算法來自動處理調度優化問題,但該模型未體現VE生產任務調度的層次性;蘇平等[5]建立的VE生產任務調度模型僅考慮了生產任務的完成時段,且模型較為簡單;高陽等[6]指出VE生產任務調度優化問題類似于Job Shop問題,結合生產任務之間的約束關系,建立了生產任務調度優化模型,但該模型未考慮合作伙伴自身的生產任務集。VE各合作伙伴是一個獨立的實體企業,其自身也存在生產任務,該生產任務是影響VE調度層優化的重要因素,而這一重要因素在目前的相關研究中卻往往被忽視。為此,本文針對VE調度層的優化問題,給出了VE生產任務調度的層次框架(包括VE全局調度與合作伙伴局部調度兩個層次),綜合考慮VE生產任務的時序邏輯關系、作業時間和生產任務集等影響因素,建立以任務總作業時間最小化為目標的數學模型,并基于蟻群優化求解算法,提出VE生產任務調度優化方案。

1 層次框架

為更好地完成各個生產任務,需要從全局和局部兩個角度對生產任務進行調度。由于V E生產任務調度涉及多個合作伙伴,因此VE生產任務應分為VE調度和合作伙伴調度兩個層次,如圖1所示。

圖1 VE生產任務調度層次框架Fig.1 Level framework of production tasks scheduling in VE

VE調度層是全局調度層,主要由盟主企業負責,其工作內容包括生產任務的分解、任務時序關系的確立以及合作伙伴的選擇。從全局視點出發對生產任務進行優化調度,可確定各生產任務的作業時段,以滿足交貨期預定目標的要求。合作伙伴調度層是局部調度層,其調度目標是力求在V E調度層所規劃的作業時段內完成各個生產任務。合作伙伴調度層由各個合作伙伴負責,具體的工作內容包括合作伙伴將其承擔的生產任務進一步分解為子任務,并在優化的基礎上,確定各子任務作業時段和加工作業。通過合作伙伴的協同作業,共同完成VE生產任務。

由于V E全局優化與合作伙伴局部優化存在耦合關系,因此它們之間不可避免地會出現沖突問題。如某一生產任務由于合作伙伴加工設備出現故障或出現緊急生產任務等原因,使得優化后的調度方案仍無法在預定時段完成該生產任務作業時出現沖突。沖突問題的解決需要盟主企業與合作伙伴協商解決,可放松某些生產任務的約束條件或縮短某些生產任務的作業時間,或者引入新的資源,重新選擇承擔某生產任務作業的合作伙伴,在相互協調的基礎上,提出VE全局調度或局部調度優化方案。V E生產任務調度是一個持續協調和優化的過程。

2 優化模型

2.1 問題提出

在V E全局優化生產任務調度之前,盟主企業先將總任務分解為若干具有時序關系的各個生產任務(生產任務之間用活動網絡圖來表示)。在完成合作伙伴局部選擇的基礎上,根據每個伙伴自身已確定的生產任務信息、完成VE全局優化各個生產任務所需作業時間和生產任務之間轉運時間(將運輸和資源的調整時間,統稱為轉運時間)等信息來進行生產任務調度優化,其目標是在兼顧生產任務時序約束關系、生產任務作業時間和各個伙伴自身任務集等信息前提下,使得生產任務調度方案既能保證產品交貨期要求,也能使得所有生產任務總的作業時間最小化。VE全局調度優化完成后,各個生產任務的作業時段也就初步確定。隨后合作伙伴將自身所承擔的各個生產任務再次分解,并根據生產任務分解、設備占用等信息進行局部調度方案的優化,其目標是保證生產任務在已規劃的時段內完成作業。由于VE全局調度與合作伙伴局部調度的優化模型類似,且VE生產任務調度的關鍵在于全局調度優化,因此以下僅討論V E全局調度優化模型及其求解。

2.2 條件假設

以最小化生產任務作業時間為目標,建立了VE全局調度層優化模型。該優化模型的假設條件如下:①每個生產任務的開始作業時間應遵循時序邏輯的約束關系,在生產任務執行過程中不容許中斷;②考慮到伙伴自身生產能力和條件限制,在生產任務執行過程中,一次能且僅能執行一個生產任務;③生產任務的起始作業時間為0。

2.3 模型符號

VE全局調度層優化模型的符號設定如下:P為合作伙伴集,m為合作伙伴總數,P={P1,P2,…,Pk,…,Pm},k∈[1,m];T為生產任務集,n為生產任務總數,T={T1,T2,…,Ti,…,Tn};Rk為Pk承擔的生產任務集,Rk={T1,…,Ti,…},i∈[1,n],且各個伙伴任務集滿足Rk∩Rk′=φ(k,k′∈[1,n]),R1∪R2∪…∪Rm=T;H為滿足時序約束關系的所有生產任務對集合;Fi為Ti的緊前生產任務集,(Ti′,Ti)∈H,Ti′∈Fi,i′∈[1,n];zi′i為Ti′～Ti的轉運時間,當Ti′與Ti由同一伙伴完成時,zi′i=0;TBi為由Pk承擔的生產任務集,且作業順序位于Ti緊前的一個生產任務,TBi∈Rk;si為Ti的開始作業時間;ti為完成Ti所需的作業時間;fi為Ti的結束作業時間;Mk為Pk先于VE組建前已確定的生產任務集,用時間段表示,記為Mk={[m1,m2],…};D為產品交貨期。

2.4 模型描述

基于以上假設條件及符號設定,VE全局生產任務優化調度模型描述如下:

式(1)為目標函數,即生產任務總的作業時間,優化調度方案力求最后一個生產任務盡早完成;式(2)為某生產任務開始作業時間,必須在其所有的緊前生產任務轉運完成后才能夠開始,即滿足作業邏輯順序約束;式(3)為某生產任務開始作業時間,必須在由同一個伙伴完成且作業順序位于該生產任務緊前的生產任務完成后才能夠開始,即滿足資源約束;式(4)為生產任務開始作業時間與完成作業時間的關系;式(5)為合作伙伴執行V E全局生產任務時,不能與自身已確定的生產任務相沖突;式(6)為交貨期約束。

3 蟻群算法優化求解

蟻群算法[7-8]是一種模擬螞蟻覓食行為的進化算法。蟻群算法對離散組合優化問題有較好的求解效果。因此,以下采用蟻群算法對VE全局生產任務調度問題進行優化求解。

3.1 算法設計

3.1.1 約束矩陣的建立

蟻群算法在求解VE全局生產任務調度時,每次迭代中均要求每只螞蟻從起始節點開始,遍歷所有生產任務節點,最后到達終止生產任務節點,螞蟻走過的節點順序便是構造的解。由于生產任務之間存在時序邏輯關系,因此只有建立生產任務間的約束矩陣,才能有效保證構造解的合理性,進而保證VE全局生產任務調度優化方案的合理性?？刹捎?個常量來建立VE全局生產任務間的時序邏輯約束矩陣,并以生產任務Ti與Tj為例加以說明。0表示Ti與Tj之間不存在時序邏輯約束關系;1表示Ti與Tj之間存在時序邏輯約束關系,且Ti先于Tj開始作業;2表示Ti與Tj之間存在先后順序關系,且Ti后于生產任務Tj開始作業。VE全局生產任務間的時序邏輯約束矩陣A(A的行與列的編號均為生產任務編號)描述如下:

3.1.2 狀態轉移概率

螞蟻從一個生產任務節點i轉向下一個生產任務節點j時,其轉移概率計算式為

3.1.3 信息素更新

在第t次迭代中,螞蟻按式(8)的選擇規則遍歷所有生產任務節點,構造出一個調度序列,即得到所有生產任務的作業順序。在第t+1次迭代開始前,需要對信息素進行更新,其更新式為

式中:Δτij=1/fmax(k),其中fmax(k)為螞蟻k在第t次迭代后得到的生產任務總作業時間,d;ρ為信息素的揮發因子。

3.2 求解步驟

VE全局生產任務調度優化的求解步驟如下:

(1)初始化:①建立生產任務時序約束矩陣;②參數初始化,即初始化外激素信息矩陣、設置外激素消逝速度等參數;③在虛擬起始點生成一定數量的一代螞蟻。

(2)迭代直至滿足預定迭代次數:①每只螞蟻都可根據約束矩陣判斷生產任務節點;②螞蟻按照式(8)進行狀態遷移;③完成對所有生產任務節點的遍歷;④按照式(9)進行信息素更新;⑤記錄最優的生產任務調度優化方案。

(3)輸出最優的生產任務調度方案。

4 實例分析

4.1 應用實例

由5個合作伙伴(編號為P1～P5)組成的V E共同完成某汽車起重機產品的制造任務,交貨期為100 d。該制造任務可分解為包括汽車起重機的起升機構制造、回轉機構制造、變幅機構制造以及裝配調試等23個生產任務,生產任務之間活動網絡如圖2所示。生產任務分工后,P1～P5分別完成生產任務集為ET1～ET5:ET1為{T2,T6,T8,T15,T22},ET2為{T5,T11,T20,T21,T23},ET3為{T10,T14,T18},ET4為{T3,T7,T12,T16,T17},ET5為{T4,T9,T13,T19,T24}。由圖2可看出,圓角矩形框下的數字是合作伙伴完成該零部件生產任務所需的作業時間,箭頭線上的數字標注代表轉運時間(當生產任務由同一伙伴完成時,轉運時間為0)。若生產任務的開始時間設定為0,則P1已確定的生產任務集為{[40,60]},P2已確定的生產任務集為{[65,75]},P3已確定的生產任務集為{[15,35]},P4已確定的生產任務集為{[40,50]},P5已確定的生產任務集為{[68,75]}。綜合考慮上述已知信息,V E優化的生產任務調度方案是求解最小化起重機產品的制造完工時間。

4.2 調度優化

綜合以上給定信息,采用蟻群算法進行優化求解。設定螞蟻數量為20,α=β=0.9,ρ=0.9,迭代次數為200。VE全局優化后的汽車起重機生產任務調度方案如圖3所示(生產任務開始時間設定為原點)。在該調度方案下,生產任務T24～T2的制造和轉運時間總計為83.5 d,加上10 d的產品裝配和調試時間,整個汽車起重機產品制造生產任務可在93.5 d內完成,滿足了客戶交貨期要求。

圖2 汽車起重機生產任務活動網絡Fig.2 Activity network diagram of production tasks of truck crane

圖3 VE全局生產任務調度方案Fig.3 Global scheduling plan of production tasks in VE

4.3 調度調整

在生產任務作業初期,合作伙伴P3由于企業自身生產任務的調整使得在時間段[35,60]以內生產任務較重,合作伙伴P3不能在上述時段對生產任務T14進行作業,因此需要對生產任務調度方案進行適當調整。在不影響其他合作伙伴生產任務作業的前提下,VE全局優化后的汽車起重機生產任務調度方案如圖4所示。在該調度方案下,生產任務T14的作業時段由[35,45.5]調整為[21.5,32],并且生產任務T2～T23的制造和轉運時間總計仍為83.5 d,也滿足了產品的交貨期要求。

當某生產任務延期完成時,可根據VE全局生產任務的延遲程度對生產任務調度方案進行適當的調整。若生產任務T22延遲2 d完成,則對合作伙伴P4而言,可將其承擔的生產任務作業時間適當延遲。VE全局生產任務調整后的汽車起重機生產任務調度方案如圖5所示。在該調度方案下,生產任務T2～T23的制造及轉運時間總計為84 d,滿足了產品交貨期要求。

圖4 T14作業時段調整后的VE全局生產任務調度方案Fig.4 Global scheduling plan of production tasks in VEafter adjusting operating time of T14

圖5 T22作業延遲的VE全局生產任務調度方案Fig.5 Global scheduling plan of production tasks in VE under operating delay of T22

當生產任務T22延遲2 d完成,并且合作伙伴P4由于企業自身生產任務的調整使得在時間段[26,50]以內無法對其承擔的生產任務進行作業時,V E全局生產任務優化后的生產任務調度方案如圖6所示。在該調度方案下,生產任務T2～T23的制造和轉運時間總計為96.5 d,無法滿足產品交貨期要求。為不影響產品交貨期,合作伙伴P4需要通過引入合作企業或新增加工設備等方法來縮短生產任務T12或T16的作業時間,并將完成自身生產任務的時間段控制在[40,50]以內,以保證VE全局生產任務調度方案進度的執行。

圖6 P4任務集調整的VE全局生產任務調度方案Fig.6 Global scheduling plan of production tasks in VEafter adjusting task sets of P4

基于上述方法,并結合各個生產任務作業的實際情況,對VE全局生產任務調度方法進行優化和調整,從而保證了汽車起重機制造生產任務的按期完成。

4.4 算法有效性的驗證

以文獻[6]提供的實例,我們驗證了蟻群算法求解V E全局生產任務調度優化問題的有效性。VE全局優化后的生產任務調度方案如圖7所示。在該生產任務調度方案下,求得制造周期為99 d,與文獻[6]給出的VE全局優化結果相同。本研究運用蟻群算法在Pentium IV PC機上的平均求解時間僅為2.6 s,明顯優于文獻[6]給出的6～8 s的平均求解時間。因此,蟻群算法可有效地求解V E全局生產任務調度優化問題。

圖7 不考慮合作伙伴任務集的VE全局生產任務調度方案Fig.7 Scheduling plan of production tasks in VEafter neglecting partner’s task sets

5 結語

生產任務調度是典型的NP難題。本文描述了VE生產任務調度的層次框架(包括V E全局調度層和合作伙伴局部調度層)。VE生產任務調度層主要內容是從全局視點出發對生產任務進行優化,在滿足交貨期的預定目標前提下,達到最小化生產任務的作業完成時間;而合作伙伴調度層主要內容是力求在VE調度層所規劃的作業時段內完成各個生產任務。針對VE生產任務調度層的優化問題,建立了以生產任務總的作業時間最小化為目標的優化模型,并給出了蟻群求解算法。通過某汽車起重機制造實例驗證了優化模型及其求解算法的有效性,并針對實際情況給出了VE生產任務調度調整的具體方案。

[1] Nagel R,Dove R.21stcentury manufacturing enterprise strategy:an industry-led view[R].Bethlehem:Iacocca Institute,Lehigh University,1991:122-134.

[2] Abbe M.Virtual organization[J].Communication of the ACM,1997,40(9):30-37.

[3] WuNQ,Sun J.Grouping the activities in virtual enterprise paradigm[J].Production Planning and Control,2002,13(4):407-415.

[4] 高陽,周偉.基于多Agent的虛擬企業調度研究與實現[J].中國機械工程學報,2004,15(11):978-982.

[5] 蘇平,伍乃騏.一種可重構制造系統的生產計劃方法[J].計算機集成制造系統,2003,9(3):189-193.

[6] 高陽,江資斌.用混合遺傳算法求解虛擬企業生產計劃[J].控制與決策,2007,22(8):931-934.

[7] Marco D,Vittorio M,Alberto C.Ant system:optimization by a colony of cooperating agents[J].IEEE Transactions on Cybernetics,1996,26(1):29-41.

[8] Marco D,Luca M G.Ant colonies for the traveling sales-man problem[J].Bio Systems,1997(43):73-81.