考慮主/被動資源約束的隨機(jī)MDP項目調(diào)度優(yōu)化*

楊建衛(wèi)，任曉莉，李乃乾

寶雞文理學(xué)院，陜西 寶雞 721016

1 引言

資源約束調(diào)度問題最早于1998年提出，開始于一個海軍合作項目，干船塢是主要的資源約束項。其中空間是在制造業(yè)中普遍存在的資源約束問題，對企業(yè)產(chǎn)能的提升具有制約性，因此研究制造業(yè)中的資源約束問題具有非常重要的工程意義[1]。但是空間資源約束問題的最大難點在于問題處理的不確定性。在以往的研究中，對調(diào)度和項目調(diào)度的研究主要是考慮固定資源容量和確定工期問題。然而，在現(xiàn)實環(huán)境中，只獲取確定性信息是不現(xiàn)實的。因此，不確定性已成為近幾十年來項目調(diào)度的一個不可避免的問題。在過去的幾十年中，很多作者探討了許多處理不確定性項目調(diào)度問題[2]。

第一個研究重點主要是考慮資源受限項目調(diào)度的隨機(jī)項目最小化完工時間的問題。策略是一組決策規(guī)則，它決定特定決策時刻的某些動作，這些是項目執(zhí)行的完成時間。考慮資源受限項目調(diào)度的隨機(jī)項目最小化完工時間問題已經(jīng)提出了很長時間，文獻(xiàn)[3]提出了一種針對考慮資源受限項目調(diào)度的隨機(jī)項目最小化完工時間問題尋找全局最優(yōu)的調(diào)度策略，實現(xiàn)了資源調(diào)度過程的優(yōu)化。文獻(xiàn)[4]提出一種基于資源約束的項目調(diào)度模型，該算法也是基于最小化完工時間的資源約束的項目調(diào)度優(yōu)化過程，其根據(jù)項目調(diào)度過程特點設(shè)計了一種單目標(biāo)形式的項目調(diào)度優(yōu)化方法；文獻(xiàn)[5]基于半正定規(guī)劃建立項目調(diào)度優(yōu)化算法，實現(xiàn)了資源約束的項目調(diào)度完工時間的最小化，這種半正定方法一定程度上可實現(xiàn)項目調(diào)度過程的簡化。總體上，考慮資源受限項目調(diào)度的隨機(jī)項目最小化完工時間的問題的研究成果不多，原因可能是找到這樣一個最優(yōu)策略似乎是難以計算的，因此大多數(shù)作者集中于在預(yù)定義的策略類中找到最優(yōu)或接近最優(yōu)的策略。例如，優(yōu)先級策略類、早期啟動策略類、（線性）預(yù)選策略類、基于活動的策略類和預(yù)處理器策略類。

第二個研究重點是主動和被動的項目調(diào)度問題研究。第一階段是建立時間調(diào)度表，這就是所謂的基準(zhǔn)調(diào)度，對某些類型的不確定性具有最大的魯棒性。第二階段是對正在進(jìn)行的項目計劃中發(fā)生沖突時合理地進(jìn)行重新調(diào)度安排（沖突響應(yīng)）。當(dāng)前已有很多文獻(xiàn)對這個問題進(jìn)行了研究，例如，文獻(xiàn)[6]研究了人員不確定性對于項目調(diào)度問題的影響，并設(shè)計了針對人員不確定性的目標(biāo)優(yōu)化函數(shù)，實現(xiàn)了對項目調(diào)度過程的優(yōu)化分析；文獻(xiàn)[7]提出一種考慮學(xué)習(xí)/遺忘因子的項目調(diào)度優(yōu)化框架，實現(xiàn)了項目調(diào)度優(yōu)化模型的自適應(yīng)學(xué)習(xí)，其本質(zhì)上是一種多目標(biāo)項目調(diào)度優(yōu)化方法。文獻(xiàn)[8]指出即使在單機(jī)環(huán)境下，具有單一沖突和優(yōu)先約束的調(diào)度也是強(qiáng)NP-難的。文獻(xiàn)[9]提出精確的方法來構(gòu)造一個只有一個沖突情況下的魯棒基線時間表解決方案。文獻(xiàn)[10]主要研究目的是尋求理想質(zhì)量和解決方案健壯性之間的權(quán)衡。文獻(xiàn)[11]提出了針對資源流依賴的浮動因子魯棒調(diào)度啟發(fā)式方法等。

