一種改進的多模式項目反應性調度問題

彭武良, 林家利

(煙臺大學 經濟管理學院,山東 煙臺 264005)

0 引言

傳統的資源受限項目調度問題(resource-constrained project scheduling problems, RCPSP)屬于確定性項目調度問題，假定項目具有完全信息且項目的執行環境是靜態不變的。也就是說，所有的項目參數在項目計劃階段均已知，而且這些參數在項目實際執行過程中不會發生變化。然而，這樣的假定在現實中常常不成立，因為定義一個項目的所有參數在項目執行階段都可能發生改變[1]。反應性調度又被稱為重調度，指的是在項目執行過程中，發生干擾事件后，當基準調度方案變得不再可行或者不再最優時，對基準調度方案進行修改或者再優化的過程。根據是否考慮基準調度方案，可將項目反應性調度方法分為兩類，一類是不考慮基準調度方案的完全重調度方法，完全重調度指的是按原調度問題的目標和求解方式對受到干擾的項目完全重新進行調度求解[2,3]。另一類就是考慮基準調度方案并以最大化基準調度方案的穩定性為目標的反應性調度方法。完全重調度與傳統項目調度的調度方法和目標均相同，所以針對完全重調度的研究很少。既有的項目反應性調度問題主要是以最大化調度穩定性為目標的反應性調度問題。

反應性調度前后新舊調度方案的偏差越小則調度穩定性越高，且這種偏差通常用反應調度時產生的變更成本來衡量[4～6]。Van de Vonder等[7]、Deblaere等[8]、崔曉等[9]以最小化反應性調度前后活動開始時間的加權總偏差(即∑i∈Nwi·∣Si-si)為目標，其中，wi表示活動i的開始時間每提前或延遲一個單位所產生的成本，si為基準調度方案中活動i的開始時間，Si為新調度方案中活動i的開始時間。文獻[4,5,10,11]均以最小化項目反應性調度成本為目標，但對反應性調度成本的定義不完全相同。其中，程序和吳澄[5]認為反應性調度成本應由活動時間變更費用、活動模式變更費用和項目拖期罰金三部分組成；張沙清等[4]將反應性調度前后活動開始時間的加權總偏差和項目拖期罰金兩者之和作為反應性調度成本；Deblaere等[10]和王艷婷等[11]則認為反應性調度成本應由反應性調度前后活動開始時間的加權總偏差和執行模式轉換成本組成。除上述目標函數以外，還有諸如最小化總體流程拖延、活動執行成本和計劃修改次數的加權總和[12]、最小化項目工期與反應性調度前后各活動結束時間的加權總偏差之和[13]等比較小眾的目標函數。在約束條件方面，絕大多數項目反應性調度問題模型[4,5,7,9,11,12]僅考慮緊前關系約束和資源約束，少數模型會在此基礎上要求各活動的實際開始時間不能早于基準開始時間[8]，還有少數模型會將需要被重調度的活動的開始時間限制在恢復時間窗內[1]。

項目反應性調度問題從本質上可歸類為RCPSP，是一種NP-hard問題。開發該問題的求解算法是項目反應性調度領域的一個重要研究方向。針對單模式的項目反應性調度問題，學者們已開發出一些精確算法[6]、啟發式算法[7,8]以及智能優化算法[4]。Larsen和Pranzo[2]在既有研究的基礎上構建了一個通用的反應性調度框架。除了上述單模式反應性調度問題以外，更為復雜的多模式項目反應性調度問題也引起了學者們的關注。Zhu等[1]為不確定性RCPSP提出了一種混合整數規劃/約束規劃的混合算法。程序和吳澄[5]、Deblaere等[10]分別設計了粒子群優化算法、幾種精確算法和一種禁忌搜索啟發式算法。Godinho和Branco[14]提出了不確定性下多模式項目調度的自適應模型，并設計出一種自適應調度策略。Chakrabortty等[13]針對搶占-重復模式下和搶占-恢復模式下的多模式反應性調度模型提出了一種反應性調度程序。為求解活動工期不確定情況下的多模式反應性調度問題，王艷婷等[11]設計了一種遺傳禁忌混合搜索算法，崔曉等[9]則提出了一種雙層禁忌搜索啟發式算法。蔣淳等[15]針對項目型產品裝配過程中的重調度問題，構建了以最小化項目成本和最小化計劃變動偏差為目標的數學模型，并設計了基于帝國競爭機制的多目標算法。

雖然目前學者們對項目反應性調度問題的模型和算法進行了充分研究，但是，所有研究都聚焦于最小化反應性調度前后新舊調度方案的偏差。面對資源條件的不確定性，資源可用量增加時，項目進度在新的資源條件下原本可以加快，但既有的項目反應性調度方法無法滿足項目管理者的該需求?？傊?，既有的項目反應性調度問題專注于最小化新舊調度方案的偏差，卻無法保證新的調度方案在新的項目執行環境下是最優的。在更多的情況下，為了縮短工期、規避風險和提升項目績效，保證新調度方案的最優性仍然是項目反應性調度需要優先考慮的問題。但是，既有文獻中，尚無這方面的研究。

