基于計算實驗的資源受限多項目調度策略優化

李遷，張懷明，丁翔

（南京大學a.工程管理學院；b.政府管理學院，南京 210093）

近年來，“標準化”、“工廠化”、“預制化”等建造模式在工程建設過程中被大力推廣應用，它不僅能夠保證工程質量和進度，也能促使業主與供應商之間建立更加緊密的協作關系。工程業主通過合同方式委托供應商生產工程材料或部件，并要求其按時、按質、按量供貨；供應商針對不同工程業主訂單建立各個不同的項目團隊來組織生產材料或部件，并基于其資源和收益進行多項目資源調度。由于工程建設的不確定性，工程業主為了保證工程進度，往往采取一定激勵策略來鼓勵供應商為其優先安排生產，供應商在考慮不同訂單最晚交貨期及其總體資源約束等情況下，采用內部資源傾斜或外購資源來開展多項目資源調度，實現供應商的整體收益最大化。

資源受限項目調度（RCPSP）問題已經被證明是NP-hard問題[1]。許多研究用來計算該問題的下界，其中一些是基于線性規劃的思想展開的，Carlier等[2]提出了一種高效的工具來解決資源受限項目調度問題，該工具是基于活動執行時間下界來確定完工時間。對于RCPSP問題可以展開若干問題的研究，其中模糊項目調度成本-時間的平衡問題是其中的研究熱點，該問題的研究需要在最小化項目成本與最大化項目縮短時間之間進行平衡。Deblaere等[3]研究了多模式RCPSP 反應調度問題，并提出了一種精確式算法在多模式資源受限項目調度中應用。Leu等[4]研究發現，在資源調度過程中采取“自己完成、承包商完成及合作完成”3種任務模式下活動成本的差異，Chen等[5]指出，活動時間的減少與活動成本的增加這兩者之間存在一定的線性關系，因此，將模糊項目調度的時間-成本平衡問題抽象為模糊線性規劃問題。Ashtiani等[6]針對隨機模糊資源受限項目調度問題提出了一種預處理的調度策略，并結合遺傳算法提出兩階段算法。通過對其進行仿真實驗發現，此種算法對于方差較大的問題明顯優于其他算法。同時，也有學者針對資源調度方案質量開展魯棒性問題研究，它是指調度方案對于在項目執行過程中因不可控制因素而造成的對各種資源需求突然增加的適應能力[7]。Van de Vonder等[8]分析了資源受限調度問題中的質量魯棒性和方案魯棒性之間的平衡關系。另外，也有部分學者針對RCPSP問題中的不同目標進行研究。劉振遠等[9]在資源受限條件下，以活動成本為目標進行工程調度的研究，不僅只局限于傳統的靜態固定成本，還包括項目完工后的持有成本。Elmaghraby[10]提出了多執行模式的概念，每項任務在開始之前要從不同的模式中選擇一種模式開始。劉士新等[11]探討了多執行模式下資源受限工程建設項目調度問題的算法，設計了一種SA/GA 的混合算法，并通過對標準問題的測試取得了良好的效果[11]。

綜上所述，現有關于RCPSP 的研究主要集中在作業任務調度設計、模糊項目調度設計、調度方案的魯棒性以及資源受限項目調度算法設計等，缺乏基于工程項目多利益干系人之間交互行為對資源調度影響的研究。因此，本文將工程業主激勵機制引入到供應商資源決策模型中，建立相應的資源受限多項目調度模型，通過分析工程業主、供應商以及供應商項目團隊等主體之間的動態交互規則，研究不同情景下的工程業主激勵策略對供應商資源調度方案的影響。

1 資源受限多項目調度模型設計

1.1 模型說明

假設某供應商同時有來自M個獨立工程項目的訂單同時開始生產，這M個項目使用供應商的共享資源R，各自的資源約束分別為（R1，R2，…，Rm），工期約束為（D1，D2，…，Dm）。這M個項目中每個項目內部有N個任務，這N個任務之間滿足緊前活動關系，每個項目內部的N個活動之間不存在資源方面的約束。假設M個工程業主中的某一業主實施了激勵措施，在沒有實施激勵前，供應商對該項目的投入成本為Ci，項目執行工期為Di，供應商項目團隊得到的收益為，工程業主根據負責其項目生產的供應商項目團隊努力水平α、投入S來進行項目激勵，供應商根據激勵S可以采取3種行為：①完全購買額外的市場資源進行補充；②通過傾斜內部資源優先分配給實施激勵的項目；③購買外部資源和傾斜內部資源的策略共同使用。本文建立此情景下的數學模型：

