以啟發式演算法求解資源受限條件下 資源分派與排程問題

The Development Of Heuristics For Solving The RCPSP With Resource Allocation And Scheduling

許展維(Hsu, Jason)

指導教授 ： 陳明德

國立中正大學/管理學院/企業管理學系/碩士(2012年)

摘要

「資源受限之專案排程問題（Resource-Constrained Project Scheduling Problem, RCPSP）」被提出以來，RCPSP問題本身以及求解方式在學術期刊或是相關文獻中不斷被學者廣泛討論，然而在一般專業期刊和相關的文獻中，學者對於RCPSP研究大多集中在作業排程上，而較少探討到作業-資源分派與排程以及資源可獲得性和里程碑問題等這些重要的專案觀點。
因此林榮基(2006)使用了數學規劃方法建立模型，將上述觀點整合到RCPSP問題上，目標為求解最小化總專案完成時間，而本研究接續了林榮基(2006)的研究，提出了啟發式演算法求解此類型問題，目的在於解決數學規劃模型在執行大型專案時所造成NP-hard問題，且啟發解能夠幫助管理者更有效率安排專案與分派資源。
在本研究中利用實際的範例分別對數學規劃模式與啟發式演算法的求解效率、效能、限制與資源負荷量分析比較之後，均可以證明此一啟發式演算法能有效地適用於解決專案資源分派與排程問題上。

關鍵字

資源受限之專案排程問題 ； 資源分派 ； 資源可獲得性 ； 里程碑 ； 啟發式演算法 ； 作業優先權規則

並列摘要

Since resource-constrained project scheduling problem (RCPSP) was proposed, the solution methods and the modeling approach of problem have been extensively studied in the project management related literature. The relevant issues addressed include single-mode resource-constrained project scheduling problem (SM-RCPSP), multi-mode resource-constrained project scheduling problem (MM-RCPSP), solution for single project and multi projects etc. In addition, a number of heuristic algorithms were developed for solving RCPSP.
However, most of the RCPSP related literatures focus on job or activity scheduling. The resource allocation and scheduling problems which take into account the resource availability and milestone job/activity are seldom addressed. Lin (2006) started to work on this issue, and proposed mathematical programming models to solve the aforementioned problem. The objective is to minimize the total project completion time. However, Lin’s model fails to solve the large-scale project scheduling problem which is NP-hard in nature.
Thus, the objectives of this research are two-fold. The first is to improve the Lin’s model by cutting down the number of binary decision variables. The second is to propose heuristic algorithms for solving the RCPSP of enormous size. Based on a number of test problems, the revised mathematical model and the proposed algorithms indeed improve the performance in many aspects including the solving capability (i.e., problem size), solving speed, and work-load balance.

並列關鍵字

resource-constrained project scheduling problem (RCPSP) ； resource allocation ； resource availability ； milestone ； heuristic algorithm ； job priority rules

參考文獻

【3】洪長裕，2009，「以啟發式搜尋法求解資源限制專案排程」，國立清華大學，工業工程與工程管理學系工業工程組，碩士論文。

【4】郭詩豪，2004，「於時間區間配置下有限資源專案排程問題最佳化之研究—以混合整數線性規劃求解」，國立成功大學，工業與資訊管理研究所，碩士論文。

【7】劉秋蘭，2011，「多重作業方式及資源限制下最大淨現值專案排程模式暨求解演算法之研究」，國立中央大學，土木工程研究所所，碩士論文。

【8】Alcaraz, J., Maroto, C., and Ruiz, R., 2003, “ Solving the Multi-Mode Resoure-Constrained Project Scheduling Problem with genetic algorithms,” Journal of the Operational Research Society, Vol.54, pp.614–626.

【9】Baptiste, P., Demassey, S., 2004, “Tight LP Bounds for Resource Constrained Project Scheduling,” OR Spectrum, Vol .20, pp.251–262.