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

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

1 引言

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

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

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

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

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

2 問(wèn)題模型描述

2.1 問(wèn)題定義

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 解決方法

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

3.1 狀態(tài)描述

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

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

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

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

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

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

離開(kā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)之間確實(shí)存在一個(gè)決策弧。圖1描述了狀態(tài)(s,t,O,v)的甘特圖形式。

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

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

對(duì)于每個(gè)不可行狀態(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)度過(guò)程的響應(yīng)越靈活。如果S是有限集合，則集合Γ1(s,t,O)可能是s、t和O的一些組合的空集。如果狀態(tài)(s,t,O,v)是不可行的，且有Γ1(s,t,O)=? ，則其不存在項(xiàng)目響應(yīng)的可能，可將這種狀態(tài)標(biāo)記為“deadstate”。

3.3 動(dòng)態(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)換的期望成本。同時(shí)，引入c1(s,t,O,v)作為直到執(zhí)行結(jié)束時(shí)，離開(kāi)可行狀態(tài)(s,t,O,v)的預(yù)期成本。首先，計(jì)算每個(gè)決策弧直到執(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)可計(jì)算為：

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

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

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

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

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

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

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

算法1池生成程序

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

輸出：S。

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

5.end for

6.forl=1,2,…,Ldo

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

9.end for

4 實(shí)驗(yàn)分析

4.1 算例分析

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

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

Table 1 Duration distribution of project表1 項(xiàng)目持續(xù)時(shí)間分布

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

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

這個(gè)響應(yīng)過(guò)程的成本計(jì)算如下：

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

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

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

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

表3實(shí)驗(yàn)數(shù)據(jù)中選取收斂精度和計(jì)算時(shí)間作為評(píng)價(jià)指標(biāo)，對(duì)比本文算法與選取的兩種對(duì)比算法的性能優(yōu)勢(shì)。根據(jù)表3數(shù)據(jù)可知，本文算法在收斂精度上，偏差大小相對(duì)于設(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)勢(shì)。同時(shí)，在項(xiàng)目調(diào)度時(shí)間上，3種算法相差并不大，本文算法相對(duì)略優(yōu)于文獻(xiàn)[14]和文獻(xiàn)[15]兩種對(duì)比算法。

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

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

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

4.3 真實(shí)案例實(shí)驗(yàn)驗(yàn)證

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

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

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

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

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

5 結(jié)束語(yǔ)

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

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