式（1）表示當某工程業主實施激勵措施后新的所有項目工期目標；式（2）表示實施激勵后供應商的總收益最大化，ρ為購買額外資源的比例；式（3）表示當某項目實施激勵后，其項目工期最小化；式（4）表示供應商通過完全傾斜內部資源來滿足某個激勵項目時的資源約束，其中，rij為供應商多個項目在實施過程中對某一資源的實際需求量，Ri為供應商擁有某一資源的數量，QRi為供應商對實施激勵項目進行的資源傾斜，SRi/Ci為工程業主通過實施S激勵所對應增加的供應商額外資源；式（5）表示供應商通過完全購買外部資源來滿足某個激勵項目時的資源約束；式（6）表示供應商通過購買外部資源和傾斜內部資源結合使用的方式來滿足某個激勵項目的資源約束條件；式（7）表示通過實施激勵后，供應商新的資源約束條件；式（8）表示新的某項目任務時間變化；式（9）中，Δtij為通過增加額外資源投入，某項目任務所減少的時間；式（10）表示某項目工期約束。

1.2 主體動態目標

1.2.1供應商Agent設計 供應商在制定多項目調度決策時一般分為兩個階段進行：第1階段，根據供應商內部資源的狀態以及多個項目的工期資源約束情況，計算調度方案集合；然后，根據供應商的最小工期目標進行調度方案的篩選，選擇出最符合執行的調度方案，交由供應商項目團隊負責執行。第2階段，在項目執行過程中或制定調度方案開始前，供應商分析工程業主對某一具體項目實施激勵方案，并對其激勵方案進行評估（包括激勵強度和新的工期約束）。

供應商根據激勵方案，優先通過對內部資源的調度來滿足激勵方案的約束，工程業主激勵S可以直接轉化為供應商的收益。這種行為不會增加供應商總的資源數量，但其會對其他項目的資源配置及工期產生直接影響，因此，供應商對于是否接受工程業主的激勵措施，需要進行嚴格計算；如果通過購買部分或全部S的外部資源來滿足激勵項目的工期要求，則該行為會導致供應商的資源總量變大，對其他項目產生間接影響。同時，此種方式下供應商的收益會減少，供應商在進行決策時需要對如下兩方面進行綜合考量：

（1）完全通過內部資源調配滿足激勵要求。供應商收益和供應商資源總量分別為：

（2）通過購買一定量的外部資源滿足激勵要求。供應商新收益和供應商資源總量分別為：

1.2.2工程業主Agent設計 工程業主通過對激勵措施來加快項目生產進度，并根據激勵措施實施前后的項目進度以及供應商資源投入情況的比較分析，來決定是否在項目實施的某一階段開展激勵，如果工程業主通過評估認為激勵措施取得了預期效果，則其在下一階段實施激勵的概率就會增大；反之，工程業主在下一階段會降低激勵實施的概率或停止進行激勵措施。工程業主通過供應商項目團隊的努力水平這一觀測指標對項目激勵的效果進行評估。

工程業主在項目執行過程中的某階段實施S激勵，供應商根據激勵增加資源。根據上文假設，當供應商在某個項目的i階段上增加的資源，該階段的工期

因此，工程業主在進行評估時主要依據f（ri）（供應商實際再投入資源與業主給予激勵后所期望資源傾斜的差值）、g（ri）（激勵后期望工期與實際工期差值）進行決策，通過分析f（ri）、g（ri），可得供應商項目團隊的實際努力水平與工程業主對其預期努力水平αi之間的關系，如表1所示。

表1 努力水平關系表

1.2.3供應商項目團隊Agent設計 供應商項目團隊是連接工程業主和供應商之間的橋梁，其在進行多項目之間的調度問題上具有關鍵作用。供應商項目團隊在決策過程中主要分為兩個階段：第1階段，針對自己所負責的項目，進行細致地分析和研究，將具體項目任務的工期以及所需要的資源情況上報給供應商，供應商根據所有項目的情況，進行資源統一分配；第2階段，在項目實施過程中盡可能地付出努力水平α（期望努力水平），如果工程業主在項目Q階段對其實施S的激勵，供應商項目團隊要將新的項目工期約束、所需要傾斜的資源數量以及所需要購買資源的情況報告供應商。供應商項目團隊在項目執行過程中不斷修正自身的努力水平，從而使得α與（實際水平）盡量保持一致。

1.3 主體交互規則

