活動執(zhí)行時間可提前的多模式反應性項目調(diào)度優(yōu)化

曹芳芳, 何正文, 王能民

(西安交通大學 管理學院,陜西 西安 710049; 過程控制與效率工程教育部重點實驗室(西安交通大學),陜西 西安 710049)

0 引言

受不確定因素的干擾，如天氣變化、原材料到達延期、合同期限變更等，項目的實際進度往往不能按照基準計劃準確執(zhí)行[1,2]，此時，需要對受影響的活動進行局部修復或重調(diào)度，以確保項目的順利實施，該過程稱為反應性項目調(diào)度[1]。反應性項目調(diào)度發(fā)生在項目執(zhí)行中，通過對執(zhí)行中斷修復從而彌補了前攝性項目調(diào)度對不確定性的預判不足。

實際中，由于必需的原材料延遲送達、與分包商簽訂的固定協(xié)議或活動提早啟動會對后續(xù)活動造成無法估量的損失等，使得活動不得早于基準時間啟動，該調(diào)整規(guī)則稱為“鐵路調(diào)度(Railway Scheduling)”[3]。然而，在實際的某些情況下，該執(zhí)行規(guī)則對開始時間的約束使其并不能適用于所有項目。與之相反的另外一種規(guī)則為“接力賽調(diào)度(Roadrunner scheduling)”，要求執(zhí)行中活動只要滿足執(zhí)行的資源需求，可在其緊前活動結束后盡早啟動[4]。對于該類項目，活動提前啟動不僅不會對其后續(xù)活動造成較大影響，甚至可為后續(xù)不確定性較高的活動留出更多的時間緩沖；尤其對于關鍵鏈上的活動，在資源可用時應盡早啟動，提高資源利用率的同時也保證了項目的按期交付或不至于延期太久，并可避免為了加速某些活動而投入額外費用[5]；另外，在項目執(zhí)行中可以根據(jù)資源實際情況適時安排活動，減小因嚴苛的基準時間約束而帶來過多的資源調(diào)配成本；因此，反應性調(diào)整過程中允許活動提早啟動，利用緊前活動提前完成的優(yōu)勢加快項目進度，某種程度上降低后續(xù)活動與基準計劃的偏差。

綜上，圍繞隨機工期引起的中斷，研究活動開始時間可提前的多模式反應性項目調(diào)度優(yōu)化問題。論文后續(xù)，首先綜述相關文獻；其次構建優(yōu)化模型；隨后設計啟發(fā)式算法；并通過一個案例說明；最后得出結論。

1 文獻綜述

不確定型項目調(diào)度已成為項目調(diào)度領域的一個重要研究方向。Herroelen和Leus[1]針對該研究問題提出了五種方法，其中反應性調(diào)度由于其重要的現(xiàn)實意義引起眾多研究者的關注。Zhu等[6]將引起中斷的不確定因素分為網(wǎng)絡結構、活動及資源三類，其中針對不確定活動工期與資源可用量的研究較為普遍。

早期，Van de Vonder等[7]比較了隨機工期下的多種反應性啟發(fā)式算法。Haruhiko和Daisuke[8]引入“計劃進度水平”指標來評估反應性計劃的進展程度。Long和Ohsato[9]提出模糊關鍵鏈反應性調(diào)度方法，允許活動盡早啟動，但因關注緩沖滲透水平及進度的控制，而忽略了活動開始時間的穩(wěn)定性。盧睿和林瑛[10]設計基于迭代局部搜索算法來求解隨機工期下的加權提前-拖期懲罰反應性問題。任世科等[11]在應急救援反應性研究中允許實際時間提前，將其表示為減少的相應損失。Van de Vonder等[12]針對隨機工期反應性中斷對比了現(xiàn)有的前攝性與反應性調(diào)度算法。Lambrechts等[13]對資源中斷的單模式反應性問題設計了多種前攝性及反應性策略。張沙清等[14]研究多項目反應性問題設計了基于優(yōu)化資源流約束的算法；隨后又提出多項目預測-反應性調(diào)度算法[15]。Dhib等[16]研究多技能反應性調(diào)度問題。Chakrabortty等[17]設計了兩種離散時間模型來處理資源中斷反應性問題。Chand等[18]針對資源動態(tài)變化提出了多目標超啟發(fā)式方法來解決“搶占-重復”與“搶占-繼續(xù)”兩類反應性中斷問題。

