擾動環(huán)境下非標自動化設備項目反應性調(diào)度*

劉珩達,王子陽,楊宏兵

(蘇州大學機電工程學院,蘇州 215137)

0 引言

隨著項目管理理論研究成果不斷實踐發(fā)展,在項目實施過程中,無法準確預見的不確定因素很多,尤其是在非標設備項目中,這也逐漸成為項目管理的一個重要研究領域。其中反應性調(diào)度方法為該領域最新的研究分支。

應對擾動的方案研究的必要性源自于項目的實際實施過程中,原先通過項目調(diào)度得到的基準計劃時常會受到各式各樣不確定因素的擾動[1],以非標設備項目為例,非標件供應商供貨不及時、設計臨時變更、作業(yè)所需資源判斷失誤以及資源的短缺等[2-4]。這些擾動的存在,使得管理人員在項目的實施過程中需要依照基準計劃根據(jù)擾動做出調(diào)整,所以引入反應性調(diào)度就是應對這些未曾預料到的擾動。通過對原有計劃的迅速調(diào)整及修復甚至重新調(diào)度,要求計劃滿足當前以及后續(xù)的約束要求,并減輕在項目實施過程中突發(fā)因素造成的擾動對項目過程帶來的損害[5-8]。目前,反應性項目調(diào)度方法主要分為完全重新調(diào)度以及修復性調(diào)度。

由于生產(chǎn)活動十分依賴項目調(diào)度計劃,調(diào)度計劃的質(zhì)量要求突發(fā)狀況下對原有計劃進行完全重新調(diào)度,即將未完成的作業(yè)看作一個新的項目按照某些評價指標對他進行新一輪的調(diào)度。如YANG[9]以工期最小化為目標,利用算法進行重新調(diào)度,由于希望新計劃能夠與原有計劃盡量保持一致,盡量少的作業(yè)變動數(shù)量[10]、盡量小的提前/延遲成本[11]都會是反應性項目調(diào)度的目標。SERVRANCKX等[12]創(chuàng)建了多個備份計劃,以應對項目進度中的意外更改,在存在不確定性的情況下,可以在不同的決策時刻在這些替代時間表之間進行切換。蔣淳等[13]提出考慮工人資源的項目型產(chǎn)品裝配作業(yè)調(diào)度模型,以最小項目總工期為目標設計混合算法求解工程案例。盧睿等[14]基于局部搜索算法,以最小化提前/延遲期為目標求解該類問題。由于完全重新調(diào)度耗時較長,而反應性調(diào)度追求快速響應,提高重新調(diào)度的速度使之在管理人員接受程度內(nèi)是其主要的研究方向。

1 問題描述

企業(yè)在制定好項目調(diào)度計劃后,即刻開始投入實施裝配。由于非標自動化設備的特殊性,客戶定制化需求時有變更,因此導致設計上的變更,從而增加該作業(yè)環(huán)節(jié)先前預計的作業(yè)量,延長其作業(yè)周期。此外,企業(yè)眾多非標件由供應商提供,企業(yè)無法對其供應商生產(chǎn)過程進行全程的監(jiān)控,確保其供貨進度與企業(yè)生產(chǎn)活動進度保持一致,供應商突發(fā)的供貨延遲導致后續(xù)作業(yè)環(huán)節(jié)往往由于資源受限無法在規(guī)定時間進行,同理,人力資源也有類似突發(fā)狀況。為應對以上問題,一是對制定的基準調(diào)度計劃進行優(yōu)化,使其擁有一定的抗擾動能力,這里可以理解為提高基準計劃的魯棒性;二是立即對此采取措施,對基準計劃進行修復或重排,即反應性項目調(diào)度。

2 模型建立

(1)參數(shù)。I是計劃期間內(nèi)項目總數(shù),J是單個項目內(nèi)作業(yè)總數(shù),VIJ是計劃期間內(nèi)所有作業(yè)集合,|VIJ|是計劃期間內(nèi)所有作業(yè)總數(shù),M是可選的作業(yè)實施模式數(shù)量,R是項目涉及的資源種數(shù),Fi是各項目的交期,T是整個計劃周期,Eij是作業(yè)ij在各個作業(yè)模式選定后的最早開始時間(ij∈IJ),Lij是作業(yè)ij在各個作業(yè)模式選定后的最晚開始時間(ij∈IJ),dijm是作業(yè)ij在模式m下完工所需時間,Nr是資源r的數(shù)量總額(r∈R),rijm是在模式m下完成作業(yè)ij所需資源r的數(shù)量,Ti是項目i的實際完工時間,Nrt是時間t時對資源r的需求量,Sij是作業(yè)ij開始時間(ij∈IJ),Fij是作業(yè)ij結(jié)束時間(ij∈IJ),mij是作業(yè)ij選用的作業(yè)模式。