在供應商與工程業主之間的交互中，工程業主通過觀測供應商項目團隊對于項目的進展情況以及外部環境變化對產品生產提出新的要求，決定是否實施激勵措施。當工程業主決定實施激勵措施時，根據觀測到供應商項目團隊的努力水平制定S的激勵。供應商根據其項目團隊提供的項目資源約束，在所有項目之間進行資源調度。同時，當供應商決定接受激勵方案時，其項目團隊需要向供應商提供所需傾斜資源的額度來確保激勵項目的實施。因此，供應商項目團隊不僅是項目的執行者，更是供應商和工程業主之間信息傳遞的紐帶。同時，供應商和工程業主需要根據供應商項目團隊的數據進行正確的決策。供應商與工程業主之間的信息交互模式如圖1所示。

圖1 工程業主、供應商與項目團隊主體交互規則

具本規則：

（1）工程業主根據項目具體情況，向供應商提供一定的激勵措施來加快項目工期。

（2）供應商項目團隊根據工程業主提出的激勵機制，進行評估工期和資源約束情況，并反饋給其所在的供應商，制定相應的方案。

（3）供應商根據其項目團隊提出的方案，決定資源配置模式（傾斜內部資源或購買外部資源）。

（4）供應商根據其項目團隊的執行情況以及工程業主的激勵情況，進行激勵績效的評估，并根據評估結果決定下一階段的策略。

（5）供應商項目團隊根據其供應商績效評估的結果，調整自身的努力水平。

（6）工程業主根據供應商項目團隊在激勵機制下的努力表現水平，決定下一階段的激勵策略。

（7）重復（1）～（6），直到工程業主、供應商項目團隊的努力水平以及供應商的績效評估達到資源調度的動態平衡狀態。

2 實驗案例與結果分析

2.1 實驗案例

某供應商同時承接了5個工程項目訂單，由于這5個項目都屬于同一類型，每個項目劃分為10個階段來完成，當項目執行過程中沒有異常干擾時，可以得到這5 個項目中每個階段關鍵資源使用情況以及階段工期。同一項目在不同階段的關鍵資源不同，但是不同項目處于同一階段時所使用的資源相同，供應商將項目分別交給5 個項目團隊負責。表2 項目（a，b，c，d）中，a、b、c表示某個階段需要的3類資源數量，d表示此階段所需要的工期。5個項目的具體工期約束為：項目1工期約束70天、項目2～5的工期約束為100天，針對上述5個項目，供應商在每個階段的總資源約束情況如表2所示。

表2 項目不同階段的資源使用、工期及供應商資源約束

2.2 計算實驗算法設計

在項目工期計算過程中，主要是通過改進優化對齊技術算法，按照資源和工期約束的具體情況，進行動態設計，具體步驟如下：

（1）確定每一個項目的資源約束因子

每一個項目的工期約束因子

綜合約束因子λi=αηi+βξi，α、β為工期和資源的平衡關系；

（2）設定算法循環n次停止；

（3）根據綜合約束因子排序，在滿足初始資源約束的條件下，產生初始解，生成集合A1；

（4）計算在步驟（1）初始解產生后，檢查系統資源池的數據，根據最小資源約束性，生產集合E1；

（5）A1集合完成某個項目后，釋放可用資源進入資源池，資源池更新，同時產生集合F1，并更新A1變為A2，更新E1為E2；

（6）檢查Ei集合中的各個項目，是否達到最遲項目工期，若達到最遲項目工期，則進行逆向調度；否則，繼續進行正向調度；

（7）檢查Ei、Ai是否為空集；

（8）若為空集，則輸出集合Fi，產生一種可行解，并計算此解下目標函數；若為非空，則返回（4）進行循環；

（9）隨機產生初始解，返回（3）進行循環；

（10）輸出n次計算結果，并從中得到最優解。

2.3 實驗結果及分析

2.3.1初始最優調度方案根據項目的工期及

資源約束，通過對齊技術來計算多項目的資源調度，得到119種調度方案。根據工期最小化原則，本文初始最優調度方案如表3所示。

表3 初始最優調度方案

在最優調度方案的基礎上，計算工程業主激勵策略以及供應商資源分配策略。根據供應商項目團隊的努力水平，通過對兩種情景模式進行實驗設計，分析這兩種情景模式下工程業主激勵策略對資源調度方案的影響，以及供應商采取不同資源分配方式下對項目調度安排的影響。

2.3.2情景1：努力水平一致下的激勵實施效果情景假設：供應商項目團隊在激勵措施下的努力水平與未接受激勵措施的努力水平一致，即αi，供應商通過傾斜內部資源的方式來滿足激勵的要求。圖2（a）～（f）分別表示當有1～5個項目進行激勵時，項目工期變化情況以及供應商收益隨著激勵實施的變化情況。