以上針對不同中斷類型提出了多種反應性策略，但集中于單模式情形，當活動具有多種模式時，增加反應性問題的復雜性[19]。例如Deblaere等[20]研究工期及資源隨機下的多模式反應性調(diào)度問題，基于“鐵路調(diào)度”設計精確和啟發(fā)式算法。王艷婷等[21]研究隨機工期中斷的多模式前攝性與反應性權衡問題。李佳媛等[22]研究資源可用量不確定的多模式反應性項目調(diào)度問題。Chakrabortty等[23]設計了兩種多模式反應性恢復方案來解決單個或一系列資源中斷問題。

上述反應性研究大多集中于單模式，且研究問題大多基于“鐵路調(diào)度”規(guī)則。而本文基于不同的現(xiàn)實情形，允許活動提前啟動。據(jù)此，研究不確定工期下活動開始時間可提前的多模式反應性項目調(diào)度優(yōu)化問題。

2 問題界定及模型構建

(1)

(5)

上述，式(1)最小化反應性總成本；式(2)將T時刻已開始活動的執(zhí)行模式與開始時間初始化為基準計劃對應值；式(3)為優(yōu)先關系約束；式(4)任何執(zhí)行時刻t正在進行活動Pt對可更新資源的需求總量不超過資源可用量；式(5)為決策變量的取值約束。上述，將已完成與正在進行的活動的開始時間及模式設置為與基準值；對UT的活動，可通過提前基準時間啟動，來減小后續(xù)活動的開始時間偏差；另外通過選擇合理的模式組合，達到降低更多開始時間偏差成本的目的。

需注意，項目實際中會發(fā)生多次中斷，每次均會調(diào)用上述模型，并將新生成的ST賦值于基準進度計劃SB，以供下次中斷時調(diào)用。

3 禁忌搜索啟發(fā)式算法設計

本文研究問題為多模式資源約束反應性項目調(diào)度向活動工期不確定情況的擴展，屬于NP-hard[24]，選用禁忌搜索算法(TS)進行求解，且該算法已被眾多學者采用[11,13,20～22]。

3.1 解的表示與解碼

解的表示使用活動次序列表AL，模式轉換列表ML和時間裕量列表SL來表示。

AL:列表{l1,l2,…,ln}定義n個實活動的優(yōu)先次序，li為活動i對應的位置，決定活動i在反應性進度計劃中的優(yōu)先次序。

ML：列表{m1,m2,…,mn}定義了n個活動的執(zhí)行模式，mi為活動i執(zhí)行模式。

SL：{b1,b2,…,bn}定義了n個活動的時間裕量。bi為活動i開始時間之前添加的時間裕量，確保算法搜索能夠覆蓋整個解空間。

編碼及解碼過程用圖1示例項目說明。示例項目包含7個活動，其中0和6是虛活動。有一種可更新資源，其可用量R1=3。模式數(shù)據(jù)標注在圖中。圖2是三個編碼列表，例如AL中l(wèi)3=5，表示活動3在計劃安排中的優(yōu)先次序為第5；ML中m4=2，表示活動4按照模式2執(zhí)行；SL中的b3=1，表示在活動3前有1個單位時間裕量；最終，通過SSGS解碼得到進度計劃為SB=(0,0,0,4,2,4,7)。

圖1 示例項目AoN網(wǎng)絡圖

圖2 示例項目編碼列表

3.2 初始解構造

禁忌搜索初始解(AL0,ML0,SL0)構造如下：

AL0:在滿足優(yōu)先關系的前提下按照wi降序排列，已開始的活動的優(yōu)先次序不變。

ML0:i(i∈UT)為隨機選擇一種執(zhí)行模式。

SL0:將活動i(i∈UT)的時間裕量設置為0。

3.3 鄰點生成機理

當前解(AL1,ML1,SL1)的鄰點解(AL2,ML2,SL2)由以下三個算子隨機生成：

活動位置交換算子(AO)：不違背優(yōu)先關系條件下，在UT中隨機選擇兩個活動并交換位置，得到AL2；令ML2:=ML1，SL2:=SL1。

執(zhí)行模式改變算子(MO)：隨機選擇一個活動，改變其模式，得到ML2；令AL2:=AL1，SL2:=SL1。