上述文獻(xiàn)在研究中存在的主要問題有兩方面：（1）忽略了反應(yīng)性調(diào)度策略的選擇對基線調(diào)度最優(yōu)性的影響。該過程不僅提供了基于仿真的啟發(fā)式解決方案，而且還從一類早期啟動策略中選擇了被動策略，這極大地限制了過程的靈活性。（2）只是簡單地假設(shè)這些項目執(zhí)行響應(yīng)對于基準(zhǔn)調(diào)度以及調(diào)度策略的制定不存在影響。事實上，這種假設(shè)是不準(zhǔn)確的，因此激發(fā)了基線調(diào)度的必要性。

對此，本文提出一種考慮主動/被動資源約束的隨機(jī)圖馬爾可夫決策過程（Markov decision process,MDP）的項目調(diào)度優(yōu)化方法，引入一種新的應(yīng)對沖突的方法，并將主動和被動項目調(diào)度問題作為一個單一的綜合問題來制定，然后利用Markov過程對上述項目調(diào)度優(yōu)化問題進(jìn)行建模。實驗結(jié)果驗證了所提方法的有效性。

2 問題模型描述

2.1 問題定義

首先介紹主動和被動資源約束的項目調(diào)度問題。給出了每個問題實例表達(dá)所需參數(shù)定義[12-13]：

（2）資源約束集合R，在處理時間內(nèi)，每個項目i需要rik單位的資源類型k∈R。資源類型k的資源的可用性可表示為Rk。

2.2 解集的項目執(zhí)行鏈表示

前人的研究一般將主動調(diào)度和被動調(diào)度作為兩個獨立的問題，因此，這兩個問題的解決方案表示也不同。對此，這里提出一種綜合主動和被動資源約束的解決策略（PR-策略）。在PR-策略調(diào)度中，對于每個項目pl，如果該項目執(zhí)行，則其會產(chǎn)生vΠ,i的響應(yīng)序列，該響應(yīng)序列為ΦΠ,l：

只有在項目執(zhí)行結(jié)束時，PR-策略的調(diào)度才知道項目的發(fā)生及其相關(guān)聯(lián)的連鎖反應(yīng)。解集的項目執(zhí)行鏈中，如果存在死路節(jié)點，則稱該項目執(zhí)行鏈為死鏈，引入?yún)?shù)γΠ,l對死鏈情形進(jìn)行區(qū)分，如果ΦΠ,l為項目執(zhí)行的死鏈，則γΠ,l=1，否則γΠ,l=0。對于PR-策略Π的每個項目調(diào)度執(zhí)行順序鏈ΦΠ,l計算其綜合成本費(fèi)用f(Π,l)，形式為：

其中，ωb≥0表示基準(zhǔn)調(diào)度的完成時間成本。ωr≥0是每個項目執(zhí)行響應(yīng)產(chǎn)生的固定成本。ωi,k≥0表示在第k次響應(yīng)中，項目i的啟動時間偏離所造成的單位時間成本增加。M表示項目執(zhí)行鏈路中存在死路的懲罰因子。

成本函數(shù)由三部分組成：（1）從管理的角度來看，基準(zhǔn)調(diào)度過程的成本，是違反最初商定的項目交付時間的成本。（2）序列項目反應(yīng)的成本，其中ωi,k可以看作是項目進(jìn)行重新規(guī)劃的成本。ωi,k可以被認(rèn)為是處理項目響應(yīng)的行政（固定）成本。（3）死鏈所造成的懲罰成本。

參數(shù)ωb、ωr和M可用于確定各部分在合并成本中的權(quán)重份額。PR-策略Π由一組決策規(guī)則描述，也可以由其相關(guān)聯(lián)的一組執(zhí)行順序鏈來描述：

PR-策略Π的預(yù)期合并成本：

類似于執(zhí)行鏈的合并成本，PR-策略Π的預(yù)期合并成本也由三部分組成：基準(zhǔn)調(diào)度過程的成本、序列項目反應(yīng)的成本以及死鏈所造成的懲罰成本。