由圖2可知，當只有一個或兩個項目實施激勵時，供應商能夠通過內部資源重新配置來滿足工程業主的激勵要求，項目工期大幅縮短，同時滿足其他工期的約束要求，供應商的收益有很大的提升；但是當有3個以上項目同時采取激勵措施時，此時被激勵項目的工期沒有明顯得到縮短，供應商的收益情況趨向于穩定。這說明，此時供應商通過內部資源調控手段使得資源利用率達到最大化。由此可見，當供應商在進行內部資源重新配置過程中，不同項目之間實施激勵策略的順序顯著影響激勵效果，并且存在一個資源瓶頸點，使得激勵措施的效果明顯減弱。在此情況下，供應商可以不再接受其他工程業主的激勵方案。

2.3.3情景2：努力水平不一致下的激勵實施效果情景假設：供應商項目團隊在工程業主激勵機制下的努力水平與未接受激勵的努力水平不一致，當工程業主在實施激勵策略時，供應商項目團隊的努力水平、工期及供應商收益也會不斷發生變化。根據前文分析可知，當有一個或兩個項目進行激勵時，供應商通過傾斜內部資源的方式能夠達到激勵約束的要求，在這種背景下，本文研究當努力水平不一致時，工程業主實施激勵的效果。假設工程業主有4種激勵方案，如表4所示的修正系數x/y，當項目團隊實際努力水平小于正常期望的努力水平a時，給予其·y激勵；反之，則給予·x。

通過對不同修正系數進行實驗分析，圖3、4分別所示為在不同修正系數下，項目1的工期及供應商的收益變化情況。當修正系數組合為0.7/1.3時，修正曲線與期望努力水平下的曲線重合度最高；當修正系數組合為0.9/1.1時，項目工期縮短情況最明顯，但此情景下供應商激勵收益最小。因此，當工程業主實施項目激勵時，供應商需要平衡好項目工期最小化和收益最大化這兩者關系，相應地，工程業主要根據供應商收益變化來制定最佳的修正系數組合。

圖5、6模擬了工程業主在進行連續激勵時，多個項目的工期變化及供應商收益變化的情況，當供應商接受兩個項目同時進行激勵時，供應商的總收益最大；當供應商同時接受5個項目進行激勵時，因為通過外部資源采購而使得供應商資源總量最大，但是總收益卻明顯減少。在5個項目同時進行激勵的過程中，當激勵發生在第8階段時，此時供應商收益達到最大。因此，供應商通過控制實施激勵項目的數量與激勵實施過程的節點，能夠使得自身收益最大化。

圖2 項目工期及激勵實施變化情況示意圖

表4 激勵實施下的努力水平變化表

圖3 一個項目動態激勵工期變化

圖4 一個項目動態激勵供應商收益變化

圖5 外部資源采購下項目工期變化

圖6 外部資源采購下供應商收益變化

3 結語

工程項目“標準化”和“裝配化”的實施過程是由工程業主、供應商以及供應商項目團隊三方共同完成的，不同主體的利益訴求存在差異。工程業主主要目標是交付的材料或部件質量高和工期短；供應商主要目標是在成本最小的前提下，其收益最大；供應商項目團隊主要目標是在最小努力水平下收益最大。本文將激勵機制引入到對資源受限調度問題的研究中，構建了多項目調度模型；基于計算實驗理論設計了工程業主、供應商和供應商項目團隊的主體屬性及相互之間的交互規則。通過對實驗數據的計算，分析了工程業主提供激勵措施下，供應商項目團隊努力水平“一致”及“不一致”兩種情景下，供應商資源配置方式、項目工期以及供應商收益等變化情況，這為工程業主設計有效激勵措施以及供應商的資源調度方案決策提供如下參考意見：

（1）供應商在制定資源調度方案時，需要對多個項目進行評估：①需要評估工程業主對項目的重視程度，這一點關系到工程業主在項目執行過程中實施激勵機制的可能性；②需要評估工程業主對項目所制定的標準，項目標準直接關系到供應商對選擇項目資源種類以及數量等方面的決策。

（2）工程業主在實施激勵之后，對于激勵績效的評估需要考慮兩方面：①項目工期是否縮短；②供應商項目團隊在項目實施過程中努力程度是否保持一致。因此，工程業主在進行項目控制過程中需要將結果控制和過程控制相結合，如定期開展考核及派駐專業人員到供應商現場監督項目團隊執行。

（3）供應商項目團隊作為供應商中實施項目的主體，在進行實施項目之前需要進行如下評估：①根據項目工期、項目實施標準等情況，結合過往項目實施經歷，制定合理的努力水平值，確保能夠滿足項目的工期約束；②供應商項目團隊在接受工程業主激勵方案后，需保持其努力水平與工程業主的激勵策略一致，確保項目團隊在努力水平值最小的條件下獲得較高的激勵收益。