由于作業(yè)順序約束的存在,在整個項目調(diào)度周期內(nèi)每一項作業(yè)ij(i=1,2,…,I,j=1,…,J)的緊前作業(yè)集合為Pij,本文將各項作業(yè)開始時間與其所有緊前作業(yè)完成的最晚時間之間的時間差作為各項作業(yè)擁有的時間緩沖,Δij為作業(yè)ij所擁有的時間緩沖:

(1)

設定各項作業(yè)的時間緩沖值與其分配的權(quán)重系數(shù)乘積之和為研究的魯棒系數(shù)從根據(jù)企業(yè)對各個項目長期的歷史記錄,每個項目中各個作業(yè)時間的均值μj以及標準差σj,基于作業(yè)時間標準差σj以及各項項目的權(quán)重ωi為每個作業(yè)定義一個權(quán)重系數(shù)ρij:

(2)

其中,ρij越大,該作業(yè)的變化性越高,其對基準計劃的影響就越大,所以ρij也可以理解為作業(yè)ij上的單位時間緩沖對基準計劃魯棒性的貢獻,而時間緩沖Δij對基準計劃魯棒性的總貢獻即為Δijρij。

在強調(diào)效率的項目調(diào)度計劃實施過程中必不可少需要利用反應性調(diào)度對突發(fā)狀況快速做出響應。事實上,在反應性調(diào)度的實施過程中,各作業(yè)的作業(yè)時間是按照它們之間的邏輯關(guān)系,依次由隨機變量變成確定值的。由于擾動環(huán)境下突發(fā)狀況的影響,在擾動發(fā)生的時刻,原項目調(diào)度計劃內(nèi)的作業(yè),分為3個集合:①在該時刻已經(jīng)完成的作業(yè)集合FT;②正在進行的作業(yè)集合PT;③尚未開始的作業(yè)集合UT,而本文研究的是在突發(fā)擾動的狀況下如何快速調(diào)整PT以及UT集合內(nèi)的作業(yè),調(diào)整原有的基準調(diào)度計劃使之滿足當前的運行要求。

(2)反應性調(diào)度模型。由于是多模式項目調(diào)度問題,作業(yè)的變動不僅考慮其作業(yè)開始時間的延期或提前引起的成本損失,同時也要考慮作業(yè)模式變動引起的成本損失,因此以上兩個成本最小化建立反應性調(diào)度模型,目標為:

(3)

(4)

s.t.

Eij≤Sij≤Lij,?i∈I,j∈J

(5)

Sij≥max(Fij′+dij′m),?i∈I,?(j,j′)∈J×J,?m∈M

(6)

(7)

Nrt

(8)

max(Sij+dijm-1)≤Fi,?i∈I,?j∈J,?m∈M

(9)

zijt=1,Sij≤t≤Sij+dijm-1,?i∈I,?j∈J

(10)

(11)

xijr,yijij′,zijt∈{0,1}

(12)

值得注意的是,在反應性調(diào)度實施過程中,隨著各作業(yè)時間依次由隨機變量變成確定值,基準計劃的調(diào)整可能不止一次。所以,上述反應性調(diào)度模型可能會反復多次地重復調(diào)用。在此需要特別強調(diào)的是,當每次利用上述模型對基準計劃進行調(diào)整后,應將活動的基準開始時間更新為新得到的開始時間,作為計劃下一次調(diào)整時的基準開始時間使用。

3 算法設計及優(yōu)化

為了能達到快速響應的要求,設計雙層嵌套變鄰域搜索算法,上層算法對模式選擇進行優(yōu)化,下層在模式組合已定的情況下對作業(yè)開始時間選擇進行尋優(yōu)。

下層算法在模式組合已定的情況下,先對各個作業(yè)開始時間進行可選范圍的縮小,以此大大減小不可行解出現(xiàn)的概率,這樣可以理解為下層算法在各個作業(yè)開始時間可選的鄰域內(nèi)進行搜索,而作業(yè)模式的可選項已有限制,這樣可以大大提高算法的搜索效率。

為了擴大算法的搜索能力,對變鄰域算法中的關(guān)鍵擾動因子進行設置,算法將擾動因子設計為此次迭代過程中將有n個作業(yè)會進行模式或作業(yè)時間的隨機鄰域選擇,n小于或等于需要重新進行調(diào)度的作業(yè)數(shù)量。通過隨機確定需要進行調(diào)整的作業(yè)數(shù)量,隨機選取作業(yè),再隨機對其作業(yè)模式或作業(yè)開始時間進行調(diào)整以提高算法的搜索能力,其具體的步驟為:

步驟1:參數(shù)初始化,將上層算法迭代計數(shù)器重置為0,隨機生成一個可行解作為初始解;

步驟2:隨機生成需調(diào)整的作業(yè)數(shù)量,按其隨機挑選相應數(shù)量作業(yè)改變作業(yè)模式,計算模式轉(zhuǎn)換成本;