2.3 優(yōu)化目標(biāo)模型

解集的項目執(zhí)行鏈表示，可將問題表示為相對緊湊的形式。具體可由以下定理進(jìn)行表示：

定理1基于項目執(zhí)行鏈表示的PR-策略規(guī)模是有界的，其上界為，其中mi表示不同項目的離散持續(xù)時間。

證明假定每個PR-策略包含|β|個執(zhí)行順序鏈，這個數(shù)量可能非常大。首先，證明對于PR-策略Π的每個執(zhí)行順序鏈最多具有個響應(yīng)。同時，考慮可以從S中選擇的一個任意的調(diào)度表如果調(diào)度表對于pl是可行的，則PR-策略Π不產(chǎn)生任何的響應(yīng)，執(zhí)行順序鏈ΦΠ,l的大小為1；否則，PR-策略Π在時刻t1上執(zhí)行調(diào)度策略的有關(guān)響應(yīng)。假定存在一個項目i1會導(dǎo)致調(diào)度表對于p′是不可行的，則有：

其中，α(s,p,i)是使得調(diào)度表s對于p是可行的的最大取值。同時，注意到項目i1可能會引起執(zhí)行順序鏈ΦΠ,l的另一個調(diào)度策略不可行，類似的，則可定義：

通過上述定義可得到α(s,pl,i)的不同取值，其中s是任意的調(diào)度方案，最大規(guī)模為mi，由項目i8所造成的不可行項目執(zhí)行鏈的最大數(shù)量及其所需要解決的響應(yīng)數(shù)量等于mi。類似的論點對任何其余項目i∈N{i1}都是成立的，因此可以得到非常直接的結(jié)論，即每個鏈包括最多的響應(yīng)。由此可得，基于項目執(zhí)行鏈表示的PR-策略規(guī)模是有界的，其上界為

這里定義所有可能PR-策略集Π，即PR-策略集可利用S進(jìn)行構(gòu)造，對P進(jìn)行簡化：

式中，P是一個非常難解決的問題，即使對于非常小的實例也是如此。這里將P的求解問題簡化為P1的求解問題，其包含較小的策略集：在上述優(yōu)化模型中，Π1是所有的PR-策略中只包括在S內(nèi)的調(diào)度表。

3 解決方法

問題P可以被建模為馬爾可夫決策過程（MDP）。本文的模型描述如下：（1）給定模型的狀態(tài)描述；（2）引入狀態(tài)之間的轉(zhuǎn)換；（3）遞歸系統(tǒng)描述；（4）通過例子介紹圖表示方法；（5）提出調(diào)度表生成算法。

3.1 狀態(tài)描述

組合(s,t,O,v)表示模型的狀態(tài)，其中s表示當(dāng)前調(diào)度，t是當(dāng)前時刻，O表示在時刻t中正在進(jìn)行的項目集，v表示項目執(zhí)行響應(yīng)總數(shù)。狀態(tài)可被標(biāo)記為可行的或不可行的。令J(s,t)是s中所有應(yīng)該在t時間啟動的項目集合。

定義1（可行與不可行狀態(tài)）如果狀態(tài)(s,t,O,v)可以并行執(zhí)行J(s,t)?O中所有的項目，則稱其為可行的，否則為不可行。

3.2 狀態(tài)轉(zhuǎn)換過程

狀態(tài)轉(zhuǎn)換過程中，進(jìn)入狀態(tài)(s,t,O,v)意味著調(diào)度方案s被認(rèn)為是執(zhí)行的，當(dāng)前時刻是t,O中的項目正在執(zhí)行，沖突次數(shù)為v。取決于是否面臨沖突，也取決于所選擇實現(xiàn)和PR-策略，可進(jìn)入不同狀態(tài)。當(dāng)且僅當(dāng)兩個狀態(tài)之間存在弧線時，兩個狀態(tài)間轉(zhuǎn)換是可能的。如果狀態(tài)(s,t,O,v)是可行的，這意味著沒有沖突發(fā)生，在這個決定時刻不需任何反應(yīng)。

