帶有GPRs的前攝性資源受限項目調度建模與優化

魏亞鋒，張夢茹，蘇志雄

(南昌工程學院 工商管理學院，江西 南昌 330099)

資源受限項目調度問題(RCPSP)作為一類NP-hard問題一直備受項目管理人員和學者的關注。RCPSP主要研究在資源以及工期約束的情況下，如何合理地安排各個工序間的優先關系以實現預期的目標?，F有的關于RCPSP的研究大多是在確定性環境下進行的[1]，即假設項目中各工序的工期、所需資源等都是確定的。然而，在實際執行過程中，由于受到各種不確定因素的影響，大多數的項目在實施過程中都存在一定程度的不確定性。例如工序工期的延期或中斷、資源可用量的減少或者設備的維修等，都會干擾項目的正常進行，進而造成工序間優先關系以及資源流的變化，導致基準進度計劃的推遲或者中斷。因此，應考慮不確定因素的資源受限項目調度問題[2]，即在滿足項目工期和資源約束的前提下，如何合理安排工序間的優先關系。在項目面對干擾時，生成一個具有較高的魯棒性的調度計劃逐漸成為項目調度領域研究的熱點?，F有的關于RCPSP的研究大多是基于CPM網絡計劃，但是在CPM網絡計劃中，工序間優先關系的表示方式單一，不能很好地描述工序間復雜的關系網絡。廣義優先關系(GPRs)[3]很好的彌補了CPM網絡的這一不足，因此本文選擇以廣義優先關系作為網絡計劃的工具，進一步擴展了工序間優先關系的表示方法。

經過多年的發展，對項目調度問題的研究已經取得了不少研究成果。Herroelen[4]等根據項目所處的階段，在制定項目計劃時將不確定環境下項目調度分為兩種情況，即前攝性項目調度問題和反應性項目調度問題。根據對擾動的處理方法的不同，何正文[5]等將現有的研究分為前攝性調度方法、反應性調度方法以及關鍵鏈方法等。除了對項目調度中的問題的研究之外，王凌[6]等根據不確定資源受限項目調度中存在的大規模、強約束、多目標和不確定性等諸多復雜性，導致模型求解困難的問題，對資源受限項目調度的求解算法進行的深入研究，提出了多種求解算法。

前攝性資源受限項目調度問題是在項目開始之前，在事先考慮各種不確定因素的影響下，在進度計劃中加入一定的緩沖，生成一個具有魯棒性的基準進度計劃，使得項目在面臨干擾時具有一定的穩定性。針對前攝性項目調度方法如今已經有了廣泛的研究和應用，Lambrechts[7]等針對資源可用量問題研究了隨機資源中斷問題的前攝性和反應性調度策略。李雪[8]等考慮了魯棒成本的多模式雙目標問題并設計了相應的前攝性求解模型和算法。馬詠[9]等對具有隨機活動工期和柔性資源約束的前攝性項目調度優化問題進行了研究和求解。蘇志雄[10]等針對在帶有廣義優先關系(簡稱GPRs)的項目中尚缺乏對這兩類時差的分析計算，從多視角研究GPRs下工序共用時差的量化及特性。

在模型求解方面，包含不確定性的RCPSP問題求解主要由精確解算法和啟發式算法組成?；跀祵W模型求解精確解的算法主要以分支定界算法為主，即將解空間用樹形結構劃分為多個子空間，不斷通過各個子空間的最大或最小值來縮小搜索范圍；由于不確定RCPSP問題的解空間隨著項目中工序數量的增加呈指數增長。為了應對大規模問題的求解，除了求解精確解的方法之外采用啟發式規則快速獲得問題的解的啟發式算法在大規模問題上得到了廣泛的應用，其主要包括禁忌搜索算法[11]、蝙蝠算法[12]等，但是啟發式算法只是得到相對的最優解，而不能得到實際意義上的最優解。

當前，國內外對廣義優先關系(GPRs)條件下網絡計劃的研究主要集中在項目調度領域。Neumann[13]等利用分支定界方法對資源受限項目調度問題進行求解。蘇志雄[14]等針對GPRs條件下的時間費用權衡問題，提出了相應的求解方法并對廣義優先關系下的隱性時間、隱性時差和偽時差進行了研究并給出了參數值的正確算法。Wei[15]等對廣義優先關系條件下的離散化時間成本權衡的截止時間問題進行了研究并提出了一種求解大規模復雜問題的有效算法。

本文基于項目調度理論，在廣義優先關系條件下，考慮工期和其他因素的不確定性導致項目在執行過程中偏離基準進度計劃甚至導致項目中斷的問題。為了使基準進度計劃在滿足項目工期約束的前提下具有較高的抵御不確定性干擾的能力，本文在資源和優先關系的約束下，構建了以魯棒性最大化以及項目工期最小化為目標的多目標前攝性資源受限項目調度模型。

1 問題描述

