可用資源成本之專案排程問題求解 － 和聲搜尋基礎之啟發式演算法應用

Solving the Resource Availability Cost Problem in Project Scheduling by Harmony Search-Based Meta-Heuristic

李偉菁(Wei-Ching Lee)

指導教授 ： 張美香

中原大學/工學院/土木工程研究所/碩士(2011年)

https://doi.org/10.6840/CYCU.2011.00066

摘要

專案排程問題一直以來備受各界關注，此領域之研究也未曾中斷過。本研究所探討為以專案完工時間限制為首要條件，在時間期限內調動資源以成功執行專案之可用資源成本專案排程問題 (RACP-PS)，強調在特定期限內以最小的資源成本完成專案。本研究先以分散搜尋法 (SS)、和聲搜尋法 (HS) 及參數自我適應和聲搜尋法 (SGHS) 結合 ILOG CP Optimizer，對 RACP-PS 分別進行限制規劃求解，進一步採用 SS 來補強 HS 的局部搜尋能力，發展改良式和聲搜尋法 (IMHS)。本研究中的設計問題採用國際測試題庫 PSPLIB 提供之線上測試例題 (http://129.187.106.231/psplib/)，並針對單一專案問題題庫中作業數為 30、60 及 90 三種題型做為實驗測試依據，執行四種演算法求解 RACP-PS 之最佳參數測試，分析其求解數值範例的結果，比較四種演算法之運算成效。

關鍵字

混合式通用啟發式演算法 ； 可用資源成本專案排程問題 ； 分散搜尋法 ； 和聲搜尋法

並列摘要

The project management problems solving has received substantial attention from managers and professionals in recent years. This thesis explores solving the resource availability cost problem in project scheduling (RACP-PS). Under the time limit of a project, a project schedule is made to minimize the total cost of resource. Integrating with ILOG CP Optimizer, three meta-heuristics, scatter search (SS), harmony search (HS), and self-adaptive global best harmony search (SGHS), are developed to solve RACP-PS. In addition, a hybrid meta-heuristic combined SS with HS is proposed to solve RACP-PS and named as improved global best harmony search (IMHS). In this thesis, computational tests of these four proposed meta-heuristics are performed instances with four resources and 30, 60, and 90 activities obtained from the PSPLIB library (http://129.187.106.231/psplib/) and adapted to the RACP-PS.

並列關鍵字

harmony search ； scatter search ； resource availability cost problem in project scheduling ； hybrid meta-heuristic

參考文獻

楊偉智，2009，”和聲搜尋法於巨大廢棄物回收網路設計之探討”，中原大學，土木工程學系碩士論文。

羅冠君，2008，”基於和聲搜尋法與離散拉格郎日法之混合演算法於結構最佳化設計的研究”，國立中央大學，土木工程研究所碩士論文。

徐開評，2009，”應用和聲演算法探討溫室氣體排放限制下之電力系統容量擴增計畫”，中原大學，土木工程學系碩士論文。

Amal de silva (2000), “Bus Driver Duty Optimization by Combining Constraint Programming and Linear Programming”, ILOG(S) Pte Ltd. Singapore.

Boctor, F. F., (1990), “Some Efficient Multi-Heuristic Procedures for Resource-Constrained Project Scheduling,” European Journal of Operation Research, Vol. 49, pp. 3-13.