在這種情況下，需要對新狀態(tài)(s,t′,O′,v)進(jìn)行轉(zhuǎn)換，其中，t′是在時刻t之后的s的決策時刻，O′?O?J(s,t)。s之后下一個決策時刻是最小t′＞t，滿足?i∈N，st=t′。集合O′可能取決于項目執(zhí)行過程的不同，在離開可行狀態(tài)時，可以從左側(cè)狀態(tài)進(jìn)入有機(jī)會弧存在狀態(tài)。連接 (s,t,O,v)和 (s,t′,O′,v)機(jī)會弧為：(s,t→t′,O→O′,v)。當(dāng)狀態(tài)轉(zhuǎn)換從 (s,t,O,v)到(s,t′,O′,v)過程中，每個活躍項目O?J(s,t)都具有以下可能中的一種：（1）活躍項目i從時刻t不間斷地持續(xù)到t′，因此存在i∈O?O′；（2）活躍項目i從時刻t開始不間斷執(zhí)行，并在時刻t′前結(jié)束，因此存在i∈OO′；（3）活躍項目i從時刻t啟動，并且不間斷持續(xù)到t′，因此存在i∈J(s,t)?O′；（4）活躍項目i從時刻t啟動，并在時刻t′前結(jié)束，因此存在i∈J(s,t)O′?？衫没钴S概率的乘積計算在某個機(jī)會弧下的躍遷(s,t→t′,O→O′,v)幾率：

離開可行狀態(tài)的機(jī)會弧的概率之和必須等于1。如果O=? 且有J(s,t)={n+1}，則項目的執(zhí)行已經(jīng)完成，沒有機(jī)會弧離開(s,t,O,v)，在此情形下，(s,t,O,v)是終結(jié)狀態(tài)。

離開不可行狀態(tài)后，決定轉(zhuǎn)移到可行狀態(tài)。然而，并非所有的轉(zhuǎn)換都是有效的。當(dāng)且僅當(dāng)U(s,t)=U(s′,t)以及si=si′(i∈NU(s,t))，則在不可行狀態(tài)(s,t,O,v)到可行狀態(tài)(s′,t,O,v+1)之間確實存在一個決策弧。圖1描述了狀態(tài)(s,t,O,v)的甘特圖形式。

Fig.1 State conversion Gantt diagram圖1 狀態(tài)轉(zhuǎn)換甘特圖

圖1中F代表了項目的完成時間，O表示在時刻t啟動的項目，U(s,t)表示在時間t之前沒有開始執(zhí)行的調(diào)度表s中的活動。F和O中項目的開始時間應(yīng)該完全相同，在時刻t從狀態(tài)s到s′的轉(zhuǎn)換意味著管理團(tuán)隊根據(jù)調(diào)度表s′可決定項目是否執(zhí)行，這些轉(zhuǎn)換稱為正常轉(zhuǎn)換。

對于每個不可行狀態(tài)(s,t,O,v)，引入Γ1(s,t,O)代表所有調(diào)度集，均存在可從(s,t,O,v)轉(zhuǎn)換得到的有效狀態(tài)。如果s′∈Γ1(s,t,O),則存在從狀態(tài)(s,t,O,v)到(s′,t,O,v+1)的狀態(tài)轉(zhuǎn)換。集合Γ1(s,t,O)的規(guī)模越大，則調(diào)度過程的響應(yīng)越靈活。如果S是有限集合，則集合Γ1(s,t,O)可能是s、t和O的一些組合的空集。如果狀態(tài)(s,t,O,v)是不可行的，且有Γ1(s,t,O)=? ，則其不存在項目響應(yīng)的可能，可將這種狀態(tài)標(biāo)記為“deadstate”。

3.3 動態(tài)規(guī)劃算法

這里引入d1(s→s′,t,O,v→v+1)作為直到執(zhí)行結(jié)束前決定從狀態(tài)(s,t,O,v)向(s′,t,O,v+1)轉(zhuǎn)換的期望成本。同時，引入c1(s,t,O,v)作為直到執(zhí)行結(jié)束時，離開可行狀態(tài)(s,t,O,v)的預(yù)期成本。首先，計算每個決策弧直到執(zhí)行結(jié)束的預(yù)期成本：

