資源受限項目調度問題的時間窗分解算法研究.pdf

1、資源受限項目調度問題是項目管理領域的一類長期受人關注的研究課題，此類問題是各類新的高性能優(yōu)化方法的實驗床。在此類問題的求解中，人們一般會直接利用活動的整體時間窗屬性，通過可行解空間的搜索來獲取最優(yōu)調度方案，而在搜索中卻忽略了活動的時間窗的可分解特性。通過活動時間窗的分解，可以有效縮小可行解空間，減少搜索過程中的計算量和時間花費，這對求解大規(guī)模的資源受限項目調度問題具有重大意義，因此本文對時間窗分解算法進行了創(chuàng)新性的嘗試。
　　本研

2、究結合活動時間窗分解的基本思想，首先設計并分析了合適的時間窗分解活動的選擇策略與可行解空間分解策略，將原問題可行解空間分解成多個子可行解空間，然后根據重定義方法更新子可行解空間的時間窗，隨后基于不同采樣策略設置每個子可行解空間的采樣規(guī)模，最后分別在不同的子可行解空間中進行調度方案的搜索。經過實驗對不同策略的檢驗，本文選取了五種時間窗分解活動的選擇策略、三種可行解空間分解策略和兩種采樣策略進行詳細介紹，并對上述策略進行有效組合，通過基于標

3、準案例庫PSPLIB的計算實驗，分別在J30、J60與J120三組測試集上做了實驗分析和對比，廣泛地驗證了本算法的有效性。
　　實驗結果表明，RCPSP的時間窗分解算法在具體案例上能將可行解空間有效降低，并在不同可行解空間分解策略和采樣策略下，均相對于未分解的算法在求解時間效率上有顯著提高，充分表明了算法的合理性和有效性。此外，本算法具有良好的可拓展性，可嵌套多種啟發(fā)式算法進一步提高求解效率，這對于未來的研究方向也指出了可行的道路