資源受限項(xiàng)目調(diào)度問題的時(shí)間窗分解算法研究.pdf

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

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

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