然后，最佳決策及其相關(guān)的預(yù)期成本為：

令F1是所有可行狀態(tài)的集合，I1是所有不可行狀態(tài)的集合。同樣，所有終止?fàn)顟B(tài)“endstates”和“deadstate”分別表示為E1和D1。函數(shù)c1(s,t,O,v)可計算為：

式中，t′是時刻t后做出第一個決策時刻，O′是滿足O′∈O?J(s,t)的任意集合。需要選擇S中調(diào)度表作為基準(zhǔn)調(diào)度表。為此，可在解決模型的過程中使用所提供的信息。基準(zhǔn)調(diào)度表選擇成本是c1(s,0,?,0)+ωbsn+1。因此選取基準(zhǔn)調(diào)度表如下：

很直觀地可以看出式（9）～（13）可實現(xiàn)對P1最優(yōu)化求解，最優(yōu)目標(biāo)值等于令Omax是具有最大時間復(fù)雜度基數(shù)的活躍項目集，則總的狀態(tài)數(shù)量為，離開狀態(tài)的最大弧數(shù)（機(jī)會弧或決策?。┑扔趍ax{n2|Omax|,|S|}。則上述模型算法的計算復(fù)雜度為對比算法中，文獻(xiàn)[14]算法的計算復(fù)雜度為文獻(xiàn)[15]算法的計算復(fù)雜度為，單純從算法計算復(fù)雜度上看，本文算法與文獻(xiàn)[14]和文獻(xiàn)[15]兩種算法處于相同的數(shù)量級上，具體算法執(zhí)行效率情況將在后續(xù)實驗中進(jìn)行驗證。

3.4 基于隨機(jī)模型圖的調(diào)度優(yōu)化

每個狀態(tài)由一個節(jié)點表示：右側(cè)節(jié)點代表可行的狀態(tài)，左側(cè)節(jié)點代表不可行的狀態(tài)，中間節(jié)點代表“deadstates”，見圖2所示。

Fig.2 Graph model representation of state transformation圖2 狀態(tài)變換的圖模型表示

圖2中，每個狀態(tài)(s,t,O,v)上面顯示的數(shù)字表示直到執(zhí)行結(jié)束時所需的預(yù)期成本，對于可行狀態(tài)其等于c1(s,t,O,v)，對于不可行狀態(tài)其等于對于“deadstates”狀態(tài)其等于M。每個狀態(tài)的躍遷可用弧線表示：左側(cè)弧線是決定弧，右側(cè)弧線是機(jī)會弧。在每個機(jī)會弧上顯示的數(shù)字是穿越機(jī)會弧的概率。在每個決策弧上顯示的數(shù)字要么是基準(zhǔn)調(diào)度的成本（離開起始節(jié)點的?。?，要么是相關(guān)聯(lián)的項目響應(yīng)的成本（離開除起始節(jié)點以外的任何不可行狀態(tài)的?。?。

在算法1中提出了基于池生成的項目調(diào)度優(yōu)化程序，其對于給定的一組初始調(diào)度集輸出一組優(yōu)化的調(diào)度集。

算法1池生成程序

輸入：初始調(diào)度的集合sinit。

輸出：S。

在上述程序中，k1是要生成的調(diào)度表的確切數(shù)量。為了降低所提方法的計算復(fù)雜度，將參數(shù)k1限制在k1≤2 000。生成的調(diào)度表的數(shù)量過大會導(dǎo)致算法的計算復(fù)雜度過高，大量的運(yùn)算浪費(fèi)在調(diào)度表的生成和計算過程中，而調(diào)度表的生成數(shù)量過低，會導(dǎo)致算法在調(diào)度精度上出現(xiàn)下降，本文通過實驗發(fā)現(xiàn)k1≤2 000是較為合適的參數(shù)選取方式。池生成程序中所使用的其他子程序為：rndSchedule(S)返回一個從所有已生成的調(diào)度表的集合S中隨機(jī)選擇的方案，rndRealization(β)返回一個隨機(jī)實現(xiàn)。如果調(diào)度方案s在決策時刻t對于實現(xiàn)pl而變?yōu)椴豢尚?，則infeas(s,pl,t)返回true，否則infeas(s,pl,t)返回false。nextDM(s,t)返回調(diào)度表J(s,t)中s時刻后的下一決策時刻。子程序react(s,pl,t)對于決策時刻t的沖突反應(yīng)，是一個強(qiáng)大的并行調(diào)度方案，詳細(xì)計算過程及有關(guān)參數(shù)說明可見文獻(xiàn)[10]所示，具體過程見算法2所示。