由于各種不確定因素的存在，項目在執行之前，項目管理人員會在考慮各種干擾的情況下，基于工序工期均值E(di)生成一個基準進度計劃。假設一個項目中共有n+2個工序，其中工序0和工序n+1為虛工序，即項目的開始節點和結束節點。項目實施總共需要K種可更新資源，其中第k(k=1，2，…，K)種資源的總供應量為Rk，其中工序i對第k種資源的需求量為qik。由于在項目實際執行過程中各種不確定干擾的存在，可能會導致項目中工序的工期在一定范圍內波動。因此，項目中各工序的工期并不是一個固定值。一般來說，工序i工期用其期望值E(di)來表示，用其標準差δi表示工序i的工期的波動，各工序工期的期望和標準差均是基于該工序的歷史數據求得的。其中工序0和工序n+1工期的均值以及標準差均為0。

在GPRs網絡中，工序間優先關系的表述方式不僅僅局限于“開始—結束”關系類型，GPRs網絡對工序間優先關系的類型進行了進一步的擴展，具體類型如表1所示。

表1 GPRs下工序間優先關系的類型

2 模型構建

由于項目中各資源的總的供應量為Rk，并且虛工序0和n+1分別為項目的開始節點和結束節點，不同于以往文獻中虛工序對于資源需求為零的假定。為了保證項目在各個時期各種資源流動的總量不高于各資源的總供應量，本文假定項目中各資源均從開始節點流出并最終流入結束節點，即虛工序0和n+1對各種可更新資源的需求量為各資源的總供應量Rk，即

(1)

現假定一個項目的基準進度計劃為P=(S，D)，其中S=(s0，…，sn+1)和D=(d0，…，dn+1)分別為各工序計劃開始時間si和工期均值E(di)的集合，其中s0=d0=dn+1=0。然而項目在實際執行過程中，項目中各工序工期的實際值并不一定完全等于期望值。因此，為了使生成的調度計劃具有一定的穩定性，項目管理人員通常會采用加入緩沖的機制來增加基準進度計劃的穩定性。在進度計劃中加入的緩沖機制主要包括資源緩沖[16]和時間緩沖[17]兩種。由于本文主要考慮資源受限情況下，對項目的基準進度計劃的影響，因此本文采用在工序中加入時間緩沖的方法來增加項目基準進度計劃的穩定性。

在GPRs網絡中，項目中各工序的優先關系有多種表示方式，因此，各工序擁有多個時間參數。在考慮項目總工期最小化的前提下，為了增加基準進度計劃的穩定性，本文用工序的計劃最遲開始時間(LSi)減去其計劃開始時間(si)，即在不影響項目預定的總工期的前提下工序i的開始時間最多能推遲的時間表示工序的時間緩沖Δi，其中

Δi=LSi-si.

(2)

項目在實際執行過程中，由于工期的波動或者其他預料之外的因素，會造成工序的實際結束時間偏離基準進度計劃中的結束時間，只要其偏離程度不大于時間緩沖，其后續工序就仍可以按照基準進度計劃正常執行。

(3)

在RCPSP的一般模型中，模型的目標函數為最小化項目的總工期。本文在總工期最小化的目標的基礎上，增加了魯棒性最大化的目標函數，其中項目中各工序的魯棒性指標為robui，用工序的權重因子與該工序的時間緩沖的大小的乘積來表示，即

robui=ξiΔi，

(4)

進而對各個工序的魯棒性的值進行求和得到整個項目的總的魯棒性為

(5)

在上述對問題描述的基礎上，針對本文所提問題構建如下的前攝性資源受限項目調度模型：

(6)

Minsn+1，

(7)

s.t.

sn+1≤LSn+1，

(8)

si+di≤sj+B(1-zij)(1-aij)?i，j∈A∪R，

(9)

LSi+di+B(zij-1)(aij-1)≤LSj?i，j∈A∪R，

(10)

rijk≤B(zij+aij)?i，j∈A?k，

(11)

(12)

(13)

di≥0；rijk≥0；

(14)

zij∈{0，1}

(15)

目標函數(6)為基準進度計劃的總工期最小化；目標函數(7)為基準進度計劃的魯棒性指標最大化，使基準進度計劃具有較高穩定性。約束條件(8)為項目工期的限制，保證基準進度計劃的工期不超過項目的完工期限，其中項目的工期等于虛工序n+1的最遲結束時間；約束條件(9)為工序間優先關系約束；約束條件(10)為各工序的最遲開始時間約束；約束條件(11)為項目中各工序間優先關系以及資源流之間聯系的約束，如果工序i和工序j之間有資源流動則zij=1，若zij=0則工序i和工序j之間的不存在資源流動；約束條件(12)為資源總量約束，保證項目的資源流入量等于項目的資源流出量等于各資源的總的可用量；約束條件(13)為資源流約束，保證各工序上各種資源的總流出量等于總流入量；約束條件(14)～(15)為決策變量的定義域，保證各工序的工期、資源流為非負整數。

