多重作業方式及資源限制下最大淨現值專案排程模式暨求解演算法之研究

Multi-mode resource constrained project scheduling model to maximize net present value and a Solution Algorithm

劉秋蘭(Chiu-lan Liu)

指導教授 ： 顏上堯

國立中央大學/工學院/土木工程學系/碩士(2011年)

摘要

在全球化經濟快速發展下，企業為求得生存與發展需更有效地利用有限的資源、盡量縮短專案時間週期及降低作業成本，以求得最大的利潤。然而隨著專案規模的迅速成長，專案排程問題牽涉的相關因素逐漸複雜。雖然過去的專案排程有利用要徑法與計畫評核術進行專案作業排程，但是近幾年來因環境資源匱乏，單憑考量時程的控管而未考量有限的資源，則決策缺乏整體最佳化分析，常非最佳及最有效率之決策。若能將資源限制及不同作業方式等因素加以考量，並建立決策模式，則可望幫助決策者有效地求解此類複雜的專案作業排程。
本研究針對多重作業方式及資源限制下最大淨現值專案排程問題，考量現金流量時間價值及相關作業流程與資源限制，利用時空網路流動技巧及數學規劃方法構建一數學模式，以整合有限的資源規劃專案作業排程。此模式為一含額外限制整數網路流動問題，可以利用CPLEX數學規劃軟體求解。為測試本研究模式及演算法的求解績效，本研究以國際測試題庫(PSPLIB)所提供之專案資訊，進行一範例研究，測試結果良好，顯示本研究模式應可為學術及實務業者之參考。

關鍵字

多重作業方式及資源限制下之專案排程 ； 淨現值 ； 時空網路 ； 含額外限制整數網路流動問題

並列摘要

Due to the fast development of global economy, the enterprises must efficiently use limited resources and essentially reduce the working time period and the operating cost for the project in order to maximize its profit. Because the project size grows rapidly nowadays, these factors involving project scheduling are more and more complex than before. Traditionally, the critical path method (CPM) and the program evaluation and review technique (PERT) were used to formulate the project scheduling. The past time-controlled process for CPM and PERT is neither efficient nor effective from a system perspective, especially due to the short of environment resources recently. A model incorporating the resource-constrained and the different ways of working is expected to help the decision maker to efficiently solve the complicated project scheduling problem.

Dealing with the multi-mode resource constrained project scheduling problem with discounted cash flow (MRCPSPDCF), this research adopts the time-space network technique to formulate a mathematical programming model which considers the cash flow value of time and related operating and resource constraints. The mode is formulated as an integer network flow problem with side constraints, which is characterized as NP-hard in terms of optimization. We employ the CPLEX mathematical programming solver, to solve the problem. To evaluate the performance of the proposed model, numerical tests regarding the project scheduling problem library (PSPLIB) are performed. The test results show that the model could be useful references for academics and practicals.

並列關鍵字

MRCPSPDCF ； net present value ； time-space network ； integer network flow problem with side constrain

參考文獻

3.邱明琦、陳春益、林佐鼎，「海運貨櫃排程模式之研究」，運輸計劃季刊，第三十一卷，第三期，第495-522頁 (2002)。

13.顏上堯、翁綵穗，「季節轉換間緩衝期飛航排程之研究」，運輸計劃季刊，第三十卷，第四期，第891-921頁 (2001)。

12.盧華安，「因應班機延遲之最佳化即時機門指派」，運輸計劃季刊，第三十卷，第四期，第849-869頁 (2001)。

2.林士鈞，「定期貨櫃運輸船舶排程暨船期表建立之研究」，碩士論文，國立中央大學土木工程系 (2006)。

17.Desaulniers, G., Desrosiers, J., Dumas, Y., Solomon, M. M. and Soumis, F., “Daily aircraft routing and scheduling,” Management Science, Vol. 43, pp. 841-855 (1997).