算法2react(s,pl,t)

輸入：算法參數(shù)s,pl,t。

1.fort=0,1,…,Tdo

2.檢查新的調(diào)度信息。

3.if不存在新的調(diào)度信息thenst=st-1并跳轉(zhuǎn)t+1

4.else跳轉(zhuǎn)過程6。

5.end for

6.forl=1,2,…,Ldo

8.存儲可使得Δ(s0,st)最小化的調(diào)度策略st

9.end for

4 實驗分析

4.1 算例分析

本節(jié)通過設(shè)定的算例對上述項目調(diào)度優(yōu)化方案的選取過程進(jìn)行描述。圖3描述了項目活動的優(yōu)先關(guān)系和資源需求。每個節(jié)點代表一個項目，每個弧代表一個優(yōu)先關(guān)系，每個節(jié)點上面的數(shù)字顯示該項目的資源需求。

Fig.3 Priority network of sample project圖3 示例項目的優(yōu)先級網(wǎng)絡(luò)

Table 1 Duration distribution of project表1 項目持續(xù)時間分布

考慮上述設(shè)計的PR-策略Π可得如下解集的項目執(zhí)行鏈表示：

式中，β1?β2?β3?β4?β5=β。在上述描述中每個執(zhí)行鏈表示一組相同的鏈。例如，表示與所有實現(xiàn)pl∈β1相關(guān)聯(lián)的鏈集。PR-策略Π選取s9作為基準(zhǔn)調(diào)度策略。如果p1執(zhí)行，則s9將不會變?yōu)椴豢尚?，因此不需要其他的項目?zhí)行響應(yīng)。然而，如果執(zhí)行，s9在時刻2變?yōu)椴豢尚校ㄒ妶D4（a））。PR-策略Π執(zhí)行從s9到s8的轉(zhuǎn)換以解決不可行問題。與之關(guān)聯(lián)的甘特圖如圖4所示。

Table 2 Scheduling set example表2 調(diào)度集示例

Fig.4 Gantt graph representation of association example圖4 關(guān)聯(lián)示例的甘特圖表示

這個響應(yīng)過程的成本計算如下：

對于β1中的項目調(diào)度實現(xiàn)pl，計算項目之間關(guān)聯(lián)鏈的成本如下：f(Π1,l)=40×18=720。對于β1中的項目實現(xiàn)的累計概率等于類似的，可計算：（1）對于pl∈β2，f(Π1,l)=1 773；（2）對于pl∈β3，f(Π1,l)=773；（3）對于pl∈β4，f(Π1,l)=1 835；（4）對于pl∈β5，f(Π2,l)=835。同時可計算：，因此PR-策略Π1的期望混合成本為：

4.2 標(biāo)準(zhǔn)算例實驗驗證

為驗證所提項目調(diào)度優(yōu)化算法的性能，本文選取的實驗對象是PSPLIB數(shù)據(jù)庫，對應(yīng)的問題算例模型的標(biāo)號分別是J11、J13、J15、J17、J19、J21、J31。選取的每組問題算例模型的數(shù)量分別為650個，去除部分不可行算例，則總共選取的模型算例的數(shù)量是3 287個。

選取的仿真軟件是Matlalb2012b，實驗平臺的硬件設(shè)置是：CPU-2300K 2.0 GHz，RAM 4 GB ddr4-2 400 GHz，系統(tǒng)為Win 10旗艦版。表3所示為本文算法獨立執(zhí)行200次進(jìn)化迭代后所得到的計算數(shù)據(jù)與文獻(xiàn)[14-15]兩種算法的計算數(shù)據(jù)對比情況。