開始時間裕量算子(SO)：隨機選擇一個活動i(i∈UT)，保證bi≥0，隨機變化一個單位，得到SL2；令AL2:=AL1，ML2:=ML1。

三個算子的的移動定義如下：

AO移動：(i,li)及(j,lj)表示兩個需交換位置的活動的移動，其中l(wèi)i、lj為兩個活動(i,j)交換前對應的位置，將二者加入禁忌列表。

3.4 禁忌列表及終止規(guī)則

禁忌搜索算法定義三個禁忌列表TLA，TLM和TLS，分別對應編碼列表。禁忌列表的禁忌對象分別為3.3節(jié)中三個算子逆向移動。

禁忌列表應用“First-in-First-out”規(guī)則；每次從該列表底部將鄰點解的逆向移動加入；因此，當禁忌列表排滿時，最早從底部進入的元素將從列表頂部被移出。該列表中的元素在生成鄰點時不允許使用，但當某元素對應的目標值最優(yōu)時，禁忌激活，移出列表。禁忌列表長度通過實驗法獲得。當搜索次數(shù)達到上限時算法結束，并輸出當前最好解。

3.5 算法搜索步驟

步驟1輸入(AL0,ML0,SL0)及對應的LOSS0；清空禁忌列表TLA,TLM,TLS；算法迭代上限Nmax；令迭代次數(shù)iter=0；解的初始化。

步驟2隨機選擇一個算子，生成鄰點(AL2,ML2,SL2)，計算LOSS2，判斷該鄰點的逆向移動是否在對應的禁忌列表TLA、TLM或TLS中，若在，則轉步驟4；否則轉至步驟3。

步驟3令(AL1,ML1,SL1):=(AL2,ML2,SL2)，LOSS1:=LOSS2；令iter:=iter+1；更新禁忌列表。若LOSS2

步驟4若LOSS2

步驟5若iter≥Nmax，到步驟6；否則轉步驟2。

步驟6輸出(AL*,ML*,SL*)和LOSS*。

圖3 TS算法偽代碼

4 案例分析

4.1 項目背景及數(shù)據(jù)提煉

FZDJ項目是XH有限公司的一個加工項目，項目歷時30天。圖4為該項目的AoN網(wǎng)絡圖，包含34個活動，其中活動0和33是虛活動。該項目單位時間內(nèi)可安排的熱工6人、銑工6人及其他工種8人。項目相關數(shù)據(jù)見表1。

表1 FZDJ項目不同模式下工期均值、標準差、資源需求及模式轉換成本

項目基準計劃SB=(0,0,8,18,22,45,22,22,26,22,30,30,39,78,91,96,124,22,25,82,43,45,91,52,53,78,99,141,169,58,187,194,200,201)，初始模式為1?；顒訉嶋H工期為(0,8,10,4,16,5,8,8,6,4,27,12,7,8,12,40,35,6,21,14,8,8,15,12,20,10,5,35,38,39,7,6,1,0)，實際進度計劃為(0,0,8,18,22,45,22,22,26,22,30,30,49,78,91,103,143,22,28,97,43,45,111,52,53,78,126,178,201,58,225,232,238,239)。實際執(zhí)行239小時，約30天，超計劃5天，總損失22930元，其中模式調(diào)整成本1000元，開始時間偏離成本21930元。

圖4 FZDJ項目AoN網(wǎng)絡圖

4.2 求解結果討論

4.2.1 滿意解與實際結果對比

求解得到FZDJ項目反應性調(diào)整具體過程見表2。第1次到第7次反應性調(diào)整中，與基準時間不同的活動數(shù)量為8、4、2、1、1、1、1，開始時間偏差成本也從最初的2270元降低至80元，開始時間變化的活動數(shù)目及反應性成本均減小，但由于開始時間偏差權重及工期變化程差異，反應性成本會局部增大，比如第6、7次調(diào)整較前幾次增大；同時項目的完工時間卻維持不變，這是由于前7次調(diào)整使得工期變化帶來的影響控制在一定范圍之內(nèi)。但第8次調(diào)整的活動數(shù)目較多，是由于優(yōu)先關系中靠后的活動28的工期變化較大，使得后續(xù)活動均偏離基準時間，引起調(diào)整成本較高。另外，提前啟動的活動為5、13、14、19，23，24，25，其中活動5、13提前啟動是由于其后續(xù)活動14、15、16實際工期增大；活動14提前是由于該活動本身及后續(xù)活動15、16實際工期增大；活動19、21提前是因其緊后活動22實際工期增大；活動23，24，25提前是因其后續(xù)活動27、28實際工期增大；正是對活動的適時提前啟動，使得后續(xù)活動的時間偏差量減小，從而降低項目反應性總成本。