鑒于此，本文基于多模式資源受限項目調度問題(multi-mode RCPSP, MRCPSP)的框架，提出了一種改進的多模式項目反應性調度問題。該問題與既有研究不同，它首先保證新的調度方案在新的項目執行環境下是最優的，然后再最小化新舊項目調度方案之間的偏差。

1 問題描述與模型構建

1.1 問題描述

現假設：在項目執行過程中，資源可用量發生了改變而其他項目參數保持不變，并且，這樣的變化在項目開始到項目完工這段時間內可能發生多次。資源可用量的變化很可能會使得原先制定的基準調度方案Πb變得不再最優甚至不再可行，這樣的結果對于追求最短項目工期的項目管理者來說是無法接受的。此時，就需要進行反應性調度，在盡可能小地調整基準調度方案的同時，制定出能實現新環境下最短項目工期的新調度方案。然而，現有的反應性調度方法無法同時滿足項目管理者的這兩個需求。

因此，為突破現有反應性調度方法的局限，本文在現有多模式項目反應性調度模型(如崔曉等[9])的約束條件的基礎上增加一個約束條件，要求新調度方案的項目工期等于新的資源可用量狀況下的最短項目工期，以確保項目調度目標的最優實現，滿足項目管理者“趕工期”的需求。

一般情況下，項目管理者都希望調整后的新調度方案和基準調度方案非常相似，因為新舊方案差異較大會引起人員、設備、物料等方面的大幅調整[16]，產生諸如必須更改與分包商的協議、累積庫存成本、處理員工不滿的不良后果[10]。所以，本文提出的多模式項目反應性調度問題以最小化反應性調度前后活動開始時間的總偏差與活動結束時間的總偏差兩者之和為目標，以確保各活動的開始時間和執行模式都盡量保持不變。

總之，本文要解決的問題是：在項目執行階段，資源可用量發生變化、其他項目參數保持不變的情況下，如何調整基準調度方案以獲得一個新調度方案，該方案能夠保證：(1)滿足緊前關系約束和資源約束；(2)實現新的項目執行環境下的最短項目工期；(3)在此基礎上，與基準調度方案之間的差異要盡可能小。其中(2)在目前的項目反應性調度研究中尚未受到關注。

1.2 模型構建

根據1.1節對問題的描述，本文提出的多模式項目反應性調度問題在盡可能縮短項目工期的前提下最大化調度穩定性，其數學模型如下所示:

(1)

(10)

需要強調的是，與項目反應性調度的既有研究不同，本文在目標函數中同時最小化每個活動的開始時間偏差與結束時間偏差。這樣既能保證各活動的開始時間盡量不變，還能要求新的調度方案盡可能不改變各活動的執行模式。另外，由于資源可用量在項目執行過程中可能變化多次，所以可能需要進行多次反應性調度。在本文中，每次反應性調度都以上一次反應性調度的結果為基礎。也就是說，除了第一次調整以外，之后的每一次調整都將上一次調整后的調度方案定義為該次反應性調度的基準調度方案。

2 求解流程

針對問題特點，本文基于IBM ILOG優化編程語言OPL和CPLEX V12.8.0設計了該問題的求解程序，具體流程如下：

步驟1在項目計劃階段，假定所有項目參數提前可知且固定不變，制定一個滿足緊前關系約束和資源約束的最優(即項目工期最短)調度方案作為基準調度方案Πb。

步驟2在項目執行階段，資源可用量發生變化后，對新的資源條件下的項目進行完全重調度，得到新的資源可用量狀況下可以實現的最短項目總工期δq。

步驟3由步驟2求得δq后，調用本文提出的改進多模式項目反應性調度問題模型，對基準調度方案Πb進行調整以獲得新的調度方案Πq。Πq是新項目執行環境下所有實現最短項目工期的調度方案中，與基準調度方案Πb偏差最小(即活動開始時間總偏差與活動結束時間總偏差兩者之和最小)的那一個。

步驟4若資源可用量再次發生變化，則先后執行步驟2、3，直至項目完工。需要注意的是，每次反應性調度都應該將上一次反應性調度后生成的新調度方案作為基準調度方案。

3 計算實驗

3.1 實驗設計

本節將對本文提出的改進多模式項目反應性調度問題、現有的反應性調度問題、完全重調度問題進行比較測試，三者的主要區別如表1所示。鑒于既有的反應性調度問題調度目標的多樣性，為方便問題的比較，在本文的實驗中，將現有的反應性項目調度問題的目標設定為“最小化反應性調度前后活動開始時間的總偏差與活動結束時間的總偏差兩者之和”。

表1 三種不同類型的反應性調度問題的主要區別

在本文中，所有的調度問題均用IBM ILOG優化編程語言OPL建模，并用CPLEXV 12.8.0中的約束規劃優化引擎(CP Optimizer)求解。運行配置為：Intel(R) Core(TM)i5-9500 CPU @ 3.00GHz (6 CPUs),～3.0GHz處理器；8192MB RAM內存；Windows 10操作系統。 從PSPLIB標準問題庫的MRCPSP問題集中隨機選取20個J20標準算例，J20中的每個算例包含20個實活動且每個實活動均有三種執行模式，涉及兩種可更新資源R1、R2和兩種不可更新資源N1、N2。設定兩種不同的項目執行環境變化的情景：可更新資源R1、R2和不可更新資源N1、N2的可用量同時增加10%； R1、R2、N1、N2的可用量同時減少10%。隨機選取各個算例的調整時刻q,q>0。