表3實驗數(shù)據(jù)中選取收斂精度和計算時間作為評價指標(biāo)，對比本文算法與選取的兩種對比算法的性能優(yōu)勢。根據(jù)表3數(shù)據(jù)可知，本文算法在收斂精度上，偏差大小相對于設(shè)定值的百分比約為0.12%～1.36%之間，而文獻(xiàn)[14]的精度指標(biāo)分布在0.18%～2.25%之間，文獻(xiàn)[15]的精度指標(biāo)分布在0.16%～2.14%之間，本文算法在收斂精度上具有較為明顯的優(yōu)勢。同時，在項目調(diào)度時間上，3種算法相差并不大，本文算法相對略優(yōu)于文獻(xiàn)[14]和文獻(xiàn)[15]兩種對比算法。

圖5給出了選取的項目數(shù)量為30情況下，本文算法、文獻(xiàn)[14]和文獻(xiàn)[15]3種算法的計算甘特圖分布情況。根據(jù)圖5所示3種算法的計算甘特圖分布情況可知，相對于文獻(xiàn)[14]和文獻(xiàn)[15]兩種算法，本文算法得到的項目執(zhí)行甘特圖中，項目的總執(zhí)行時間要顯著優(yōu)于文獻(xiàn)[14]和文獻(xiàn)[15]兩種算法。這體現(xiàn)了本文算法在項目調(diào)度過程中的算法性能優(yōu)勢，其所執(zhí)行的項目調(diào)度的方案更加合理。

Table 3 Comparison of results of example model表3 算例模型結(jié)果對比

Fig.5 Gantt graph distribution of 3 algorithms圖5 3種算法的計算甘特圖分布

4.3 真實案例實驗驗證

本實驗中選取某制造廠的設(shè)備進(jìn)行工序的調(diào)度，該實驗算例中分別含有4臺機(jī)床和零件，相關(guān)的時間參數(shù)情況見表4，設(shè)備運(yùn)行網(wǎng)絡(luò)圖見圖6所示。本實驗中選取的基準(zhǔn)參數(shù)是時間均值，利用本文算法進(jìn)行最優(yōu)方案的調(diào)度設(shè)計，調(diào)度過程中的4臺機(jī)床加工順序是π1=(O11,O13),π2=(O14,O12,O23,O21),π3=(O22,O33,O31)，π4=(O24)?？紤]工件制造過程中的緊前關(guān)系，對所有的工序起止時間進(jìn)行計算。

Table 4 Process,equipment and time estimation for remanufacturing workshop表4 某再制造車間工序、設(shè)備及時間估計

Fig.6 Pre-resource relationship made by workpiece圖6 工件制造的資源緊前關(guān)系

對未進(jìn)行壓縮的100%和壓縮一半的50%的工件制造的工序進(jìn)行計算機(jī)模擬，仿真模擬次數(shù)設(shè)置為900次，實驗結(jié)果見表5。實驗結(jié)果顯示，本文方法在制造廠的設(shè)備工序的調(diào)度上是有效的，能夠降低工件的制造工期。

Table 5 Data table of simulation result表5 仿真結(jié)果數(shù)據(jù)表

5 結(jié)束語

本文提出了一種考慮主動/被動資源約束的隨機(jī)圖MDP的項目調(diào)度優(yōu)化方法，主要創(chuàng)新點如下：（1）引入一種新的應(yīng)對沖突的方法，實現(xiàn)了算法計算效率的提升。（2）將主動和被動項目調(diào)度問題作為一個單一的綜合問題來制定，實現(xiàn)了資源的綜合考慮。（3）設(shè)計了一種基于隨機(jī)圖的動態(tài)規(guī)劃求解方法，對所建立的MDP模型進(jìn)行優(yōu)化。實驗結(jié)果顯示了所提方法的有效性。

在未來的研究中，主要研究方向有：（1）可能會考慮優(yōu)化尋找到具有更低合并成本的解決方案。（2）尋找新的顯性規(guī)則來消除項目不良響應(yīng)的可能性，有助于減少模型所需的計算資源。（3）考慮對持續(xù)時間依賴的項目調(diào)度問題進(jìn)行研究。（4）重點考慮反應(yīng)性調(diào)度策略的選擇對基線調(diào)度最優(yōu)性影響的必要性。