應用蟻群演算法解資源有限專案排程問題

Ant Colony System to Resource-Constraint Project Scheduling Problems

鄭英杰(Ying-Chieh Cheng)

指導教授 ： 羅仕堂

崑山科技大學/資訊科技學院/資訊管理研究所/碩士(2012年)

https://doi.org/10.6828/KSU.2012.00003

摘要

在本論文中，使用蟻群演算法解決資源限制專案排程問題。最近幾年專案排程的研究已被許多學者重視，也有許多文獻被提出，其中有許多是採用泛用啟發式演算方法，試圖在較短的演算時間內獲致令人滿意的近似最佳解，例如遺傳演算方法、模擬退火演算、蟻群演算法與粒子群演算法等。然而，這些方法在求解效能上的表現仍然存在著可供改進之空間。究其原因，應在於演算方法本身對於開發與探索行為的控制未能達到適切的平衡，以致需要較長的求解的時間，所以本文利用分散式平行處理於強調累積搜尋經驗的開發行為將更容易收斂至區域最佳解。相對地，若過於強調未探訪或相對未探索區域之探索行為則將促使演算方法趨於不穩定狀態，造成不易收斂。因此，本論文以蟻群演算法的設計理念，來解決上述所提及的缺點。在傳統資源限制專案排程問題之資源並未特別將資源視為人力資源，但實務上許多專案之執行是透過不同人力專長資源加以完成，由於搜尋問題解所耗費的時間會隨問題規模變大而呈現指數成長，要解決以上的問題，在進行資源分配與排程的問題時加上平行同步的方式來做蟻群演算法運算，更大幅縮短求得解時間。實驗結果表示，蟻群系統是比螞蟻系統還好。

關鍵字

蟻群演算 ； 排程問題

並列摘要

在本論文中，使用蟻群演算法解決資源限制專案排程問題。最近幾年專案排程的研究已被許多學者重視，也有許多文獻被提出，其中有許多是採用泛用啟發式演算方法，試圖在較短的演算時間內獲致令人滿意的近似最佳解，例如遺傳演算方法、模擬退火演算、蟻群演算法與粒子群演算法等。然而，這些方法在求解效能上的表現仍然存在著可供改進之空間。究其原因，應在於演算方法本身對於開發與探索行為的控制未能達到適切的平衡，以致需要較長的求解的時間，所以本文利用分散式平行處理於強調累積搜尋經驗的開發行為將更容易收斂至區域最佳解。相對地，若過於強調未探訪或相對未探索區域之探索行為則將促使演算方法趨於不穩定狀態，造成不易收斂。因此，本論文以蟻群演算法的設計理念，來解決上述所提及的缺點。在傳統資源限制專案排程問題之資源並未特別將資源視為人力資源，但實務上許多專案之執行是透過不同人力專長資源加以完成，由於搜尋問題解所耗費的時間會隨問題規模變大而呈現指數成長，要解決以上的問題，在進行資源分配與排程的問題時加上平行同步的方式來做蟻群演算法運算，更大幅縮短求得解時間。實驗結果表示，蟻群系統是比螞蟻系統還好。

並列關鍵字

ant colony system ； scheduling problems

參考文獻

[28]. 黃榮華、楊長林、劉士豪,「考慮資源限制與穩健性之專案排程研究」, 輔仁大學管理學研究所管理期刊,2008

[36]. 吳育周、廖光彬,「運用基因演算法規劃資源受限專案排程問題之探討」，崑山科技大學企業管理研究所碩士論文,2005

[1]. S. E. Elmaghraby. Activity networks: Project planning and control by network models. Wiley, New York, 1977.

[2]. R. Slowinski. Two approaches to problems of resource allocation among project activities: A comparative study. Journal of the Operational Research Society, 31:711–723, 1980.

[3]. S. Hartmannand R. Kolisch. Experimental evaluation of state-of-the-art heuristics for the resource- constrained project scheduling problem. European Journal of Operational Research, 127:394–407,2000.