步驟3:將下層算法迭代計數(shù)器重置為0,根據(jù)生成模式組合計算各作業(yè)開始時間選擇區(qū)間;

步驟4:隨機生成需調(diào)整的作業(yè)數(shù)量,按其隨機挑選相應數(shù)量作業(yè)改變作業(yè)開始時間,計算作業(yè)時間變動成本并記錄;

步驟5:判斷下層算法是否滿足迭代終止條件,若不符合跳轉(zhuǎn)步驟3,若符合輸出該模式下最優(yōu)解,結(jié)合模式轉(zhuǎn)換成本與初始解進行對比,若由于初始解則代替初始解跳轉(zhuǎn)步驟2,否則保留初始解跳轉(zhuǎn)步驟2;

步驟6:判斷上層算法是否滿足迭代終止條件,若滿足終止運算。

為了便于理解,圖1為算法流程圖詳細展示其算法流程。為了能滿足算法的收斂性,對下層進行測試得到作業(yè)時間變動成本收斂圖,如圖2所示。

圖1 算法流程圖

圖2 下層算法收斂圖

由此可見下層算法在迭代到100次左右時開始收斂,在滿足算法收斂的同時提高算法運行效率設置下層算法迭代次數(shù)k=200。

設定上層算法迭代次數(shù)IT為100,1000和10 000,子算法層參數(shù)設定為迭代上限k=200。GD表示收斂性評價指標,值越小收斂性越好,SP表示空間的均勻性評價指標。由表1可以看出,迭代次數(shù)和算法運行時間呈倍數(shù)影響趨勢。在低迭代次數(shù)的情況下(IT=100),算法已經(jīng)擁有很好的收斂性,從SP結(jié)果來看,算法的迭代次數(shù)差異并不會對結(jié)果的均勻性產(chǎn)生影響。

表1 上層算法性能對比

故上層算法迭代次數(shù)IT=100,子算法迭代上限k=200,算法在擁有較高的運算性能的同時運算時間極短,滿足生產(chǎn)活動中快速求解要求。

4 實驗分析

實驗以某企業(yè)非標自動化設備項目為背景,即各作業(yè)模式選擇為[2,2,1,2,2,2,1,2,1],開始時間選擇為[0,0,2,3,6,3,10,12,14],設定第7天兩類資源可用量分別縮減為兩個單位,且作業(yè)4在兩種作業(yè)模式下作業(yè)時間分別增加1天,以模擬生產(chǎn)過程中可能發(fā)生的突發(fā)擾動。

利用設計的算法求得最終方案如表2所示,表3和表4分別為各方案的項目甘特圖,圖3為各方案的資源負載情況。

表2 帕累托解集具體方案

表3 方案1項目甘特圖

表4 方案2項目甘特圖

(a) 方案1資源負載情況 (b) 方案2資源負載情況圖3 各方案資源負載情況

以上工作為驗證算法的可行性,為了驗證其(簡稱VNS)優(yōu)越性,選取文獻中出現(xiàn)頻率較高的遺傳算法(GA)、模擬退火算法(SA)、禁忌搜索算法(TS)進行對比,對比結(jié)果如表5所示。由表5及圖4可知,4種算法在求解質(zhì)量上沒有明顯差距,但在運算時間上,本文設計算法擁有明顯優(yōu)勢,相較于遺傳算法(GA)、模擬退火算法(SA)、禁忌搜索算法(TS),其運算速度提升62.9%、46.2%以及55.0%,由此可見本文設計的算法在求解該問題上的優(yōu)越性。

表5 算法結(jié)果性能對比

圖4 算法結(jié)果性能對比

5 結(jié)論

非標自動化設備項目因內(nèi)外環(huán)境頻繁擾動導致其執(zhí)行過程中經(jīng)常面臨快速重調(diào)度的需求,在分析了作業(yè)延期或提前以及模式變更引發(fā)成本損失的基礎上,建立了資源受限的多模式項目反應性調(diào)度模型。為了快速求解獲得項目調(diào)度方案,設計了一種新穎的雙層嵌套變鄰域搜索算法,上下層算法分別對模式選擇和作業(yè)開始時間進行優(yōu)化,同時設計了一種高效的擾動算子,有效提升了算法的搜索效率。最后以某非標自動化設備企業(yè)的實際項目為例,通過與遺傳算法、模擬退火算法和禁忌搜索算法進行了實驗對比,在求解質(zhì)量沒有明顯差距的情況下,所提出的雙層嵌套變鄰域搜索算法在求解效率上分別提升了62.9%、46.2%以及55.0%,實驗結(jié)果驗證了算法的有效性和性能的優(yōu)越性,能夠滿足非標自動化設備企業(yè)的實際生產(chǎn)需求。