定義兩個用于問題比較的優化性能評價指標：①COST，項目調度方案的變更成本，定義為反應性調度前后活動開始時間的總偏差與活動結束時間的總偏差兩者之和；②MAKESPAN(簡寫為M-S)，反應性調度后新調度方案對應的項目總工期。

3.2 實驗結果

情形1可更新資源R1、R2與不可更新資源N1、N2的可用量同時增加10%，其他項目參數保持不變。在該情形下，隨機選取各個算例的調整時刻q，對隨機選取的20個J20算例進行測試，得到三種不同的反應性調度問題的優化性能對比結果，如表2所示。其中，OM表示基準調度方案對應的項目總工期(即資源可用量變化前可以實現的最短項目工期)，FR表示完全重調度方法，NR表示本文提出的改進多模式項目反應性調度方法，OR表示現有的多模式項目反應性調度方法。

表2 資源可用量增加時三種反應性調度問題的優化性能對比結果

由表2可知，由于完全重調度的目標是最小化項目工期，所以完全重調度方案的項目工期在新的資源條件下在三種反應性調度方法中總是最短的。但由于完全重調度不考慮基準調度方案如何，所以完全重調度方案的變更成本在三種反應性調度方法中總是最高的。在資源可用量增加而其他項目參數保持不變的情況下，基準調度方案必定滿足新的項目執行環境下的緊前關系約束和資源約束，即滿足現有的多模式項目反應性調度問題的約束條件，再加上現有的反應性調度問題以最大化調度穩定性為目標，因此，最終的調度結果會是：不對基準調度方案做出任何調整(表現為OR的COST為零)。但是，像這樣保護調度穩定性是有代價的，代價是放棄縮短原本可以進一步縮短的項目工期，所以，通過OR求得的新調度方案對應的項目工期是三種反應性調度方法中最長的。由表2還可知，對算例進行本文提出的改進多模式項目反應性調度，得到的新調度方案的項目工期總是與完全重調度方案的項目工期一樣長，也就是說，這些新調度方案實現了新項目執行環境下的最短項目工期。與此同時，通過NR求得的調度方案的變更成本明顯低于完全重調度方案的變更成本。所以說，本文提出的多模式項目反應性調度問題明顯優于完全重調度問題。對于想要趕工期的項目管理者來說，與現有的項目反應性調度方法相比，本文提出的項目反應性調度方法顯然更優。

情形2可更新資源R1、R2與不可更新資源N1、N2的可用量同時減少10%，其他項目參數保持不變。在該情形下，隨機選取各個算例的調整時刻q，對隨機選取的20個J20算例進行測試，得到三種不同的反應性調度問題的優化性能對比結果，如表3所示。

表3 資源可用量減少時三種反應性調度問題的優化性能對比結果

由表3可知，通過NR求得的調度方案的項目工期總是最短的，等于完全重調度方案的項目工期，而通過OR求得的調度方案的項目工期總是最長的。完全重調度方案的變更成本在三種反應性調度方案中最高，通過OR求得的調度方案的變更成本是最低的，而通過NR求得的調度方案介于兩者之間。因此，本文提出的改進多模式項目反應性調度問題兼顧了調度穩定性的保護和項目調度目標(如最小化項目工期)的最優實現。

綜合來看，本文提出的兩階段多模式資源受限項目反應性調度問題能夠很好地應對項目執行過程中的不確定性因素，無論是在維護調度穩定性上還是在確保項目調度目標(如最小化項目工期)的實現上，均優于完全重調度問題。在確保項目調度目標的最優實現方面，與現有的項目反應性調度問題相比，本文提出的項目反應性調度問題具有明顯優勢。

4 結論

本文的主要貢獻體現在兩個方面：(1)對既有項目反應性調度問題的模型改進。本文提出的改進多模式項目反應性調度問題以最小化反應性調度前后活動開始時間的總偏差與活動結束時間的總偏差兩者之和為目標，在既有反應性調度問題的緊前關系約束和資源約束的基礎上增加了約束條件，確保反應性調度方案實現新的項目執行環境下的最短項目工期。(2)兩階段項目反應性調度方法的提出。在第一階段，面對新的項目執行環境，對項目進行完全重調度，得到新的最優調度目標值；在第二階段，以新的最優調度目標值為約束，以最大化調度穩定性為目標，求得新的最優調度方案。

基于標準算例，對本文提出的反應性調度方法、既有的反應性調度方法、完全重調度方法進行了充分的比較測試。測試結果表明，本文提出的反應性調度方法在縮短項目工期、保護基準方案的穩定性方面具有明顯優勢。未來可以嘗試為本文提出的多模式項目反應性調度問題設計高效的啟發式算法。