述調(diào)整中模式改變的活動有：T=58，活動14、25的模式轉換為2；T=91，活動15的模式轉換為2，T=103，活動16的模式轉換為2；T=141，活動27的模式轉換為2；T=169，活動28的模式轉換為2，上述活動因?qū)嶋H工期增大幅度較大，導致實際開始時間延后且對后續(xù)活動造成影響，因此通過轉換模式可降低與基準時間偏差，也減小了對后續(xù)活動影響。

不進行模式調(diào)整得到的進度為(0,0,8,18,22,38,22,22,26,22,30,30,39,71,84,101,148,22,25,48,43,42,89,50,51,71,104,113,183,62,201,208,214,215)，反應性成本為13190元，較模式轉換后的損失增大2800元。雖模式調(diào)整引起2100元的成本，但卻降低開始時間偏差成本4900元，因此模式調(diào)整是有效的。

表2 FZDJ項目的反應性調(diào)整結果

從滿意解與實際情況對比發(fā)現(xiàn)，滿意解總工期比實際提前28小時；反應性總損失比實際減少12540元；實際執(zhí)行通過“右移”規(guī)則處理中斷，而本文通過提前活動時間及模式調(diào)整，減小了總成本，并縮短了項目總工期。

4.2.2 滿意解與開始時間不可提前結果對比

為了進一步驗證優(yōu)化模型的有效性，將滿意解與活動時間不可提前結果比較(表3)。

表3 活動開始時間可提前與不可提前的對比結果

活動開始時間不可提前得到的計劃為(0,0,8,18,22,45,22,22,26,22,30,30,39,79,92,100,140,22,25,97,43,46,108,52,54,79,116,159,182,58,206,213,219,220)；活動執(zhí)行模式為(1,1,1,1,1,1,1,1,1,1,1,1,1,1,2,1,2,1,1,2,1,1,1,1,1,1,1,2,2,1,1,1,1,1)，其中活動14、16、19、27、28從模式1轉換至模式2。從表3可知，后者的調(diào)整次數(shù)及模式轉換活動數(shù)量均小于前者；由于后者按照“鐵路調(diào)度”進行調(diào)整，未充分利用緊前活動提前啟動預留的時間裕量，使得其調(diào)整效果較差，分別體現(xiàn)在：開始時間變化活動數(shù)與開始時間偏差量均較大；資源平均利用率為55.9%，較前者低5.3%；項目完工時間為220小時，比前者大9小時；反應性總成本為13870元，高于前者3480元。因此，活動時間不可提前的策略在實際中效果較差。

4.3 敏感性分析

(a)資源可用量變化對反應性成本的影響

(a)模式轉換成本對模式轉換的影響

5 結論

本文研究不確定活動工期下活動執(zhí)行時間可提前的多模式反應性項目調(diào)度優(yōu)化問題。得出結論：與案例實際結果及活動時間不可提前的反應性結果相比，通過本文方法得到的反應性成本及項目完工時間均較低，且資源利用率高。反應性成本及活動影響數(shù)目隨著反項目推進呈減小趨勢，但由于開始時間偏差權重及工期變動程度不同會有局部增大現(xiàn)象，同時在某些時刻項目完工時間保持不變；通過將工期增大較大的活動或其緊前活動適當提前，或通過調(diào)整模式可降低成本；反應性成本隨資源可用量增加先下降后不變，與開始時間偏差權重及模式轉換成本呈單調(diào)正相關關系，并隨活動工期標準差的增大而上升；另外模式轉換成本與開始時間偏差成本的數(shù)量關系對是否進行模式調(diào)整有一定的影響，當模式轉換成本增加或開始時間偏差成本減小到一定程度時，無需模式轉換。

本文允許活動可提前于基準時間啟動，并通過合理調(diào)整活動模式，有效降低與基準計劃的執(zhí)行偏差。研究問題為在不確定環(huán)境下制定合理的反應性進度計劃提供新思路。