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

寶雞文理學院，陜西 寶雞 721016

1 引言

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

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

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

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

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

2 問題模型描述

2.1 問題定義

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

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

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

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

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

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

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

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

PR-策略Π的預期合并成本：

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

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

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

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

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

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

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

這里定義所有可能PR-策略集Π，即PR-策略集可利用S進行構造，對P進行簡化：

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

3 解決方法

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

3.1 狀態(tài)描述

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

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

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

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

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

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

離開不可行狀態(tài)后，決定轉移到可行狀態(tài)。然而，并非所有的轉換都是有效的。當且僅當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)轉換甘特圖

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

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

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

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

然后，最佳決策及其相關的預期成本為：

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

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

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

3.4 基于隨機模型圖的調度優(yōu)化

每個狀態(tài)由一個節(jié)點表示：右側節(jié)點代表可行的狀態(tài)，左側節(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í)行結束時所需的預期成本，對于可行狀態(tài)其等于c1(s,t,O,v)，對于不可行狀態(tài)其等于對于“deadstates”狀態(tài)其等于M。每個狀態(tài)的躍遷可用弧線表示：左側弧線是決定弧，右側弧線是機會弧。在每個機會弧上顯示的數(shù)字是穿越機會弧的概率。在每個決策弧上顯示的數(shù)字要么是基準調度的成本（離開起始節(jié)點的?。?，要么是相關聯(lián)的項目響應的成本（離開除起始節(jié)點以外的任何不可行狀態(tài)的?。?/p>

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

算法1池生成程序

輸入：初始調度的集合sinit。

輸出：S。

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

算法2react(s,pl,t)

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

1.fort=0,1,…,Tdo

2.檢查新的調度信息。

3.if不存在新的調度信息thenst=st-1并跳轉t+1

4.else跳轉過程6。

5.end for

6.forl=1,2,…,Ldo

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

9.end for

4 實驗分析

4.1 算例分析

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

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

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

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

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

Table 2 Scheduling set example表2 調度集示例

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

這個響應過程的成本計算如下：

對于β1中的項目調度實現(xiàn)pl，計算項目之間關聯(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 標準算例實驗驗證

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

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

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

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

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

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

4.3 真實案例實驗驗證

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

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

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

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

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

5 結束語

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

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