本文所提出的模型可以看作為資源受限項目調度問題(RCPSP)，由于資源受限項目調度問題的NP-hard性質[18]，因此，本文所提出的模型必然為NP-hard問題。針對NP-hard問題的求解可以選擇采用獲得精確解的算法或者求得近似解的算法。由于模型中的決策變量為整數和0～1變量，因此本文提出的前攝性資源受限調度模型為整數規劃模型。前攝性調度模型主要用來生成基準進度計劃，基準進度計劃的優劣會對整個項目在實際執行過程中的穩定性產生直接影響。因此，在對前攝性資源受限項目調度模型進行求解時，為了得到模型的最優解，本文采用線性松弛和分支定界算法，在可接受的求解時間內求得基準進度計劃的精確解，然后對其進行可行性修正。

3 算例生成及測試

本文采用分支定界算法對所建立的模型進行求解，但是相比于啟發式算法，分支定界等精確算法一般只適用于小規模問題的求解。為了進一步驗證所建立模型的求解規模以及求解效率，本文首先對前攝性調度模型進行了算例測試。分別對含有不同數目的工序的項目，在可更新資源數目為一種和多種的情況下進行仿真實驗，驗證其在可接受的時間內能夠求解的算例規模的大小，并選取固定的參數對模型進行多次求解實驗，驗證前攝性模型在求解時間方面的穩定性。本文中提出的前攝性調度模型的代碼均采用MATLAB進行編碼，并在計算機上運行求解。

由于所選的測試案例均為隨機生成案例，在隨機生成過程中，需要對資源總量、各工序工期的標準差及期望值等的范圍進行確定，在進行案例測試時，對部分參數設置如表2所示。

表2 案例參數

首先對前攝性調度模型的最大求解規模進行實驗，即在資源類型分別為1、2和4種的情況下，逐步增加項目中所包含工序的數目，在可允許的時間范圍內得出可求解包含的工序的最大數目。在資源類型分別為1、2和4種的情況下，設定求解時間為1 000 s，可求解的最大規模的項目分別為210、200、180。

在得到模型的最大求解規模之后，為了進一步分析前攝性調度模型的穩定性，本文分別選取了包含工序數目為30、60、90的算例進行測試，在資源類型分別為1、2和4種的情況下，對每種情況進行30次求解運算，得到用分支定界算法求解不同組合情況下所需的時間，然后求出求解時間的平均值。實驗結果如表3所示。

表3 求解時間的平均值

從表3可以看出對于含有相同工序的項目，平均求解時間隨可更新資源種類的增加逐漸增大，并且隨著項目中包含工序數目的增加，平均求解時間增加量逐漸增大。對于具有相同種類可更新資源包含不同工序數目的項目，平均求解時間隨工序數目的增加明顯增大。實驗結果符合預期。

為了更加清晰全面地了解仿真實驗的結果，根據表1中“包含工序的數目”和“可更新資源種類”的不同組合，采用分支定界算法分別進行30次實驗，得出結果并繪制出相應的散點圖，如圖1～3所示。圖1(a)～(c)為包含30個工序，資源類型分別為1，2，4種資源的散點圖，圖2(a)～(c)為包含60個工序，資源類型分別為1、2、4種資源的散點圖，圖3(a)～(c)為包含90個工序，資源類型分別為1、2、4種資源的散點圖。

圖1 包含30個工序的散點圖

圖2 包含60個工序的散點圖

圖3 包含90個工序的散點圖

從散點圖可以看出，隨著可更新資源的增加，包含不同工序數量的項目的求解時間都隨之增大。同樣，對于具有相同種類的可更新資源的項目，隨著其包含的工序數目的增加求解時間也隨之增加。但是，對于具有相同工序和相同類型可更新資源的項目，求解時間分布較為均衡，波動起伏較小，穩定性較高。對于只含有30個工序的項目，可更新資源的種類的增加對模型的求解時間的影響并不顯著，但是對于包含90個工序的項目而言，隨著可更新資源種類的增加，模型的求解時間增加較為明顯。

4 結束語

本文通過對帶有廣義優先關系的資源受限項目調度進行分析，在不確定環境下以工期最小化和魯棒性最大化為目標構建了雙目標的前攝性資源受限項目調度模型，考慮到所建立模型的NP-hard性質和前攝性項目調度對進度計劃穩定性要求的性質，選用求解精確解的分支定界算法對模型進行求解。為了驗證所建立模型的有效性和穩定性，分別對模型在可接受時間內的最大求解規模以及針對不同規模的算例的求解的穩定性進行了測試。結果顯示隨著項目中所包含的工序的數目和可更新資源的種類的增加，模型求得精確解所需要的時間隨之增加，但是針對具有相同的工序數目和可更新資源類型的項目，求得精確解所需的時間的波動較小，穩定性較高。此外，隨著項目中所包含工序數目的增加，可更新資源種類的多少對模型求解精確解的時間影響逐漸增大，可更新資源種類的增加會導致大規模項目求解精確解所需的時間增加較為明顯。

本文在建立模型時僅考慮了工期以及魯棒性，并未考慮加入時間緩沖造成的項目成本的增加以及其他不確定因素的干擾，并且模型中模型的時間緩沖的表示方式可能會導致部分工序的時間緩沖有所重疊，造成魯棒性指標偏高。因此，在后續的研究中可以更進一步研究如何合理地表示工序的時間緩沖的大小，使魯棒性指標更加合理。